LR(0)项目举例p131 设拓广文法G[S]该文法的所有LR(O)项目： 的产生式为： 1.S?→.E10.A→d. S'→E 2.S’→E. 11.E→.bB E→ aA bB 3.E→.aA 12. E→b.B A cA d 4.E →a. A 13. E→bB. B 一→ cBd 5.E ->aA. 14. B→.cB 归约 移进 6.A→.cA 15. B→c.B 接受 待约 7.A→c.A 16. B→CB. 8。A→cA. 17. B→.d 9.A→.d 18.B →d. 2025/4/3 ☑D11
2025/4/3 11 LR(0)项目举例 p131 设拓广文法G[S] 的产生式为： S → E E → aA | bB A → cA | d B → cB | d 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 该文法的所有LR(0)项目: 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. 归约 接受 移进 待约
LR(0)项目的分类p131-p132 ■A>o.归约项目(Reduce) ◆句柄形成于栈顶，可归约 ■S'→a.接受项目 ◆接受，句子分析成功 ■A→o.aB移进项目(Shift) ◆移进符号a ■A→0.BB待约项目 ◆等待分析完B,才能继续分析A的右部 2025/4/3 小节目绿 ☑12
2025/4/3 12 LR(0)项目的分类 p131-p132 ◼A→. 归约项目(Reduce) ◆句柄形成于栈顶，可归约 ◼S’→α. 接受项目 ◆接受，句子分析成功 ◼A→.a 移进项目(Shift) ◆移进符号a ◼A→.B 待约项目 ◆等待分析完B，才能继续分析A的右部 小节目录
构造识别活前缀的DFA ■先按一定规则用所有LR(O)项目表示状态构造NFA p132 6.A→.cAe7.A→c.AA, 8.A→cA. 图7.7 e 9.A→.da 10.A→d E 3.E-→.aA a4.E-→a.A 5.E→aA. e 1.S→.EE2.S"→E. 11.E→.bBb12.E→b.BB 13.E→bB. 17.B.d418.B→d 14.B→.c5.B→c.BB16.B→cB. 2025/4/3 13
2025/4/3 13 构造识别活前缀的DFA ◼先按一定规则用所有LR(0)项目表示状态构造NFA p132 图7.7 1.S’→.E 3.E→.aA 6.A→.cA 7.A→c.A 9.A→.d 12.E→b.B 14.B→.cB 17.B→.d 15.B→c.B 2.S’→E. 4.E→a.A 11.E→.bB ε ε E 8.A→cA. 10.A→d. 5.E→aA. 13.E→bB. 18.B→d. 16.B→cB. a ε ε A c ε ε A d b ε ε B c ε ε B d
构造识别活前缀的D价 A ■再对NFA确定化和最小 A→cA. 化最后得到一个识别活前 A→d. 缀的DFAp132图7.8 L10 CA A a E→aA. Io A I; b.B B E→bB. B cB I0, I1, ,I11 B d 状态—LR(O)项目集合 B→C.B B→d. 状态（项目集）间转移函数I5 B→.cB G0函数 B→. B→cB. 求解太麻烦，如何优化？ 2025/4/3 小节目绿 14
2025/4/3 14 构造识别活前缀的DFA ◼再对NFA确定化和最小 化最后得到一个识别活前 缀的DFA p132 图7.8 I0 S’→.E E→.aA E→.bB E S’→E. I1 a I2 E→a.A A→.cA A→.d 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 I0，I1，.，I11 状态——LR(0)项目集合 状态(项目集)间转移函数 ——GO函数 小节目录 求解太麻烦，如何优化？
LR(0)项目集规范族的定义p132 ■文法的LR(O)项目集规范族，记作C ◆构成识别一个文法活前缀的DFA的项目集合 (或状态)的全体 ◆例如，C={1o,I1,I11} ■LR(0)项目集（合） ◆识别一个文法活前缀的DFA的状态 ■ 函数go ◆LR(0)项目集间的转移函数 2025/4/3 ☑15
2025/4/3 15 LR(0)项目集规范族的定义 p132 ◼文法的LR(0)项目集规范族,记作 C ◆构成识别一个文法活前缀的DFA的项目集合 (或状态)的全体 ◆例如，C={I0，I1，.，I11 } ◼LR(0)项目集(合) ◆识别一个文法活前缀的DFA的状态 ◼函数go ◆LR(0)项目集间的转移函数