本笔记关于编译器的阶段只包含了词法分析、语法分析、语义分析和中间代码生成，如果发现笔记有错误的地方欢迎大家给我指正。
文章目录
- 1.介绍
- 2.词法分析(Lexical Analysis)
- 3.语法分析(Syntax Analysis)
- 4.语义分析(Semantic Analysis)
- 5.Intermediate Code Generation(中间代码生成)
1.介绍
1.1 什么是编译器(Compiler)
编译器是将高级编程语言代码转换为机器语言代码的程序，它通常由多个阶段组成，每个阶段都有特定的功能和作用
主要阶段及其功能：
- 词法分析(Lexical Analysis)：
- 功能：将源代码转换为token stream。每个token表示源代码中的一个基本组成单元（如关键字、标识符、常量、操作符和分隔符）
- 工具：词法分析器(Lexer)或扫描器(Scanner)
- 输出：Tokens
- 语法分析(Syntax Analysis)：
- 功能：根据上下文无关法(Context-Free Grammar, CFG)对token stream进行分析，生成语法树(Syntax Tree)
- 工具：语法分析器(Parser)
- 输出：语法树(Syntax Tree)
- 语义分析(Semantic Analysis)：
- 功能：检查语法树是否符合语言的语义规则，如类型检查、作用域检查或变量绑定
- 工具：语义分析器(Semantic Analyzer)，通常包括符号表(Symbol Table)和类型检查器(Type Checker)
- 输出：带注释的语法树(Annotated Tree)
- 中间代码生成(Intermediate Code Generation)：
- 功能：将经过语义分析的AST转换成中间代码，中间代码是一种介于源代码和机器代码之间的中间表示，通常与具体机器无关
- 工具：中间代码生成器(Intermediate code generation)
- 输出：中间代码（如三地址码、静态单赋值形式SSA）(Intermediate code)
- 代码优化(Code Optimization)
- 功能：对中间代码进行优化，以提高代码的执行效率和减少资源占用，优化可以是局部的（如基本块内）或全局的（跨基本块）
- 工具：中间代码优化器(Intermediate code optimizer)
- 输出：优化后的中间代码
- 目标代码生成(Target Code Optimization)
- 功能：将优化后的中间代码转换成目标机器代码（机器语言或汇编语言）
- 工具：代码生成器(Code Generation)
- 输出：目标代码(Target code)
- 目标代码优化(Target Code Optimization)：
- 功能：对生成的目标代码进行进一步优化，主要针对特定的硬件平台进行的优化，如指令选择、寄存器分配和指令调度
- 工具：目标代码优化器(Target code optimizer)
- 输出：优化后的目标代码
- 汇编与链接(Assembly and Linking)：
- 功能：将汇编代码转换为机器代码，链接器将多个目标文件利用库文件链接成可执行文件
- 工具：汇编器(Assembler)或链接器(Linker)
- 输出：可执行文件(Executable File)
例题：
1.2 编译器 vs. 解释器(Interpreter)
编译器和解释器是将高级编程语言转换为机器可执行代码的两种不同的工具
编译器：
- 工作方式：
- 编译器在执行程序之前，将整个源代码在转换成机器代码
- 生成的机器代码可以独立于源代码直接执行
- 执行步骤：
- 编译过程分为多个阶段，具体看上面
- 编译过程通常一次性完成，生成可执行文件
- 性能：
- 编译后的程序执行速度较快，因为是直接执行的，不需要进一步翻译
- 由于编译时预处理步骤，程序启动时间较短
- 错误处理：
- 在编译过程中， 编译器会报告所有的语法和语义错误
- 必须修正所有错误后，程序才能编译成功并执行
- 示例语言：C、C++、Rust、Go等
解释器：
- 工作方式：
- 解释器逐行读取和执行源代码，不需要分阶段的编译过程
- 不生成独立的机器代码文件，每次执行都需要重新翻译源代码
- 性能：程序启动时间较长，因为每次执行都需要解释源代码
- 错误处理：
- 解释器在运行时遇到错误时立即报告，可能在程序运行到由错误的地方之前就已经执行了部分代码
- 运行期间可以进行调试，允许动态修改和测试代码
- 示例语言：Python、Ruby、JavaScript、Perl等
综合比较：
- 开发和调试：
- 编译器适合在代码成熟后进行优化和发布，因为编译后的代码的执行效率更高
- 解释器适合快速开发和测试，因为可以即使运行和修改代码
- 部署和分发：
- 编译器生成的可执行文件更容易分发，不需要源代码或或解释器
- 解释器需要在目标机器上安装解释器，并且需要源代码才能执行
- 安全性：
- 编译后的代码更难反向工程和破解，有一定安全性
- 解释型语言源代码需要随程序发布，安全性较低
既使用了编译器也使用了解释器的语言：Java，解释器是JVM
1.3 预处理器(Preprocessor)
预处理器是一个在编译器开始正式编译之前运行的工具。
一般负责的任务：
- 宏展开：预处理识别和替换宏定义。
- 文件包含：将被包含文件的内容插入到源文件中
- 条件编译：决定哪些代码片段应该被编译
预处理器运行后，会生成一个经过预处理的源文件，这个文件包含了素有已经被宏展开的源语言语句。
1.4 符号表(Symbol Table)
**定义：**是一个数据结构，编译器使用它来存储关于程序中各种标识符（如变量、函数、类、对象等）的信息，它维护每个标识符的属性，如类型、作用域、内存位置等
**功能：**符号表在编译的多个阶段都起着重要作用，特别是在词法分析、语法分析、语义分析和中间代码生成阶段。主要功能包括：
- 记录标识符信息：存储标识符的名称及其相关属性，如数据类型、作用域、存储类、维数（对于数组）、函数参数类型等
- 作用域管理：处理嵌套作用域和作用域链，支持局部变量和全局变量的区分
- 查找和更新：处理查找标识符的信息，并在必要时更新其属性
- 错误检测：帮助检测未声明变量的使用、重复声明等语义错误
1.5 其他
在编译原理的语法分析这个阶段，会看到许多ε，ε可以认为是任意存在的非终结符字符，它并不是说包含所有的非终结符字符，而是要看上下文的。比如一个非终结符的FOLLOW集包含{a, b, c}，那ε就可以“视作”a, b, c任意一个非终结字符。ε通常跟FOLLOW集挂钩。
语法树和抽象语法树的区别：
- AST使用运算符/操作作为根节点和内部节点，并使用操作数作为子节点
- AST与语法树不同，不使用内部节点来表示语法规则
- AST省略了节点和括号等细节
- AST与语法树相比，AST是密集的
2.词法分析(Lexical Analysis)
2.1 正则表达式(Regular Expression)
**定义：**描述字符串模式的符号表示法，匹配字符集合和特定的字符序列
组成部分：
-
字符(Character)：直接匹配自身的字符，如’a’, ‘b’, '1’等
-
元字符(Metacharacter)：特殊的符号，用于表示更复杂的模式
元字符 含义 . 匹配除换行符外的任意单个字符 * 匹配前面的字符零次或多次，'a*'匹配0个或多个a + 匹配前面的字符一次或多次 ? 匹配前面的字符零次或一次 | 表示选择，匹配左边或右边的模式 () 用于分组，将多个字符或模式视为一个整体 ^ 匹配字符串开头，'^abc’匹配以’abc’开头的字符串 $ 匹配字符串结尾，'$abc’匹配以’abc’结尾的字符串 -
转义字符(Escape character, ESC)：使用反斜杠’\‘转义元字符，一匹配其字面含义，如’\*‘匹配星号’*’
应用：
- 词法分析器生成：RE(正则表达式)用于定义token的模式，匹配标识符(Identifier)
- 自动生成词法分析器：如Lex，Flex使用RE来自动生成词法分析器代码，能够识别由开发者定义的一系列正则表达式和相应的动作
例题：
-
不包含子串101的所有由0和1组成的字符串
0*(1*000*)*1*0* 让101的1之间有多个零即可
-
至少同时有两个子串00的所有由0和1组成的字符串
(0|1)*00(0|1)*00(0|1)* | (0|1)*000(0|1)* -
注释，由/*和*/包围的字符串组成，没有中间的*/，除非它在双引号内
- a 代表所有的字符除了*，"和/
- o 代表了*（不是元字符了这里）
- /o ( o*(a|"|“o/”) | / )* o+/
2.2 有限自动机(Finite Automata)
FA是词法分析中的重要工具，用于实现词法分析器(Lexer)。FA有两种主要形式：非确定有限自动机(NFA)和确定有限自动机(DFA)。
非确定有限状态机(NFA)：
- 定义：允许从一个状态在读入一个符号后可以转移到多个状态。包括五个元素：一个有限状态集合，一个字母表，一个转换函数，一个初始状态和一个接受状态集合
- 特性：
- 可以有多个初始状态
- 从一个状态在读入相同的符号后转移到多个状态
- 可以有ε(epsilon)转移，即在没有输入符号的情况下进行状态转移
确定有限状态机(DFA)：
- 定义：在读入一个符号后，总是确定地从一个状态转移到另一个状态。包括五个元素：一个有限状态集合，一个字母表，一个转移函数，一个初始状态和一个接受状态集合
- 特性：
- 从任何状态出发，在读入一个符号后只能转移到一个确定的状态
- 没有ε转换
2.3 从RE到NFA
将RE转换成NAF通常使用Thompson构造法。
基本规则：
-
基础：对于每个符号a，构造一个NFA：
-
连接(Concatenation)：对于ab，构造一个NFA：
-
选择(Alternation)：对于a|b，构造一个NFA：
-
闭包(Kleene Star)：对于a*，构造一个NFA：
例题：
(0|1)*00(0|1)*00(0|1)* | (0|1)*000(0|1)* 的NFA
(0|1)*的NAF如下所示：
可以用下图表示：
先看左边的产生式(0|1)*00(0|1)*00(0|1)*，可以画出下图（不含ε产生式，省掉了）：
在此基础上加上右边的产生式(0|1)*000(0|1)*，可以画出下图：
2.4 从NFA到DFA
将NFA转换成DFA通常使用子集构造法(Subset Construction)
三个状态：
- 初始状态：通过NFA的ε闭包确定DFA的初始状态（从NFA的初始状态通过ε能够到达的所有状态的集合）
- 状态转移：对于DFA的每个状态（对应NFA状态的集合）以及每个输入符号，计算这个集合中的所有NFA状态在读取该符号后的集合
- 接受状态：如果DFA的某个状态包含NFA的某个接受状态，则该DFA状态为接受状态
主要步骤：
- NFA的初始节点和初始节点所有ε可达的节点共同构成DFA的初始节点，然后对初始DFA节点执行步骤2
- 对当前的DFA节点，找到其中所有NFA节点对输入符号x所有可达的NFA节点，这些节点共同构成的NFA节点作为当前DFA节点对输入x可达的DFA节点
- 如果步骤2中找到了新节点，就对新节点重复执行步骤2
- 重复步骤2和步骤3直到找不到新DFA节点为止
- 把所有包含NFA接受节点的DFA节点标记为DFA的接受节点
具体示例：
-
初始节点：
-
对DFA节点0执行步骤2，找到NFA中输入a可达的NAF节点构成的集合作为DNF节点1
-
对DFA节点1执行步骤2，找到NFA中输入b可达的NFA节点构成的集合作为DFA节点2
-
对DFA节点2执行步骤2，找到NFA中输入c可达的NFA节点构成的集合作为DFA节点3
-
重复步骤2，3可获得以下DFA图
NFA DFA a b c 0 A B 1,2,4,6,8,9 B C D 2,3,4,6,7,9 C C D 2,4,5,6,7,9 D C D
例题：
在上面那个RE到NFA的例题上，将NFA转换为DFA
NFA：
转DFA步骤：
- 将NFA0作为初始DFA节点A，对其输入0和1，看是否有得到新节点，输入0到达了0和0，作为DFA1（B）
- 对B输入0，得到新节点C(0,1,2,3)，输入1，移动到A
- 对C输入0，得到新节点D(0,1,2,3,4)，输入1，得到新节点E (0,2)
- 对D输入0和1，还是D
- 对E输入1，还是1，输入0移动到C
根据上面的步骤，可作出如下表格：
| NFA | DFA | 0 | 1 |
|---|---|---|---|
| 0 | A | B | A |
| 0, 1 | B | C | A |
| 0, 1, 2, 3 | C | D | E |
| 0, 1, 2, 3, 4 | D | D | D |
| 0, 2 | E | C | E |
如图：
2.5 最小化DFA
DFA的最小化旨在减少状态数，使其成为最小的等价DFA。（state-minization algorithm）
主要概念：
- 可区分：对于两个状态i和s，若从以状态出发接受输入字符串str，而从另一状态出发不接受这个str（即同样输入str到达不同状态），则称状态s和状态i是可区分的
- 不可区分：设想任何输入序列str对i和s都是不可区分的，则说明从s出发和从i出发，分析任何输入序列str均得到相同结果，因此i和s可以合并为一个状态
步骤：
- 初始划分：将DFA的所有状态分为两组：接受状态组和非接受状态组
- 划分细化：根据转移函数细化状态集合，将那些相同输入符号下转移到不同组的状态分开
- 构建最小化DFA：
- 对于每个状态组，选择一个代表状态
- 构建新的转移函数，其中状态组作为新的状态，转移到其他状态组
2.6 从FA到RE
（可能不考）
将FA转换成RE的常用方法是通过消除状态法(State Elimination Method)
步骤：
- 转换DFA为GNFA：
- GNFA是一种扩展的NFA，其中每个转换可以是任意正则表达式
- 初始化GNFA：
- 增加一个新的初始状态q_start，使用ε转换到原初始状态
- 增加一个新的接受状态q_accept，所有原接受状态用ε转换到q_accept
- 确保每对状态之间最多有一个直接转换，转换标签可以是正则表达式
- 状态消除：
- 选择一个中间状态q_k
- 对每个入状态q_i和出状态q_j，通过q_k的路径可以描述为：q_i – r1 --> q_k – r2 – > q_j
- 替换为直接转换：q_i – (r1r2 | r1r2r3)* --> q_j，r3表示q_k到自身的转换（如果有的话）
- 得到最终的RE：剩下的GNFA只有q_start和q_accept，q_start和q_accept的转换标签就是对应的RE
2.7 RE和上下文无关文法(CFG)的区别
定义：
- RE：是一种用来描述字符模式的符号表示法，适用于定义token
- CFG：是一种用于定义编程语言语法的形式化系统。CFG由一组递归的生产规则组成，每条规则定义如何从一个符号生成字符串
应用场景：
- RE：适用于词法分析阶段
- CFG：适用于语法分析阶段
表达能力：
- RE：适用于描述简单、线性的语言结构。
- CFG：能够描述复杂的语言结构，包括递归、嵌套等
2.8 例题
(a|b)*abb(a|b)*
将RE转换为NFA（使用Tompson算法），再转换为DFA（子集构造法），最后最小化DFA
从RE到NFA：
从NFA到DFA：
| NFA | DFA | a | b |
|---|---|---|---|
| 0,1,2,3,7 | A | B | C |
| 1,2,3,4,6,7,8,9 | B | B | D |
| 1,2,3,5,6,7 | C | B | C |
| 1,2,3,5,6,7,10,11 | D | B | E |
| 1,2,3,5,6,7,12,13,14,15,19 | E | F | G |
| 1,2,3,4,6,7,8,9,13,14,15,16,18,19 | F | F | H |
| 1,2,3,5,6,7,13,14,15,17,18,19 | G | F | G |
| 1,2,3,5,6,7,10,11,13,14,15,17,18,19 | H | F | I |
| 1,2,3,5,6,7,12,13,14,15,17,18,19 | I | F | G |
最小化DFA：
最开始，假设{A, B, C, D}为一组，{E, F, G, H, I}为一组（接受状态为一组）。对两组都输入a和b，最终发现A,C为一组，B为一组，D为一组，接受状态的为一组，则有：
3.语法分析(Syntax Analysis)
3.1 上下文无关文法(CFG)
CFG用于定义编程语言的语法，能够描述许多编程语言的语法结构，包括表达式、语句、程序块等，下面讨论的所有文法都是上下文无关文法
3.1.1 基本概念
定义： 一个CFG由四个组成部分构成：
- 非终结符集合(V)：非终结符是文法中的变量，可以被替换
- 终结符集合(Σ)：终结符是文法中的常量，表示语言中的基本符号
- 生成规则集合§：生成规则定义了如何将非终结符替换为终结符或其他非终结符的组合
- 开始符号(S)：开始符号是文法生成过程的起点
形式化定义为：G = (V, Σ, P, S)
**生成规则：**是形式为A -> α 的替换规则，其中A是一个非终结符，α是终结符和非终结符的组合
例子：
考虑一个简单的文法G，用于描述算术表达式：
- 非终结符：E, T, F
- 终结符： +, -, *, /, (, ), id
- 开始符号：E
- 生成规则：
- E -> E + T | E - T | T
- T -> T*F | T/F | F
- F -> (E) | id
- 这个文法G可以生成算法表达式如 id+id*id 或 (id+id) * id
3.1.2 推导(Derivation)
推到是从开始符号出发，根据生成规则逐步替换非终结符，直到只剩下终结符的过程。这个过程可以是通过左推导(Leftmost Derivation)或右推导(Rightmost Derivation)来完成
左推导：左推导总是替换最左边的非终结符，以下是生成id+id*id（上面的例子）的左推导
- E -> E + T
- E + T -> T + T
- T + T -> F + T
- F + T -> id + T
- id + T -> id + T * F
- id + T * F -> id + F * F
- id + F * F -> id + id * F
- id + id * F -> id + id * id
右推导：右推导是每个总是替换最右边的非终结符。还是上面的例子
- E -> E + T
- E + T -> E + T * F
- E + T * F -> E + T * id
- E + T * id -> E + F * id
- E + F * id -> E + id * id
- E + id * id -> T + id * id
- T + id * id -> id + id * id
3.1.3 语法树(Parse Tree)
语法树是一种树状结构，用于表示推导过程。树的根节点是开始符号，内部节点是非终结符，叶节点是终结符
示例：还是拿上面的id + id * id举例
3.1.4 性质
二义性(Ambiguous)：如果存在至少一个字符串有多于一种的语法树，则说明一个文法是二义的。消除二义性通常需要重新设计文法，使得每个字符串只有唯一的语法树
归约(Reduction)：归约是推导的反向过程，使用产生式规则将终结符和非终结符的串还原为非终结符(α -> A)，直到还原为开始符号。归约用于语法分析器的自底向上(Bottom-Up)分析方法
文法的范式：
- Chomsky范式：每个产生式要么是 A -> BC，要么是A -> α，其中A，B，C是非终结符，α是终结符
- 格雷巴赫范式：每个产生式是A- > aα，其中A是非终结符，a是终结符，α是非终结符的串
3.1.5 左因子(Left Factoring)
左因子是指在一个产生式中，多个选择有共同的前缀，为了使文法适合自顶向下分析，通常需要消除左因子
左因子问题：如果一个非终结符的多个产生式共享一个共同前缀，例如A→α β 1 β_1 β1 ∣ α β 2 β_2 β2，这里α是前缀
消除左因子：
- 对于每个有共同前缀的规则A→α β 1 β_1 β1 ∣ α β 2 β_2 β2 ∣ … ∣α β n β_n βn ∣ γ，其中γ不以α开头
- 引入一个新的非终结符A‘
- 重写规则如下：
- A→αA′ ∣ γ
- A′→ β 1 β_1 β1 ∣ β 2 β_2 β2 ∣ … ∣ β n β_n βn
示例：
将以下左因子文法：S→iEtS ∣ iEtSeS ∣ a，重写为：
- S→iEtSS′ ∣ a
- S′→eS ∣ ϵ
3.1.6 左递归(Lef Recursion)
左递归是一种递归规则的形式，在语法分析中可能导致无限递归，从而使语法分析器无法正常工作，一个文法规则是左递归，当且仅当它自身可以递归地出现在它的最左边
直接左递归：是指一个非终结符的产生式直接引用自身，例如：A→Aα ∣ β，其中α和β是符号串，且α不能以ε开头
间接左递归：是通过其他非终结符间接引用自身，例如：A→Bα，B→Aβ ∣ γ
消除左递归：为了避免语法分析中的无限递归，需要消除左递归
- 对于每个左递归规则 A → A α 1 ∣ A α 2 ∣ . . . ∣ A α n ∣ β 1 ∣ β 2 ∣ . . . ∣ β m A→Aα_1 ∣ Aα_2 ∣ ... ∣ Aα_n ∣ β_1 ∣ β_2 ∣ ... ∣ β_m A→Aα1∣Aα2∣...∣Aαn∣β1∣β2∣...∣βm，其中 α i α_i αi不能以ε开头， β j β_j βj不能以A开头
- 引入一个新的非终结符A’
- 重写规则如下：
- A → β 1 A ′ ∣ β 2 A ′ ∣ . . . ∣ β m A ′ A→β_1A′ ∣ β_2A′ ∣ ... ∣ β_mA′ A→β1A′∣β2A′∣...∣βmA′
- A ′ → α 1 A ′ ∣ α 2 A ′ ∣ . . . ∣ α n A ′ ∣ ϵ A′→α_1A′ ∣ α_2A′ ∣ ... ∣ α_nA′ ∣ ϵ A′→α1A′∣α2A′∣...∣αnA′∣ϵ
- 将Aα这一坨变成A‘，然后放到后面那些候选式后面，然后A’ -> 这一条要把A’放后面
示例：将E→E+T ∣ T重写为：
- E→TE’
- E′→+TE′ ∣ ϵ
3.2 自顶向下语法分析(Top-Down Parsing)
自顶向下是一种语法分析技术，从文法的开始符号出发，是最左推导的过程，通过一系列推导步骤，尝试生成输入串的语法树。自顶向下语法分析器的两种主要类型是预测分析(Predictive Parsing, LL分析)和递归下降分析(Recursive Descent Parsing)
3.2.1 预测分析(LL分析)
预测分析是一种更高效的自顶向下分析方法，它通过使用预测表来决定应使用哪个产生式进行推导。预测分析可以避免递归下降中的回溯问题
预测表的构建：预测分析器需要构建一个预测分析表(Parse Table)，该表根据文法的FIRST和FOLLOW集合构建
- FIRST集合：对于任意符号X，FIRST(X)是能够出现在由X推导出的任意字符串的第一个终结符集合。如果X可以推导出空串ε，则ε也在FIRST(X)中
- FOLLOW集合：对于任意非终结符A，FOLLOW(A)是能够紧跟在A之后的终结符集合，如果A可以出现在某推导的最右边，则文法的结束符号 '$'也在FOLLOW(A)中
- 如果A是开始符号，则$$ \in Follow(A)$
- 如果有产生式 B → α A a β B\to αAaβ B→αAaβ， a ∈ V t a\in V_t a∈Vt，把a加入到Follow(A)中
- 如果有产生式 B → α A X β B\to αAXβ B→αAXβ，把 F i r s t ( X β ) First(Xβ) First(Xβ)中非c元素加入到Follow(A)中
- 如果 B → α A B\to αA B→αA，或者 B → α A β B\to αAβ B→αAβ且 β = > ε β=>ε β=>ε，把Follow(B)加入到Follow(A)中
- 对于每一个非终结符，浏览每个产生式，连续使用上述规则，直到A的Follow集不再增大为止
示例：考虑一下文法：
E
→
T
E
′
E
′
→
+
T
E
′
∣
ϵ
T
→
F
T
′
T
′
→
∗
F
T
′
∣
ϵ
F
→
(
E
)
∣
i
d
\begin{aligned} &E\to TE^{\prime} \\ &E^{\prime}\to+TE^{\prime}\mid\epsilon \\ &T\to FT^{\prime} \\ &T^{\prime}\to*FT^{\prime}\mid\epsilon \\ &F\to(E)\mid id \end{aligned}
E→TE′E′→+TE′∣ϵT→FT′T′→∗FT′∣ϵF→(E)∣id
构建FIRST集合和FOLLOW集合：
F
I
R
S
T
(
E
)
=
F
I
R
S
T
(
T
)
=
F
I
R
S
T
(
F
)
=
{
′
(
′
,
′
i
d
′
)
F
I
R
S
T
(
E
′
)
=
{
′
+
′
,
ε
}
F
I
R
S
T
(
T
′
)
=
{
′
∗
′
,
ε
}
F
O
L
L
O
W
(
E
)
=
F
O
L
L
O
W
(
E
′
)
=
{
′
)
′
,
$
}
F
O
L
L
O
W
(
T
)
=
F
O
L
L
O
W
(
T
′
)
=
{
′
+
′
,
′
)
′
,
$
}
F
O
L
L
O
W
(
F
)
=
{
′
∗
′
,
′
+
′
,
′
)
′
,
$
}
\begin{aligned}&\mathrm{FIRST}(\mathrm{E})=\mathrm{FIRST}(\mathrm{T})=\mathrm{FIRST}(\mathrm{F})=\{\mathrm{'}(\mathrm{'},\mathrm{'id}\mathrm{'})\\&\mathrm{FIRST}(\mathrm{E}^{\prime})=\{^{\prime}+^{\prime},\varepsilon\}\\&\mathrm{FIRST}(\mathrm{T}^{\prime})=\{^{\prime}*^{\prime},\varepsilon\}\\&\mathrm{FOLLOW}(\mathrm{E})=\mathrm{FOLLOW}(\mathrm{E'})=\{^{\prime})^{\prime},\mathrm{\$}\}\\&\mathrm{FOLLOW}(\mathrm{T})=\mathrm{FOLLOW}(\mathrm{T'})=\{^{\prime}+^{\prime},^{\prime})^{\prime},\mathrm{\$}\}\\&\mathrm{FOLLOW}(\mathrm{F})=\{^{\prime}*^{\prime},^{\prime}+^{\prime},^{\prime})',\mathrm{\$}\}\end{aligned}
FIRST(E)=FIRST(T)=FIRST(F)={′(′,′id′)FIRST(E′)={′+′,ε}FIRST(T′)={′∗′,ε}FOLLOW(E)=FOLLOW(E′)={′)′,$}FOLLOW(T)=FOLLOW(T′)={′+′,′)′,$}FOLLOW(F)={′∗′,′+′,′)′,$}
预测分析表：ε产生式是否写入分析表，看其FOLLOW集字符
| ( | ) | id | * | + | $ | |
|---|---|---|---|---|---|---|
| E | E->TE’ | E->TE’ | ||||
| E’ | E’->ε | E’->+TE’ | E’->ε | |||
| T | T->FT’ | T->FT | ||||
| T’ | T’->ε | T’->*FT’ | T’->ε | T’->ε | ||
| F | F->(E) | F->id |
预测分析中的错误恢复(Error Recovery)：处理输入串中语法错误的一种机制
- 恐慌模式(Panic Mode)：当预测分析器遇到错误时，它会丢失输入中的符号，直到找到一个可以继续解析的同步符号(Synchronization Token)。同步符号通常是语句分隔符（如分号）、块结束符（如右花括号）等
- 实现步骤：
- 检测错误：当分析器在预测表中找不到对应的产生式时，报告错误
- 跳过输入：丢弃输入符号，直到遇到一个同步符号
- 继续解析：从同步符号之后继续解析
- 实现步骤：
- 错误产生式(Error Productions )：通过在文法中明确指定错误处理规则的技术。它允许文法包含一些特殊的产生式，当遇到错误时，分析器可以应用这些产生式来处理错误并尝试继续解析
- 实现步骤：
- 扩展文法：在文法中加入错误产生式
- 匹配错误产生式：当遇到错误时，应用错误产生式来处理并尝试继续解析
- 实现步骤：
- 前缀分析(Phrase-Level Recovery)：一种更复杂的错误恢复技术，它试图对错误进行本地修复，使得解析器能够在当前位置继续解析。它可能尝试插入、删除或替换输入符号，以便恢复到一个合法状态
- 实现步骤：
- 检测错误：当分析器在预测表中找不到对应的产生式时，报告错误
- 本地修复：尝试插入、删除或替换输入符号，使其符合预测表中的某个产生式
- 继续解析：应用修复后的符号继续解析
- 实现步骤：
LL(1)文法”LL表示从左到右进行扫描(Left-to-right scanning)，并从左到右构造最左推导(Leftmost derivation)。‘1’表示使用一个符号的前瞻(lookahead)来决定解析动作
- 特点：
- 单一前瞻符号：仅需要一个前瞻符号来决定使用哪个产生式规则
- 无左递归：不能包含左递归，因为左递归会导致预测分析器的无限递归
- 无二义性和无回溯：LL(1)文法是非二义性的，并且解析器在任何时刻不要回溯即可确定下一个步骤
- 判断是否为LL(1)文法步骤：
- 提取左因子：通过提取左因子来消除产生式的共同前缀，以确保每一步解析都可以通过一个前瞻符号唯一确定产生式
- 消除左递归：确保文法没有直接或间接的左递归，因为左递归会导致无限递归
- 到这一步，没有左因子和左递归，则计算每个产生式规则的所有候选式FIRST集并判断其是否相交（即是否有回溯），如果每个产生式规则都满足LL(1)的判定条件1（相交为空集），看下一步
- 若存在某个A -> ε，求A的FOLLOW集，然后判断A的FIRST集和FOLLOW集是否相交，如果满足LL(1)的判别条件2（相交为空集），则该文法是LL(1)文法
3.2.2 递归下降分析
递归下降分析是一种基于递归函数的语法分析方法，每个非终结符对应一个函数，这些函数根据产生式规则调用自身或其他函数来解析输入串。
递归下降分析是直接以程序的方式模拟产生式产生语言的过程，即为每一个非终结符造一个函数，每个函数的函数体按非终结符的候选式分情况展开，遇到终结符进行比较，看是否与输入的符号相同；遇到非终结符就调用该非终结符对应的函数。
3.3 自底向上语法分析(Bottom-Up Parsing)
自底向上语法分析是一种构造最右推导逆过程的解析方法。在编译原理中，最常见的自底向上分析器是LR分析器（包括SLR, SALR, LR(0))。
3.3.1 基本概念
右句型(Right Sentential Forms)：
- 定义：从文法的其实符号出发，通过一系列产生式规则推导而来的字符串，这个字符串在推导过程中总是以最右边的符号进行替换。简单来说，右句型是最右推导(Rightmost Derivation)过程中的任一中间结果
- 特性：右句型是通过最右推导步骤生成，每一步推导都替换当前右边的非终结符
句柄(Handle)：在一个输入串中，句柄是指一个子串，它是某个产生式右部，并且可以被替换为该产生式左部以形成文法的右推导步骤（句柄指的是右推导过程中的句子）
归约(Reduction)：将输入串的句柄替换为相应的非终结符
移进(Shift)：将输入串的下一个输入符号移入栈中
状态(State)：用于表示解析的当前位置以及所处的文法规则
可行前缀(Viable Prefix)：指某个句子的前缀，它可以扩展为句子的一部分，并且在过程中任何一步都不需要超过句柄的边界
LR分析器的基本工作流程：
- 初始化：栈中最初包含初始状态
- 移进：根据当前状态和输入符号，决定是否将输入符号移入栈中，并转移到新的状态
- 归约：根据当前状态和栈顶符号，决定是否将符号归约为某个非终结符
- 接受：如果输入符号和栈顶符号匹配起始符号，则接受输入串‘
- 错误处理：如果没有合法的移进或归约操作，则报告错误
3.3.2 LR(0)分析
LR(0)分析器使用LR(0)项集和分析表来解析输入串
基本概念：
-
项(Item)：LR(0)项是一个带有“点”的产生式，表示解析器在处理产生式的过程中可能处于各种位置。例如，产生式A->XYZ可能对应以下LR(0)项
A → ⋅ X Y Z (尚未处理任何符号) A → X ⋅ Y Z (已处理符号 X) A → X Y ⋅ Z (已处理符号 XY) A → X Y Z ⋅ (已处理符号 XYZ) \begin{aligned}&A\to\cdot XYZ\text{(尚未处理任何符号)}\\&A\to X\cdot YZ\text{(已处理符号 X)}\\&A\to XY\cdot Z\text{(已处理符号 XY)}\\&A\to XYZ\cdot\text{(已处理符号 XYZ)}\end{aligned} A→⋅XYZ(尚未处理任何符号)A→X⋅YZ(已处理符号 X)A→XY⋅Z(已处理符号 XY)A→XYZ⋅(已处理符号 XYZ) -
项集(Item Set)：一个项集是一个LR(0)的集合，表示解析器在某一个时刻可能处于的状态。项集通过“闭包(Closure)”操作和“转移(Goto)”操作构建
-
项集闭包：用于扩展当前项集，包含所有可能的项。例如，对于项集中的项A ->α · Bβ，如果存在产生式B -> γ，，则将其加入项集中
-
项集转移：描述了从一个项集通过符号转移到另一个项集的过程
构建LR(0)分析表：
- 构造初始项集：从扩展文法（增广文法）的起始项开始构造初始项集。扩展文法通常添加一个新的起始符号S’ -> S，其中S是原文法的起始符号
- 构造LR(0)项集规范族：
- 初始项集：从扩展文法的起始项S’ -> S开始，应用闭包擦欧总
- 项集闭包：对于每个项，如果点号后面是非终结符，则将该非终结符的所有产生式前加上点号，直到项集不再变化
- 项集转移：通过移进操作和闭包操作，生成所有可能的项集
- 构建分析表
sn：将符号a、状态n压入栈
rn：用第n个产生式进行归约
注意：如果有类似这样的产生式A->ε，也要在项目集中加入A->·，而且是直接作归约
判断是否为LR(0)文法：需要检查在构建LR(0)项集和对应的LR(0)分析表是否存在移进/归约冲突或归约/归约冲突。如果没有，则该文法是LR(0)文法
- 移进/归约冲突：同一状态和输入符号组合下，既需要移进又需要归约
- 归约/归约冲突：同一状态和输入符号组合下，存在多个归约操作
3.3.3 SLR分析
SLR(Simple LR)分析是在LR(0)分析的基础上，引入了FOLLOW集以减少归约/归约冲突和移进/归约冲突。SLR分析结合了LR(0)和FOLLOW集来构建分析表，使得解析器可以处理更复杂的文法
基本步骤：
- 构造扩展文法：添加新的起始符号，并相应地添加起始产生式。
- 构造LR(0)项集规范族：
- 初始项集：从扩展文法的起始项S’ -> S开始，应用闭包擦欧总
- 项集闭包：对于每个项，如果点号后面是非终结符，则将该非终结符的所有产生式前加上点号，直到项集不再变化
- 项集转移：通过移进操作和闭包操作，生成所有可能的项集
- 计算FOLLOW集：用于确定在何处进行归约操作的集合，
- 构建SLR分析表：根据项集规范族和FOLLOW集，构建SLR分析表
- 检查冲突，在SLR分析表中，如果某个状态和输入符号同时存在移进和归约操作，或存在多个归约操作，且FOLLOW集也无法判断是进行移进还是归约，则表示文法不是SLR文法
3.3.4 LR(1)分析
LR(1)分析是比LR(0)和SLR(0)更强大的解析器技术。LR(1)分析器利用更丰富的信息（即Lookahead符号）来进行语法解析。LR(1)分析使用LR(1)项集和分析表来解析输入字符串
基本概念：
- LR(1)项：LR(1)项是带有一个点和展望符号(Lookahead Symbol)的产生式。它的形式[A -> α · β, α]，表示当前解析到α，点在β前面，并且在β之后期望看到的终结符是α
- 项集闭包：将所有可能的LR(1)项加入项集中。例如，对于项[A -> α · Bβ, α]，如果B是非终结符，并且B -> γ是一个产生式，那么[B -> ` γ, b]也应加入项集中，这里的b是预测可能跟随β的lookahead
- 项集转移：项集的转移操作描述了从一个项集通过一个符号转移到另一个项集的过程
构建LR(1)分析表：
- 构建扩展文法：添加一个新的起始符号并相应地添加起始产生式
- 构造初始项集：从扩展文法的起始项[S’ -> ·S, $]开始，构造初始项集 I 0 I_0 I0并应用闭包操作
- 构造项集规范族
- 构建LR(1)分析表
- 检查冲突：检查是否存在移进/归约冲突或归约/归约冲突，如果存在，则该文法不是LR(1)文法
3.3.5 LALR(1)分析
LALR(1)（Look-Ahead LR(1)）分析结合了LR(1)分析的强大能力和SLR分析的低资源消耗。LALR(1)分析通过合并具有相同内核的LR(1)项集，显著减少了分析表的大小，但仍保留了处理复杂文法的能力
基本步骤：
- 构造扩展文法
- 构造LR(1)项集规范族
- 合并项集：合并那些具有相同内核（不包括lookahead符号）的项集。合并后的项集的lookahead是所有被合并项集的lookahead符号的并集
- 构建LALR(1)分析表
- 检查冲突
3.4 例题
3.4.1 自顶向下语法分析例题
文法：S -> S+S | SS | (S) | S* | a
字符串：(a+a)*a
-
求最左推导和最右推导
-
提取左因子和消除左递归
-
判断该文法是否为LL(1)文法
-
构建LL(1)分析表
a ( ) * + $ S S -> aS’’ S -> (S)S’’ S’ S’ -> S S’ -> S S’ -> * S’ -> +S S’’ S’’ -> S’S’‘
S’’ -> εS’’ -> S’S’‘
S’’ -> εS’’ -> ε S’ -> S’S’‘
S’’ -> εS’’ -> S’S’‘
S’’ -> εS’’ -> ε 表中S’‘对应项并不都唯一，推导过程不能确定产生式，S’'->ε这个产生式，只有在FOLLOW集中的字符输入，才能在分析表中写入
-
LL(1)分析过程模拟
step stack input action 1 S$ (a+a)*a$ S -> (S)S’’ 2 (S)S’'$ (a+a)*a$ match 3 S)S’'$ a+a)*a$ S -> aS’’ 4 aS’‘)S’'$ a+a)*a$ match 5 S’‘)S’’ +a)*a$ S’’ -> S’S’‘
S’’ -> ε产生式不唯一，LL(1)分析无法进行下去
3.4.2 自底向上语法分析例题
文法：S -> SS+ | SS* | a
字符串：aaa*a++
最右推导：
可行前缀：（画红线的依然为句柄）
SLR DAF：有个小错误，在 I 1 I_1 I1项目集中S -> a·，应该是S -> ·a，点在a前面，还少了S -> ·SS+和S -> ·SS*（该文法不是LR文法因为 I 1 I_1 I1存在移进-归约冲突，S’->S·归约【接受状态也要先归约】，其余四个移进）
这里可能会有疑惑，就是为什么 I 0 I_0 I0到 I 1 I_1 I1，不应该只有S->S·、S->S·S+、S->S·S*吗？为什么还有多出来的那些，对 I 1 I_1 I1执行闭包的操作，仅着三个项输入ε的操作，例如S->S·S+，点后面输入ε，那就可以到达S的所有候选式的状态， I 3 I_3 I3则是输入S后有的S->S·S+和S->S·S*，然后在闭包操作，有了后面三个
SLR解析表：FOLLOW集内的非终结符才能进行归约操作
SLR分析过程模拟：（栈顶可以找到句柄，遇到句柄就会归约，然后从最前面的状态输入归约后的符号即可得到新的状态，例如0a2，a归约后是S，0输入S后达到状态1）
| Step | Stack | Input | Action | Goto |
|---|---|---|---|---|
| 1 | $0 | aaa*a++ $ | s2 | |
| 2 | $0a2 | aa*a++ $ | r4 | 1 |
| 3 | $0S1 | aa*a++ $ | s2 | |
| 4 | $0S1a2 | a*a++ $ | r4 | 3 |
| 5 | $0S1S3 | a*a++ $ | s2 | |
| 6 | $0S1S3a2 | *a++ $ | r4 | 3 |
| 7 | $0S1S3S3 | *a++ $ | s5 | |
| 8 | $0S1S3S3*5 | a++ $ | r3 | 3 |
| 9 | $0S1S3 | a++ $ | s2 | |
| 10 | $0S1S3a2 | ++ $ | r4 | 3 |
| 11 | $0S1S3S3 | ++ $ | s4 | |
| 12 | $0S1S3S3+4 | + $ | r2 | 3 |
| 13 | $0S1S3 | +$ | s4 | |
| 14 | $0S1S3+4 | $ | r2 | 1 |
| 15 | $0S1 | $ | accept |
判断LL(1)文法和SLR文法：
S -> AaAb | BbBa
A -> ε
B -> ε
First(AaAb)={a}
First(BbBa)={b}
First(AaAb) ∩ First(BbBa)= Φ
First(A) ∩ Follow(A)={ɛ} ∩ {a,b}= Φ
First(B) ∩ Follow(B)={ɛ} ∩ {a,b}= Φ
是LL(1)文法
Follow(S)= {$}
Follow(A)= {a,b}
Follow(B)={a,b}
Follow(A) = Follow(B)，无法根据follow集选择哪个产生式做归约，不是SLR文法
4.语义分析(Semantic Analysis)
4.1 概述
主要任务：
- 类型检查(Type Checking)：确保在操作符、函数调用、赋值等操作中，操作数和返回值的类型是兼容的。例如，在赋值语句中，左侧变量的类型必须与右侧表达式的类型匹配
- 作用域检查(Scope Checking)：确保变量和函数在声明的作用域内使用，避免引用未生命的变量或超出作用域的变量
- 符号表管理(Symbol Table Management)：建立和维护符号表，记录每个标识符的信息，包括其类型、作用域、存储位置等
- 名称解析(Name Resolution)：将标识符的引用与其声明相匹配，确保每个标识符在使用时已经被正确声明
- 类型推断(Type Inference)：对未明确标注类型的表达式或变量进行类型推断。例如，函数参数或返回值类型的推断
- 一致性检查(Consistency Checking)：确保函数调用的参数个数和类型与函数声明一致，确保数据下标是整数类型等
实现方法：语义分析通常是在抽象语法树(AST)上进行，通过遍历AST节点并结合符号表来完成各种语义检查。常用方法包括：
- 遍历AST：使用递归或迭代的方法遍历AST的每个节点，对每个节点进行相应的语义检查
- 构建和维护符号表：在遍历过程中，根据声明和作用域信息构建和更新符号表。在遇到变量或函数引用时，从符号表中找到相应的声明
- 类型检查和推断：对表达式节点进行类型检查和推断，确保操作数和返回值的类型一致性
4.2 属性文法(Attribute Grammer)
属性文法是在语法规则的基础上，为语法符号附加属性并定义这些属性的计算方式。属性可以用来表示语义信息，例如类型、值、作用域等
核心思想：通过在上下文无关文法的基础上，增加属性和相关的计算规则来传递语义信息。
组成：属性语法由语法规则和附加的语义规则组成，通常以语法制导定义(Syntax-Directed Definition, SDD)来描述
属性类别：
- 综合属性(Synthesized Attributes)：综合属性是从子节点的属性计算得到的，通常在语法树的自底向上遍历过程中进行计算。综合属性用于从子节点传递信息到父节点。
- 继承属性(Inherited Attributes)：继承属性是从父节点或兄弟节点的属性计算得到的，通常在语法树的自顶向下或横向遍历过程中进行计算。继承属性是用于从父节点或兄弟节点传递信息到子节点
属性文法的应用：在语义分析阶段
- 类型检查：通过传递和计算类型属性，确保操作数和运算符之间类型的兼容性
- 类型推断：在缺少显式类型标注时，通过属性传递和推断计算处表达式或变量的类型
- 符号表管理：在语法树中传递和维护变量、函数等的作用域和类型信息
4.3 语法制导定义(Syntax-Directed Definition)
SSD是编译原理中的一种技术，用于将语法规则与语义动作结合起来，以描述如何计算与语法结构相关的属性。SDD通过在上下文无关文法的基础上，增加属性和相关的计算规则来传递语义信息。
组成部分：
- 上下文无关文法(CFG)：描述程序语言的语法结构
- 属性和语义规则：每个语法符号都关联有属性，并为每个产生式定义计算这些属性的语义规则
S-属性语法：是一类属性文法。
- 特点：
- 仅包含综合属性(Synthesized Attributes)
- 属性值的计算从子节点传递到父节点
- 应用：适合用于自底向上的语法分析器，如LR分析器，许多实际编译器生成工具（如Yacc和Bison）使用S-属性语法来生成分析器
L-属性语法：是一类属性文法
- 特点：
- 包含综合属性和继承属性
- 继承属性只能依赖于该节点的左侧兄弟节点或父节点的属性
- 应用：由于其灵活性，适用于自顶向下的语法分析器，如递归下降分析器。这种属性语法适用于需要继承属性的情况，例如在声明和作用域处理中
依赖图(Dependency Graph)：是一种有向图，用于表示SDD中属性之间的依赖关系。
- 在依赖图中：
- 节点：表示语法树中的语法符号及其属性
- 有向边：表示属性之间的依赖关系，即一个属性的值依赖于另一个属性的值
- 构建依赖图：
- 节点表示：每个语法符号的每个属性在依赖图中有一个对应的节点
- 边表示：如果属性’a’的值依赖于属性’b’的值，则在依赖图中从’b’到’a’有一条有向边（b -------> a，a依赖于b，b传递属性给a）
属性的评估(Attribute Evaluation)：属性评估是根据依赖图的拓扑排序计算属性值的过程，主要分为以下两种方法：
- 自顶向下评估：
- 适用于L-属性文法
- 从根节点开始，按照依赖图顺序计算属性值
- 自底向上评估：
- 适用于S-属性文法
- 从叶子节点开始，按照依赖顺序计算属性值
拓扑排序：
- 是一种线性排序，使得对于途中每一条有向边(u, v)，顶点u在顶点v之前
- 通过拓扑排序，可以确保在计算一个属性的值时，所有依赖的属性都已被计算
带注释的解析树(Annotated Parse Tree)：是语义分析过程中使用的一种数据结构，不仅表示程序语法结构，还包含了与语法符号相关的语义信息（如类型、值等）。这种解析树通过在每个节点上附加属性和对应的值，来实现语法和语义相结合。
- 语法分析阶段：使用CFG生成解析树，表示程序的语法结构
- 属性计算：根据SDD计算每个节点的属性值（画依赖图）
- 注释节点：在解析树的每个节点上附加计算好的属性值，生成带注释的解析树
4.4 其他
类型检查(Type Checking)：是语义分析阶段的关键任务之一，用于确保程序中所有操作数和操作符类型的正确性。类型检查通过对表达式、变量、函数调用等进行类型验证，防止类型错误。过程：
- 符号表构建：在词法分析和语法分析阶段，构建符号表，记录所有变量和函数的类型信息
- 类型属性传递：通过属性文法将类型信息传递到各个节点
- 类型规则验证：使用类型规则检查操作数和操作符的类型一致性
S-属性语法优点：
- 简化属性计算：由于只包含综合属性，属性值的计算和传递机制简单明了，从子节点到父节点的传递过程使得计算顺序自然，有助于避免循环依赖和复杂的属性传递
- 与LR分析兼容：S-属性语法非常适合LR分析器，LR分析器是自底向上的分析方法，符合S-属性语法的属性传递方向。使用S-属性语法可以轻松继承语法分析和属性计算，增强编译器效率
- 实用性强
L-属性语法优点：
- 灵活性：允许继承属性的存在，使得属性计算更加灵活。继承属性可以从父节点或左侧兄弟节点传递信息到子节点，满足更多语义分析需求，如作用域管理、类型检查等
- 与递归下降分析兼容：L-属性语法非常适合递归下降分析器，递归下降分析是自顶向下的分析方法，符合L-属性语法的属性传递方向。
- 支持复杂的语义规则：如上下文敏感的语法和语义检查
4.5 例题
表达式： (3 + 4) * (5 + 6) n
SDD：
| Productions | Semantic rules |
|---|---|
| 1) L -> En | L.val = E.val |
| 2) E -> E1 + T | E.val = E1.val + T.val |
| 3) E -> T | E.val = T.val |
| 4) T -> T1 * F | T.val = T1.val * F.val |
| 5) T -> F | T.val = F.val |
| 6) F -> (E) | F.val = E.val |
| 7) F -> digit | F.val = digit.lexval |
依赖图 ：（注意是虚线，syntax tree是实线的）
注释解析树：
5.Intermediate Code Generation(中间代码生成)
5.1 概述
中间代码生成的目的是在源代码和目标机器代码之间生成一种独立于特定机器的中间表示(IR)，这种表示便于进一步的优化和目标代码生成
为什么需要中间代码：
- 简化编译过程：将编译过程分解为多个阶段，便于处理和调试
- 提高编译器的可移植性：通过生成独立于具体机器的中间代码，可以更容易地为不同目标机器生成代码
- 便于优化：中间代码提供了一种抽象表示，便于应用各种优化技术，提高代码的性能
中间代码生成步骤：
- 遍历语法树：自顶向下或自底向上遍历语法树，根据语法节点生成相应的中间代码
- 表达式求值：对每个表达式节点生成中间节点指令，处理算术运算、逻辑运算等
- 控制流处理：处理条件分支、循环结构等控制流语句，生成跳转和条件跳转指令
- 临时变量管理：使用临时变量保存中间计算结果，确保中间代码的正确性和可读性
中间代码优化：在生成中间代码后，可以应用多种优化技术，如：
- 常量折叠：将编译时已知的常量表达式直接计算出结果，例如：‘x=3+5’优化为’x=8’
- 复制传播：消除不必要的复制操作，例如：‘y=x’, ‘z=y+1’优化为’z=x+1’
- 死代码消除：移除不会影响程序结果的代码，例如：'int x = 10; … ;'如果’x’没有被使用，可以将其移除
- 循环优化：包括循环不变代码外提、循环展开等，例如，将循环中不变的计算移到循环外
5.2 中间表示(IR)
IR是编译过程中使用的中间表现形式，像语法树（解析树）也算是一种IR
常见的中间代码中的IR：
- 三地址代码(Three-Address Code, TAC)：每条指令包含最多三个操作数（通常是两个操作数和一个结果），示例：‘t1=a+b’, ‘t2=t1*c’
- 静态单赋值形式(Static Single Assignment, SSA)：每个变量在代码中只被赋值一次，通过版本号区分不同的赋值，示例：‘a1=5’, ‘a2=a1+3’
- 四元式(Quadruple)：每条指令由四个部分组成：操作符、结果、操作数1、操作数2。示例：‘(+, t1, a, b)’, ‘(*, t2, t1, c)’
- 三元式(Triple)：每条指令由三个部分组成：操作符、操作数1、操作数2，结果通过位置引用。示例：‘(+,a, b)’, ‘(*, #0, c)’，其中’#0’引用第一条指令的结果
5.3 语法制导翻译(Syntax-Directed Translation, SDT)
语法制导翻译是一种通过在语法树节点上附加语义规则来生成中间代码的技术。SDT结合了语法分析（抽象语法树）和语义分析（SDD定义了每个文法符号的属性和计算这些属性的规则），用于将源代码翻译为中间代码。
基本概念：
-
在代码生成中使用的函数：newlabel()，每次调用时返回一个新标签
-
在代码生成中使用的属性：
- E.true(E.false)：当E是true或false时控制流向的标签
- S.next：是在S的代码之后执行的地址指令的标签
- S.beign：是附在S的代码生成的第一条指令上的标签
if E then S1：
语义规则(Semantic Rules)：
- E.true = newlabel()
- E.false = S.next
- S1.next = S.next
- S.code = E.code ++ Label E.true ++ S1.code
if E then S1 else S2：
语义规则：
- E.true = newlabel; E.false = newlabel
- S1.next = S.next; S2.next = S.next
- S.code E.code ++ Lable E.true ++ S1. code ++ goto S.next ++ Label E.false ++ S2.code
while E do S1：
语义规则：
- S.begin = newlabel;
- E.true = newlabel;
- E.false = S.next;
- S1.next = S.begin
- S.code = Label S.begin ++ E.code ++ Label E.true ++ S1.code ++ goto S.begin
E -> E1 or E2：
如果E1是true，那E一定是true，所以E1.true = E.true
如果E1为假，那么E2就必须执行，所以E.false是E2代码的第一个语句
由图可得语义规则：
- E1.true = E.true;
- E1.false = newlabel;
- E2.true = E.true;
- E2.false = E.false
- E.code = E1.code ++ Label E1.false ++ E2.code
E -> E1 and E2：
语义规则：
- E1.true = newlabel
- E1.false = E.false
- E2.true = E.true;
- E2.false = E.false
- E.code = E1.code ++ Label E1.true ++ E2.code
E -> not E1：
语义规则：
- E1.true = E.false
- E1.flase = E.true
- E.code = E1.code
例题1：
例题2：
5.4 例题
给出下面代码的三地址码：
for (i = 0;i < 10; i++)
x = x + 1;
答案：
