搜索
P788.构造一个DFA，他接受正规式（a|ba）*定义的字符串。解：状态转换，如表所示对上表简化，得表如下abS,1,Z1,Z21,Z1,Z221,ZP95消除以下文法的左递归，并构造文法分析表，应用上述预测分析表分析输入串i*i。E→E+T|TT→T*F|FF→(E)|i解：(1)○1E→E+T|T＝E→TE’E’→+TE’|ε○2T→T*F|F＝T→FT’T’→*FT’|ε○3F→(E)|I＝(E)|i(2)○1E→TE’FIRST(TE’)={i,(}FOLLOW(E)={),#}○2E’→+TE’FIRST(+TE’)={+}FOLLOW(E’)={),#}○3E’→εFIRST(ε)={ε}○4T→FT’FIRST(FT’)={(,i}FOLLOW(T)={+,),#}○5T’→*FT’FIRST(*FT’)={*}FOLLOW(T’)={+,),#}○6T’→εFIRST(ε)={ε}○7F→（E）FIRST((E))={(}FOLLOW(F)={*,+,),#}○8F→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将步骤细列于下表ab○0○011○0步骤序号符号栈输入串查表项调用产生式/匹配/出错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|∧|（T）T→T,S|S(1)计算该文法的FIRSTVT集合和LASTVT集合。(2)计算该文法的优先关系。(3)给出输入串（a，（a，a））的算符优先分析过程。解：(1)FIRSTVT和LASTVT集合如下：FIRSTVT(S)={a，∧，（}FIRSTVT（T）={，，a，∧，（}LASTVT(S)={a，∧，)}LASTVT(T)={,,a,∧,)}(2)构造优先关系（3）分析过程栈优先关系输入字符串动作#（a，（a，a））#移进#（a，（a，a））#移进#（a，（a，a））#归约#（N1，（a，a））#移进#（N1，（a，a））#移进#（N1，（a，a））#移进#（N1，（a，a））#归约#（N1，（N2，a））#移进#（N1，（N2，a））#移进#（N1，（N2，a））#归约#（N1，（N2，N3））#归约#（N1,(N4≈））#移进#（N1,(N4)）#归约#（N1,N4）#归约#（N1≈）#移进#（N1）#归约#S#Successa∧（），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)(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’):○0S’→S○1S→DbB○2D→d○3D→ε○4B→a○5B→Bba○6B→ε构造LR（1）项目集规范簇，识别该文法所产生的活前缀的DFA，如图所示：I0:S’→•S#SS→•DbB#I1：S’→S•#D→•dbDD→•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#6024678#DbBba#90246#DbB#1001#S#