编译原理目录
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 q1
NFA→右线性文法
定理:设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, )$