《编译原理》习题解答081202[xiwang].pdf 24页

'《编译原理》习题解答：第一次作业：P142、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？答：被翻译的程序称为源程序；翻译出来的程序称为目标程序或目标代码；将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；编译程序是将高级语言写的源程序翻译成目标语言的程序。关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4图1.3。P143、编译程序是由哪些部分组成？试述各部分的功能？答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。P144、语法分析和语义分析有什么不同？试举例说明。答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量x：=y符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。补充：为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。１ 第二次作业：*+P381、设T1＝{11，010}，T2＝{0，01，1001}，计算：T2T1，T1，T2。T2T1＝{011，0010，0111，01010，100111，1001010}*T1＝{ε，11，010，1111，11010，01011，010010„„}+T2＝{0，01，1001，00，001，01001，010，0101„„}P38-398、设有文法G[S]：S∷＝aAbA∷＝BcA|BB∷＝idt|ε试问下列符号串（1）aidtcBcAb（2）aidtccb（4）abidt是否为该文法的句型或句子。（1）SaAbaBcAbaidtcAbaidtcBcAb句型但不是句子；（2）SaAbaBcAbaidtcAbaidtcBcAbaidtccAbaidtccBbaidtccb；是句型也是句子；（4）该文法的句子或句型的最后一个字符串一定是字符“b”；２ 第三次作业：P3911、试分别描述下列文法所产生的语言（文法开始符号为S）：（1）S∷＝0S|01（2）S∷＝aaS|bcn（1）L(G)＝{01|n≥1}；{解题思路：将文法转换为正规表达式}2n（2）L(G)＝{abc|n≥0}。P3912、试分别构造产生下列语言的文法：n（1）{aba|n=0，1，2，3„„}n（3）{aba|n≥1}nmp（5）{abc|n，m，p≥0}（1）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，P：S∷＝aAaA∷＝bA|ε（3）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，P：S∷＝abAA∷＝aA|a（5）①G＝{VN，VT，P，S}，VN＝{S，A，B，C}，VT＝{a，b，c}，P：S∷＝ABCA∷＝aA|εB∷＝bB|εC∷＝cC|ε②G＝{VN，VT，P，S}，VN＝{S}，VT＝{a，b，c}，P：S∷＝aS|bS|cS|εP3915.设文法G规则为：S：：=ABB：：=a|SbA：：=Aa|bB对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。（2）baabaab(3)bBABb解（2）SABAaSbbBABabBaa句型baabaab的短语a,ba,baa,baab,baabaab，简单短语a，句柄a３ S（3）ABbBSbAB短语bB,AB,ABb，bBABb简单短语bB,AB，句柄bB４ 第四次作业P4124.下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？1.S::=aBB::=cBB::=bC::=c2.S::=aBB::=bCC::=cC::=ε3.S::=aAbaA::=aBaA::=aaAB::=bA::=a4.S::=aCdaC::=BaC::=aaAB::=b5.S::=ABA::=aB::=bCB::=bC::=c6.S::=ABA::=aB::=bCC::=cC::=ε7.S::=aAS::=εA::=aAA::=aBA::=aB::=b8.S::=aAS::=εA::=bAbA::=a短语结构文法（0）4上下文有关文法（1）3上下文无关文法（2）568或者25678正规文法（3）127或者1P4229.用扩充的BNF表示以下文法规则：1．Z::=AB|AC|A2．A::=BC|BCD|AXZ|AXY3．S::=aABb|ab4．A::=Aab|ε解:1．Z::=A（B|C|ε）::=A[B|C]2．A::=BC（ε|D）|{X（Z|Y）}::=BC[D]|{X（Z|Y）}3．A::=a((AB|ε)b)::=a[AB]b4．A::={ab|ε}::={ab}５ 第五次作业：P744.画出下列文法的状态图：Z：：=BeB：：=AfA：：=e|Ae并使用该状态图检查下列句子是否该文法的合法句子：f,eeff,eefe。由状态图可知只有eefe是该文法的合法句子。P745.设右线性文法G=({S,A,B},{a,b},S,P)，其中P组成如下：S：：=bAA：：=bBA：：=aAA：：=bB：：=a画出该文法的状态转换图。P746.构造下述文法G[Z]的自动机，该自动机是确定的吗？它相应的语言是什么？Z：：=A0A：：=A0|Z1|0解1：将左线性文法转换为右线性文法，由于在规则中出现了识别符号出现在规则右部的情形，因此不能直接使用书上的左右线性文法对应规则，可以引入非终结符号B，将左线性文法变为Z：：=A0A：：=A0|B1|0B：：=A0，具体为：A:=Z1A:=B1A:=A01Z:=A0B:=A0将所得的新左线性文法转换成右线性文法：此时利用书上规则，其对应的右线性文法为：A：：=0A|0B|0Z：：=0AB：：=1A解2：先画出该文法状态转换图：６ NFA=（{S，A，Z}，{0，1}，M，{S}，{Z}）其中M：M（S，0）={A}M（S，1）=øM（A，0）={A，Z}M（A，1）=øM（Z，0）=øM（Z，1）={A}显然该文法的自动机是非确定的；它相应的语言为：{0，1}上所有满足以00开头以0结尾且每个1必有0直接跟在其后的字符串的集合；那么如何构造其相应的有穷自动机呢？先构造其转换系统：0εS’00SAZ’εZ1根据其转换系统可得状态转换集、状态子集转换矩阵如下表所示：II0I1S01{S’,S}{A}Ф01Ф{A}{A,Z,Z’}Ф12Ф{A,Z,Z’}{A,Z,Z’}{A}221则其相应的DFA为：0100210P748.设(NFA)M=({A,B},{a,b},M,{A},{B})，其中M定义如下：M(A,a)={A,B}M(A,b)={B}M(B,a)=øM(B,b)={A,B}请构造相应确定有穷自动机(DFA)M’。解：构造一个如下的自动机(DFA)M’，(DFA)M’={K,{a,b},M’,S,Z}K的元素是[A][B][A,B]由于M（A,a）={A,B}，故有M’（[A],a）=[A,B]同样M’（[A]，b）=[B]M’（[B]，a）=øM’（[B]，b）=[A，B]由于M（{A，B}，a）=M（A，a）UM（B，a）={A，B}Uø={A，B}故M’（[A，B]，a）=[A，B]由于M（{A，B}，b）=M（A，b）UM（B，b）={B}U{A，B}={A，B}故M’（[A，B]，b）=[A，B]７ S=[A]，终态集Z={[A，B]，[B]}重新定义：令0=[A]1=[B]2=[A,B]，则DFA如下所示：可以进一步化简，把M’的状态分成终态组{1，2}和非终态组{0}由于{1，2}a={1，2}b={2}{1，2}，不能再划分。至此，整个划分含有两组{1，2}{0}令状态1代表{1，2}，化简如图：８ 第六次作业：P7411（1）(0|11*0)*0解：先构造该正规式的转换系统：εε(0|11*0)*ZS1ZS01042εεS1Zε3ε11*01由上述转换系统可得状态转换集K={S,1,2,3,4,Z}，状态子集转换矩阵如下表所示：II0I1K01{S,1,Z}{1,Z}{2,3,4}012{1,Z}{1,Z}{2,3,4}112{2,3,4}{1,Z}{3,4}213{3,4}{1,Z}{3,4}3130由状态子集转换矩阵可知，1状态0和1是等价的，而状态20和3是等价的，因此，合并等价1状态之后只剩下2个状态，也即1210是最少状态的DFA。1030111010P7412.将图3.24非确定有穷自动机NFA确定化和最少化。aa,b01a图3.24NFA状态转换图解：设(DFA)M={K,VT,M,S,Z}，其中，K={[0],[0,1],[1]}，VT={a,b}，M：９11 M([1],a)=[0]M([1],b)=ФM([0,1],a)=[0,1]M([0,1],b)=[1]M([0],a)=[0,1]M([0],b)=[1]S=[1]，Z={[0],[0,1]}令[0,1]=2，则其相应的状态转换图为：b现在对该DFA进行化简，先把状态分为两组：01终态组{0,2}和非终态组{1}，易于发现{0,2}不可以继续划分，因此化简后的状态转换图如下：aaabb20,21aaP7418.根据下面正规文法构造等价的正规表达式：S::=cC|a„„①A::=cA|aB„„②B::=aB|c„„③C::=aS|aA|bB|cC|a„„④解：由③式可得B=aB+c→B=a*c由②式可得A=cA+aB→A=c*aa*c由①式可得S=cC+a由④式可得C=aS+aA+bB+cC+a→C=c*(aS+aA+bB+a)→C=c*(aS+ac*aa*c+ba*c+a)→S=cc*(aS+ac*aa*c+ba*c+a)+a=cc*aS+cc*(ac*aa*c+ba*c+a)+a=(cc*a)*(cc*(ac*aa*c+ba*c+a)+a)=(cc*a)*(cc*(ac*aa*c|ba*c|a)|a)另一种答案是S=c(ac|c)*(ac*aa*c|ba*c|aa|a)|a１０ 第七次作业：P1421.试分别消除下列文法的直接左递归（采用两种方法——重复法和改写法）（1）G[E]:E::=T|EAT„„①T::=F|TMF„„②F::=(E)|i„„③A::=+|-„„④M::=*|/„„⑤解：先采用“重复法”：再采用“改写法”：E::=T{AT}E::=TE’T::=F{MF}E’::=ATE’|εF::=(E)|iT::=FT’A::=+|-T’::=MFT’|εM::=*|/F::=(E)|iA::=+|-M::=*|/P1422.试分别消除下列文法的间接左递归（2）G[Z]:Z::=AZ|b„„①A::=ZA|a„„②解：将②式代入①式可得，Z::=ZAZ|aZ|b消除左递归后得到：Z::=(aZ|b)Z’Z’::=AZZ’|εA::=ZA|aP1435.对下面的文法G[E]:E::=TE’E’::=+E|εT::=FT’T’::=T|εF::=PF’F’::=*F’|εP∷＝(E)|a|b|∧（1）计算这个文法的每个非终结符号的FIRST和FOLLOW；（2）证明这个文法是LL（1）文法；（3）构造它的LL（1）分析表并分析符号串a*b+b;解:（1）构造FIRST集：FIRST(E’)={+,ε}FIRST(F’)={*,ε}FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(，a，b，∧}FIRST(T’)={(，a，b,ε，∧}构造FOLLOW集：规则一＃∈FOLLOW(E)FOLLOW(E)={#}规则二１１ )∈FOLLOW(E)FOLLOE(E)={)，#}FIRST(E’)-{ε}FOLLOW(T)FOLLOW(T)={+}FIRST(T’)-{ε}FOLLOW(F)FOLLOW(F)={(，a，b，∧}FIRST(F’)-{ε}FOLLOW(P)FOLLOW(P)={*}规则三FOLLOW(E)FOLLOW(E’)FOLLOW(E’)={#，)}FOLLOW(E)FOLLOW(T)FOLLOW(T)={＋，＃，）}FOLLOW(T)FOLLOW(T’)FOLLOW(T’)={＋，＃，）}FOLLOW(T)FOLLOW(F)FOLLOW(F)={(，)，a，b，＋，＃，∧}FOLLOW(F)FOLLOW(F’)FOLLOW(F’)={(，)，a，b，＋，＃，∧}FOLLOW(F)FOLLOW(P)FOLLOW(P)={(，)，a，b，＋，＃，∧,*}最后结果为：FIRST(E’)={+,ε}FIRST(F’)={*,ε}FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(，a，b，∧}FIRST(T’)={(，a，b,ε，∧)FOLLOE(E)={),＃}FOLLOW(E’)={＃，)}FOLLOW(T)={＋，＃，）}FOLLOW(T’)={＋，＃，）}FOLLOW(F)={(，)，a，b，＋，＃，∧}FOLLOW(F’)={(，)，a，b，＋，＃，∧}FOLLOW(P)={(，)，a，b，＋，＃，∧,*}（2）证明该文法是LL（1）文法：证明：对于规则E’::=+E|ε，T’::=T|ε，F’::=*F’|ε（仅有一边能推出空串）有FIRST(+E)={+}∩FIRST(ε)=ø，FIRST(T)={(,a,b,∧}∩FIRST(ε)=øFIRST(*F’)={*}∩FIRST(ε)=ø，FIRST(+E)={+}∩FOLLOW(E’)={#,)}=øFIRST(T)={(,a,b,∧}∩FOLLOW(T’)={+,#,)}=øFIRST(*F’)={*}∩FOLLOW(F’)={(，)，a，b，＋，＃，∧}=ø所以该文法是LL（1）文法。（3）构造文法分析表ab+*()∧#EE→TE’E→TE’E→TE’E→TE’E’E’→+EE’→εE’→εTT→FT’T→FT’T→FT’T→FT’１２ T’T’→TT’→TT’→εT’→TT’→εT’→TT’→εFF→PF’F→PF’F→PF’F→PF’F’F’→εF’→εF’→εF’→*F’F’→εF’→εF’→εF’→εPP→aP→bP→(E)P→∧下面分析符号串a*b+b步骤分析栈余留输入串所用的产生式1#Ea*b+b#E→TE’2#E’Ta*b+b#T→FT’3#E’T’Fa*b+b#F→PF’4#E’T’F’Pa*b+b#P→a5#E’T’F’aa*b+b#6#E’T’F’*b+b#F’→*F’7#E’T’F’**b+b#8#E’T’F’b+b#F’→ε9#E’T’b+b#T’→T10#E’Tb+b#T→FT’11#E’T’Fb+b#F→PF’12#E’T’F’Pb+b#P→b13#E’T’F’bb+b#14#E’T’F’+b#F’→ε15#E’T’+b#T’→ε16#E’+b#E’→+E17#E++b#18#Eb#E→TE’19#E’Tb#T→FT’20#E’T’Fb#F→PF’21#E’T’F’Pb#P→b22#E’T’F’bb#23#E’T’F’#F’→ε24#E’T’#T’→ε25#E’#E’→ε26##成功所以符号串a*b+b是该文法的句子；P1446.对下列文法，构造相应的FIRST和FOLLOW：（1）S∷＝aAdA∷＝BCB∷＝b|εC∷＝c|ε（2）A∷＝BCc|gDBB∷＝ε|bCDEC∷＝DaB|caD∷＝ε|dDE∷＝gAf|c１３ 解：（1）构造FIRST集FIRST(S)={a}FIRST(B)={b，ε}FIRST(C)={c，ε}FIRST(A)={b，c，ε}构造FOLLOW集规则一＃∈FOLLOW(S)FOLLOW(S)={#}规则二d∈FOLLOW(A)FOLLOE(A)={d}FIRST(C)-{ε}FOLLOW(B)FOLLOW(B)={c}规则三FOLLOW(A)FOLLOW(B)FOLLOW(B)={d，c}FOLLOW(A)FOLLOW(C)FOLLOW(C)={d}最后结果为：FIRST(S)={a}FIRST(A)={b，c，ε}FIRST(B)={b，ε}FIRST(C)={c，ε}FOLLOW(S)={#}FOLLOW(A)={d}FOLLOW(B)={d，c}FOLLOW(C)={d}（2）构造FIRST集规则二FIRST(A)={g},FIRST(B)={b，ε},FIRST(C)={c},FIRST(D)={d，ε},FIRST(E)={g，c}.规则三FIRST(A)={g，b，c},FIRST(C)={a，c，d},FIRST(A)={a，b，c，d，g}.构造FOLLOW集规则一＃∈FOLLOW(A)FOLLOW(A)={#}１４ 规则二f∈FOLLOW(A)FOLLOE(A)={f，＃}c∈FOLLOW(C)FOLLOE(C)={c}a∈FOLLOW(D)FOLLOE(D)={a}FIRST(Cc)-{ε}FOLLOW(B)FOLLOW(B)={c，d，a}FIRST(B)-{ε}FOLLOW(D)FOLLOW(D)={b，a}FIRST(DE)-{ε}FOLLOW(C)FOLLOW(C)={d，g，c}FIRST(E)FOLLOW(D)FOLLOW(D)={b，c，a，g}规则三FOLLOW(A)FOLLOW(B)FOLLOW(B)={a，c，d，f，#}FOLLOW(A)FOLLOW(D)FOLLOW(D)={a，b，c，f，g，＃}FOLLOW(B)FOLLOW(E)FOLLOW(E)={a，c，d，f，#}FOLLOW(C)FOLLOW(B)FOLLOW(B)={a，c，d，g，f，#}FOLLOW(B)FOLLOW(E)FOLLOW(E)={a，c，d，g，f，#}最后结果为：FIRST(A)={a，b，c，d，g},FIRST(B)={b，ε},FIRST(C)={a，c，d},FIRST(D)={d，ε},FIRST(E)={g，c},FOLLOE(A)={f，＃}FOLLOW(B)={a，c，d，g，f，#},FOLLOW(C)={d，g，c},FOLLOW(D)={a，b，c，f，g，＃},FOLLOW(E)={a，c，d，g，f，#}.P1449.设已给文法G[S]:S∷＝SaB|bBA∷＝SaB∷＝Ac（1）将此文法改写为LL（1）文法（4）构造LL（1）分析表解：此题消除左递归之后，构造LL（1）分析表存在“多重入口”问题，故采用以下方法：（1）改写为LL（1）文法：S∷＝bB{aB}１５ A∷＝SaB∷＝Ac（4）FIRST(S)={b},FIRST(A)={b},FIRST(B)={b},FOLLOE(S)={a，＃},FOLLOW(A)={c},FOLLOW(B)={a，＃}.abc#SS∷＝bB{aB}AA∷＝SaBB∷＝AcP14410.证明下述文法不是简单优先文法：（1）S∷＝bEbE∷＝E+T|T（2）S∷＝bEbE∷＝F|F+T|T|iT∷＝i|(E)证明：(1)画语法树：S╱│╲bEb╱│╲E+T可以得出b=E和b*i>*)>+T>+F>+(b)<说明表>=;BEGIN=<说明表>REAL=<标识符表><变量>=:=;=<语句表>:==iBEGIN<<说明>BEGIN;<<变量>;>;<标识符表>>;i>;i>:=P14513.利用表4.6文法G[E]的优先关系矩阵，来分析符号串#b(((aa)a)a)b#和#((aa)a)#。１６ (1)步骤符号栈关系输入串规则1#a)a)a)b#7#b(((M=a)a)a)b#M∷=a8#b(((Ma=)a)a)b#9#b(((Ma)>a)a)b#10#b(((L>a)a)b#L∷=Ma)11#b((M=a)a)b#M∷=(L12#b((Ma=)a)b#13#b((Ma)>a)b#14#b((L>a)b#L∷=Ma)15#b(M=a)b#M∷=(L16#b(Ma=)b#17#b(Ma)>b#18#b(L>b#L∷=Ma)19#bM=b#M∷=(L20#bMb>#21#Z>#Z∷=bMb(2)步骤符号栈关系输入串规则1#<((aa)a)#2#(<(aa)a)#3#((a)a)#5#((M=a)a)#M∷=a6#((Ma=)a)#7#((Ma)>a)#8#((L>a)#L∷=Ma)9#(M=a)#M∷=(L10#(Ma=)#11#(Ma)>#12#(L>#L∷=Ma)13#M>#M∷=(LP14619.证明下面文法不是算符优先文法:S∷＝A[]|[A∷＝aA|B]１７ B∷＝a证明：S→A[]SA→aAA[]∵A→aAaAA→B]∴a·<]B]∵A→B]aB→a∴a>·]a>·]和a·<]矛盾，所以该文法非算符优先文法P14621.利用表4.8文法G[E]优先关系矩阵分析下列句子:i,i+i,i*i+i,i*(i*i)以及i*(i+i*i)+((i+i)*i解：以i*i+i为例，其余类似：符号栈关系输入串最左素短语＃··*i+i#i＃∨·<*i+i#＃∨*··+i#i＃∨*∨>·+i#∨*∨＃∨·<+i#＃∨+··#i＃∨+∨>·#∨+∨＃∨#成功∴i*i+i是文法G[E]的句子；再以i*(i*i)为例：符号栈关系输入串最左素短语＃··*(i*i)#i＃∨·<*(i*i)#＃∨*·<(i*i)#＃∨*(··*i)#i＃∨*(∨·<*i)#＃∨*(∨*··)#i＃∨*(∨*∨>·)#∨*∨＃∨*(∨)#１８ ＃∨*(∨)>·#(∨)＃∨*∨>·#∨*∨＃∨#成功∴i*（i*i）是文法G[E]的句子；１９ 第十一次作业P14622.设有文法G[Z]:Z∷＝A|BA∷＝aAb|cB∷＝aBb|d（1）试构造能识别此文法的全部活前缀DFA；（2）试构造LR(0)分析表；（3）试分析符号串aacbb是否为此文法的句子。解：在上述文法中引入新的开始符号Z’，并将Z’::=Z作为第0个规则，从而得到所谓的拓广文法G’，则其LR（0）项目有：○1Z’::=·Z○2Z’::=Z·○3Z::=·A○4Z::=A·○5Z::=·B○6Z::=B·○7A::=·aAb○8A::=a·Ab○9A::=aA·b○10A::=aAb·○11B::=·aBb○12B::=a·Bb○13B::=aB·b○14B::=aBb·○15B::=·d○16B::=d·○17A::=·c⒅A::=c·(1)２０ (2)构造LR（0）分析表状态ACTIONGOTOabc#ZAB0S4S6S51231acc2r1r1r1r13r2r2r2r24S4S6S5785r4r4r4r46r6r6r6r67S98S109r3r3r3r310r5r5r5r5规则顺序：r1：Z→Ar2：Z→Br3:A→aAbr4:A→Cr5:B→aBbr6:B→d(3)分析符号串aacbb是否为该文法的句子步骤状态栈符号栈输入串分析动作下一状态10＃aaacbb＃S44204＃aacbb＃S443044＃aacbb＃S5540445＃aacbb＃r4GOTO[4,A]=750447＃aaAbb＃S99604479＃aaAbb＃r3GOTO[4,A]=77047＃aAb＃S9980479＃aAb＃r3GOTO[0,A]=2902＃A＃r1GOTO[0,Z]=11001＃Z＃acc成功２１ 第十二次作业P14724.给定文法：E∷＝EE+|EE*|a（1）构造它的LR(0)项目集规范族；（2）它是SLR(1)文法吗？若是，构造它的SLR(1)分析表；解：(1)在上述文法中引入新的开始符号E’,并将E’作为第0个规则r1:E∷=EE+r2:E∷=EE*r3:E∷=a则基本LR(0)项目集为：⑴E’∷=•E⑵E’∷=E•⑶E∷=•EE+⑷E∷=E•E+⑸E∷=EE•+⑹E∷=EE+•⑺E∷=•EE*⑻E∷=E•E*⑼E∷=EE•*⑽E∷=EE*•⑾E∷=•a⑿E∷=a•I0:E’∷=•EEI1:E’∷=E•EI3:E∷=•a+E∷=•EE+E∷=E•E+E∷=EE•+I4:E∷=EE+•E∷=•EE*E∷=•EE+E∷=E•E+E∷=•aE∷=E•E*E∷=•EE+E∷=•EE*E∷=EE•**I5:E∷=EE*•E∷=•aE∷=E•E*E∷=•EE*aaI2:E∷=a•aE(2)在I1中存在“移进E->•a”和“归约：E’->E•”冲突，因此该文法不是LR(0)文法，但有FOLLOW(E’)={#}∩{a}=Ф，而该动作冲突可用SLR(1)方法解决，该文法是SLR(1)文法，其分析表如下：ACTIONGOTO状态+*a#E0S211S2acc32r3r3r33S4S5S234r1r1r15r2r2r2(3)拓广文法：①S’::=E②E::=EE+③E::=EE*④E::=a识别G[S’]的LR(1)项目集及状态转移图如下：２２ I1：S’→E.,#aI4:E→a.,a/+/*E→E.E+,#/aaEE→E.E*,#/aaE→.EE+,+/a/*I5：E→.EE*,*/a/+E→EE.+,a/+/*EI3：E→.a,+/*/aE→EE.*,a/+/*E→EE.+,#/aE→E.E+,a/+/*EE→EE.*,#/a+EE→E.E*,a/+/*I8:E→EE+.,a/+/*E→E.E+,+/a/*E→.EE+,a/+/*I0：S’→.E,#E→E.E*,+/a/*E→.EE*,a/+/*E→.EE+,#/aE→.EE+,+/a/*E→.a,+/*/a*I9:E→EE*.,a/+/*E→.EE*,#/aE→.EE*,+/a/*E→.a,#/aE→.a,+/*/a+I6:E→EE+.,#/aa*I2:E→a.,#/aI7:E→EE*.,#/a文法G[S’]LR(1)分析表：Actiongoto状态+*a#E0S211S4acc32r4r43S6S7S454r4r4r45S8S9S456r2r27r3r38r2r2r29r3r3r3不存在多重定义的元素，所以该文法是LR(1)文法。（4）为LALR(1)文法，其分析如下：Actiongoto状态+*a#E0S2411S24acc3524r4r4r4r435S68S79S243568r2r2r2r279r3r3r3r3２３ P1942.给出下面表达式的后缀式表示：解：(2)┐a∨┐(c∨┐d):a┐cd┐∨┐∨(3)a+b*(c+d/e):abcde/+*+(4)(a∧b)∨(┐c∨d):ab∧c┐d∨∨(5)–a+b*(-c+d):a-bc-d+*+(6)(a∨b)∧(c∨┐d∧e):ab∨cd┐e∧∨∧(7)if(x+y)*z<>0then(a+b)↑celsea↑b↑c:xy+z*p1JEZab+c↑p2JUMPab↑c↑２４'