国家精品课程
——
4
《编译原理》
1 绪论——计算机语言的发展
机器语言(Machine Language)与汇编语言
(Assemble Language) 高级语言(High Level Language)

强制式语言(Imperative Language) 函数(应用)式语言(Functional Language) 逻辑式(基于规则)语言(Logical Language) 面向对象语言(Object-Oriented Language)

33
I0 : S’→.S S→.L=R S→.R L→.*R L→.id R→.L
S
I1 : S’→S. I2 : S→L.=R R→L.R R→.L L→.*R L→.id
I9 : R S→L=R.

国家精品课程
——
19
《编译原理》
4 自顶向下语法分析
LL(1)文法
A→α1|α2|…|αn FIRST(αi)∩FIRST(αj)=Φ i≠j 当ε∈FIRST(αj)时，FOLLOW(A)∩FIRST(αi)=Φ
求FIRST(α)的算法
α=X1 X2…Xn

国家精品课程
——
3
《编译原理》
“编译原理”是一门非常好的课程
掌握“编译原理”中的基本概念、基本理论、基 本方法，在系统级上再认识程序和算法，提升计算 机问题求解的水平，增强系统能力，体验实现自动 计算的乐趣 实验情况
递归子程序、LL(1)、SLR(1)、LR(1) 多种形式的输入 LR(1)分析表的自动生成 错误处理与续编译
方法
算符优先分析法 LR分析法

国家精品课程
——
26
《编译原理》
分析器结构
输入缓冲区 id + id ＊ id # 输出产生 式序列
＋
Ｅ 栈

移进归约 控制程序
分析表
#
4种操作：移进、归约、接受、出错 栈内容 ♁ 输入缓冲区内容＝#“当前句型”# ？？LL(1)分析法
LL(1)分析 器系统结构
栈
控制程序 P 77
输出的 产生式 序列
预测分析表M
LL(1)通用控制算法 预测分析表的构造算法

国家精品课程
——
《编译原理》
表达式文法的预测分析表
E→TE'
语法 变量 E E' T T' F
→id
→FT'
E' →+TE' |ε
T→FT'

国家精品课程
——
8
《编译原理》
Ｔ 形图
表示语言翻译的 Ｔ 形图
源语言 目标语言
表示语言
功能
1) 交叉编译/移植：用A机的C编译构造B机的C编译 2) 本机编译器利用：用A机的C编译构造A机的B编译
3) 自展技术

国家精品课程
——
9
《编译原理》
If a与b无优先关系 then 出错

国家精品课程
——
28
《编译原理》
算符优先分析法
算符文法（不含形如 A→αBCβ 的产生式） 算符优先级
栈内栈外、优先函数
算符优先文法
素短语和最左素短语 句型#N1a1 N2a2… Nnan #的最左素短语是满足下列条 件的最左子串 Niai Ni+1ai+1… Njaj Nj+1 其中：ai-1≮ai≡ai+1≡…≡aj-1≡aj≯aj+1
候选式： α→β1|β2|…|βn
推导（派生） ：αＡβαγβ Ａ→γ∈ P
αβ； αnβ；α*β； α+β
句型：S *α α∈(ＶT∪ＶN)* 句子：S * x， x∈ＶT*

国家精品课程
——
11
《编译原理》
2 文法与语言
最左(Left-most)推导——最左分析
23
+
E T ＊ Ｔ
E→T(+T)*
简化的语法图
T→F(*F)*
Ｆ
Ｆ
（
Ｅ
）
F→(E)|id
id
国家精品课程
——
24
《编译原理》
简单算术表达式的分析器
Ｅ的子程序(E→T(+T)*) procedure E; begin T; while lookhead='+' do begin match(‘+’); T end end;
Ｔ的过程调用 lookhead：当前符号 当前符号等于＋时 处理终结符＋ Ｔ的过程调用

