《编译原理》习题解答：.doc 36页

'《编译原理》习题解答：第一次作业：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∪A+＝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（1）L(G)＝{0n1|n≥1}；（2）L(G)＝{a2nbc|n≥0}。P3912、试分别构造产生下列语言的文法：（1）{abna|n=0，1，2，3……}（3）{aban|n≥1}（5）{anbmcp|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∷＝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，T，C}，VT＝{a，b，c}，P：S∷＝TCT∷＝aTb|ε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，简单短语a，句柄aS（3）ABbBSbAB短语bB,AB,ABb，３６ 简单短语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|i3)S::=A|BA::=aCbA|aB::=BCC|aC::=ba1)对于句子iiieii可构造两棵不同的语法树，所以证明该文法是二义的。SiSeSiSiSiiSiSiSeSiiSi2)对于句子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正规文法1上下文无关文法25678上下文有关文法3短语结构文法4P4126.给出产生下列语言L（G）={W|W∈{0，1}+且W不含相邻1}的正规文法。G=({S,A,B},{0,1},P,S)P:S::=0|1|0B|1AA::=0|0SB::=0|1P4127.给出一个产生下列语言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|εP4229.用扩充的BNF表示以下文法规则：1．Z::=AB|AC|A2．A::=BC|BCD|AXZ|AXY3．S::=aABa|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解：先画出该文法状态转换图：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直接跟在其后的字符串的集合；那么如何构造其相应的有穷自动机呢？SZ’001A0ZS’εε先构造其转换系统：根据其转换系统可得状态转换集、状态子集转换矩阵如下表所示：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直接跟在右边，然后，再构造该语言的正规文法。解：DFA=（{S，A，Z}，{0，1}，M，S，{Z}）其中M：M（S，0）=ZM（S，1）=AM（A，0）=ZM（Z，0）=ZM（Z，1）=A该语言的正规文法G[Z]为：右线性文法：//S：：=0|1A|0Z左线性文法：//S：：=0|A0|Z0A：：=0|0ZA：：=1|Z1Z：：=0|1A|0ZZ：：=0|A0|Z0P748.设(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}S的元素是[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}，化简如图：３６ 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其左线性文法G=（VN,VT,P,S）VN={A,S}VT={a,b,c}P:A→cA→AbS→AaP7410.已知正规文法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}，状态子集转换矩阵如下表所示：II0I1S01{S}{1,2,3}01{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}，再根据是否可继续划分来确定最后的组数）：P7412.将图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}不可以继续划分，因此化简后的状态转换图如下：ab0,21aP7413.构造下列正规式的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’的规则如下表：II0I1S01[X][Z][X]021[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]66301100013001124,60其中[Y,Z]为不可到达状态，应该删去，所以S’={[X]}，Z’={[Z],[X,Z],[X,Y,Z]}，再进行化简，发现4和6两状态等价，最后其DFA如下所示：XZ’101000Y0ZSεε第二种方法：先构造其对应的转换系统：３６ 由上述转换系统可得状态转换集、状态子集转换矩阵如下表所示：II0I1S01{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)P7419.Σ＝{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*３６ （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*；第七次作业：P1421.试分别消除下列文法的直接左递归（采用两种方法——重复法和改写法）（1）G[E]:E::=T|EAT……①T::=F|TMF……②F::=(E)|i……③A::=+|-……④M::=*|/……⑤解：先采用“重复法”：再采用“改写法”：E::=T{AT}E::=TE’T::=T{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|aP1424.试分别用两种方法（框图法和类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’)的框图形式，其余相似从略）３６ 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’)={+,#,}}∩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→ε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)={ε，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∷＝Ac第九次作业：P14410.证明下述文法不是简单优先文法：（1）S∷＝bEbE∷＝E+T|T（2）S∷＝bEbE∷＝F|F+T|T|iT∷＝i|(E)证明：(1)画语法树：S╱│╲bEb╱│╲E+T可以得出b=E和b>E,因此该文法不是简单优先文法。(2)因该文法中含E∷=i３６ T∷=i右部两个产生式相同，故该文法不是简单优先文法.P14511.构造下述文法的优先关系矩阵，它们是简单优先文法吗？S∷＝M|UM∷＝iEtMeM|aU∷＝iEtS|iEtMeUE∷＝b解：优先关系矩阵如下SMUiEteabSM=>Ui=b>其中含多重定义的表项，因而该文法不是简单优先文法。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∷=(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∷=(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）＋*↑()i+>··<·<·<>··<*>·>··<·<>··<↑>·>··<·<>··<(·<·<·<·<=·<３６ )>·>·>·>·(>·>·>·>·（2）用迭代法构造优先函数若R=S则f(R）=g(S)若R··S则f(R）>g(S)＋*↑()if111111g111111根据·<的优先关系＋*↑()if111111g222212根据·<的优先关系＋*↑()if333133g222212根据=的优先关系＋*↑()if333133g244414循环―＋*↑()if355155g244414＋*↑()if355155g246616＋*↑()if355177g246616最终结果：＋*↑()if355177g246616（3）３６ +*↑()i)(↑*+i优先函数为：＋*↑()if466199g358718（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∷＝a证明：∵S→A[A→aA∴a>·[∵A→AaA→B]∴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＃∨*∨+∨>·#∨+∨＃∨*∨>·#∨+∨＃∨>·#成功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::=·cA::=c·bBbAdcadcaBAZ(1)I0: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·(2)构造LR（0）分析表状态ACTIONGOTOabcd#ZAB0S4S5S6123781acc2r1r1r1r1r13r2r2r2r2r24S4S5S65r4r4r4r4r46r6r6r6r6r67S98S109r3r3r3r3r310r5r5r5r5r5规则顺序：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•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#E３６ 0S211S2acc32r3r3r33S4S5S234r1r1r15r2r2r2P14726.对如下文法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]=1901#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,bI3: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.给出下面表达式的后缀式表示：解：(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∧∨∧３６ P1954.将下列中缀式改写为后缀式表示：解：(2)((a*d+c)*d+e)*f+g:adc+*d*e+f*g+(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:=-Vab*(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-Tbc+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-Ecd)#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)#(+,c,d,T1)1903461825#V:=T*(E)-Va-Tb-T1#F∷＝(E)SUB6(+,c,d,T1)20034614#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３６'