《编译原理》习题解答 南京邮电大学版.doc 48页

'《编译原理》习题解答：第一次作业：P142、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？答：被翻译的程序称为源程序；翻译出来的程序称为目标程序或目标代码；将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；编译程序是将高级语言写的源程序翻译成目标语言的程序。关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4图1.3。P143、编译程序是由哪些部分组成？试述各部分的功能？答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。P144、语法分析和语义分析有什么不同？试举例说明。答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量x：=y符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。P155、编译程序分遍由哪些因素决定？答：计算机存储容量大小；编译程序功能强弱；源语言繁简；目标程序优化程度；设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。补充：1、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。补充：2、赋值语句：A：=5*C的语法和语义指的是什么？答：语法分析将检查该语句是否符合赋值语句规则，语义是指将5*C的结果赋值为A。第二次作业：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……}P383、令A＝{0，1，2}，写出集合A+和A*的七个最短符号串。４８ A+：0，1，2，00，01，02，10（有多种可能）A*：ε，0，1，2，00，01，02（有多种可能）P385、试证明：A+＝AA*＝A*A。证明：A+＝A1∪A2∪……∪An∪……A*＝A0（即{ε}）∪A+AA*＝A（A0∪A+）＝A∪A2∪A3∪A4……＝A+＝A+∪A＝（A0∪A+）A＝A*A（证毕）P387、设有文法G[S]：S∷＝AA∷＝B|IFATHENAELSEAB∷＝C|B+C|+CC∷＝D|C*D|*DD∷＝X|(A)|-D试写出VN和VT。VN＝{S，A，B，C，D}VT＝{IF，THEN，ELSE，+，*，X，(，)，-}P38-398、设有文法G[S]：S∷＝aAbA∷＝BcA|BB∷＝idt|ε试问下列符号串（1）aidtcBcAb（3）ab（5）aidtcidtcidtb是否为该文法的句型或句子。（1）SaAbaBcAbaidtcAbaidtcBcAb句型但不是句子；（3）SaAbaBbaεbab是句型也是句子；（5）SaAbaBcAbaidtcAbaidtcBcAbaidtcidtcBbaidtcidtcidtb句型也是句子。P3910、给定文法：S∷＝aB|bAA∷＝aS|bAA|aB∷＝bS|aBB|b该文法所描述的语言是什么？L(G)＝{相同个数的a与b以任意次序连接而成的非空符号串}。P3911、试分别描述下列文法所产生的语言（文法开始符号为S）：（1）S∷＝0S|01（2）S∷＝aaS|bc（3）S::=aSd|aAdA::=aAc|bc（4）S::=ABA::=aAb|abB::=cBd|ε（1）L(G)＝{0n1|n≥1}；{解题思路：将文法转换为正规表达式}（2）L(G)＝{a2nbc|n≥0}；４８ （1）L(G)＝{aibcjdk|i,j,k≥1,i=j+k-1}；或者L(G)＝{aj+k-1bcjdk|j,k≥1}；（2）L(G)＝{anbncmdm|m≥0,n≥1}。P3912、试分别构造产生下列语言的文法：（1）{abna|n=0，1，2，3……}（2）{anbn|n=1，2，3，4……}（3）{aban|n≥1}（4）{anbam|n,m≥1}（5）{anbmcp|n，m，p≥0}（6）{ambmcp|m，p≥0}（1）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，P：S∷＝aAa或S∷＝aBA∷＝bA|εB∷＝bB|a（2）G＝{VN，VT，P，S}，VN＝{S}，VT＝{a，b}，P：S∷＝aSb|ε（3）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，P：S∷＝abA或S∷＝Sa|abaA∷＝aA|a（4）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，P：S∷＝aS|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|ε（6）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b，c}，P：S∷＝aSbA|εA∷＝cA|ε４８ 第三次作业：P3915.设文法G规则为：S：：=ABB：：=a|SbA：：=Aa|bB对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。（2）baabaab(3)bBABb（2）SABAaSbbBABabBaa句型baabaab的短语a,ba,baa,baab,baabaab，简单短语a，句柄aS（3）ABbBSbAB短语bB,AB,ABb，bBABb简单短语bB,AB，句柄bBP4018.分别对i+i*i和i+i+i中每一个句子构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。<表达式>：：=i|(<表达式>)|<表达式><运算符><表达式><运算符>：：=+|-|*|/1．i+i*i<表达式><表达式><运算符><表达式>i+<表达式><运算符><表达式>i*i<表达式>４８ <表达式><运算符><表达式><表达式><运算符><表达式>*ii+i由于句子i+i*i可构造两棵不同的语法树，所以证明该文法是二义的。2.i+i+i<表达式><表达式><运算符><表达式>i+<表达式><运算符><表达式>i+i<表达式><表达式><运算符><表达式><表达式><运算符><表达式>+ii+i由于句子i+i+i可构造两棵不同的语法树，所以证明该文法是二义的。P4019.证明下述文法是二义的1)S::=iSeS|iS|i2)S::=iEtS|iEtSeS|aE::=b存在句子ibtibtaeibta或者ibtibtaea有两颗不同的语法树3)S::=A|BA::=aCbA|aB::=BCC|aC::=ba(最简单的就是a为句型)1)对于句子iiieii可构造两棵不同的语法树，所以证明该文法是二义的。SiSeSiSiSiiS４８ iSiSeSiiSi3）对于句子ababa可构造两棵不同的语法树，所以证明该文法是二义的。SAaCbAbaaSBBCCababaP4121.令文法N：：=D|NDD：：=0|1|2|3|4|5|6|7|8|9给出句子0127，34，568最左推导和最右推导。解：0127的最左推导N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>01270127的最右推导N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>012734的最左推导N=>ND=>DD=>3D=>3434的最右推导N=>ND=>N4=>D4=>34568的最左推导N=>ND=>NDD=>DDD=>5DD=>56D=>568568的最右推导N=>ND=>N8=>ND8=>N68=>D68=>568P4123.设有文法如下：<目标>::=V1V1::=V2|V1iV2V2::=V3|V2+V3|iV3V3::=)V1*|(４８ 试分析句子(,)(*,i(,(+(,(+(i(,(+)(i(*i(。解<目标>=>V1=>V2=>V3=>(<目标>=>V1=>V2=>V3=>)V1*=>)V2*=>)V3*=>)(*<目标>=>V1=>V2=>iV3=>i(<目标>=>V1=>V2=>V2+V3=>V3+V3=>(+V3=>(+(<目标>=>V1=>V1iV2=>V1iV3=>V1i(=>V2i(=>V2+V3i(=>V2+(i(=>V3+(i(=>(+(i(<目标>=>V1=>V1iV2=>V2iV2=>V2+V3iV2=>V3+V3iV2=>(+V3iV2=>(+)V1*iV2=>(+)V1iV2*iV2=>(+)V2iV2*iV2=>(+)V3iV2*iV2=>(+)(iV2*iV2=>(+)(iV2*iV2=>(+)(iV3*iV2=>(+)(i(*iV2=>(+)(i(*iV3=>(+)(i(*i(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正规文法127或者1上下文无关文法568或者25678上下文有关文法3短语结构文法4P4126.给出产生下列语言L（G）={W|W∈{0，1}+且W不含相邻1}的正规文法。G=({S,A,B},{0,1},P,S)P:S::=0|1|0S|1AA::=0|0S解题思路一：写出满足要求的符号串，例如0，1，00，01，10，000，101，010，001等，根据符号串从左至右的次序画出状态转换图，然后根据状态转换图来推导出文法。这将会得到S::=0|1|0S|1A|0Z|1ZA::=0|0S|0Z经过分析其中Z为多余状态可删去。SZ100100A解题思路二：写出其正规表达式(0|10)*(10|0|1)【如果仅有(0|10)*的话推导不出1，因为是连接关系，后面缺了10的话就会以1结尾，同样的道理还要推导出0，所以得到此正规式】，画出转换系统，然后根据转换系统来推导出文法。也可以根据正规表达式直接写文法，例如正规表达式(0|10)*(10|0|1)可以看成是a*b，推导出A::=(0|10)A|10|0|1，即A::=0A|1B|４８ 10|0|1，其中B::=0A，但是10此项不符合正规文法的选项，可以进行改写从而得到A::=0A|1B|0|1B::=0A|0。P4127.给出一个产生下列语言L（G）＝{W|W∈{a,b}*且W中含a的个数是b个数两倍的前后文无关文法。文法G=({S,A,B},{a,b},P,S)P:S::=AAB|ABA|BAA|εA::=aSB::=bS或者S::=Saab|aSab|aaSb|aabS|Saba|aSba|abSa|abaS|Sbaa|bSaa|baSa|baaS|ε或者S::=aaB|aBa|Baa|εB::=SbSP4128.给出一个产生下列语言L(G)={w|w∈{a,b,c}+且w由相同个数的a，b，c组成的前后文有关文法。文法G=({S,A,B},{a,b,c},P,S)P:S::=ABCA::=aS|aB::=bS|bC::=cS|cAB::=BABC::=CBAC::=CAP4229.用扩充的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}第四次作业：P742.什么叫超前搜索？扫描缓冲区的作用是什么？词法分析程序在识别单词的时候，为进一步判明情况，确定下一步要做什么，一般采用超前读字符的方法，称超前搜索，扫描缓冲区的作用是为了识别单词符号。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}SZ’001A0ZS’εε显然该文法的自动机是非确定的；它相应的语言为：{0，1}上所有满足以00开头以0结尾且每个1必有0直接跟在其后的字符串的集合；也可以通过求解正规表达式得到A=0(0|01)*，Z=0(0|01)*0那么如何构造其相应的有穷自动机呢？先构造其转换系统：根据其转换系统可得状态转换集、状态子集转换矩阵如下表所示：(其中S’可以忽略，结果是一样的)II0I1S01{S’,S}{A}Ф01Ф{A}{A,Z,Z’}Ф12Ф{A,Z,Z’}{A,Z,Z’}{A}2211201000则其相应的DFA为：P747.构造一个DFA，它接受{0，1}上所有满足下述条件的字符串，其条件是：字符串中每个1都有0直接跟在右边，然后，再构造该语言的正规文法。【其它解法可参考P41-26题】0解(一)：其状态转换图为(状态S表示空串开始，状态A表明串的末尾是1，状态Z表示串的末尾是0)01SZA01DFA=（{S，A，Z}，{0，1}，M，S，{Z}）其中M：M（S，0）=ZM（S，1）=AM（A，0）=Z４８ M（Z，0）=ZM（Z，1）=A该语言的正规文法G[Z]为：右线性文法：//S：：=0|1A|0Z左线性文法：A：：=0|0ZA：：=1|Z1Z：：=0|1A|0ZZ：：=0|A0|Z0若终止状态只引入不引出则适合构造右线性文法，若开始状态只引出不引入则适合构造左线性文法，若终态和初态均既有引入又有引出，则构造文法要注意。解(二)：可以先写出该文法的正规表达式为(0|10)*，根据该正规式构造转换系统SZAεε01B0A01B0对于该转换系统可以采用子集法将其转变为DFA，再根据DFA写出其正规文法；但是注意观察后，发现开始状态S通过ε到达A状态，可以直接删去S状态，由A状态作为新的开始状态，同理，只有A状态通过ε才能到达终止状态Z，因此可以删去Z状态，由A状态作为终止状态。这样，A状态就既为开始状态又为终止状态。可画出化简后的转换图。可写出右线性文法为：A：：=0|0A|1BB：：=0|0SP748.设(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如下所示：４８ P749.设有穷自动机M=({S,A,E},{a,b,c},M,S,{E})，其中M定义为M(S,c)=AM(A,b)=AM(A,a)=E请构造一个左线性文法。解：先求右线性文法S→cAA→bAA→a|aE{A→aE实际上是多余的规则，应该去掉}其左线性文法G=（VN,VT,P,S）VN={A,S}VT={a,b,c}根据书上左右线性文法的转换规则，得到P:A→cA→AbS→Aa{E→Aa实际上是多余的规则，应该去掉}画出状态转换图之后就非常清晰。P7410.已知正规文法G=({S,B,C},{a,b,c},P,S)，其中P内包含如下产生式：S::=aS|aB……①B::=bB|bC……②C::=cC|c……③请构造一个等价的有穷自动机。解：M=({S,B,C,T},{a,b,c},M,{S},{T})M(S,a)=SM(S,a)=BM(S,b)=øM(S,c)=øM(B,a)=øM(B,b)=BM(B,b)=CM(B,c)=øM(C,a)=øM(C,b)=øM(C,c)=TM(C,c)=C第六次作业：P7411.构造下列正规式相应的DFA：（1）1(0|1)*101【老课本】解：先构造该正规式的转换系统：SZ1(0|1)*101S1534Z1101(0|1)*S1534Z11012εε01由上述转换系统可得状态转换集K={S,1,2,3,4,5,Z}，状态子集转换矩阵如下表所示：II0I1K01{S}Ф{1,2,3}0Ф1{1,2,3}{2,3}{2,3,4}123４８ {2,3}{2,3}{2,3,4}223{2,3,4}{2,3,5}{2,3,4}343{2,3,5}{2,3}{2,3,4,Z}425{2,3,4,Z}{2,3,5}{2,3,4}543其对应的DFA状态转换图为：051123100114001100511,23401111000现在对该DFA进行化简，最终得到下列化简后的状态转换图（先将其分成两组——终态组{5}和非终态组{0,1,2,3,4}，再根据是否可继续划分来确定最后的组数）：（1）(0|11*0)*【新课本】解：先构造该正规式的转换系统：SZ(0|11*0)*SZε10ε213ε10ε4SZε10ε11*0由上述转换系统可得状态转换集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}313４８ 113000010112由状态子集转换矩阵可知，状态0和1是等价的，而状态2和3是等价的，因此，合并等价状态之后只剩下2个状态，也即是最少状态的DFA。100101P7412.将图3.24非确定有穷自动机NFA确定化和最少化。10aa,ba图3.24NFA状态转换图解：设(DFA)M={K,VT,M,S,Z}，其中，K={[0],[0,1],[1]}，VT={a,b}，M：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]}10abaa2b令[0,1]=2，则其相应的状态转换图为：现在对该DFA进行化简，先把状态分为两组：终态组{0,2}和非终态组{1}，易于发现{0,2}不可以继续划分，因此化简后的状态转换图如下：10,2abaP7413.构造下列正规式的DFA：（1）b(a|b)*bab此题的与P74第11题基本一样，见上；P7415.用两种方法将(NFA)M=({X,Y,Z},{0,1},M,{X},{Z})，构造相应的DFA，其中：M(X,0)={Z}M(X,1)={X}M(Y,0)={X,Y}４８ M(Y,1)=ФM(Z,0)={X,Z}M(Z,1)={Y}XZ101000Y0第一种方法：先画出其状态转换图，利用非子集法：假设(DFA)M’=(K’,VT’,M’,S’,Z’)，其中K’={[X],[Y],[Z],[X,Y],[X,Z],[Y,Z],[X,Y,Z]}，VT’={0,1}，M’的规则如下表：II0I1K01[X][Z][X]020[Y][X,Y]Ф13Ф[Z][X,Z][Y]241[X,Y][X,Y,Z][X]360[X,Z][X,Z][X,Y]443[Y,Z][X,Y,Z][Y]561[X,Y,Z][X,Y,Z][X,Y]663其中[Y,Z]为不可到达状态，应该删去，所以S’={[X]}，Z’={[Z],[X,Z],[X,Y,Z]}，再进行化简，发现4和6两状态等价，最后其DFA如下所示：0110001301124,60XZ’101000Y0ZSεε第二种方法：先构造其对应的转换系统：由上述转换系统可得状态转换集、状态子集转换矩阵如下表所示：II0I1K01４８ {S,X}{Z,Z’}{X}012{Z,Z’}{X,Z,Z’}{Y}134{X}{Z,Z’}{X}212{X,Z,Z’}{X,Z,Z’}{X,Y}335{Y}{X,Y}Ф45Ф{X,Y}{X,Y,Z,Z’}{X}562{X,Y,Z,Z’}{X,Y,Z,Z’}{X,Y}665141050001013,610,2先化简，分为非终态集{2,4,5,0}和终态集{6,1,3}，易于发现可划分为{0,2}，{1}，{3,6}，{4}，{5}，其DFA如下所示：P7416.已知e1=(a|b)*，e2=(a*b*)*，试证明e1=e2。证明：L(e1)=L((a|b)*)=(L(a|b))*=(L(a)∪L(b))*={a,b}*；L(e2)=L((a*b*)*)=(L(a*b*))*=(L(a*)L(b*))*={{a}*{b}*}*={a,b}*；因此e1=e2（得证）P7418.根据下面正规文法构造等价的正规表达式：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)|aP7419.Σ＝{a,b}，写出下列正规集：（1）(a|b)*(aa|bb)(a|b)*解：L((a|b)*(aa|bb)(a|b)*)=L((a|b)*)L((aa|bb))L((a|b)*)=(L(a|b))*{aa,bb}(L(a|b))*={a,b}*{aa,bb}{a,b}*P7520.证明下列关系式成立，其中A、B是任意正规表达式。（1）A|A=A（3）A*=ε|AA*（4）(AB)*A=A(BA)*（1）解：L(A|A)=L(A)∪L(A)=L(A)，所以A|A=A；（3）解：L(A*)=(L(A))*，L(ε|AA*)={ε}∪L(A)L(A*)=(L(A))*，所以A*=ε|AA*；４８ （4）解：(AB)*A=((AB)0∪(AB)1∪(AB)2∪……)A=A∪ABA∪ABABA∪……=A((BA)0∪(BA)1∪(BA)2∪……)=A(BA)*。第七次作业：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::=*|/（4）G[Z]:Z::=V1……①V1::=V2|V1iV2……②V2::=V3|V2+V3……③V3::=)V1*|(……④解：先采用“重复法”：再采用“改写法”：Z::=V1Z::=V1V1::=V2{iV2}V1::=V2V1’V2::=V3{+V3}V1’::=iV2V1’|εV3::=)V1*|(V2::=V3V2’V2’::=+V3V2’|εV3::=)V1*|(P1422.试分别消除下列文法的间接左递归（2）G[Z]:Z::=AZ|b……①A::=ZA|a……②解(一)：将②式代入①式可得，Z::=ZAZ|aZ|b消除左递归后得到：Z::=(aZ|b)Z’Z’::=AZZ’|εA::=ZA|a解(二)：将①式代入②式可得，A::=AZA|bA|a消除左递归后得到：Z::=AZ|bA::=bAA’|aA’A’::=ZAA’|ε４８ P1424.试分别用两种方法（框图法和类Pascal语言或类C语言）写一个识别下面文法句子的递归子程序文法G[A]:A::=[B……①B::=X]|BA……②X::=Xa|Xb|a|b……③解：消除该文法的左递归和回溯，得到文法如下：A::=[BB::=X]B’B’::=AB’|εX::=aX’|bX’X’::=aX’|bX’|ε用类Pascal语言写出其递归子程序：P(A):SCINIFch=’[‘THENREAD(ch)ELSEERRORP(B)SCOUTP(B):SCINP(X)IFch=’]‘THENREAD(ch)ELSEERRORP(B’)SCOUTP(B’):SCINIFch=’#’THENSCOUTELSEP(A)P(B’)SCOUTP(X):SCINIFch=’a‘THEN{READ(ch)P(X’)}ELSEIFch=’b‘THEN{READ(ch)P(X’)}ELSEERRORSCOUTP(X’):SCINIFch=’]’THENSCOUTELSEIFch=’a‘THEN{READ(ch)P(X’)}ELSEIFch=’b‘THEN{READ(ch)P(X’)}ELSEERRORSCOUT用框图法来表述：（此处仅给出P(A)和P(X’)的框图形式，其余相似从略）当消除左递归和回溯之后，可能某些非终结符号例如U的右部会出现ε４８ 的情况，书上的处理方法是ε将自动获得匹配，并无对此类规则的具体处理方法，实际上应该求出FOLLOW(U)，对于FOLLOW(U)中的每个终结符号进行判定，例如此例中的P(X’)，否则将无法判定出[a]SCIN1ch=]?=32READP(X’)SCOUT<>4107ch=a?=5P(X’)<>6ch=b?=8READ<>9ERRORP(A):P(X’):SCIN1ch=[?<>3ERROR2READP(B)SCOUT=456第八次作业：P1435.对下面的文法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∷＝Sa|aB∷＝Ac（1）将此文法改写为LL（1）文法（4）构造LL（1）分析表解：该题消除左递归之后，文法变为S∷＝bBS’S’∷＝aBS’|εA∷＝Sa|aB∷＝AcFIRST(S)={b},FIRST(A)={a,b},４８ FIRST(B)={a,b},FOLLOE(S)={a，＃},FOLLOW(S’)={a，#},FOLLOW(A)={c},FOLLOW(B)={a，＃}.abc#SS∷＝bBS’AA∷＝aA∷＝SaBB∷＝AcB∷＝AcS’S’∷＝aBS’，S’∷＝εS’∷＝ε存在冲突，不是LL(1)文法，主要的冲突在于[S’,a]此栏，是LL(2)文法，即每次遇见当前非终结符号为S’时，要向前看两个符号才可，改写以上LL(1)分析表如下：a(第一个字符)bc#SS∷＝bBS’AA∷＝aA∷＝SaBB∷＝AcB∷＝AcS’a或b(第二个字符)c(第二个字符)S’∷＝aBS’S’∷＝εS’∷＝ε第九次作业：P14410.证明下述文法不是简单优先文法：（1）S∷＝bEbE∷＝E+T|T（2）S∷＝bEbE∷＝F|F+T|T|iT∷＝i|(E)证明：(1)画语法树：S╱│╲bEb╱│╲E+T可以得出b=E和beb000001000因此冲突，不是简答优先文法优先关系矩阵如下：４８ SMUiEteabSM=Ui=E=t==e==ab其中含多重定义的表项，因而该文法不是简单优先文法。P14512.根据图4.25的语法树，确定全部优先关系：(a)E=++=TT=**=F(=EE=)*<(+*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∷=(L４８ 20#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∷=(L第十次作业：P14617.设已给文法G[S]:E∷＝E+T|TT∷＝T*F|FF∷＝P↑F|PP∷＝(E)|i（1）构造此文法的算符优先矩阵；（2）用迭代法构造优先函数；（3）用有向图法构造优先函数；（4）用优先函数表分析符号串i+i*i↑i解：（1）ETFP(i*+)↑E0000000000T0000000000BF0000000000=P0000000000(0000000010i0000000000*0000000000+0000000000)0000000000↑0000000000４８ ETFP(i*+)↑E0000000110T0000001000BF0000000000=P0000000001(1000000000i0000000000*0010000000+0100000000)0000000000↑0010000000ETFP(i*+)↑E1100000000T0110000000BLF0001000000=P0000110000(0000000000i0000000000*0000000000+0000000000)0000000000↑0000000000ETFP(i*+)↑E1111110000T0111110000BL*F0011110000=P0001110000(0000100000i0000010000*0000001000+0000000100)0000000010↑0000000001ETFP(i*+)↑E0000000100T0000001000BL1F0000000001=P0000110000(0000000000i0000000000*0000000000+0000000000)0000000000↑0000000000４８ BL1BL*BB·<==ETFP(i*+)↑ETFP(i*+)↑E0000000110E0000000100T0000001000T0000001000B··=ETFP(i*+)↑E0000011111T0000011011B（R*）（R1）F0000010011=P0000010010(0000000000i0001000000*0100000000+1000000000)0001000000↑0010000000４８ ETFP(i*+)↑E0000000000T0000000000B(（R*）（R1）)TF0000000000=P0000000000(0000000000i1111000000*1100000000+1000000000)1111000000↑1110000000ETFP(i*+)↑ETFP(i*+)↑E0000000000E0000000110T0000000000T0000001000∴B>·F0000000000F0000000000=P0000000000P0000000001(0000000000×(1000000000i1111000000i0000000000*1100000000*0010000000+1000000000+0100000000)1111000000)0000000000↑1110000000↑0010000000ETFP(i*+)↑E0000000000T0000000000B>·F0000000000=P0000000000(0000000000i0000001111*0000001110+0000000110)0000001111↑0000001110(i*+)↑(·<·<·<·<=··>·>·>·*·<·<>·>·>··<+·<·<·<>·>··<)>·>·>·>·↑·<·<>·>·>··<或４８ +*↑()i+>··<·<·<>··<*>·>··<·<>··<↑>·>··<·<>··<(·<·<·<·<=·<)>·>·>·>·i>·>·>·>·（2）用迭代法构造优先函数若R=S则f(R）=g(S)若R··S则f(R）>g(S)初始值＋*↑()if111111g111111根据·<的优先关系修改f和g值＋*↑()if111111g222212根据>·的优先关系修改f和g值＋*↑()if333133g222212根据=的优先关系修改f和g值＋*↑()if333133g244414重复―＋*↑()if355155g244414＋*↑()if355155g246616＋*↑()if355177g246616最终结果：＋*↑()i４８ f355177g246616（3）+*↑()i)(↑*+i优先函数为：＋*↑()if466299g358828（4）用优先函数表分析字符串i+i*i↑i符号栈关系输入串最左素短语＃f(#)··g(+)+i*i↑i#i＃∨f(#)··g(*)*i↑i#i＃∨＋∨f(+)··g(↑)↑i#i＃∨＋∨*∨f(*)··g(#)#i＃∨＋∨*∨↑∨f(↑)>·g(#)#∨↑∨４８ ＃∨＋∨*∨f(*)>·g#)#∨*∨＃∨＋∨f(+)>·g(#)#∨＋∨＃∨#成功P14619.证明下面文法不是算符优先文法:S∷＝A[]|[A∷＝aA|B]B∷＝aS证明：S→A[]A→aAA][Aa∵A→aAA→B]B]∴a·<]a∵A→B]B→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）项目有：Z’::=·ZZ’::=Z·Z::=·AZ::=A·Z::=·BZ::=B·A::=·aAbA::=a·AbA::=aA·bA::=aAb·B::=·aBbB::=a·BbB::=aB·bB::=aBb·B::=·dB::=d·A::=·c⒅A::=c·(1)４８ ZI0:Z’::=·ZZ::=·AZ::=·BA::=·aAbA::=·cB::=·aBbB::=·dI1:Z’::=Z·I5:A::=c·I4:A::=a·AbA::=·aAbA::=·cB::=a·BbB::=·aBbB::=·dI3:Z::=B·I2:Z::=A·I6:B::=d·I7:A::=aA·bI8:B::=aB·bI10:B::=aBb·I9:A::=aAb·bABacdacdAbB(2)构造LR（0）分析表状态ACTIONGOTOabcd#ZAB0S4S5S6123781acc2r1r1r1r1r13r2r2r2r2r24S4S5S65r4r4r4r4r46r6r6r6r6r67S98S109r3r3r3r3r310r5r5r5r5r5规则顺序：r1：Z→Ar2：Z→Br3:A→aAbr4:A→Cr5:B→aBbr6:B→d(3)分析符号串aacbb是否为该文法的句子步骤状态栈符号栈输入串分析动作下一状态10＃aacbb＃S44204＃aacbb＃S443044＃aacbb＃S55４８ 40445＃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)分析表；（3）它是LR(1)文法吗？若是，构造它的LR(1)分析表；（4）它是LALR(1)吗？若是，构造它的LALR(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•E*+aEEaI5:E∷=EE*•I4:E∷=EE+•I2:E∷=a•I3:E∷=•aE∷=EE•+E∷=E•E+E∷=•EE+E∷=EE•*E∷=E•E*E∷=•EE*I1:E’∷=E•E∷=E•E+E∷=•EE+E∷=E•E*E∷=•EE*E∷=•aI0:E’∷=•EE∷=•EE+E∷=•EE*E∷=•aa(2)在I1中存在“移进E->•a”和“归约：E’->E•”冲突，因此该文法不是LR(0)文法，但有FOLLOW(E’)={#}∩{a}=Ф，而该动作冲突可用SLR(1)方法解决，该文法是SLR(1)文法，其分析表如下：状态ACTIONGOTO+*a#E0S211S2acc32r3r3r3r33S4S5S23４８ 4r1r1r1r15r2r2r2r2(3)拓广文法：①S’::=E②E::=EE+③E::=EE*④E::=a识别G[S’]的LR(1)项目集及状态转移图如下：I0：S’→.E,#E→.EE+,#/aE→.EE*,#/aE→.a,#/aI1：S’→E.,#E→E.E+,#/aE→E.E*,#/aE→.EE+,+/a/*E→.EE*,*/a/+E→.a,+/*/aI4:E→a.,a/+/*I8:E→EE+.,a/+/*EI2:E→a.,#/aaI3：E→EE.+,#/aE→EE.*,#/aE→E.E+,+/a/*E→E.E*,+/a/*E→.EE+,+/a/*E→.EE*,+/a/*E→.a,+/*/aI9:E→EE*.,a/+/*aEaI5：E→EE.+,a/+/*E→EE.*,a/+/*E→E.E+,a/+/*E→E.E*,a/+/*E→.EE+,a/+/*E→.EE*,a/+/*E→.a,+/*/a+*EaEI6:E→EE+.,#/aI7:E→EE*.,#/a*+文法G[S’]LR(1)分析表：状态Actiongoto+*a#E0123456789S6r4S8r2r3S7r4S9r2r3S2S4r4S4r4S4r2r3r2r3accr4r2r31355不存在多重定义的元素，所以该文法是LR(1)文法。（4）为LALR(1)文法，其分析如下：状态Actiongoto+*a#E４８ 0124356879r4S68r2r3r4S79r2r3S24S24r4S24r2r3accr4r2r313535P14726.对如下文法G：S∷＝S(S)S∷＝ε构造LR(1)项目规范集以及LR(1)分析表，并用分析器给出(())的分析过程。解：()()(SSSI6:S->S(S•),(,)S->S•(S),(,)I5:S->S(•S),(,)S->•(,)S->•S(S),(,)I7:S->S(S)•),(I4:S->S(S)•,#,(I0:S’->•S,#S->•S(S),#,(S->•#,(I3:S->S(S•)#,(S->S•(S),(,)I2:S->S(•S),#,(S->•(,)S->•S(S),(,)I1:S’->S•,#S->S•(S),#,(引入开始符号S’。则拓广文法：S’->S，S->S(S)，S->ε。其中r1:S->S(S)r2:S->εLR(1)分析表如下所示：状态ACTIONGOTO（）#S0r2r211S2acc2r2r233S5S44r1r15r2r266S5S77r1r1分析符号串（（））步骤状态栈符号栈输入串分析动作下一状态00#(())#r2GOTO[0,S]=1101#S(())#S222012#S(())#r2GOTO[2,S]=330123#S(S())#S55401235#S(S())#r2GOTO[5,S]=65012356#S(S(S))#S7760123567#S(S(S))#r1GOTO[2,S]=370123#S(S)#S44801234#S(S)#r1GOTO[0,S]=1４８ 901#S#acc成功P14830.给出如下文法：G1[S]:S∷＝aSbS|aS|cG2[S]:S∷＝aAa|aBbA∷＝xB∷＝xG3[S]:S∷＝aAa|aBb|bAbA∷＝xB∷＝xG4[S]:S∷＝aAa|aBb|bAb|bBaA∷＝xB∷＝x（1）证明二义性文法G1[S]不是LR(0)文法；（2）证明G2[S]是SLR(1)文法但不是LR(0)文法；（3）证明G3[S]是LR(1)文法但不是SLR(1)文法；（4）证明G4[S]是LR(1)文法但不是LALR文法。(1)证明：构造其LR(0)项目集：I0:S’->•SS->•aSbSS->•aSS->•cI1:S->a•SbSS->a•SS->•cS->•aSbSS->•aSI2:S->aS•bSS->aS•因为I2中出现了“移进-归约”冲突，因此不是LR(0)文法；(2)证明：构造其LR(0)项目集：I0:S’->•SS->•aAaS->•aBbI1:S’->S•I2:S->a•AaS->a•BbA->•xB->•xI3:S->aA•aI4:S->aB•bI5:A->x•B->x•I6:S->aAa•I7:S->aBb•由于I5中出现了“归约-规约”冲突，因此G2[S]不是LR(0)文法；∵FOLLOW(A)={a}∩FOLLOW(B)={b}=Φ∴ACTION[i,a]=“用产生式A->x进行归约”；ACTION[i,b]=“用产生式B->x进行归约”；因而该文法为SLR(1)文法。(3)证明：构造其LR(1)项目集：I0:S’->•S,#S->•aAa,#S->•aBb,#S->•bAb,#I1:S’->S•,#I2:S->a•Aa,#A->•x,aS->a•Bb,#B->•x,bI3:S->b•Ab,#A->•x,bI4:A->x•,aB->x•,b（其余从略）此时由I4可知存在“归约-归约”冲突，且FOLLOW(A)={a,b}∩FOLLOW(B)={b}≠Ф故该文法不是SLR(1)文法，但有ACTION[i,a]=“用产生式A->x进行归约”，ACTION[i,b]=“用产生式B->x进行归约”，所以是LR(1)文法。(4)证明：构造其LR(1)项目规范集：I0:S’->•S,#S->•aAa,#S->•aBb,#S->•bAb,#S->•bBa,#I1:S’->S•,#I2:S->a•Aa,#S->a•Bb,#A->•x,aB->•x,b４８ I3:S->b•Ab,#S->b•Ba,#A->•x,bB->•x,aI4:S->aA•a,#I5:S->aB•b,#I6:A->x•,aB->x•,bI7:S->bA•b,#I8:S->bB•a,#I9:A->x•,bB->x•,aI10:S->aAa•,#I11:S->aBb•,#I12:S->bAb•,#I13:S->bBa•,#对于I6与I9并不存在“归约-归约”冲突，于LR(1)文法相符；然合并同心集I6和I9，得：A->x,a/bB->x,a/b出现了“归约-归约”冲突，故该文法并非LALR文法。第十一次作业：P1941.按照语法制导翻译的一般原理，给出表达式(5*4+8)*2的语法树各结点并注明语义值VAL。E(56)E(28)E*()E(28)2E(28)854E(4)*E(5)E(20)E(8)+解：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↑P1954.将下列中缀式改写为后缀式表示：解：(2)((a*d+c)*d+e)*f+g:ad*c+d*e+f*g+(3)a+x*(b+x*(c+x*(d+x*(e+x*f)))):axbxcxdxexf*+*+*+*+*+(4)x-5∨x5:x5-x5∨P1955.将下列后缀式改写为中缀式表示：解：(1)abc-*cd+e/-:a*(b-c)-(c+d)/e(3)abc+a0>∧ab+0<>a0<∧∨:(ab+c∧a>0)∨(a+b<>0∧a<0)P1956.利用所给的语义子程序给出下列算术表达式语法制导翻译过程：以（1）(a+b)为例进行分析，（2）（3）两题与（1）类似；解：参看P118表4.15，该表存在错位，应纠正：步骤状态栈符号栈输入串规约规则调用子程序后缀表示10#(a+b)#204#(a+b)#3045#(a+b)#F∷＝iSUB6a4043#(F+b)#T∷＝FSUB4a5042#(T+b)#E∷＝TSUB2a6041#(E+b)#a70416#(E+b)#a804165#(E+b)#F∷＝iSUB6ab904163#(E+F)#T∷＝FSUB4ab1004169#(E+T)#E∷＝E(1)+TSUB1ab+11048#(E)#ab+120481#(E)#F∷＝(E)SUB5ab+1303#F#T∷＝FSUB4ab+1402#T#E∷＝TSUB2ab+1501#E#accP1958.写出下列赋值语句的自下而上语法制导翻译过程，并给出产生四元式序列：a:=b*(c+d)步骤状态栈符号栈PLACE输入串规约规则调用子程序四元式10#-a:=b*(c+d)#202#a-Va:=b*(c+d)#V∷＝iSUB8303#V-Va:=b*(c+d)#４８ 4034#V:=-Va-b*(c+d)#50349#V:=b-Va-Fb*(c+d)#F∷＝iSUB760347#V:=F-Va-Tb*(c+d)#T∷＝FSUB570346#V:=T-Va-Tb*(c+d)#803461#V:=T*-Va-Tb(c+d)#9034618#V:=T*(-Va-Tb-c+d)#100346189#V:=T*(c-Va-Tb-Fc+d)#F∷＝iSUB7110346187#V:=T*(F-Va-Tb-Tc+d)#T∷＝FSUB5120346186#V:=T*(T-Va-Tb-Ec+d)#E∷＝TSUB3130346182#V:=T*(E-Va-Tb-Ec+d)#1403461820#V:=T*(E+-Va-Tb-Ec-d)#15034618209#V:=T*(E+d-Va-Tb-Ec-Fd)#F∷＝iSUB716034618207#V:=T*(E+F-Va-Tb-Ec-Td)#T∷＝FSUB517034618203#V:=T*(E+T-Va-Tb-T1)#E∷＝E(1)+TSUB2(+,c,d,T1)180346182#V:=T*(E-Va-Tb-T1)#1903461825#V:=T*(E)-Va-Tb-T1#F∷＝(E)SUB620034614#V:=T*F-Va-T2#T∷＝T(1)*FSUB4(*,b,T1,T2)210346#V:=T-Va-T2#E∷＝TSUB3(*,b,T1,T2)220345#V:=E-Va-T2#A∷＝V:=ESUB1(:=,T2,,a)2301#A-#accP19510.将下列布尔表达式翻译成四元式序列，并给出语法制导翻译过程（作为条件控制）：a∧b∧c>d解：四元式序列如下所示：(1)(jnz,a,,3)a的四元式，当a为真时，则转向第3个四元式(2)(j,,,0)(3)(jnz,b,,5)b的四元式，当b为真时，则转向第3个四元式(4)(j,,,2)无条件转向第2个四元式(5)(j>,c,d,0)c>d的四元式(6)(j,,,4)无条件转向第4个四元式•TC表示真出口的链首•FC表示假出口的链首，每个链尾的四元式第4分量均为0，表示结束标记语法制导翻译过程四元式a∧b∧c>d(1)E∧b∧c>d100(jnz,a,,0/102){E•TC:=100;E•FC:=101}101(j,,,0)(2)E∧b∧c>d{BP(E(1)•TC=100,NXQ=102);４８ E∧•FC:=E(1)•FC=101}(3)E∧E∧c>d102(jnz,b,,0/104){E•TC:=102;E•FC:=103}103(j,,,0/101)(4)E∧E∧’c>d{BP(E(1)•TC=102,NXQ=104);E∧’•FC:=E(1)•FC=103}(5)E∧E∧’E104(j>,c,d,0){E•TC:=104;E•FC:=105}105(j,,,0/103)(6)E∧E(1){E(1)•TC:=E•TC=104;E(1)•FC:=MERG(E∧’•FC=103,E•FC=105)=105}(7)E(2){E(2)•TC=E(1)•TC=104;E(2)•FC:=MERG(E∧•FC=101,E•FC=105)=105}第十二次作业：P19512.写出下列条件赋值语句的四元式序列：z:=ifa>cthenx+yelsex+y-0.5解：根据语义子程序，其条件赋值语句四元式序列为：100(j>,a,c,102)101(j,,,105)102(+,x,y,T1)103(:=,T1,,z)104(j,,,108)105(+,x,y,T2)106(-,T2,0.5,T3)107(:=,T3,-,z)108P19513.将下列条件语句翻译成四元式序列：ifx=y+1thenx:=x*yelsewhilex<>0dobeginx:=x-1;y:=y+2end解：根据语义子程序，其条件赋值语句四元式序列为：100(+,y,1,T1)101(j=,x,T1,103)102(j,,,106)103(*,x,y,T2)104(:=,T2,,x)105(j,,,113)106(j<>,x,0,108)107(j,,,113)108(-,x,1,T3)109(:=,T3,,x)110(+,y,2,T4)111(:=,T4,,y)４８ 112(j,,,113)113P19514.将下列while语句翻译成四元式序列：(2)whileagthenp:=p+1被翻译成如下四元式序列：100(*,b,2,T1)101(+,a,T1,T2)102(:=,T2,,i)103(+,c,d,T3)104(+,T3,10,T4)105(:=,T4,,T)106(j,,,108)107(+,i,1,i)108(j>,i,T,114)109(j>,h,g,111)110(j,,,113)111(+,p,1,T5)112(:=,T5,,p)113(j,,,107)114４８'