《编译原理题库-综合题》由会员分享，可在线阅读，更多相关《编译原理题库-综合题（109页珍藏版）》请在金锄头文库上搜索。
1、真诚为您提供优质参考资料，若有不当之处，请指正。编译原理A卷已知文法 A-aAd|aAb| 判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。解：增加一个非终结符S/后，产生原文法的增广文法有： S-A A-aAd|aAb| 下面构造它的LR(0)项目集规范族为： 从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOLLOW(A)a=b,d,#a=，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该
2、文法是SLR(1)文法。 其SLR(1)分析表为： 对输入串ab#给出分析过程为： 编译原理B卷构造下述文法 GS 的自动机： S-A0 A-A0|S1|0 该自动机是确定的吗？若不确定，则对它确定化。解：由于该文法的产生式S-A0，A-A0|S1中没有字符集VT的输入，所以不是确定的自动机。 要将其他确定化，必须先用代入法得到它对应的正规式。把S?A0代入产生式A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入S-A0有该文法的正规式：0(0|01)*0，所以，改写该文法为确定的自动机为： 由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化： 下
3、表由子集法将NFA转换为DFA: 由上表可知DFA为：编译原理C卷6(20分)已知上下文无关文法：S L=R | RL *R | idR L(1) 请构造非终结符的FIRST和FOLLOW集合。（5分）(2) 构造该文法的LL(1)分析表。该文法是LL(1)文法吗？（15分7. （20分）考虑以下文法：S AA BA | B aB| b证明该文法是LR（1）的。(1)证明它是LR(1)文法；(2)构造它的LR(1)分析表。7（20分）阅读下面的LEX程序，并回答：（1）该程序完成了什么功能？（2）修改该程序，使之能够计算输入的标识符个数。（直接改在试题上）LEX程序如下：%# include
4、int num_int = 0;int num_float = 0;int num_line = 0;int num_id = 0;%digit 0-9integer +-?digit+flt +-?digit+.digit+lettera-zA-zidletter(letter|digit)*%integer num_int+ ;flt num_float+ ;n num_line+ ;. ;idnum_id+;%main()yylex() ;printf(“n%d integers, %d floating point numbers, %d lines, %d identifiers.n
5、”,num_int, num_float, num_line, num_id) ;C卷答案6解：(1)根据L *R | id，可得到FIRST(L)=*, id；根据R L，可得到FIRST(R)= FIRST(L)=*, id；根据S L=R | R，可得到FIRST(S)= FIRST(L) FIRST(R)=*, id；S是开始符号，所以有$FOLLOW(S)；又根据S L=R，可得到=FOLLOW(L)；又根据S L=R | R，可得到FOLLOW(S)FOLLOW(L)；又根据L *R，可得到FOLLOW(L)FOLLOW(R)；又根据R L，可得到FOLLOW(R)FOLLOW(L
6、)；所以有FOLLOW(S)=$，FOLLOWL= FOLLOWR=$, =。(2) 构造LL(1)分析表如下：*=id$SS L=RS RS L=RS RLL *RL idRR LR L由于分析的表目中存在冲突，该文法不是LL(1)文法。7. （20分）考虑以下文法：S AA BA | B aB| b证明该文法是LR（1）的。(1)证明它是LR(1)文法；(2)构造它的LR(1)分析表；7答：该程序完成的功能：计算整数、浮点数的个数，统计行数，并分别输出。修改见程序。编译原理D卷7、证明下面文法是SLR(1)但不是LR(0)的。SAAAbbBaBaAcaaAb8、证明下面的文法是LL(1)的
7、但不是SLR(1)的。SAaAbBbBaAB1.构造表达式（4*7+1）*2的附注语法树。四、（20分）设文法GS为SaAcB 问：1、该文法是否为算符文法，为什么？AAb|b 2、构造算符优先关系表。Bd 3、该文法是否可改造为LL（1）文法，为什么？五、（本题20分）设文法G为： EeAf|eBg AaA|a BBb|a对于输入串eaaaf，采用LR（0）、LL（1）、SLR（1）等方法中合适的一种进行分析。六、（25分）有作控制用的布尔表达式文法GE及其语义动作如下：1、 构造SLR（1）分析表（若不是SLR(1)）的，则说明理由）2、 分析布尔式abc的四元式生成过程，并画出最后的真假
8、链表。3、 给出语句IF abc THEN I:=m*n ELSE I:=m+n的完整四元式序列。文法GE：(1)Eii E.TC:=NXQ; E.FC=NXQ+1;GEN(J,ENTRY(i),ENTRY(i),O);GEN(J, , ,0)(2)EAE E.FC:=E.FC; E.FC:=MERGE(A.TC ,E.TC)(3)AB BACKPATCH(B.FC ,NXQ); A.TC:=B.TC(4)Bi B.TC:=NXQ; B.FC:=NXQ+1;GEN(Jnz, ENTRY(i), ,0); GEN(J, , ,0)答案：7证明：求该文法的LR(0)项目集规范族如下：I0=S，Ab
9、BaGO(I0，A)=SA，AAb =I1GO(I0，b)=AbBa，BaAc，Ba，BaAb=I2GO(I1，b)=AAb=I3GO(I2，B)=AbBa=I4GO(I2，a)=BaAc，Ba，BaA b，AAb，Ab Ba=I5GO(I4，a)= AbBa= I6GO(I5，A)= BaAc，BaAb，AAb= I7GO(I5，b)= AbBa，BaAc，Ba，BaAb = I2GO(I7，c)= BaAc= I8GO(I2，b)= BaAb，AAb= I9考虑I1，I5都存在“移进归约”冲突，所以该文法不是LR(0)的。由于FOLLOW(S)=#，不包含b，所以I1的冲突可以消解；由于F
10、OLLOW(B)=a，不包含b，所以I5的冲突可以消解；由于FOLLOW(B)=a，FOLLOW(A)=c，b，#，二者不相交，所以I9的冲突也可以消解。综上所述，该文法是SLR(1)的。8证明：因为FIRST(AaAb)=a，FIRST(BbBa)=bFIRST(AaAb)FIRST(BbBa)=所以该文法是LL(1)的。求该文法的LR(0)项目集规范族如下：I0=SS，SAaAb，SBbBa，A，BI1=SSI2=SAaAbI3=SBbBaI4=SAaAb，AI5=SBbBa，BI6=SAaAbI7=SBbBaI8=SAaAbI9=SBbBa考虑I0：FOLLOW(A)=FOLLOW(B)
11、=a，bA和B的冲突无法消解，所以该文法不是SLR(1)的。1解：LE.val = 58nT.val = 58T.val = 29F.val = 2*digit.lexval= 2F.val = 29 (E.val = 29 )E.val = 28T.val = 1 +E.val = 1digit.lexval=1 11111= 1T.val = 28F.val = 7 *digit.lexval = 7digit.lexval=4四 答：1、该文法是算符文法。因为其任一产生式的右部都不含相继（并列）的非终结符，即不含如下形式QR的产生式右部。 （4分）2、FIRST(S)=a, LAST(S
12、)=c,FIRST(A)=b, LAST(A)=b,FIRST(B)=d, LAST(B)=d。 （3分）构造算符优先关系表如下： （5分）abcd#abcd#=3、该文法可以改造为LL（1）文法。 （8分）原因： 消除左递归：SaAcB AbA AbA| Bd； FIRST(A)=a, FOLLOW(A)=c,FIRST(A)=b, , FOLLOW(A)=c,FIRST(B)=d, FOLLOW(B)=#,FIRST(S)=a, FOLLOW(S)=#,对于每个非终结符的各个产生式的FIRST集两两不相交； 对于A，FIRST（A）FOLLOW（A）=。 综上所述，原文法可以改造成LL（1）文法。五、（20分）原文法不是LL（1）文法，故
