编译原理学习过程中的笔记和一些小思考。
2. 第一单元： 编译器介绍
Overview
|---源---|-----------------前端-----------------|----后端----|
**源程序** --> **词法分析器** --> *记号流*
--> **语法分析器** --> *抽象语法树*
--> **语义分析器** -----------------> *中间表示*
3. 第三单元：词法分析
3.1 [XC]Overview
RE -1.Thompson算法-> NFA -2.子集构造算法-> DFA -3.Hopcroft最小化算法 -> 词法分析器代码
3.2 子集构造算法
[XC] 子集构造算法作用 TODO
q0 <- eps_closure(n0) // 计算起始点的闭包，确定DFA的起始节点的边界
Q <- {q0}
workList <- q0 // worklist可以使用队列实现
while (workList != [])
remove q from workList
foreach (character c)
t <- eps_closure(delta(q, c))
D[q, c] <- t
if (t not in Q)
add t to Q and workList
3.3 DFA的最小化
在将NFA转换为DFA时，有不止一种表达形式，而DFA的最小化目的在于求出最小的等价DFA形式。
Hopcroft算法
[XC] Hopcroft算法思路 TODO
// 基于等价类的思想
split(S) // S为状态的集合，对其进行切分
foreach (character c) // c如果为ASCII的话循环256次
if (c can split S) // 在S用c进行处理后，可以切分成多个子集
split S into T1, ..., Tk
hopcroft()
split all nodes into N, A // 最开始，N为非接受状态，A为接受状态
while (set is still changes)
split(S)
3.3 DFA的代码表示
DFA的代码表示
- 概念上讲，DFA是一个有向图
- 实际上，有不同的DFA的代码表示。如转移表（类似邻接矩阵）、哈希表、跳转表
- 取决于在实际实践中，对时间和空间的权衡
(1) 转移表
转移表示例如下，如此表达后可以在编码时利用二维数组来表达这个表。状态，即列数根据状态图可以确定，有多少个状态。而字符的可能性由编码确定，如果是ASCII码，则有256种可能性。
Chart:
| 状态\字符 | a | b | c |
|---|---|---|---|
| 0 | 1 | ||
| 1 (ACCEPT) | 1 | 1 |
Code:
char table[M][N]
table[0]['a'] = 1;
table[1]['b'] = 1;
table[1]['c'] = 1;
// other table entries are ERROR, like -1
有了转移表之后，可以转换到词法分析驱动代码： 转移表 <=> 词法分析驱动代码
Code:
nextToken()
state = 0 // 当前自动机中目前走到的状态，此处初始状态为0
stack = [] // 初始化为空，目的是为了实现最长匹配，在识别标识符时很有效
while (state != ERROR)
c = getChar()
if (state is ACCEPT
clear(stack)
stack.push(state)
state = table[state][c]
while (state is not ACCEPT) // 在匹配完成后往前走，但匹配不了，则回滚到最近的接受状态
state = stack.pop()
rollback() // 将读入的无法匹配的值扔回字符串
(2) 跳转表(jump table)
思路：跳转表拓扑结构与自动机拓扑结构相同，跳转表把每个状态变成一段代码，把状态直接边的转移变成一个显式的跳转，每个代码段负责识别当前状态上所能识别的所有字符和转换
Code:
nextToken()
state = 0
stack = []
goto q0
q0:
c = getChar()
if (state is ACCEPT)
clear(stack)
stack.push(state)
if (c == 'a')
goto q1
q1:
c = getChar()
if (state is ACCEPT)
clear(stack)
stack.push(state)
if (c == 'b' || c == 'c')
goto q1
跳转表优点： 不需要维护巨大的状态表，如果字符为Unicode，转移表会有上万个列，会占很大空间，flex采用跳转表。 需要根据实际使用场景确定采用哪种算法更优。
4. 第四单元： 语法分析I
Overview
4.1 语法分析的任务
- 早期语法分析器：分析源程序语言是否合法。
- 后期语法分析器：生成抽象语法树（后端核心数据结构），交给语义分析器等进行更为复杂的处理。
- 总的工作：INPUT-记号流 –> 语法分析器 –> OUTPUT-抽象语法树
- 实际上输入除了记号流（句子s）之外，还有一个输入就是 语言的语法规则（即后面会提到的语法规则G），取决于我们编译器为哪门语言而写。可以理解为一个输入是文章，另一个是判断文章是否合法的字典。
- 语法分析器的工作就是回答输入的记号流能否由语法规则G产生，回答一个yes/no的问题，如果可以，生成相应的语法树。
路线图：
- 数学理论：上下文无关问法(CFG)
- 描述语言语法规则的数学工具
- 自顶向下分析算法
- 递归下向分析算法（预测分析算法）
- LL分析算法
- 自底向上分析算法
- LR分析算法
4.2 上下文无关文法与推导
历史背景：乔姆斯基文法体系
- 乔姆斯基为研究自然语言构造的一系列数学工具，目前已经应用到研究计算机语言中
- 给出了从0到3的四种文法
- 3型文法：正则文法（可以用来描述语言的词法结构）
- 2型文法：上下文无关文法（可以用来描述语言的语法结构）
- 1型文法：上下文有关文法(计算机领域未广泛运用)
- 0型文法：任意文法(计算机领域未广泛运用)
- 3型 -> 2型 -> 1型 -> 0型，前一个为后一个的子集，越往后表达能力越强
示例：
- 自然语言中的句子典型结构：
- 主语 谓语 宾语
- 名词 动词 名词
- 例子：
- 名词：{羊、老虎、草、水}
- 动词：{吃、喝}
- 句子：
- 羊吃草、羊喝水、羊吃老虎、老虎吃羊…
- 符合语法规则，但有些并不合逻辑
形式化：
- 符号：
- 非终结符：{S, V, N}
- 终结符号：{s, t, g, w, e, d}
- 开始符号：{S}
- 非终结符一般使用大写，终结符一般使用小写，从而可以简化表达形式
-
上述句型的形式化表达：
S -> N V N // 名词 动词 名次，如羊吃草 N -> s | t | g | w V -> e | d
上下文无关文法的数学定义
（从例子中抽象，不要过于纠结于形式化的内容）
上下文无关文法G是一个四元组：
G = (T, N, P, S)
- T：终结符集合
- N：非终结符集合
- P：产生式规则的集合，每条规则的形式都是：非终结符->终结符/非终结符
- S：唯一的开始符号
在此定义上述例子：
G = (N, T, P, S)
N = {S, N, V}
T = {s, t, g, w, e, d}
S = S
P = {
S -> N V N
N -> s
| t
| g
| w
V -> e
| d
}
若以算术表达式为例：
G = (N, T, P, S)
N = {E}
T = {num, id, +, \*}
S = E
P = {
E -> num
E -> id
E -> E + E
E -> E * E
}
注：很多情况下我们看到的是BNF范式，要求非终结符放到一对尖括号中，终结符要加上下划线， 从而区分终结符和非终结符
推导
- 给定文法G，从G的开始符号S开始，用产生式的右部替换左侧的非终结符
- 此过程不断重复，直到不出现非终结符为止
- 最终的串称为句子
最左推导和最右推导
- 最左推导：每次总是选择最左侧的符号进行替换
- 最右推导：每次总是选择最右侧的符号进行替换
语法分析：
给定文法G和句子s，语法分析要回答的问题：是否存在对句子s的推导。
4.3 分析树和二义性文法
分析树
- 推导可以表达成树状结构，和推导所用的顺序无关（最左、最右、其他）
- 特点：
- 树中的每个 内部节点 代表非终结符
- 每个 叶子节点 代表终结符
- 每一步 推导 代表如何从双亲节点生成它的直接孩子节点
-
例子： E -> num | id | E + E | E * E 分析 3 + 4 * 5
// 最左推导，先算加法 E -> E + E -> 3 + E -> 3 + E * E -> 3 + 4 * E -> 3 + 4 * 5 // 另一种最左推导，先算乘法，有问题 E -> E * E -> E + E * E -> 3 + E * E -> 3 + 4 * E -> 3 + 4 * 5 - 上述文法G存在一定问题：存在歧义（二义性）
二义性文法
- 给定文法G，如果存在句子s，它有两棵不同的分析树，那么称G是二义性文法
- 从编译器角度，二义性文法存在的问题：
- 同一个程序会有不同含义
- 因此程序运行的结果不是唯一的
- 解决方案：文法的重写
表达式文法的重写
E -> E + T // T: term, T + T + T + ...
| T
T -> T * F // F: factor, F + F + F + ...
| F
F -> num // atom
| id
推导：
E -> E + T // 左递归满足左结合
-> T + T
-> F + T
-> 3 + T
-> 3 + T * F
-> 3 + F * F
-> 3 + 4 * F
-> 3 + 4 * 5
4.4 自顶向下分析
自顶向下分析的算法思想
- 语法分析：给定文法G和句子s，回答s是否能够从G推导出来？
- 基本算法思想：从G的开始符号出发，随意推导出某个句子t，比较t和s
- 若t==s，则回答“是”
- 若t!=s，则继续推导(回溯)，遍历后看是否符合
- 因为这是从开始符号出发推出句子，因此称为自顶向下分析
- 对应于分析树自顶向下的构造顺序
- 因为可能需要遍历，是很昂贵的算法
算法伪代码描述
这个算法很深刻，用栈显式地实现了一个非递归版本的递归下降分析（非递归版本的树的遍历问题）
tokens[] // 句子s在词法分析后所有tokens
i = 0
stack = [S] // S是文法的开始符号
while (stack != [])
if (stack[top] is a terminal t)
if (t == tokens[i++])
pop();
else backtrack()
else if (stack[top] is a nonterminal T)
pop()
push(the next right hand side of T) // 从右向左开始压栈，其实是实现树的后序遍历
算法的讨论
- 算法需要用到回溯，给分析效率带来问题
- 而就这部分而言，编译器必须高效
- 实际上我们需要线性时间的算法
- 避免回溯
- 改进方法：递归下降分析算法 和 LL1分析算法
重新思考
- 避免回溯 -> 用前看符号避免回溯（偷看一眼输入串s，看开头符号是否有符合的）
- 但还是存在问题：
- 跟前看符号相同的匹配可能不止一个
- 匹配不符合仍需要回溯
4.5 递归下降分析算法
Overview
递归下降分析算法只是自顶向下分析的其中一类。
- 也称为预测分析
- 分析高效（线性时间）
- 容易实现（方便手工编码）
- 错误定位和诊断信息准确
- 被很多开源和商业的编译器采用：GCC4.0, LLVM(apple, google)
- 算法基本思想
- 每个非终结符构造一个分析函数（不一定严格对应）
- 用前看符号指导产生式规则的选择
- 使用了分治法的思想：divide and conquer
示例：
-
语法G:
S -> N V N N -> s | t | g | w V -> e | d -
句子s：g d w
-
代码：
parse_S() parse_N() parse_V() parse_N() parse_N() token = tokens[i++] if (token == s || token == t || token == g || token == w) return error("s, t, g, w expected, but only found $token") parse_V() token == tokens[i++] if (token == e || token == d) return
递归下降分析的一般算法框架
-
语法G:
x -> b11 ... b1i | b21 ... b2j | b31 ... b3k | ... -
代码
parse_X() token = nextToken() switch(token) case a1: b11 ... b1i case a2: b21 ... b2j case a3: b31 ... b3k default: error("...") -
重要问题：如果我们拿到了前看字符，如果有相同的起始字符，如何解决（case $a后有多种选择）
对算数表达式的递归下降分析
-
语法G:
E -> E + T | T T -> T * F | F F -> num -
代码:
// a first try parse_E() token = tokens[i++] if (token == num) ? parse_E(); parse_T() ? parse_T(); // 选用上述哪种不确定，还是需要回溯 else error("...") -
通过分析文法的具体特点，充分利用可以进行优化。如此例中，我们注意到E开始生成时， 会生成T+T+T+T+…的形式，即T(+T)(+T)(+T)…的形式，故而我们可以先匹配T。 同理，FFFF…我们也可以先匹配F，后匹配。 这样就避免了上述如何匹配的问题。在具体文法分析的时候可以进行具体的思考。
-
代码版本2：
// a second try parse_E() parse_T() token = tokens[i++] while (token == +) parse_T() token = token[i++] parse_T() parse_F() token = tokens[i++] while (token == *) parse_F() token = tokens[i++]
第五单元：语法分析II
- 语法分析器总的工作：INPUT-记号流 –> 语法分析器 –> OUTPUT-抽象语法树，结合输入的语法G来判断记号流是否符合语法。
- 我们可以手工来写语法分析器，如示例所示，也可以自动生成，类似词法分析器的自动生成。本节主要讨论语法分析器的自动生成。
- 数学所具备的强大抽象能力使得我们在严格定义好概念的情况下，让很多工作可以自动完成。
- 语法分析器例子：ANTLR, YACC, bison, SMLYACC
5.1 LL(1)分析算法（ANTLR)
Overview
- 从左（L）向右读入程序，最左（L）推导，采用一个（1）前看符号（辅助判断）
- 分析高效（线性时间）
- 错误定位和诊断信息准确
- 有很多开源或商业的生成工具，如ANTLR
- 算法基本思想：表驱动的分析算法
表驱动的LL分析器架构
**词法分析器** --记号--> **语法分析器** --树-->
| |
| |
分析栈 |
|
--语法-->语法分析器/自动生成器-->分析表
- 如上节分析，有时会出现符号不匹配的情况， 在使用分析栈时就需要进行回溯，会导致效率降低
- 分析表：何时字符需要输入分析栈，何时输出，指导分析栈的工作
回顾自顶向下分析算法
tokens[] // 句子s在词法分析后所有tokens
i = 0
stack = [S] // S是文法的开始符号
while (stack != [])
if (stack[top] is a terminal t)
if (t == tokens[i++])
pop();
else backtrack() --> error // 如果每次选择“正确”的右部，那么就不需要回溯了，要么匹配上，要么抛错
else if (stack[top] is a nonterminal T)
pop()
push(the next right hand side of T) // 从右向左开始压栈，其实是实现树的后序遍历
- 主要的问题在于最后一个next，目的在于遍历所有的可能。但不加选择地压入栈导致匹配不成功，只能回溯。因此我们需要压入“正确”的字符。
- 如果每次坚持压入“唯一可能正确的右部”，但仍然有错误，那么就可以直接抛错了
LL(1)分析表
-
语法G：
0: S -> N V N 1: N -> s 2: | t 3: | g 4: | w 5: V -> e 6: | d -
分析表：
| N\T | s | t | g | w | e | d |
|---|---|---|---|---|---|---|
| S | 0 | 0 | 0 | 0 | ||
| N | 1 | 2 | 3 | 4 | ||
| V | 5 | 6 |
N: 非终结符 T：终结符 数字：代表语法G的行号，从而指导应该压入什么元素进栈
First集
- 定义： FIRST(N) = 从非终结符N开始推导得出的句子开头的所有可能终结符的集合