国家精品课程
——
25
《编译原理》
5 自底向上语法分析
思想
从输入串出发，反复利用产生式进行归约，如果最 后能得到文法的开始符号，则输入串是句子，否则 输入串有语法错误
核心
寻找句型中的当前归约对象——“句柄”进行归约, 用不同的方法寻找句柄，就可获得不同的分析方法

国家精品课程
——
17
《编译原理》
3 词法分析
RG
FA
A→a
A
a
B
A→aB
正规定义式FA
A→rs*
A
a s
词法分析器的实现
按状态转移图设计主程序 设计适当的子程序 A r

国家精品课程
——
18
《编译原理》
4 自顶向下语法分析
T→T* F|F
F→( E )| id

15
2 文法与语言
0型文法 (PSG) 1型文法 (CSG) 2型文法 (CFG) 3型文法 (RG) 3型文法 (RG)
SaBC
SaBC
E→E+E
S→a|b S→aT|bT T→a|b T→1|2 T→aT|bT T→1T|2T
状态
0 1 2 3 4 5 6
动作表 action a b # s3 s4 acc s3 s4 s3 s4 r3 r3 r3 r1 r1 r1 r2 r2 r2
转移表 goto S B 1 2
5 6

国家精品课程
——
32
《编译原理》
LR 分析表的构造
拓广文法——给出分析开始和结束状态

国家精品课程
——
27
《编译原理》
算符优先分析法
根据当前输入符号a与栈顶符号b的优先 级确定动作：
if b≮a then 移进——归约对象未形成
if b≡a then 移进——归约对象未形成
if b≯a then 归约——归约对象已形成
if a=b=# then 接受——分析成功

国家精品课程
——
29
《编译原理》
LR 分析法
关键概念
规范句型活前缀——规范句型（右句型）的不 含句柄右边任何符号的前缀
句柄形成情况的表示——LR(0)项目：
A→α.β 移进项目： A→α.aβ
待约项目： A→α.Bβ
归约项目： A→α.

G=(VN ∪ {S’}, VT, P ∪{S’→S}, S’) S’V 对应S’→.S（分析开始）和S’→S.（分析成功）
识别CFG G的拓广文法的所有规范句型活前缀的 DFA
以项目集{S’→.S }的闭包为启动状态 分析器的状态——某个项目集闭包 后继项目
项目集规范族——DFA的全部状态
T' →*FT' |ε
F→(E)|id
终极符号
id
→TE' →+TE' →FT'
+
*
(
→TE'
)
#
→ε
→ε
→ε
→*FT' →(E)
→ε
→ε

21
国家精品课程
——
22
《编译原理》
4 自顶向下语法分析
语法图
简化语法图
递归子程序法
为每个语法变量编写一个处理子程序

S→a|b S→Ha|Hb S→H1|H2 H→Ha|Hb
SaSBC SaSBC E→E*E CBBC CBBC E→(E) aBab aBd E→id bBbb bBbb E→E-E bCbc bCb cC cc
H→H1|H2
H→a|b
15
cC cc
E→E/E
文法的Chomsky体系
1
总 结
国家精品课程
——
2
《编译原理》
“编译原理”是一门非常好的课程
Alfred V.Aho：编写编译器的原理和技术具有十 分普遍的意义，以至于在每个计算机科学家的研 究生涯中，本书中的原理和技术都会反复用到 “自顶向下”和“自底向上”的系统设计方法（ 思想、方法、实现全方位讨论） 一些具体的表示和变换算法 一个相当规模的系统的设计（含总体结构）
2 文法与语言
字母表∑ ：非空有穷集合 字母表的乘积： ∑1∑2={ab|a∈∑1，b∈∑2}
∑*、∑+
x∈∑*, L ∑*, x∈ L
ε语句

国家精品课程
——
10
《编译原理》
2 文法与语言
文法：Ｇ = (ＶT，ＶN，Ｐ，Ｓ)
α→β ∈P
BNF： ∷＝,[ ],{ }lu,{ }m
E E E * E id3 id1 id2

E E id1 + E id2
* E
E
E
+
id3
国家精品课程