컴 파 일 러 Compilers

차 례 1. 컴파일러 개론 8. LR구문 분석 2. 형식 언어 9. 중간 언어 3. 정규 언어 10. 중간 언어의 생성 차 례 1. 컴파일러 개론 8. LR구문 분석 2. 형식 언어 9. 중간 언어 3. 정규 언어 10. 중간 언어의 생성 4. 어휘 분석 11. 코드 최적화 5. Context-free 문법 12. 심벌 테이블 6. 구문 분석 13. 에러 처리 7. LL구문분석 14. 컴파일러 자동화 도구

1. 컴파일러 개론 1-1. Compiler 정의 1-2. Language Processing System 1. 컴파일러 개론 1-1. Compiler 정의 1-2. Language Processing System 1-3. 컴파일러 논리적구조 (phase) 1-4. Compiler Organization 1-5. 컴파일러 자동화 도구

1-1. Compiler 정의 A Compiler is a program that reads a program written in one language - source program - and translates it into an equivalent program in another language - target(object) program A Compiler is a computer program which translates other programs written in a particular high-level programming L. to executable code for a specific target computer. (translator) Source program compiler Target program error

1-2. Language processing system Skeletal source program 1) preprocessor 분석 형식이론 (확립) Front-end High-level language 2) compiler IL Low-level, assembly language 합성 경험적 이론 3) assembler Back-end Relocatable machine code 4) Loader/ Link-editor Absolute machine code (executable machine code)

1) Preprocessor 프로그래밍 언어에 유용한 기능들을 추가 시킴으로써 언어를 확장 시켜주는 역할 Macro substitution Conditional compilation Inclusion of files

2) Compiler Structure Front-End : language dependent part Back-End : machine dependent part

 Cross compiler : source program을 다른 기종에 대한 기계어로 번역하는 compiler B 기종에 대한 object program

Assembly어로 쓰여진 program을 기계어 program 3) Assembler Assembly어로 쓰여진 program을 기계어 program 으로 바꾸어 주는 번역기 Assembly Assembler 기계어 programs Programs

“An interpreter transforms a program directly into a sequence of machine actions and produces the results of the program.” Compiler : Operational System Interpreter : Developing System or Educational System

1-3. 컴파일러의 논리적 구조 (phase) Source code 전 단 부(front-end) 1) Lexical analysis (어휘분석) 2) Syntax analysis (구문분석) Symbol table 3) Semantic analysis (의미분석) Error handle 4) Intermediate code generation (중간코드생성) 5) Code optimization (코드 최적화) 6) Code generation (코드 생성) 후 단 부(back-end) Object code

=> 어휘분석 단계의 출력은 일련의 token들 1) Lexical analysis (어휘분석) source program을 읽어서 문법의 최소 단위인 token을 생성하는 일 (예) A := B + 3 ; (token의 개수 : 6개) A, B (variable), := (assignment symbol), +(plus operator), 3(numeric), ;(delimeter) => 어휘분석 단계의 출력은 일련의 token들

2) Syntax analysis (구문분석) token을 읽어 오류를 검색하고 올바른 문장에 대한 구문구조를 만든다. := Top-down 방식 (예) A := B + 3 ; A + B 3

3) Semantic analysis (의미분석) type checking(형 검사) 각 연산자가 원시 언어의 정의에 맞는 피연산자를 가지는지 검사 (예) 배열의 첨자로 실수가 사용  error로 간주 (예) 실수와 정수의 혼합 연산에서 연산 수행 전 정수를 실수로 바꾸어주는 작업  이를 형 변환 (type conversion) (예) if (a > 10) a = 1.0 ; ☞ a가 정수일 때 semantic error !

4) Intermediate code generation (중간코드 생성) 구문구조를 이용하여 중간코드 생성 또는 문법규칙에 의해 중간코드 생성 (예) A := B + 3; load 1 2 / / load B loc 3 / / load constant 3 add / / addition str 1 1 / / store A U code

5) Code optimazation (코드 최적화) Optional phase(공간적, 시간적 효율화를 위해 필수) 비효율적인 code를 구분해 내서 더 효율적인 code로 바꾸어 준다. Meaning of optimization major part : improve running time minor part : reduce code size Criteria for optimization preserve the program meanings speed up on average be worth the effort

Local optimization(지역 최적화) local inspection을 통하여 inefficient한 code들을 구분해 내서 좀 더 efficient한 code들로 바꾸는 방법. 1. Constant folding(컴파일 시간 상수 연산) 2. 중복된 load, store 명령문 제거 3. Algebraic simplification (expression 대수 학적 간소화) 4. Strength reduction(연산 강도 경감) 5. 불필요한 일련의 cobe block 삭제

Global optimization(전역 최적화) flow analysis technique을 이용 1. Common subexpression (공통 부분식의 축약) 2. Moving loop invariants ( loop 내에서 값이 변하지 않는 코드를 loop 밖으로 이동) 3. Removing unreachable codes(도달될 수 없는 코드 제거) 18

