搜索
1第1题已知文法A→aAd|aAb|ε判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。答案：文法：A→aAd|aAb|ε拓广文法为G′，增加产生式S′→A若产生式排序为：0S'→A1A→aAd2A→aAb3A→ε由产生式知：First(S')={ε,a}First(A)={ε,a}Follow(S')={#}Follow(A)={d,b,#}G′的LR(0)项目集族及识别活前缀的DFA如下图所示在I0中：A→.aAd和A→.aAb为移进项目，A→.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I0、I2中：Follow(A)∩{a}={d，b，#}∩{a}=所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下：2对输入串ab#的分析过程:第2题若有定义二进制数的文法如下：S→L·L|LL→LB|BB→0|1(1)试为该文法构造LR分析表，并说明属哪类LR分析表。(2)给出输入串101.110的分析过程。答案：文法：S→L.L|LL→LB|BB→0|1拓广文法为G′，增加产生式S′→S若产生式排序为：0S'→S1S→L.L2S→L3L→LB4L→B35B→06B→1由产生式知：First(S')={0,1}First(S)={0,1}First(L)={0,1}First(B)={0,1}Follow(S')={#}Follow(S)={#}Follow(L)={.,0,1,#}Follow(B)={.,0,1,#}G′的LR(0)项目集族及识别活前缀的DFA如下图所示：在I2中：B→.0和B→.1为移进项目，S→L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I2、I8中：Follow(s)∩{0，1}={#}∩{0，1}=所以在I2、I8中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下：4对输入串101.110#的分析过:5第6题文法G=({U,T,S},{a,b,c,d,e},P,S)其中P为：S→UTa|TbT→S|Sc|dU→US|e(1)判断G是LR(0)，SLR(1)，LALR(1)还是LR(1)，说明理由。(2)构造相应的分析表。答案：文法：S→UTa|TbT→S|Sc|dU→US|e拓广文法为G'，增加产生式S'→S若产生式排序为：0S'→S1S→UTa2S→Tb3T→S4T→Sc5T→d6U→US7U→e由产生式知：First(S')={d,e}First(S)={d,e}First(U)={e}First(T)={d,e}Follow(S')={#}Follow(S)={a,b,c,d,e,#}Follow(U)={d,e}Follow(T)={a,b}G′的LR(0)项目集族及识别活前缀的DFA如下图所示：6在I1中：S'→S.为接受项目，T→S.为归约项目，T→S.c为移进项目，存在接受-归约和移进-归约冲突，因此所给文法不是LR(0)文法。在I1中：Follow(S')∩Follow(T)={#}∩{a，b}=Follow(T)∩{c}={a，b}∩{c}=在I8中：Follow(U)∩Follow(T)∩{c}={d,e}∩{a，b}∩{c}=所以在I1中的接受-归约和移进-归约冲突与I8中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下：