资源描述：
《编译原理 试题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、P788.构造一个DFA，他接受正规式（a
2、ba）*定义的字符串。解：状态转换，如表所示对上表简化，得表如下abS,1,Z1,Z21,Z1,Z221,Zab11P95消除以下文法的左递归，并构造文法分析表，应用上述预测分析表分析输入串i*i。E→E+T
3、TT→T*F
4、FF→(E)
5、i解：(1)E→E+T
6、T＝>E→TE’E’→+TE’
7、εT→T*F
8、F＝>T→FT’T’→*FT’
9、εF→(E)
10、I＝>(E)
11、i(2)E→TE’FIRST(TE’)={i,(}FOLLOW(E)={),#}E’→+TE’FIRST(+TE’)={+}FOLLOW(E’)={),#}E’→
12、εFIRST(ε)={ε}T→FT’FIRST(FT’)={(,i}FOLLOW(T)={+,),#}T’→*FT’FIRST(*FT’)={*}FOLLOW(T’)={+,),#}T’→εFIRST(ε)={ε}F→（E）FIRST((E))={(}FOLLOW(F)={*,+,),#}F→iFIRST(i)={i}得预测分析表i+*（）#EE→TE’E→TE’E’E’→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→iF→（E）(3)应用上述预测分析表分析输入串i*i将步骤细列于下表步骤序号符号栈输入串查表项调用产生式
13、/匹配/出错0#Ei*i#M[E,i]E→TE’1#E’Ti*i#M[T,i]T→FT’2#E’T’Fi*i#M[F,i]F→i3#E’T’ii*i#匹配成功4#E’T’*i#M[T’,*]T’→*FT’5#E’T’F**i#匹配成功6#E’T’Fi#M[F,i]F→i7#E’T’ii#匹配成功8#E’T’#M[T’,#]T’→ε9#E’#M[E’,#]E’→ε10##分析成功（匹配）P1324.给定文法G4(S);S→a
14、∧
15、（T）T→T,S
16、S(1)计算该文法的FIRSTVT集合和LASTVT集合。(2)计算该文法的优先关系。(3)给出输入串（a，（a，a））的算
17、符优先分析过程。解：(1)FIRSTVT和LASTVT集合如下：FIRSTVT(S)={a，∧，（}FIRSTVT（T）={，，a，∧，（}LASTVT(S)={a，∧，)}LASTVT(T)={,,a,∧,)}栈优先关系输入字符串动作#<（a，（a，a））#移进#（，（a，a））#归约#（N1<，（a，a））#移进#（N1，<（a，a））#移进#（N1，（，a））#归约#（N1，（N2<，a））#移进#（N1，（N2，））#归约#（N1，（N2，N3>））#归约#（
18、N1,(N4≈））#移进#（N1,(N4)>）#归约#（N1,N4>）#归约#（N1≈）#移进#（N1）>#归约#S#Success(2)构造优先关系（3）分析过程a∧（），a>>∧>>（<<<≈<）>>，<<<>>PPTP145翻译条件嵌套语句：IfathenifbthenA:=2elseA:=3ElseifcthenA=4ElseA=5翻译成四元式为：可得四元式：(1)(jnz,a,_,3)(2)(j,_,_,9)(3)(jnz,b,_,5)(4)(j,_,_,7)(5)(:=,2,_,A)(6)(j,_,_,0)(7)(:=,3,_,A)(8)(j,_,_,6)
19、(9)(jnz,c,_,11)(10)(j,_,_,13)(11)(:=,4,_,A)(12)(j,_,_,8)(13)(:=,5,_,A)P1339.文法G9(S)S→DbBD→dD→εB→aB→BbaB→ε(1)构造LR（1）项目集规范簇，识别该文法所产生的活前缀的DFA。(2)构造LR(1)分析表。(3)给出用分析器分子句子baba#的过程。解：（1）拓广文法为G9(S’):S’→SS→DbBD→dD→εB→aB→BbaB→ε构造LR（1）项目集规范簇，识别该文法所产生的活前缀的DFA，如图所示：I0:S’→•S#SS→•DbB#I1：S’→S•#D→•dbDD
20、→•bI2：S→D•Bb#dbI4:S→Db•B#BI6：S→DbB•#I3:D→d•bB→•a#/bB→B•BA#/bB→•Bba#/bbB→•#/bI7:B→Bb•a#/baaI5:B→a•#/bI8:B→Bba•#/b（2）LR（1）分析表：（3）穿baba#的分析过程如下：ACTIONGOTObda#SBD0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5步骤状态符号输入串00#baba#102#Dbaba#2024#DbAba#30245#Dbaba#40246#DbBba#502467#DbBba#60
