LR(0)项目集规范族的构造p133 ■拓广文法G ◆引进新的开始符号$及新产生式 S'→S ◆S'→.S对应分析开始 ◆S→S.对应分析成功结束 ■LR(O)项目集规范族的构造算法 ◆计算项目集闭包CLOSURE(I) ◆计算状态转移函数G0 2025/4/2 22
2025/4/2 22 LR(0)项目集规范族的构造 p133 ◼拓广文法G’ ◆引进新的开始符号S’及新产生式 S’ → S ◆S’→.S对应分析开始 ◆S’→S.对应分析成功结束 ◼LR(0)项目集规范族的构造算法 ◆计算项目集闭包CLOSURE(I) ◆计算状态转移函数GO
项目集的闭包CLOSURE(I)的计算p132 ■设I是文法G的任一项目集，计算I的闭包CLOSURE(I) 的方法是： 1)I∈CLOSURE(I) 2)若A→a·BB∈CLOSURE(I),则对任何关于B的 产生式B→Y,项目B→·Y∈CLOSURE(I) 3)重复执行上述步骤，直至CLOSURE(I)不再增大 ■例I={S'.E} 例G'[S]: CLOSURE(I)={S'→.E, S'→E E→.aA, E→ aA bB E→.bB} A→ cA d B cB d 2025/4/2 ☑D23
2025/4/2 23 项目集的闭包CLOSURE(I)的计算 p132 ◼ 设I是文法G’的任一项目集，计算I的闭包CLOSURE(I) 的方法是： 1)I CLOSURE(I) 2)若 A →α·Bβ∈ CLOSURE(I)，则对任何关于B的 产生式 B→γ，项目B→·γ∈ CLOSURE(I) 3)重复执行上述步骤，直至CLOSURE(I)不再增大 例G[S]: S → E E → aA|bB A → cA|d B → cB|d ◼例 I={S →.E} CLOSURE(I)={S’→.E, E→.aA, E→.bB}
状态转移函数G0(1,X)p133 ■（当前项目集I,文法符号X)→下一项目集 ■G0(I,X)=CLOSURE(J) 其中J={A→aX·B|A→a·XB∈I} 例：I={S?→.E,E→.aA,E→.bB} 例G[S]: 1.设X=E,则J={S→E.} S′→E E→ aA bB GO(I,E)=CLOSURE(J)={S'-E. A→ cA d 2.设X=a,则J={E→aA} B cBd GO(I,a)=CLOSURE(J) ={E→aA,A→cA,A→d} 3.设X=b,则J={E→bB} G0(I,b)=CL0SURE(J)={E→bB,B→cB,B→·d} 2025/4/2 26
2025/4/2 26 状态转移函数GO(I，X)p133 ◼ (当前项目集I，文法符号X)→下一项目集 ◼ GO(I,X)=CLOSURE(J) 其中 J={A→αX ·β｜A→α·Xβ∈ I } 例 G[S]: S → E E → aA|bB A → cA|d B → cB|d 例：I={S’→.E, E→.aA，E→.bB} 1.设X=E， 则J={S’→E.} GO(I,E) =CLOSURE(J) ={S’→E.} 2.设X=a, 则J={E→a·A} GO(I,a)=CLOSURE(J) ={E→a·A 3.设X=b, 则J={E→b·B} GO(I,b)=CLOSURE(J)={E→b·B ，A→·cA ，A→·d} ，B→·cB ，B→·d}
LR(0)顶目集规范族构造举例p133 Io=CL0SURE({S→.E) I1=G0(I0,E) 14 >C.A 例G[S] I2=GO(Io,a) A→cA. I8 I3=G0(I0,b) d (0)S→E C A→d. 2 E→a.A I10(1)E-→aA A→.CA a A→. d E→aA. I6(2)E→bB Io SEE 9 → . (3)A→cA A E →E. 1 (4)A→d Is E→b.B B E→bB. B→ cB 7(5)B→cB B→， d (6)B→d B→C.B d B→d. T11 B cB B→cB. 9 2025/4/2 可 29
2025/4/2 29 LR(0)项目集规范族构造举例 p133 例 G’[S’] (0)S’→E (1)E→aA (2)E→bB (3)A→cA (4)A→d (5)B→cB (6)B→d I0=CLOSURE({S’→.E}) I0 S’→.E E→.aA E→.bB I1=GO(I0,E) E S’→E. I1 I2=GO(I0,a) a I2 E→a.A A→.cA A→.d I3=GO(I0,b) b I3 E→b.B B→.cB B→.d A E→aA. I6 c I4 A→c.A A→.cA A→.d d B E→bB. I7 c I5 B→c.B B→.cB B→.d d B→d. I11 A A→cA. I8 c d A→d. I10 B B→cB. I9 c d
LR(0)项目集规范族的构造课堂练习 例如： S→S. 拓广文法G I2 S→B.B I5 (0)S→S B S’→.S B B→.aB S→BB. (1)S→BB S→.BB B→.b b (2)B-→aB B→.aB a I (3)B→b B→.b I B→a.B B a 3 B →aB.6 BEGIN B→.aB B→.b a b b B→b. 2025/4/2 小节目录 30
2025/4/2 30 LR(0)项目集规范族的构造课堂练习 例如： 拓广文法G’ (0)S'→S (1)S→BB (2)B→aB (3)B→b S’→.S S→.BB B→.aB B→.b I 0 S S’→S. I1 B S→B.B B→.aB B→.b I2 a B→a.B B→.aB B→.b I 3 b B→b. I4 B S→BB. I5 a b B B→aB. I 6 a b BEGIN 小节目录