PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

재욱 왕
5 years ago
Views:

1 Lecture 01: Compiler Overview Kwang-Man Ko compiler.sangji.ac.kr Department of Computer Engineering Sang Ji University 2019

2 강의정보 교과목명 : 컴파일러 개설학과 : 컴퓨터공학과 4학년 학점및시수 : 3학점 3시간 강의시간 : 화 2,3,4교시 이수구분 : 전공선택 ( 이론 ) 교재 : 컴파일러입문 ( 정익사 ), 오세만 연락처 : 연구실위치 : 민주관 1층 109호. 연락처 : , kkman@sangji.ac.kr Homepage : Lecture01: Compiler Overview, kkman@sangji.ac.kr 2

3 프로그래밍언어번역기 프로그래밍언어번역기 (translator) 원시프로그램을입력으로받아의미적으로동등하면서직접기계에서실행될수있는형태로번역. Source program Target program Lecture01: Compiler Overview, 3

4 좋은 (Good) 프로그래밍언어의요건 명확한언어개념 문법적인구조 (syntax, grammar) 의미 (semantics) 프로그래머의생각을자연스럽게표현 호환성 ( 이식성 ), 신뢰성, 모듈화, 효율성 언어의확장성이우수 좋은프로그래밍환경 Lecture01: Compiler Overview, kkman@sangji.ac.kr 4

5 COBOL COmmon Business Oriented Language 1960년대초, 코다실 (CODASYL) 에서발표 주로업무용으로사용 1968 ~ 1974년에 ANSI COBOL을제정 FORTRAN FORmula TRANslation 1960년대초, J. Backus를중심으로개발 과학계산용언어 1977년 FORTRAN77이발표 Lecture01: Compiler Overview, kkman@sangji.ac.kr 5

6 ALGOL ALGOrithmic Language ALGOL 년 IFIP WG2.1에서발표 구문구조를형식문법으로표현 언어의구조와의미가명료 제어구문구조가우수 많은프로그래밍언어에큰영향 Pascal 1970년대초, N.Wirth가고안 프로그래밍언어론적인관점에서설계 전산학적인응용에적합 - 자료구조, 알고리즘 Lecture01: Compiler Overview, kkman@sangji.ac.kr 6

7 Ada 1980년미국방성 (DoD) 에서발표 reliability, simplicity, modularity, efficiency package, generic features, multi-tasking real-time application에적합 C 년 B.Stroustrup OOPL : class, inheritance, polymorphism Lecture01: Compiler Overview, kkman@sangji.ac.kr 7

8 Java James Gosling, Sun MicroSystems OOPL, Exception, Multithread Internet & Distributed Environment 플랫폼독립성 Applet, Application Lecture01: Compiler Overview, 8

9 C# John Gough, Microsoft.NET Framework, OOPL(Object-Oriented Programming Language) JIT (Just In-Time Compilation) MSIL (Microsoft Intermediate Language) CLR (Common Language Runtime) Expressiveness and Simplicity Lecture01: Compiler Overview, 9

10 번역기와컴파일러 프로그래밍언어번역기종류 컴파일러 (compiler) 인터프리터 (interpreter) 어셈블러 (assembler) 전처리기 (preprocessor)... Lecture01: Compiler Overview, 10

11 컴파일러 컴파일러 (Compiler) 정의 고급언어로쓰여진프로그램을어떤특정한컴퓨터에서직접수행가능한형태의프로그램으로번역해주는시스템프로그램. High-level Source Program Compiler Object Program (Assembly Language, Machine Language) C compiler test.c => C-complier => test.obj Lecture01: Compiler Overview, kkman@sangji.ac.kr 11

12 크로스컴파일러 (cross compiler) 크로스컴파일러정의 원시프로그램을컴파일러가수행되고있는기계에대한기계어로번역하는것이아니라다른기종에대한기계어로번역하는컴파일러. SPARC 컴퓨터에서 Intel 8086/80386 코드생성 C 프로그램 C 컴파일러 C 크로스컴파일러 (intel) SPARC 컴퓨터 목적프로그램 (SPARC) 목적프로그램 (Intel) Lecture01: Compiler Overview, kkman@sangji.ac.kr 12

