编译原理¶
Chapter 0: About the course¶
Textbook: Modern Compiler Implementation in C (Andrew W. Appel, Maia Ginsburg)
- Homework (On paper): 10%
- Class Quizzes: 10%
- Project: 30% (bonus: 2+5+5)
- Final Exam: 50% (Kill line: 40/100 pts)
不讲：chap. 12, 15, 16
project information¶
- src language: SysY
- target language: RISC-V
Chapter 1: Introduction¶
- what is a compiler?
将一种语言翻译成另一种语言，而不仅仅是高级语言到低级语言，高到高、低到低同样可以，只要内容一致（语义 semantic）。
compiler 是一个复杂的 program
compiler 在多种形式的计算中被使用。
1.1: Modules and interfaces¶
两个重要概念：
- phases: one or more modules
- interfaces: 描述 modules 和 compiler 之间交互的信息
图中方形即 modules, 中间的字样即为 interfaces。本课程学到 Assembler 为止。
modularization 可以进一步简化。
1.2: Tools and software¶
两个最常用的 abstractions:
- Context-free grammars: for parsing
- Regular expressions: for lexical analysis
特殊工具: Yacc & Lex
1.3: Data structure for tree languages¶
产生式：
- Stm: Statement
- Exp: Expression
- Binop: Binary Operator
上面的产生式只能产生直线型语法（没有 if, for），产生过程参考 CFG.
一个参考的 parse tree:
对于每个变体（CompoundStm、AssignStm 等），我们创建一个 constructor function 来 malloc 或对数据结构初始化。
Chapter 2: Lexical Analysis¶
- Front end: compiler performs analysis
- Back end: synthesis
补充: middle end
其中 front end 可拆解为:
- Lexical analysis
- Syntax analysis
- Semantic analysis
Lexical analyzer: 接收字符流，生成 tokens 序列，丢弃空白符和注释
将 lexical 和 syntax 分开，使得 parser 更加简化。
2.1: Lexical Tokens¶
Lexical Tokens 即字符序列，也是 programming language 的组成部分。
- Type:
- ID
- NUM
- REAL
- IF
- COMMA "
- NOTEQ
- LPAREN (
- RPAREN )
- EOF
Reserved words (IF, VOID, RETURN) 不能用作 identifiers
non-tokens: 注释、头、宏、空白符、制表符、换行符
tokens 的划分遵循最长匹配原则（如 0.0 不会读成 0, ., 0，而是一整个 token）。
需要空白符分隔数字、关键词和常量。
更简单、可读的 lexical analyzer: 基于 Regular expressions, DFA
2.2: Regular expressions¶
回顾 Theory of Computation.