목적 기계(target machine)에 대한 코드 생성 6) Code generation (코드 생성) 컴파일 과정의 마지막 단계 목적 기계(target machine)에 대한 코드 생성 목적코드 선택 및 생성 : 중간 코드의 의미와 일치하는 기계 명령어들 선택 레지스터 운영 : 소수의 고속 레지스터의 효율적 사용 기억장소 할당 기계 의존적인 코드 최적화 : 연속적인 명령어들을 동등한 하나의 명령어로 대체, 또는 처리 속도가 빠른 명령어로 대체 중간 코드 목적 코드 생성기 목적 코드

 Translation of a statement Lexical analyzer Semantic analyzer Syntax analyzer Code generator Code optimizer Intermediate code generator position := initial + rate * 60 id1 := id2 + id3 * 60 := id1 + id2 * id3 60 inttoreal temp1 := inttoreal(60) temp2 := id3 * temp1 temp3 := id2 + temp2 id1 := temp3 temp1 := id3 * 60.0 id1 := id2 + temp1 MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 position ... initial … rate ... 1 2 3 4 Symbol Table  Translation of a statement

1-4. Compiler Organization Logical organization(phase) Physical organization (pass) Single Pass Multi pass 속도 증가 메모리 많이 사용 속도 저하 메모리 적게 사용

Phases : logical organization of compiler  pass : physical organization of compiler : implementation 할 때 1 개 이상의 phase가 함께 작동할 때 passes : single pass  several phases (예) lexical analysis 1 pass  syntax analysis semantic analysis intermediate code generation

1-5. 컴파일러 자동화 도구 Compiler Generating Tools 1-5. 컴파일러 자동화 도구 Compiler Generating Tools (= Compiler-Compiler, Translator Writing System) Language와 machine이 발달할수록 많은 compiler가 필요. 새로운 언어를 개발하는 이유: 컴퓨터의 응용 분야가 넓어지므로. N 개의 language를 M 개의 컴퓨터에서 구현하려면 N  M 개의 컴파일러가 필요. ex) 2개의 language : C, Java 3개의 Machine : IBM, SPARC, Pentium C-to-IBM, C-to-SPARC, C-to-Pentium Java-to-IBM, Java-to-SPARC, Java-to-Pentium

Compiler-compiler Model(p29, 그림 1.15) 언어 표현(Language description)은 grammar theory를 이용 하고 있으나, 목적 기계에 대한 기계 표현(Machine description)은 정형화가 이루어져 있지 않은 상태임. Machine architecture와 programming language의 발전에 따라 automatic compiler generation이 연구됨. Compiler - Source program object code 언어 표현  기계 표현

1. Lexical Analyzer Generator (어휘 분석기 생성기) LEX : 1975년에 M. E. Lesk 가 고안. 입력 스트림에서 정규표현으로 기술된 토큰들을 찾아내는 프로그램을 작성하는데 유용한 도구. LEX Lexical Analyzer ( Scanner) Token Structure regular expression) Source program Token Stream

PGS 2. Parser Generator(파서 생성기) 언어의 문법 표현으로부터 파서(= 구문 분석기)를 자동으로 생성하는 도구 보통 파서 생성기를 파서 제작 시스템(PGS: Parser Generating System) PGS Language description ( grammar 를 이용하여 기술 ) tokens program structures Driver Routines Tables Parser

UNIX에서 수행, 1975년 벨 연구소의 S.C.Johnson C language로 쓰여 있음. 대표적인 파서 생성기 YACC(Yet Another Compiler Compiler) UNIX에서 수행, 1975년 벨 연구소의 S.C.Johnson C language로 쓰여 있음. 대표적인 파서 생성기 Scanner (Lex.yy.c) Parser y.tab.c LEX YACC tokens Source Program Regular Expression + Action code Grammar Rule 출력

3. Automatic Code Generation (코드 생성의 자동화) 코드 생성은 중간 언어를 목적 기계 언어로 바꾸는 과정 코드 생성 알고리즘(CGA: Code Generating Algorithm) Pattern matching code generation Table driven code generation CGG Code Generator Machine Description Intermediate Code Target Code <코드-생성기 생성기>

4. Compiler Compiler System 컴파일러 개발과정을 자동화하기 위한 도구 PQCC와 ACK (1) PQCC(Production Quality Compiler Compiler) W.A. Wulf (Carnegie-Mellon University) Front-End PQC PQCC 언어 표현 +기계 표현 테이블 소스 프로그램 목적 프로그램 TCOL 29

4. Compiler Compiler System (2) ACK(Amsterdam Compiler Kit) ACK는 컴파일러의 후단부를 자동화하기 위한 도구 Vrije 대학의 Andrew S. Tanenbaum을 중심으로 개발된 Compiler의 Back-End 자동화 도구. UNCOL(Unified Computer Oriented L.)개념에서 출발 EM(Encoding Machine)이라는 Abstract Machine Code를 중간 언어로 사용. Portable Compiler를 만들기에 편리.

ACK Model(p35 그림 1.23 참조) Front- End Back - Interpreter EM - 각 기계당 FORTRAN ALGOL PASCAL C ADA : Interpreter Intel 8080 / 8086 80386 Motorola 6800 6809 68000 68020 Zilog Z80 /Z8000 VAX SPARC Result 각 기계당 하나씩 필요 각 언어당 하나씩 존재