编译原理课后答案

第二章高级语言及其语法描述4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：（1）优先顺序（从高至低）为+，*和↑，同级优先采用左结合。（2）优先顺序为↑，+，*，同级优先采用右结合。解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16（2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=46．令文法G6为N→D|NDD→0|1|2|3|4|5|6|7|8|9（1）G6的语言L（G6）是什么？（2）给出句子0127、34和568的最左推导和最右推导。解：（1）L（G6）=｛a|a∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝（2）N＝＞ND＝＞NDD＝＞NDDD＝＞DDDD＝＞0DDD＝＞01DD＝＞012D＝＞0127N＝＞ND＝＞N7＝＞ND7＝＞N27＝＞ND27＝＞N127＝＞D127＝＞0127N＝＞ND＝＞DD＝＞3D＝＞34N＝＞ND＝＞N4＝＞D4＝＞34N＝＞ND＝＞NDD＝＞DDD＝＞5DD＝＞56D＝＞568N＝＞ND＝＞N8＝＞ND8＝＞N68＝＞D68＝＞5687．写一个文法，使其语言是奇数集，且每个奇数不以0开头。解：A→SN,S→+|-|∑,N→D|MDD→1|3|5|7|9,M→MB|1|2|3|4|5|6|7|8|9B→0|1|2|3|4|5|6|7|8|98.文法：ETETETTFTFTFFEi|||*|/()|最左推导:EETTTFTiTiTFiFFiiFiiiETTFFFiFiEiETiTTiFTiiTiiFiii********()*()*()*()*()*()*()最右推导:EETETFETiEFiEiiTiiFiiiiiETFTFFFEFETFEFFEiFTiFFiFiiiii**********()*()*()*()*()*()*()*()语法树：/********************************EEFTE+TFFT+iiiEEFTE-TFFT-iiiEEFT+TFFTiii*i+i+ii-i-ii+i*i*****************/9．证明下面的文法是二义的：S→iSeS|iS|I解：因为iiiiei有两种最左推导，所以此文法是二义的。10．把下面文法改写为无二义的：S→SS|(S)|()解：S→ST|T,T→(S)|()11．给出下面语言的相应文法L1=｛anbnci|n≥1,i≥0｝L2=｛aibncn|n≥1,i≥0｝L3=｛anbnambm|n,m≥0｝L4=｛1n0m1m0n|n,m≥0｝解：（1）S→AB|AA→aAb|abB→c|cB(2)S→AB|BA→a|aAB→bBc|bc(3)S→AB|A|B|∑A→aAb|abB→aBb|ab(4)S→1S0|0A1A→0A1|01第三章词法分析7.构造下列正规式的相应的DFA1(0|1)*1011(1010*|1(010)*1)*00*10*10*10*(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*解答：（1）1(0|1)*101II0I1{X}Ф{A,B,C}{A,B,C}{B,C}{B,C,D}{B,C}{B,C}{B,C,D}{B,C,D}{B,C,E}{B,C,D}{B,C,E}{B,C}{B,C,D,y}{B,C,D,y}{B,C,E}{B,C,D}S01ABBCDCCDDEDECFFED(2)1(1010*|1(010)*1)*0II0I1{X}Ф{A,B,C}{A,B,C}{y}{D,H,I,L}{y}ФФ{D,H,I,L}{E,J}{B,C}{E,J}Ф{B,C,F,G,K}{B,C}{y}{D,H,I,L}{B,C,F,G,K}{B,C,G,I,L,y}{D,H,I,L}{B,C,G,I,L,y}{B,C,G,J,y}{B,C,D,H,I,L}{B,C,G,J,y}{B,C,G,y}{D,H,I,L}{D,H,I,K,L}{E,I,J,L}{B,C}{E,J,y}Ф{B,C,F,G,K}{E,I,J,L}{J}{B,C,F,G,K}{J}Ф{K}{K}{I,L}Ф{I,L}{J}{B,C}8.给出下面正规表达式（1）以01结尾的二进制数串（2）能被5整除的十进制整数（3）包含奇数个1或者奇数个0的二进制数串（4）英文字母组成的所有符号串，要求符号串中的字母按照字典序排列。（7）不包含子串abb的由a和b组成的符号串的全体。解答：（1）（0|1）*01（2）(1|2|…|9)(0|1|2|…|9)*(0|5)|0|5（3）0*1(0*10*10*)*（4）A*B*…Z*(7)b*(a|ab)*9.对下面的情况给出DFA以及正规表达式。（1）{0，1}上的含有子串010的所有串。（2）{0，1}上不含子串010的所有串。解答：（1）（0|1）*010（0|1）*（2）1*(0|1*|1)*1*12将图3.8的（a）和(b)分别确定化和最少化。解：1确定化ab｛0｝｛0,1｝｛1｝｛0,1｝｛0,1｝｛1｝｛1｝｛0｝__令A=｛0｝B=｛0，1｝C=｛1｝则状态转换图为：2最少化首先，所有状态可分为终态集{AB}非终态集{C}其次，考察{AB}，由于{AB}由a到{B}，由b到{C}，所以不可分，令A={AB}则最少化后的状态转换图为：14构造一个DFA，它接受∑＝｛0,1｝上所有满足下列条件的字符串，每个1都有0直接跟在右边。解：1正规式为：（0|10）﹡2由正规式转化为NFA：3由NFA到DFA：01{X}{X}{b}{b}{X}__令A={X}B={b}则状态转换图为：4最少化终态集{A}非终态集{B}显然不可再划分，则最简的DFA即为：15给定右线性文法G：S→0S|1S|1A|0BA→1C|1B→0C|0C→0C|1C|1|0求出一个与G等价的左线性文法。解：1由右线性文法构造NFA：2从NFA中构造左线性文法：F→A1|B0|C0|C1A→S1|1B→S0|0C→C0|C1|A1|B0S→S0|S1|1|0第四章语法分析－自上而下分析1.考虑下面文法G1:S→a|∧|(T)T→T,S|S(1)消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。(2)经过改写的文法是否是LL（1）的？给出它的预测分析表。解答：（1）消去G1的左递归：S→a|∧|(T)T→ST’T’→,ST’|ε递归子程序：PROCEDURES;IFsym=’a’THENADVANCEELSEIFsym=’∧’THENADVANCEELSEIFsym=’(’THENBEGINADVANCET;IFsym=’)’THENADVANCEELSEERRORENDELSEERROR;PROCEDURET;BEGINS;T’END;PROCEDURES;IFsym=’,’THENBEGINADVANCES;T’END;（2）是LL（1）文法。FIRST(S)={a,∧,(}FIRST(T)={a,∧,(}FIRST(T’)={,,ε}FOLLOW(S)={#,,,ε,)}FOLLOW(T)={)}FOLLOW(T’)={)}预测分析表如下：a,∧(）#SS→aS→∧S→(T)TT→ST’T→ST’T→ST’T’T’→,ST’T’→ε2.文法：|^||)(|*||baEPFFFPFTTTFTEEETE(1)FIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε}FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#}(2)考虑下列产生式:EETTFFPEab||*|()|^||FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,该文法式LL(1)文法.(3)+*()ab^#EETE'ETE'ETE'ETE'E'EEEETTFTTFTTFTTFTT'TTTTTTTTTTTFFPFFPFFPFFPFF'FFF*FFFFFFPPE()PaPbP^(4)procedureE;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginT;E'endelseerrorendprocedureE';beginifsym='+'thenbeginadvance;Eendelseifsym')'andsym'#'thenerrorendprocedureT;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginF;T'endelseerrorendprocedureT';beginifsym='('orsym='a'orsym='b'orsym='^'thenTelseifsym='*'thenerrorendprocedureF;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginP;F'endelseerrorendprocedureF';beginifsym='*'thenbeginadvance;F'endendprocedureP;beginifsym='a'orsym='b'orsym='^'thenadvanceelseifsym='('thenbeginadvance;E;ifsym=')'thenadvanceelseerrorendelseerrorend;3.下面文法那些是LL（1）文法？（1）S→AbcA→a|εB→b|ε没有左递归且FIRST候选集不冲突且FIRST(A)∩FOLLOW(A)={a,ε}∩{b}=ФFIRST(B)∩FOLLOW(B)={b,ε}∩{c}=Ф所以该文法为LL（1）文法（2）S→AbA→a|B|εB→b|εFIRST(B)＝{b,ε}∩FIRST(ε)={ε}≠Ф所以该文法不是LL（1）文法（3）S→ABBAA→a|εB→b|ε没有左递归且FIRST候选集不冲突FIRST(A)∩FOLLOW(A)={a,ε}∩{b,#}=ФFIRST(B)∩FOLLOW(B)={b,ε}∩{b,a,#}≠Ф所以该文法不是LL（1）文法(4)S→aSe|BB→bBe|CC→cCe|d没有左递归且FIRST候选集不冲突所以该文法为LL（1）文法4.Expr→_ExprExpr→(Expr)|VarExprTailExprTail→_Expr|εVar→idVarTailVarTail→(Expr)|ε（1）构造LL（1）分析表（2）给出对句子id__id((id))的分析过程解答：（1）FIRST(Exp