第6章 ＬＲ分析程序及其自动构造 6.1 自下而上分析及其LR分析概述 6.2 LR (0) 分析 6.3 SLR(1) 分析

Presentation on theme: "第6章 ＬＲ分析程序及其自动构造 6.1 自下而上分析及其LR分析概述 6.2 LR (0) 分析 6.3 SLR(1) 分析"— Presentation transcript:

1 第6章 ＬＲ分析程序及其自动构造 6.1 自下而上分析及其LR分析概述 6.2 LR (0) 分析 6.3 SLR(1) 分析
6.5 LALR分析 6.6 使用二义文法

2 自下而上分析算法 能力强 构造复杂 最常用和最有效的模型----移进归约(动作）
自下而上分析算法 能力强 构造复杂 最常用和最有效的模型----移进归约(动作） 将输入分成两部分：未消化和半消化的 总控程序 output Input# … 栈 状态 文法符号 分析表 产生式表 Input#未消化 半消化的 总控程序 output 产生式表 分析表

3 S –> E E –> T | E + T T –> int | (E)
Reduce: 如能找到一产生式 A –> w 且栈中的内容是 qw (q 可能为空), 则可以将其归约为 qA.即倒过来用这个产生式. 如上例, 若栈中内容是 (int ，我们使用产生式 T–> int柄把栈中内容归约为(T Shift: 如不能执行一个归约且在未消化的输入中还有 token ，就把它从输入移到栈中. 如上例,假定栈中内容是 ( ,输入中还有 int+int)#.不能对( 执行一个归约，因为它不和任何产生式的右端匹配.所以把输入的第一个符号移到栈中,于是栈中内容是 (int ，而余留的输入是 +int)# .

4 Reduce的一个特殊情况：栈中的全部内容w归约为开始符号S （即施用 S –> w） ，且没有余留输入了，意味着已成功分析了整个输入串.
移进归约分析中还会出现一种情况，就是出错，比如当前的token不能构成一个合法句子的一部分，例如上面的文法，试分析 int+)时就会发生错误.

5 3 (int + int)# Reduce: T –> int 4 (T + int)# Reduce: E –> T
STACK REMAINING INPUT PARSER ACTION (int + int)# Shift 2 ( int + int)# Shift 3 (int int)# Reduce: T –> int 4 (T int)# Reduce: E –> T 5 (E int)# Shift 6 (E int)# Shift 7 (E + int )# Reduce: T –> int 8 (E + T )# Reduce: E –> E + T 9 (E )# Shift 10 (E) # Reduce: T –> (E) 11 T # Reduce: E –> T 12 E # Reduce: S –> E 13 S #

6 (E + T )# Reduce:E –> E + T
why?不用 E –> T (E ) # 若使用了E –> T，在栈中形成的(E+E不是规范句型的活前缀（viable prefixes） （E+E不能和任何产生式的右端匹配 （E+E）不是规范句型 活前缀 是规范句型（右句型）的前缀，但不超过句柄 移进归约分析的栈中出现的内容加上余留输入构成规范句型

7 规范推导 规范句型 规范归约 最右推导：在推导的任何一步αβ，其中α、β是句型，都是对α中的最右非终结符进行替换 最右推导被称为规范推导。
由规范推导所得的句型称为规范句型 G[S]： S→E E→E+T|T T→(E)|int SE T (E) (E+T) (E+int) (T+int) (int+int) 规范归约 假定α是G的一个句子，称序列αn ,αn-1 …,α0是 α的一个规范归约 如果该序列满足： （1） αn = α （2） α0为文法的开始符号 （3）对任何j,0<j<=n, αj-1是从αj经把句柄替换为相应产生式的左部而得到的

8 文法要求 shift-reduce or reduce-reduce 冲突（conflicts） 分析程序不能决定是shift 还是 reduce 或者分析程序归约时有多个产生式可选 例子 （ dangling else） ： S –> if E then S | if E then S else S 如输入if E then if E then S else S 分析某一时刻，栈的内容:if E then if E then S 而 else 是下一 token 归约还是移进？

9 特定的一种shift-reduce实现技术 ＬＲ分析
L R 最右推导 　分析器模型和分析算法 　ＬＲ　分析特征讨论

10 ＬＲ分析器模型 总控程序 output Input# S1 Xm … X1 S0 # 栈 ACTION GOTO LR分析表 产生式表 状态
文法符号 ACTION GOTO LR分析表 产生式表

11 ACTION GOTO a c e b d # S A B 0 S2 1 1 acc 2 S4 3 3 S5 S6
r r r r r r2 S r r r r r r3 S9 r r r r r r4 r r r r r r1

12 LR分析算法 置ip指向输入串w的第一个符号 令S为栈顶状态 a是ip指向的符号 重复 begin if ACTION[S,a]=Sj
then begin PUSH j,a(进栈) ip 前进(指向下一输入符号) end else if ACTION[S,a]=rj (第j条产生式为A)

13 ＬＲ分析程序 then begin pop || 项 令当前栈顶状态为S’ push GOTO[S’,A]和A(进栈) end
else if ACTION[s,a]=acc then return (成功） else error end.重复

14 ＬＲ分析程序 例: G[S]: S a A c B e [1] A b[2] A Ab[3] B d[4] w=abbcde#

15 Step states. Syms. The rest of input action goto
# abbcde# s2 #a bbcde# s4 #ab bcde# r2 goto(2,A) #aA s6 #aAb cde# r3 #aA s5 #aAc de# s8 #aAcd e# r4 #aAcB s9 #aAcBe # r1 #S acc

16 A A S B a b b c d e S  aAcBe aAcde aAbcde abbcde 符号串abbcde是否是G[S]的子
文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 步骤 符号栈 输入符号串 动作 1） # abbcde# 移进 2） #a bbcde# 移进 A 3） #ab bcde# 归约(A→b) 4） #aA bcde# 移进 A 5） #aAb cde# 归约(A→Ab) S 10） #aAcBe # 归约 6） #aA cde# 移进 7） #aAc de# 移进 B 8） # aAcd e# 归约(B→d) 9） #aAcB e# 移进 11） #S # 接受 对输入串abbcde#的移进-规约分析过程 a b b c d e 符号串abbcde是否是G[S]的子 S  aAcBe aAcde aAbcde abbcde

17 步骤 符号栈 输入符号串 动作 状态栈 ACTION GOTO 对输入串abbcde#的LR分析过程
1） # abbcde# 移进 S2 2） #a bbcde# 移进 S4 3） #ab bcde# 归约(A→b) r 4） #aA bcde# 移进 S6 5） #aAb cde# 归约(A→Ab) r 6） #aA cde# 移进 S5 7） #aAc de# 移进 S8 8） # aAcd e# 归约(B→d) r 9） #aAcB e# 移进 S9 10） #aAcBe # 归约(S→aAcBe) r 11） #S # 接受 acc 对输入串abbcde#的LR分析过程 文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d Si:移进，将状态i和输入符进栈 ri:归约，用第i个产生式归约，同时状态栈与符号栈退出相应个符号，并把GOTO表相应状态和第i个产生式的左部非终结符入栈。

18 ＬＲ分析程序 推导过程 S aAcBe[1] aAcd[4]e[1] aAb[3]cd[4]e[1]
ab[2]b[3]cd[4]e[1] 规约时在栈里的句型的前缀 规约前可在栈里的规范句型(不含句柄) 的前缀 ab[2] a aAb[3] a,aA aAcd[4] a,aA,aAc aAcBe[1] a,aA,aAc,aAcB R

19 ＬＲ分析程序 LR 文法 对于一个cfg 文法, 如果能够构造一张 LR 分析表, 使得它的每一个入口均是唯一的（Sj,rj,acc,空白），则称该 cfg 是LR 文法．

20 ＬＲ分析 特征: ．规范的 ．符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀)
．分析决策依据――栈顶状态和现行输入符号．？识别活前缀的 DFA. 四种技术 LR(0) SLR(1) LR(1) LALR(1)

21 LR(0) 分析 LR(0)文法 能力最弱，理论上最重要 存在FA 识别活前缀 识别活前缀的DFA如何构造 （LR(0)项目集规范族的构造）

22 ＬＲ分析 活前缀 G=(Vn,Vt,P,S),若有S’  αAω  αβω, γ是αβ的前缀,则称是文法G的活前缀.
其中S’是对原文法扩充(S’S)增加的非终结符. ? 为使S’不出现在任何产生式的右部. 如G=({S},{a},{SSa,Sa},S) R * R

23 识别活前缀的DFA 定义(非终结符的左文) LC(A)={ | S’A, V*, Vt*}, 对拓广文法的开始符号S’:
启示:LR分析使用的信息之一是句柄左部 的内容. 定义(非终结符的左文) LC(A)={ | S’A, V*, Vt*}, 对拓广文法的开始符号S’: LC(S’)={} 若BA 则:LC(A)LC(B).{} R *

24 G[S]: (0) S’S (1) S a A c B e (2)A b (3) A Ab (4)B d
每个非终结符的左文方程组 LC(S’)={} LC(S)=LC(S’).{} LC(A)=LC(S).{a} LC(A){} LC(B)=LC(S).{aAc} 化简为： [S’]=  [S]=[S’] [A]=[S]a+[A] [B]=[S]aAc 用代入法求解得： [S’]=  [S]=  [A]=a+[A] [B]=aAc 令 ={[S’]，[S]，[A]， [B]，a，A,c} 则方程两边都是上的正规式 而[A]=a+[A] 即为 [A]=a | [A] 由正规式所表示的正规集 得： [A]=a

25 G[S]: (0) S’S (1) S a A c B e (2)A b (3) A Ab (4)B d
定义(产生式的LR(0)左文) LR(0)LC(A)={|  =且S’A , Vt*} 有推论：LR(0)LC(A )=LC(A).{} 则有: LR(0)LC(S’S)=S LR(0)(LC(SaAcBe)=aAcBe LR(0)LC(Ab)=ab LR(0)LC(AAb)=aAb LR(0)LC(Bd)=aAcd ( =VnVt)上的正规式 R * R

26 S ① a b  2 3 ④  b a A  x 5 6 7 ⑧   a A c d 9 10 11 12 ⒀ a A c B e 14 15 16 17 18 ⒆

27 DFA a b A x 2 3 6 S b c B e 4 5 7 9 1 d 8

28 构造LR(0)项目集规范族 LR(0)项目集规范族(构成识别一个文法的活前缀的DFA的状态的全体) 。
LR（0）项目或配置（ item or configuration）. ---在右端某一位置有圆点的G的产生式 A xyz A.xyz Ax.yz Axy.z Axyz. 如：S→aAd S→.aAd S→a .Ad S→aA .d S→aAd .

29 活前缀与句柄的关系： G[S]: 若S => αAω =>αβω r是αβ的前缀，则 * R 称r是G的一个活前缀 R

30 活前缀,与句柄 ,与 LR(0)项目 为刻划这种分析过程中的文法G的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶）的情况，分别用标有圆点的产生式来指示位置。 A→β．刻划产生式A→β的 右部β已出现在栈顶 A→β1．β2 刻划A→β1β2的右部子串β1已出现在栈顶，期待从输入串中看到β2推出的符号 A→．β 刻划没有句柄的任何符号在栈顶，此时期望A→β的右部所推出的符号串 对于A→ε的LR(0)项目只有A→．

31 构造识别活前缀的DFA { J:= I; repeat for J 中的每个项目A  .B  和产生式
LR（0） 项目集的闭包ＣLOSURE, GO 函数， function CLOSURE (I); /* I 是项目集*/ { J:= I; repeat for J 中的每个项目A  .B  和产生式 B  ，若B . 不在J中 do 将 B . 加到J中 until 再没有项目加到J中 return J }; GO (I,x)=== CLOSURE(J) ; 其中， I:项目集，x: 文法符号， J={任何形如A x.  的项目|A .x  I}

32 LR（0） 项目集的闭包ＣLOSURE 若当前处于A –> X•YZ刻划的情况，期望移进 First(Y)中的某些符号，假如有产生式 Y –> u | w . 那么Y –> •u和Y –> •w这两个项目便是刻划期望移进 First(Y)中的某些符号的情况. A –> X•YZ Y –> •u Y –> •w 这三个项目对应移进归约分析的同一个状态,这三个项目构成一个配置集, 对应每个配置集，分析表将有一个状态.

33 LR(0)项目集规范族 计算LR（0）项目集规范族 C={I0 ，I1 , ... In } Procedure itemsets(G’);
Begin C := { CLOSURE ({S’.S})} Repeat For C 中每一项目集I和每一文法符号x Do if GO(I,x) 非空且不属于C Then 把 GO(I,x) 放入C中 Until C 不再增大 End;

34 例：文法G: （0）S`→E (1) E→aA (2) E→bB (3) A→cA (4) A→d (5) B→cB (7) B→d LR(0) 项目集规范族（识别G的活前缀的DFA)： I0: S`→．E I1: S`→E． I2: E→a．A E→．aA A→.cA E→．bB A→．d

35 I3: E→b．B I4: A→c.A I5: B→．cB A→．cA B→c．B B→．d A →.d B→．cB B→．d I6: I7: I8: E→aA． E→bB． A→cA． I9: B→cB． I10: A→d． I11: B→cB．

36 LR(0)分析表的构造 假定C={I0, I1,……，In}，令每个项目集Ik的下标k 为分析器的一个状态，因此，G` 的LR(0)分析表含有状态0，1，……，n。令那个含有项目S`→．S的Ik的下标k为初态。ACTION和GOTO可按如下方法构造： 若项目A→α．aβ属于Ik且GO (Ik, a)= Ij, a为终结符，则置ACTION[k, a]为“把状态j和符号a移进栈”，简记为“sj”; 若项目A→α．属于Ik, 那么，对任何终结符a, 置ACTION[k, a]为“用产生式A→α进行规约”，简记为“rj”;其中，假定A→α为文法G`的第j个产生式； 若项目S`→S．属于Ik, 则置ACTION[k, #]为“接受”，简记为“acc”; 若GO (Ik, A)= Ij, A为非终结符，则置GOTO(k, A)=j; 分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。

37 按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张LR(0)表。具有LR(0)表的文法G称为一个LR（0）文法。

38 ACTION GOTO a c b d # E A B 0 S2 S3 1 1 acc 2 S4 S10 6 3 S5 S11 7
r r r r r1 r r r r r2 r r r r r r3 r r r r r r5 r r r r r r4 r r r r r r6

39 LR(0)项目 作用？ 根据圆点所在的位置和圆点后是终结符还是非终结符或为空把项目分为以下几种：
移进项目，形如 A → • a a是终结符,  , V* 以下同 待约项目，形如 A → • B 归约项目，形如 A → • 接受项目，形如 S’ →S • A→ε的LR(0)项目只有A→ • 是归约项目 作用？

40 例：（0）S`→S (1) S→rD (2) D→D,i (3) D→i LR（0）项目 1. S`→．S S`→S． S→．rD 4. S→r．D S→rD． D→．D,i 7. D→D．,i D→D,．i 9. D→D,i． 10. D→．i D→i．

41 NFA  i 1 3 10 11  S r  D , r 4 6 7 8 9 2 D 5

42 例：（0）S`→S (1) S→rD (2) D→D,i (3) D→i LR（0）项目集规范族 I0: S`→．S I3: S→r D． S→．r D D→D．i I1: S`→S． I4: D→i． I2: S→r．D I5: D→D．i D→．D i I6: D→Di． D→．i 其中I3中含有移进/归约冲突 文法不是LR(0)的，如何解决？

43 SLR(1)技术 SLR(1)文法是无二义的。 若 LR(0) 项目集规范族中有项目集IK含 移进/归约 归约/归约 冲突：
IK :{ ...A→α.bβ , P   . , Q   . , …} 若FOLLOWQA)  FOLLOW(P) = FOLLOWP(P)  { b } = FOLLOW(Q)  { b} = 则解决冲突的SLR(1)技术： action [ k,b ] = 移进 对a FOLLOW (P) 则 action [ k,a ] =用 P   归约 对a FOLLOW (Q) 则 action [ k,a ] =用 Q   归约 能用SLR(1)技术解决冲突的文法称为SLR(1)文法。 SLR(1)文法是无二义的。

44 SLR表 假定C={I0, I1,……，In}，令每个项目集Ik的下标k 为分析器的一个状态，因此，G` 的SLR分析表含有状态0，1，……，n。令那个含有项目S`→．S的Ik的下标k为初态。函数ACTION和GOTO可按如下方法构造： 若项目A→α．aβ属于Ik且GO (Ik, a)= Ij, a为终结符，则置ACTION[k, a]为“把状态j和符号a移进栈”，简记为“sj”; 若项目A→α．属于Ik, 那么，对任何输入符号a, a∈FOLLOW(A),置ACTION[k, a]为“用产生式A→α进行规约”，简记为“rj”;其中，假定A→α为文法G`的第j个产生式； 若项目S`→S．属于Ik, 则置ACTION[k, #]为“接受”，简记为“acc”; 若GO (Ik, A)= Ij, A为非终结符，则置GOTO(k, A)=j; 分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。 按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张SLR表。具有SLR表的文法G称为一个SLR（1）文法。数字1的意思是，在分析过程中顶多只要向前看一个符号。

45 实数说明文法的SLR（1）分析表 状态 ACTION GOTO r , i # S D． 0 S 1 acc S 3 r S5 r1 r1 4 r3 r3 r3 r3 S6 6 r2 r2 r2 r2

46 ? SLR 例：文法G: （0）S`→S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e
LR(0) 项目集规范族（识别G的活前缀的DFA)： I0: S`→．S I1: S`→S． I2: S→a．Ad S→．aAd S→a．ec S→．bAc A→．e S→．aec S→．bed

47 ? SLR I3: S→b．Ac I4: I5: S→b．ed S→aA．d S→ae．c A→．e A→e ． I6: I7: I8:
S→bA．c S→be．d S→aAd． A→e． I9: S→aec． I10: S→bAc． I11: S→bed．

48 ACTION GOTO a c e b d # S A 0 S2 S3 1 1 acc 2 S5 4 3 S7 6 4 S8
r r5S9 r r r r5 S10 r r r r r7 S11 r7 r r r r r r1 r r r r r r3 r r r r r r2 r r r r r r4

49 ?? I5: S →ae．c A →e． S`==>S==>aAd==>aed S`==>S==>aec
I7: S →be．d S`==>S==>bAc==>bec S`==>S==>bed ？信息 哪些输入符号能跟在句柄之后 R R R R R R R R R R

50 Another example G[S]: (0) S`→S (1) S→L=R (2) S→R
(3) L→ *R (4) L→i (5) R→L LR(0)项目集规范族和G0函数 I1 S’ →S I6 I0 S`→．S I2 S→L．=R S →L=.R L →.*R S→．L=R R→ L R→ .L L→ .i S→．R L→．*R I3 L→．i S→R． R→．L I4 L→*． R I7 I R→．L L→*R． L→i． L→．*R L→ .i I8 R→L．

51 ∵ I2 S→L．=R R→ L.中存在移进/归约冲突 （2） SLR能否解决I2中的冲突
∴FOLLOW（R）={#,=}与{=}交不为空 不是SLR（1）文法 S→L.=R R→L. 若用 R→L 归约 则形成 R=… 而 R=不是活前缀 ?早知此信息 向前搜索符 —— LR（1）方法 若 A  .B   I 则 B  .  （ B   是一产生式）  I 把FIRST（B）中的符号作为用B   归约的搜索符

52 LR（1）项目 [ A  . ， a ] LR（K）项目 [ A  . ， a1 a2 …… aK ]

53 构造LR(1)项目集规范族和G0函数 closure(I)按如下方式构造 (1) I的任何项目属closure(I)；
(2)若[A→β1．Bβ2，a]∈closure(I)，B→δ是一产生式，那么对于FIRST(β2a)中的每个终结符b，如果[B→．δ,b]不在closure(I)中，则把它加进去； (3)重复（1）（2），直至closure(I)不再增大。

54 GO函数： 若I是一个项目集，X是一个文法符号 GO(I, X)= closure(J) 其中 J={ 任何形如[A→αX．β,a]的项目∣[A→α.Xβ,a]∈I} LR(I)项目规范族C的构造算法类同LR(0)的，只是初始时： C={ closure({[S`→．S,#]})};

55 LR(1)项目集规范族 I0: S`→．S, # I5: S →ae．c,# S →．aAd, # A →e．,d
S →．bAc, # I6: S →bA．c, # S →．aec, # I7: S →be．d, # S →． bed, # A →e．,c I1: S` →S．,# I8: S →aAd．, # I2: S` →a．Ad, # I9: S →aec．, # S →a．ec, # I10: S →bAc．, # A →．e, d I11: S →bed．, # I3: S →b．Ac, # S →b．ed, # A→．e,c I4: S →aA．d, #

56 LR(1)项目集规范族 I1: S`→S．,# I9 :S→ L=R. ,# I2: I6: S→L=．R,#
I0: S`→．S,# S→L．=R,# R→．L,# S→．L=R,# R→L．,# L→．*R,# S→．R,# I3: L→．i,# L→．*R,=/# S→R．,# L→．i,=/# I4: I11: R→．L,# L→*．R,=/# L→*．R,# L→．*R,=/# R→．L,# I5: L→i．,=/# L→．i,=/# L→．*R,# R→．L,=/# L→．i,# I7 L→*R． ,=/# I8 R→L．,#/= I I13 I12: L→i R→L．,# L→*R．,#

57 LR(1)分析表的构造 若项目[A→α．A]属于Ik, 那么 置 ACTION[k, a]为“用产生式A→α进行规约”，简记为“rj”;其中，假定A→α为文法G`的第j个产生式；

58 At the heart of the table construction is the notion of an LR(0) configuration or item. A configuration is a production of the grammar with a dot at some position on its right side. For example, A –> XYZ gives four items: A –> •XYZ A –> X•YZ A –> XY•Z A –> XYZ•