if GO(I,X)非空且不属于C THEN 把GO(I,X) 加入C中 UNTIL C 不再增大； END;
（3）测试数据
输入如下所示的文法： 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 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·
（4）结果输出
根据算法得到的项目集规范簇如下图所示：
结果也可以用表格的形式表示如下：
状态 S0 S1 项目集 { S' ? ·E E? ·aA E? ·bB } { S' ?E · } 后继符号 E a b # 后继状态 S1 S2 S3 接受态 9
S2 { E?a ·A A ? · cA A? · d } { E?b·B B? · cB B? · d } { A ?c · A A? · cA A? · d } { B?c · B B? · cB B? · d} { E?aA · } { E?bB · } { A ?cA · } { B?cB · } { A?d · } { B?d · } A c d B c d A c d B c d # # # # # # S6 S4 S10 S7 S5 S11 S8 S4 S10 S9 S5 S11 归约 归约 归约 归约 归约 归约 S3 S4 S5 S6 S7 S8 S9 S10 S11 2.构造LR(0)分析表
（1）问题描述
给定一个LR（0）文法，利用6.1得到的项目集规范簇，求出其LR（0）分析表，并以表格的形式输出。
（2）算法描述
LR(0)分析表的构造算法为： ??对于A ??·X??Ik，GO (Ik,X)=Ij ??若X ?Vt，则置action[k,X]=Sj ,即把(j,a)移进栈 ??若X ?Vn，则置goto[Ik,X]=j ??对于A?? · ? Ik ，则对所有的x?Vt和# ，均置action[k,x]=rj (设A ??是第j个产生式)，即用A ??归约） ??若S' ?S · ?Ik，则置action[k,#]=acc，即接受 ??其他均置出错。
（3）基本要求
动态模拟算法的基本功能是：
（1） 输入LR分析文法，要求可以直接输入，也可以读入文件；
10
（2） 输出项目集规范簇（可选）； （3） 输出LR(0)分析表；
（4）测试数据
输入文法：
E ?aA｜ bB A ?cA｜d B ?cB｜d
输出LR分析表如下：
3.LR分析过程的实现
（1）问题描述
给定一个LR(0)文法，利用6.2求出其LR(0)分析表；或者给定某个LR分析表（可能不是LR(0)分析表，其分析过程类似），输入一个符号串，依据LR分析表输出与句子对应的语法树，能对语法树生成过程进行模拟。
（2）算法描述
在分析过程中设置一个堆栈和一个分析表，根据分析表和输入符号串对堆栈进行操作，分析器的下一步动作是由栈顶状态Sm和当前面临的输入符号ai唯一确定的。
根据栈顶状态Sm和输入符号ai查action表, 根据表中的内容不同完成不同的动作，若action[Sm, ai]为：
? 移进：当前输入符号ai进符号栈，下一输入符号变成当前输入符号，将action表中指出的状态S进状态栈。三元式变为： (S0S1?SmS, # X1X2?Xmai, ai+1?an#)
11
? 归约：按某个产生式A→β进行归约，若产生式的右端长度为r，则两个栈顶的r个元素同时出栈。将归约后的符号A进符号栈; 根据新栈顶状态Sm-r和归约符号A查GOTO表，S=goto[Sm-r, A]进状态栈。三元式变为： (S0S1 ? Sm-r S, # X1X2?Xm-rA, aiai+1?an #) ? 接受：分析成功，终止分析。三元式不再变化。 ? 出错：报告出错信息。三元式的变化过程终止。
（3）基本要求
动态模拟算法的基本功能是：
(1). 输入LR分析表和一个句子； (2). 输出LR总控程序；
(3). 输出依据句子构对应的语法树的过程；
（4）测试数据
输入句子：i*i+i 输入文法：
(1) E ?E+T (2) E ?T (3) T ?T*F (4) T ?F (5) F?(F) (6) F ?i
和如下所示的LR分析表：
得到如下图所示的LR分析过程：
12
相关推荐：
loading