编译原理目录
1、词法分析
2、语法分析（重点）
3、语法制导翻译与抽象语法树
4、语义分析
5、代码生成
6、中间代码与程序分析
7、代码优化
1、词法分析器
词法分析的任务： 源程序字符流 => 词法分析器 => 记号流
1.1 基本概念
示例：
记号的数据结构定义
enum kind {
IF, LPAREN,
ID, INTLIT,
…
};
struct token{
enum kind k;
char *lexeme;
};词法分析器的任务：
字符流到记号流
- 字符流：和被编译的语言密切相关 (ASCII, Unicode, or …)
- 记号流：编译器内部定义的数据结构，编码所识别出的词法单元。
词法分析器的实现方法
手工编码实现法
- 相对复杂、且容易出错
- 但是目前非常流行的实现方法
- GCC, LLVM, …
词法分析器的生成器
- 可快速原型、代码量较少
- 但较难控制细节
转移图
转移图算法
token nextToken ()
c = getChar ();
switch (c)
case ‘<’: c = getChar ();
switch (c)
case ‘=’: return LE;
case ‘>’: return NE;
default: rollback(); return LT;
case ‘=’: return EQ;
case ‘>’: c = nextChar ();
switch (c): ...// similar识别关键字
关键字表算法
- 对给定语言中所有的关键字，构造关键字构成的哈希表H
- 对所有的标识符和关键字，先统一按标识符的转移图进行识别
- 识别完成后，进一步查表H看是否是关键字
- 通过合理的构造哈希表H(完美哈希)，可以O(1)时间完成
1.2 正则表达式(RE)
声明式规范 => 自动生成工具生成 => 词法分析器
对给定的字符集 $\sum ={c1, c2, … , cn}$，归纳定义：
- 空串ε是正则表达式
- 对于任意$c \in \sum$， c是正则表达式
如果M和N是正则表达式, 则以下也是正则表达式
- 选择：$M | N = \{M, N\}$
- 连接：$MN = \{mn| m\in M, n\in N\}$
- 闭包：$M* = \{ε, M, MM, MMM, … \}$
正则表达式的形式表示
e -> ε
| c
| e | e
| e e
| e*语法糖
- $[c1-cn]$ == c1|c2|… |cn
- $e+$ == 一个或多个 e
- $e?$ == 零个或一个 e
- $a*$ == a* 自身, 不是a的Kleen闭包
- $e\{i, j\}$ == i到j个e的连接
.== 除‘ n’外的任意字符
1.3 有限状态自动机(FA)
输入函数 -> FA -> {Yes, No}
M = (\sum, S, q0, F, \delta)
确定状态有限自动机DFA
- 对任意的字符，最多有一个状态可以转移
- $\delta：S × \sum → S $
非确定的有限状态自动机NFA
- 对任意的字符，有多于一个状态可以转移
- $\delta：S × (\sum \cup \epsilon) → \weierp(S) $
1.4 RE → NFA (Thompson算法)
RE -> Thompson算法 => NFA -> 子集构造算法 => DFA -> Hopcroft最小化算法 => 词法分析器代码
基于对RE的结构做归纳
- 对基本的RE直接构造
- 对复合的RE递归构造
- 递归算法，容易实现
示例: $a(b|c)*$
1.4 NFA → DFA (子集构造算法)
示例：
求出$ε-closure(s)$，$ε-closure(s)$表示由状态s经由条件ε可以到达的所有状态的集合
ε-closure(n0) = {n0}
ε-closure(n1) = {n1,n2,n3,n4,n6,n9}
ε-closure(n2) = {n2,n3,n4,n6,n9}
ε-closure(n3) = {n3,n4,n6}
ε-closure(n4) = {n4}
ε-closure(n5) = {n3,n4,n5,n6,n8,n9}
ε-closure(n6) = {n6}
ε-closure(n7) = {n3,n4,n6,n7,n8,n9}
ε-closure(n8) = {n3,n4,n6,n8,n9}
ε-closure(n9) = {n9}首先将初始态的转换闭包ε-closure(0)设为状态A，即A={0}，接着写出状态A经过上面转换图中所有转换条件得到的状态，后继状态里面不包括自身，这里的转换条件包括a和b和c。
ε-closure(0) = A
ε-closure(move(A,a)) = ε-closure({n1}) = {n1,n2,n3,n4,n6,n9} = B
ε-closure(move(A,b)) = ε-closure({})
ε-closure(move(A,c)) = ε-closure({})
ε-closure(move(B,a)) = ε-closure({})
ε-closure(move(B,b)) = ε-closure({n5}) = {n3,n4,n5,n6,n8,n9} = C
ε-closure(move(B,c)) = ε-closure({n7}) = {n3,n4,n6,n7,n8,n9} = D
ε-closure(move(C,a)) = ε-closure({}) =
ε-closure(move(C,b)) = ε-closure({n5}) = {n3,n4,n5,n6,n8,n9}
ε-closure(move(C,c)) = ε-closure({n7}) = {n3,n4,n6,n7,n8,n9}
子集构造算法
q0 <- eps_closure (n0)
Q <- {q0}
workList <- q0
while (workList != [])
remove q from workList
foreach (character c)
t <- e-closure (delta (q, c))
D[q, c] <- t
if (t\not\in Q)
add t to Q and workListε-闭包的计算：深度优先
/* ε-closure: 基于深度优先遍历的算法 */
set closure = {};
void eps_closure (x)
closure += {x}
foreach (y: x--ε--> y)
if (!visited(y))
eps_closure (y)ε-闭包的计算：宽度优先
/* ε-closure: 基于宽度优先的算法 */
set closure = {};
Q = []; // queue
void eps_closure (x) =
Q = [x];
while (Q not empty)
q <- deQueue (Q)
closure += q
foreach (y: q--ε--> y)
if (!visited(y))
enQueue (Q, y)1.5 DFA的最小化 (Hopcroft算法)
1.5.1 消除多余状态
什么是多余状态
- 从这个状态出发没有通路到达终态
- 从开始状态出发，任何输入串也不能到达的那个状态
例如：
1.5.2 等价状态
等价状态：对于两个状态s和t
- 一致性条件：状态s和t必须同时为终态或非终态
- 蔓延性条件：对于所有输入符号，状态s和状态t必须转化到等价的状态里
示例1：
示例2：
Hopcroft算法：
// 基于等价类的思想
split(S)
foreach (character c)
if (c can split S)
split S into T1, …, Tk
hopcroft ()
split all nodes into N, A
while (set is still changes)
split(S)1.6 DFA的代码表示
- 概念上讲, DFA是一个有向图。
- 实际上，有不同的DFA的代码表示：转移表 (类似于邻接矩阵)、哈希表、跳转表。。。
- 取决于在实际实现中，对时间空间的权衡。
1.6.1 转移表
驱动代码
nextToken()
state = 0
stack = []
while (state!=ERROR)
c = getChar()
if (state is ACCEPT)
clear(stack)
push(state)
state = table[state][c]
while(state is not ACCEPT)
state = pop();
rollback();1.6.2 跳转表
nextToken()
state = 0
stack = []
goto q0
q0:
c = getChar()
if (state is ACCEPT)
clear (stack)
push (state)
if (c==‘a’)
goto q1:
q1:
c = getChar()
if (state is ACCEPT)
clear (stack)
push (state)
if (c==‘b’||c==‘c’)
goto q1NFA→右线性文法
定理：设NFA: $M=(Q, \Sigma, \delta, q_0, F, )$，那么存在一个右线性文法$G_1$使得$L(G_1) = L(M)$，也存在一个左线性文法$G_2$，使得$L(G_2) = L(M)$
给定NFA： $M=(\Sigma, S, q_0, F, \delta)$
构造右线性文法：$G=(Q, \Sigma, P, q_0)$
- $q→ap$ 如果(q,a)→p
- $q→a$ 如果(q,a)→p且p∈F
- $q_0 →ε$ 如果 $q_0$ 是终结状态。
DFA: $M=(Q, \Sigma, \delta, s, F, )$