13 인터프리터 (interpreter) 인터프리터정의 원시프로그램을입력으로받아목적언어또는프로그램으로변환하지않고직접실행해서결과를출력해주는시스템프로그램. HTML 인터프리터, Bytecode 인터프리터 (Java) 입력데이터 원시프로그램 Interpreter 실행결과 Lecture01: Compiler Overview, 13

14 전처리기 (preprocessor) 기능 프로그래밍언어에유용한기능들을추가 언어확장 (language extension) 확장된프로그램은기본언어에대한언어번역기에의해번역 원시프로그램 전처리기 확장된원시프로그램 번역기 목적프로그램 Lecture01: Compiler Overview, 14

15 마크로 (macro) 유사한원시코드를마크로로정의하고필요할때마다확장 프로그래머의생산성을증가 #define Max 1000 조건부컴파일 (conditional compile) Language to Language translator C to Pascal C++ to C Lecture01: Compiler Overview, kkman@sangji.ac.kr 15

16 컴파일러의개략적인구조 원시프로그램 전단부 중간코드 후단부 목적프로그램 * 원시프로그램 : Source program * 목적프로그램 : Target program * 전단부 : Front-end * 후단부 : Back-end * 중간코드 : Intermediate Code Lecture01: Compiler Overview, kkman@sangji.ac.kr 16

17 전단부 (Front-end) 원시프로그래밍언어종류에의존적 원시프로그램을분석, 중간코드생성 원시프로그램마다전단부가각각존재 어휘분석, 구문분석, 의미분석, 중간코드생성 후단부 (Back-end) 목적기계 (target machine) 에의존적 중간코드를특정기계에대한목적코드로번역 목적기계마다각각의후단부가존재 목적코드생성, 코드최적화단계 Lecture01: Compiler Overview, 17

18 컴파일러의일반적구조 원시프로그램 컴파일러 전단부 후단부 목적프로그램 어휘분석 구문분석 의미분석 중간코드생성 코드최적화 목적코드생성 토큰구문트리중간코드 의미분석트리 최적화된중간코드 Lecture01: Compiler Overview, 18

19 어휘분석 (lexical analysis) 어휘분석기, 스캐너 (scanner) 원시프로그램에대해일련의토큰 (token) 생성 컴파일러내부에서효율적이며다루기쉬운정수로바꾸어줌. Source Programs Scanner A sequence of tokens Lecture01: Compiler Overview, kkman@sangji.ac.kr 19

20 토큰 (Token) 정의 문법적으로의미를갖는최소의단위 종류 일반형태 프로그래머에의해지정 명칭, 상수 특수형태 언어설계자에의해지정 keywords, operators, delimiter,... Lecture01: Compiler Overview, 20

21 토큰의예 A := B + 3; A, :=, B, +, 3, ; // 6 개토큰으로분리 IF A > 10 THEN... Token : IF A > 10 THEN Token number : Lecture01: Compiler Overview, kkman@sangji.ac.kr 21

22 구문분석 (syntax analyze) 구문분석기 (syntax analyzer), 파서 (parser) 토큰을받아원시프로그램에대한문법검사 올바른구문구조또는문장 파스트리 (Parse Tree) 추상화구문트리 (Abstract Syntax Tree; AST) 에러를가진구문구조 에러메시지 (Syntax Error) 출력 토큰 Parser 트리 에러메시지 Lecture01: Compiler Overview, 22

23 중간코드 (intermediate code) 생성 중간코드생성기 구문트리를입력으로받아의미검사를수행한후중간코드생성 의미검사 (semantic checking) 중간코드생성 (intermediate code generation) 장점 컴파일러를기능적으로독립적인모듈로작성 원시프로그램의이식성증가 번역과정을쉽게표현, 효율적처리 중간코드에대한최적화가능 Interpretive Compiling Lecture01: Compiler Overview, 23

24 Ex) A := B + 1; Tree : := Ucode: LOD 1 2 LDC 1 ADD STR 1 1 A + B 1 Lecture01: Compiler Overview, kkman@sangji.ac.kr 24

