2009년 1학기 컴파일러 – 필기 자료

By | 2009/06/29

  3학년 1학기에 들은 컴파일러 수업 자료입니다. 컴파일러 전반적인 내용을 배웠습니다. Flex와 Bison을 이용하여 프로젝트를 할 수 있었다는 점이 매우 재미있었습니다.

  각 파일에 대한 설명은 다음과 같습니다.

  1. Intoduction to Compiler
    Compiler에 대한 전반적인 소개를 하고 있습니다. Scanner, Parser가 있는 Front End와 Instruction selection, Instruction scheduling, Register allocation이 있는 Back End, 그 중간에 있는 Middle End에 대한 소개가 있습니다.
  2. Scanner
    Source Code를 받아 이를 Token으로 바꾸는 Scanner에 대한 소개를 하고 있습니다. NFA, DFA와 같은 얘기를 하나 교수님은 오토마타시간에 배운다며 간단히 넘기셨습니다. 개인적으로는 맞는 말이지만 조금 난감했던 기억이 있습니다.^^
  3. Parser Introduction
    Source Code가 Grammar에 맞는지 확인하는 Parser에 대한 소개입니다. Derivation과 Ambiguous Grammars, Ambiguity에 얘기합니다.
  4. Top-down Parser
    Left-to-right scan, Leftmost derivation을 하는 LL Parser인 Top-down parser에 대한 정의와 소개입니다. backtrack을 하지 않도록 Predictive Parsing을 얘기합니다. 이 때 First sets, Follow sets를 정의합니다. 그리고 Left Recursion을 제거하고 Left Factoring을 수행하는 방법을 소개합니다. 마지막으로 LL(1) Skeleton Parser 소개와 Table에 대한 소개를 합니다.
  5. Bottom-up Parser (1)
    Bottom-up parsing과 reverse rightmost derivation을 하는 LR Parser인 Bottom-up Parser에 대한 정의와 소개입니다. handle에 대한 정의와 Shift-reduce parser를 소개합니다. LR(1) Skeleton Parser를 소개하고 goto, closure을 구하는 방법을 소개합니다.
  6. Bottom-up Parser (2)
    LR(1) Table을 만드는 예제를 얘기합니다. Canonical Collection을 소개한 후 그 예제를 소개합니다. ACTION table과 GOTO table을 소개하고 shift/reduce error, reduce/reduce error에 대한 얘기도 합니다. SLR(1), LR(1), LALR(1)에 대한 소개를 하지만 매우 짧게 합니다.
  7. Context-Sensitive Analysis
    Context Free는 앞에 선언한 것과 뒤에 정의하거나 사용하는 것을 비교할 수 없는 단점이 있습니다. 따라서 이를 해결하는 Context-Sensitvie Analysis가 필요합니다. 이것을 하는 방법으로 Attribute Grammars, Ad-hoc Syntax-directed Translation, Tree Walk를 소개합니다. Symbol Table도 여기서 얘기합니다.
  8. Procedure Abstraction (1)
    Procedure의 세 가지 Abstract한 관점으로 Control Abstraction, Name Space, Interface입니다. Control Abstarction에서는 Stack Frame과 Register Usage에 대한 얘기, Name Space에서는 lexical scoping과 여기에 따른 Symbol Table에 대한 얘기, Interface에서는 OS가 프로그램을 실행할 때 부르는 함수인 main 함수라거나 library를 호출할 때 사용하는 함수처럼 interface 관점에서 Function을 얘기하고 있습니다.
  9. Procedure Abstraction (2)
    Variable은 Automatic & Local, Static, Global이 있다는 것과 Virtual Address Space와 Physical Address Space에 대한 얘기, Calling Convention에 대한 얘기가 있습니다.
  10. Intermediate Representation
    Intermediate Representation(IR)은 프로그램에 대한 지식을 encode한 것으로 Abstract Syntax Tree(AST), Directed Acyclic Graph(DAG)등의 Structural IR, 3 address code, Stack machine code등의 Linear IR, Control-flow graph등의 Hybrid IR가 있고 이런 것을 소개합니다.
  11. Object Oriented Languages
    OOL에서는 class의 상속을 얘기합니다. 그리고 Single Inheritance와 Multiple Inheritance는 Compiler가 어떻게 표현할 것인지를 소개합니다.
  12. Code Generation
    Code Shape를 어떻게 할 것인지를 얘기합니다. Expressions, Types, Control Statements, Function calls을 표현하는 방법을 얘기합니다. Assignment, Array, Boolean & Relational Values, Conditional Move & Prediction, loop, break, continue, case, register save, parameter 등에 대해 얘기합니다.
  13. Data Flow Analysis (1)
    Control Flow Graph(CFG) 정의를 한 후 Available expressions, reaching definition, Aliases, live variables, copy propagation, Upward exposed uses등의 Data flow problem을 소개합니다. Data flow information(DFI)와 Data flow equation(DFE)를 소개합니다. 그리고 한 예로 Reaching Definition을 해결하는 방법을 소개하고 Lattice와 confluence에 대한 정의도 소개합니다.
  14. Data Flow Analysis (2)
    이어서 Live Variables 문제 해결에 대한 소개가 나옵니다.
  15. Definition & Usage
    DU(Def-Use) chains, UD(Use-Def) chains, Webs, Static Single Assignment(SSA) Form, Dominance Relation, Dominators, Dominator tree, Dominance frontier에 대한 정의 및 소개가 나옵니다.
  16. Optimizations
    Optimization의 여러 방법인 Redundancy Elimination, Value Numbering, Constant folding, Algebraic identities, Extended Basic Block(EBB), Dominator Value Numbering, Algebraic Simplification, Common Subexpression Elimination, Copy Propagation, Dead Code Elimination에 대한 소개를 합니다.
  17. Instruction Selection
    BackEnd의 한 부분인 Instruction Selection에 대한 소개입니다. 여기서 문제점은 하나를 표현하는 방법은 여러 가지가 있다는 점입니다. 따라서 가장 적절한 것을 선택해야 하는데 그 방법으로 Simple Treewalk, Tree-pattern Matching, Expander, Simplifier, Matcher를 가지는 Peephole Optimization에 대한 정의 및 소개, 사용 예가 있습니다.
  18. Instruction Scheduling
    Dependece graph를 그린 후 priority function을 계산합니다. 이 후 list scheduling을 수행합니다. 이런 것을 보여주고 있습니다.
  19. Register Allocation
    Web을 사용하여 Interference graph를 그린 후 Graph Coloring을 하여 Register Allocation을 수행합니다. 여기에 사용되는 Algorithm으로 Chaitin’s Algorithm, Chaitin-Briggs Algorithm을 소개합니다. 그리고 spill할 node를 선택할 때 어떤 heristic이 좋은지를 소개합니다.
  20. 이 수업은 시험 때 A4 용지 한 장 지참이 가능합니다. 하지만 중간고사 전에 얘기를 늦게 해주셔서 정리 자료를 만들었고 그 이후 새롭게 A4 정리 용지를 만들었습니다. 따라서 둘 다 스캔 하였습니다.

  파일들

컴파일러 01.pdf

컴파일러 02.pdf

컴파일러 03.pdf

컴파일러 04.pdf

컴파일러 05.pdf

컴파일러 06.pdf

컴파일러 07.pdf

컴파일러 08.pdf

컴파일러 09.pdf

컴파일러 10.pdf

컴파일러 11.pdf

컴파일러 12.pdf

컴파일러 13.pdf

컴파일러 14.pdf

컴파일러 15.pdf

컴파일러 16.pdf

컴파일러 17.pdf

컴파일러 18.pdf

컴파일러 19.pdf

컴파일러 20.pdf

Leave a Reply