Lecture 01: Compiler Overview Kwang-Man Ko kkmam@sangji.ac.kr, compiler.sangji.ac.kr Department of Computer Engineering Sang Ji University 2018

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

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

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

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

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

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

Java James Gosling, Sun MicroSystems OOPL, Exception, Multithread Compiler, 2012. Java James Gosling, Sun MicroSystems OOPL, Exception, Multithread Internet & Distributed Environment 플랫폼 독립성 Applet, Application kkman@ssangji.ac.kr

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

번역기와 컴파일러 프로그래밍 언어 번역기 종류 컴파일러(compiler) 인터프리터(interpreter) 어셈블러(assembler) 전처리기(preprocessor) . . . kkman@ssangji.ac.kr

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

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

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

전처리기(preprocessor) 기능 전처리기 번역기 프로그래밍 언어에 유용한 기능들을 추가 Compiler, 2012. 전처리기(preprocessor) 기능 프로그래밍 언어에 유용한 기능들을 추가 언어 확장(language extension) 확장된 프로그램은 기본 언어에 대한 언어 번역기에 의해 번역 전처리기 확장된 원시 프로그램 번역기 원시 프로그램 목적 프로그램 kkman@ssangji.ac.kr

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

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

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

컴파일러의 일반적 구조 컴파일러 원시 프로그램 목적 프로그램 전단부 후단부 어휘 분석 구문 분석 의미 분석 중간 코드 생성 Compiler, 2012. 컴파일러의 일반적 구조 원시 프로그램 컴파일러 목적 프로그램 전단부 후단부 어휘 분석 구문 분석 의미 분석 중간 코드 생성 코드 최적화 목적 코드 생성 토큰 구문트리 중간코드 의미분석 트리 최적화된 중간코드 kkman@ssangji.ac.kr

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

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

A, :=, B, +, 3, ; // 6개 토큰으로 분리 토큰의 예 A := B + 3; Compiler, 2012. 토큰의 예 A := B + 3; A, :=, B, +, 3, ; // 6개 토큰으로 분리 IF A > 10 THEN ... Token : IF A > 10 THEN ↓ ↓ ↓ ↓ ↓ Token number : 29 1 20 2 35 kkman@ssangji.ac.kr

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

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

Ex) A := B + 1; Tree : := A + B 1 Ucode: LOD 1 2 LDC 1 ADD STR 1 1 Compiler, 2012. Ex) A := B + 1; Tree : := A + B 1 Ucode: LOD 1 2 LDC 1 ADD STR 1 1 kkman@ssangji.ac.kr

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

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

코드 최적화 (optimization) 종류 Compiler, 2012. 코드 최적화 (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 kkman@ssangji.ac.kr

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

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

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

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

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

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

Lex와 YACC

QnA