25 의미분석 (semantic analyze) 정의 구문분석결과에추가적인정보를출력하는단계 속성문법 (attribute grammar) Inherited attribute Synthesized attribute 형검사 (type checking) 연산자정의에맞는피연산자를가지는가를검사 실수가배열의첨자로사용 => Error 실수와정수의혼합연산 => 형변환 (type conversion) Lecture01: Compiler Overview, 25

26 코드최적화 (code optimization) 기능 동등한의미를유지하면서효율적코드생성 코드실행시기억공간, 실행시간절약 중간코드, 목적코드에대한최적화 ( 선택적 ) 단계 최적화기의위치 Pre-code Optimizer Post-code Optimizer 핍홀최적화 (Peephole Optimization) Lecture01: Compiler Overview, kkman@sangji.ac.kr 26

27 코드최적화 (optimization) 종류 코드최적화관점 ( 범위 ) 지역최적화 (local optimization) 기본블록단위에서일련의비효율적인코드들을구분해내고좀더효율적인코드로개선하는방법 1. Constant folding 2. Eliminating redundant load, store instructions 3. Algebraic simplification 4. Strength reduction 전역최적화 (global optimization) 프로그램전체흐름분석기술을이용하여기본블록들사이에최적화수행. 1. Common subexpression 2. Moving loop invariants 3. Removing unreachable codes Lecture01: Compiler Overview, kkman@sangji.ac.kr 27

28 목적코드생성 목적기계코드생성 중간코드를입력으로받아의미적으로동등한목적기계에대한코드를생성 목적기계코드생성기 (target code generator) 목적코드생성기기능 목적코드선택및생성 레지스터의운영 기억장소할당 기계의존적인코드최적화 Lecture01: Compiler Overview, 28

29 에러복구 (error recovery) 에러복구 (recovery) 정의 에러가다른문장에영향을미치지않도록수정하는것 error repair : 에러가발생하면복구해주는것 에러처리 (error handling) Error detection Error recovery Error reporting Error repair 에러종류 문법에러 (syntax error) 의미에러 (sematic error) 실행시간에러 (run-time error) Lecture01: Compiler Overview, kkman@sangji.ac.kr 29

30 컴파일러자동화도구 컴파일러자동화도구 컴파일러의전과정또는각단계들을자동적으로생성하는도구 컴파일러생성기 (compiler generator) 컴파일러-컴파일러 (compiler-compiler) Program written in L Language Description : L Machine Description : M Compiler -Compiler Compiler Executable form on M Lecture01: Compiler Overview, kkman@sangji.ac.kr 30

31 컴파일러자동화도구, 컴파일러생성기 (compiler generator) 입력을주면출력으로컴파일러를자동으로생성해주는컴파일러 - 컴파일러 : PQCC(Production-Quality Compiler Compiler) ACK(Amsterdam Compiler Kit) 어휘분석, 구문분석, 코드생성등컴파일러의단계 (phase) 를자동생성 번역기제작시스템 (translator writing system) 렉스 (Lex) 와야크 (YACC, Yet Another Compiler Compiler) Lecture01: Compiler Overview, kkman@sangji.ac.kr 31

32 렉스 (LEX) 1975 년에 M. E. Lesk 가고안 사용자가정의한토큰에대한표현인정규표현과수행코드를입력받아 C 로작성된어휘분석기 (= 스캐너 ) 출력 어휘분석기는입력프로그램에서정규표현에해당하는토큰을찾았을때, 결합된수행코드를수행하여토큰정보생성 Lecture01: Compiler Overview, kkman@sangji.ac.kr 32

33 YACC 야크 구문분석기 (= 파서, parser) 를자동생성해주는구문분석기생성기 (parser generator) 1975 년벨연구소의존슨 (Steve Johnson) 이주축이되어개발한 LALR(1) 구문분석기생성기로문법규칙에대한수행코드를 C 언어로기술 Lecture01: Compiler Overview, kkman@sangji.ac.kr 33

34 Lex 와 YACC Lecture01: Compiler Overview, 34

35 QnA

형식 언어

형식 언어 컴파일러개요 아주대학교정보및컴퓨터공학부 목차 컴파일러란 프로그래밍언어 관련프로그램들 컴파일러의일반적인구조 컴파일러자동화도구 Compiler 2 컴파일러란 Compiler A compiler is a computer program which translates programs written in a particular high-level programming