Ch1 Intro

• Back to Course Home

编译流程

• 解释器 vs. 编译器 (Interpreter vs. Compiler)

  • 解释器方便错误诊断 (Error Diagnosis)

  • 编译器得到的代码更加高效

编译器

• Ch1 Intro

  • 编译流程

    • 编译器

  • 词法分析：Lexical Analysis

  • 语法分析：Syntax Analysis

  • 词法分析 vs. 语法分析

  • 语义分析：Semantic Analysis

  • 中间代码生成：Intermediate Code Generation

  • 优化：Optimization

  • 目标代码生成：Target Code Generation

词法分析：Lexical Analysis

• Lexical Analysis: Scanning （词法分析：扫描）

  • Lexical Analyzer: Scanner （词法分析器：扫描器）

  • Recognize Words (Lexemes) -> Tokens & Symbol Table （识别单词（词素）-> 生成标记和符号表）

  • Token:

    • token-name: id, number, keywords, operators, etc. （标记名：标识符、数字、关键字、运算符等）

    • attribute-value: a pointer to the symbol table （属性值：指向符号表的指针）

语法分析：Syntax Analysis

• Syntax Analysis: Parsing （语法分析：解析）

  • Syntax Analyzer: Parser （语法分析器：解析器）

  • Produce the Grammatical Structure （生成语法结构）

    • The Relationships among Tokens （标记之间的关系）

    • Tree-like Intermediate Representation （树状中间表示）

  • Parse Tree （解析树）

    • Parser generates the Parse Tree, from which produces the Syntax Tree （解析器生成解析树，从中生成语法树）

  • Syntax Tree: Simplified Parse Tree （语法树：简化的解析树）

    • Interior Node: Operation （内部节点：操作）

    • Children: Arguments of the Operation （子节点：操作的参数）

词法分析 vs. 语法分析

• 做着相似的事情：处理字符串

• 词法分析 (Scanning)：拆分字符串成 Lexemes，并抽象成 Tokens

• 语法分析 (Parsing)：整理 Tokens 的逻辑关系

语义分析：Semantic Analysis

• Semantic Analysis （语义分析）

  • computing additional info needed for compilation （计算编译所需的附加信息）

    • which is not regarded as syntax （这些信息不被视为语法）

  • checking source code semantic consistency with the language definition （检查源代码与语言定义的语义一致性）

    • Type Checking （类型检查）

中间代码生成：Intermediate Code Generation

• Intermediate Code Generation （中间代码生成）

  • Intermediate Representations (IR), e.g., Syntax Tree, etc. （中间表示，例如语法树等）

  • Low-level or Machine-like IR （低级或类似机器的中间表示）

    • LLVM-IR (LLVM, Clang), Gimple (GCC), etc. （LLVM-IR（LLVM，Clang），Gimple（GCC）等）

    • Three-address Code, with at Most Three Operands per Instruction （三地址码，每条指令最多三个操作数）

    • Static Single Assignment (SSA) （静态单赋值）

      • Every variable is only assigned (defined) once and defined before used. （每个变量只能被赋值（定义）一次，并且在使用前必须定义。）

优化：Optimization

• Optimization （优化）

  • Improve the IR for Better Target Code （改进中间表示以生成更好的目标代码）

  • Better: Faster, Smaller, Greener （更好：更快、更小、更环保）

目标代码生成：Target Code Generation

• Target Code Generation （目标代码生成）

  • Instruction Selection （指令选择）

    • RISC vs. CISC

      • RISC: Reduced Instruction Set Computer （精简指令集计算机）

      • CISC: Complex Instruction Set Computer （复杂指令集计算机）

    • Intel Manual: > 6000 Pages （英特尔手册：超过 6000 页）

  • Register Allocation （寄存器分配）

    • Graph Coloring Problem （图着色问题）

  • Evaluation Order （计算顺序）

    • Arrange the Computation Order for Less Register Occupation （安排计算顺序以减少寄存器占用）

    • NPC (Non-Polynomial Complete) Problem （非多项式完全问题）