32
有效项目
编译原理
33
编译原理
34
示例
编译原理
35
初始项目 接收项目 规约项目
移进项目
36
编译原理
规约项目 待约项目
构造文法G’(S’)的LR(0)项目集规范族 Step1:
编译原理
37
Step2:
LR分析程序利用有穷自动机去识别给定文法的所有 规范句型的活前缀
LR(0)分析程序主要依靠LR(0)分析表进行动作 LR(0)分析表构造的思想和方法是构造其它LR分析
表的基础
LR(0)分析仅依据当前栈顶状态就能确定应执行何种 分析动作，无需向前察看任何输入符号
18
几个概念：前缀、活前缀
编译原理
9
编译原理
ACTION[si,aj]规定了栈顶状态为si时遇 到输入符号aj应执行的动作
GOTO[si,xj]规定了当栈顶状态si面临文 法符号xj时应到达的下一状态
10
动作有4种可能： ① 移进 ② 归约 ③ 接受 ④ 报错
11
编译原理
四种动作的解释
编译原理
① 移进：
– 把(si，a)的下一状态sj=GOTO[si，a]和输入符号a 移入栈。其中i，j表示状态号。
同一个文法采用的LR分析器不同时，分析表 将也不同，分析表又可分为动作表(ACTION) 和状态转换(GOTO)表两个部分，它们都可 用二维数组表示。
(3)先进后出分析栈，存有形如 s文 栈0x法 顶1s1符 ，x2号s…0是，xm初每sm始个的状s符i是态号一。串个，状其态中，每状个态xis是m位一于个
19
几个概念：LR(0)项目
编译原理
20
文法G的拓广文法G′
编译原理
若原文法G的开始符号为S，在G中加 产生式S′→S后得新的文法G′，则称G′ 为原文法G的拓广文法，而S′为拓广后 文法G′的开始符号
当用S′→S.进行规约时，整个分析工作 可视为正常结束
21
示例
文法G′[S′]为： S′→E E→aA|bB A→cA|d B→cB|d
a1
ak
$
zk
有限状态控制
zk-1
z0
7
LR分析器组成
编译原理
输入串 a1
分析栈
sm sm-1
. . .
s0
...
ai ...
驱动程序
action
goto
分析表
$ 输出
8
LR分析器组成
编译原理
一个LR分析器由3个部分组成 (1) 总控程序，也可以称为驱动程序。
对所有的LR分析器总控程序都是相同的。 (2) 分析表，不同的文法分析表将不同，
LR分析器的关键部分是分析表的构造
14
示例
编译原理
15
编译原理
16
LR(k)文法和LR(k)分析器 LR(0)分析表的构造 下一讲的内容
– SLR(1)分析表的构造 – LR(1)分析表的构造 – LALR(1)分析表的构造
编译原理
17
LR(0)简介
编译原理
LR(0)分析方法严格地执行最左规约，即每次规约都 是真正的句柄
④ 报错：
– 当遇到栈顶为某一状态下出现不该遇到的 文法符号时，则报错，说明输入串不是该 文法能接受的句子。
13
编译原理
LR分析器的总控算法
– 从初始构型(s0, a1a2…an$)开始，然后分析 器的任何一次移动都是根据栈顶状态sm和 当前输入符号ai去查ACTION表并执行 ACTION[sm,ai]规定的动作，直至执行到 “接收”动作或ERROR动作
5
LR(k)文法和LR(k)分析器 LR(0)分析表的构造 下一讲的内容
– SLR(1)分析表的构造 – LR(1)分析表的构造 – LALR(1)分析表的构造
编译原理
6
LR分析器是一个确定的PDA
编译原理
下推自动机(简称为PDA)是上下文无关文
法的识别器。一个下推自动机由一条
输入带, 一个有限控制器和一个后进先 出下推栈组成.
位置
有LR分析程序的产生器：YACC
3
编译原理
LR分析法能根据当前分析栈中的符号 串和向右顺序查看输入串的K个(K≥0) 符号就可唯一地确定分析器的动作是 移进还是归约和用哪个产生式归约， 能唯一地确定句柄.
LR分析法的归约过程是规范推导的逆 过程，所以LR分析过程是一种规范归 约过程.
4
本讲主要内容
编译原理
LR分析的基本思想
K≤1时LR分析器的基本构造原理和方法
– LR(0)分析器是在分析过程中不需向右查看输入 符号，因而它对文法的限制较大，然而它是构造 其它LR类分析器的基础
着重介绍LR(0)、SLR(1)、LALR(1)、LR(1) 四种分析器的构造方法（分两次介绍）
– SLR(1)和LALR(1)分是LR(0)和LR(1)的一种改 进
② 归约：
– 当在栈顶形成句柄为β时，则用β归约为相应的非 终结符A，即文法中有A→β的产生式. 若β的长度 为r(即|β|=r)，则从分析栈中自栈顶向下去掉2r个 符号。并把A和下一状态sj=GOTO[si，A]移进栈， 其中Si为修改指针后的栈顶状态。
12
编译原理
③ 接收：
– 当归约到分析栈中只剩文法的开始符号S 时，并且输入符号串已结束即当前输入符 是‘#’，则为分析成功。
编译原理
编译原理
主 讲：温 璞 责任教师：蒋慧平
1
编译原理
第七讲
LR(k)分析方法(I)
2
LR(k)分析法简介
编译原理
LR(K)分析方法是1965年Knuth提出 K表示向右查看输入串符号的个数 大多数用无二义性CFG描述的语言都可
以用相应的LR分析器进行识别 分析速度快，能准确即时地指出出错
22
CLOSURE(I)的构造
编译原理
23
编译原理
24
GOTO(I,X)函数
编译原理
25
示例
编译原理
26
LR(0)项目集规范族
编译原理
27
LR(0)项目集规范族求解算法
编译原理
28
文法（7-1）
编译原理
29
编译原理
30
编译原理
31
编译原理
该文法的LR(0)项目集规范族的goto函数定义了一 个确定的有穷自动机，它识别G的全部活前缀
该文法的项目有： 1． S′→·E 2． S′→E· 3． E→·aA 4． E→a·A 5． E→aA· 6． A→·cA 7． A→c·A 8． A→cA· 9． A→·d
编译原理
10. A→d· 11. E→·bB
12. E→b·B 13. E→bB· 14. B→·cB 15. B→c·B 16. B→cB· 17. B→·d 18. B→d·