编译原理及编译程序构造部分课后答案张莉杨海燕编著.doc

第一章练习12、典型的编译程序可划分为哪几个主要的逻辑部分？各部分的主要功能是什么？典型的编译程序具有7个逻辑部分：第二章练习2.24.试证明：A+ =AA*=A*A证： A*=A0A+，A+=A1A2An得：A*=A0A1A2An AA*=A（A0A1A2An）= AA0AA1AA2A An=AA2A3An +1= A+同理可得：A*A =(A0A1A2An)A=A0 AA1AA2AAnA= AA2A3An+1= A+因此： A+ =AA*=A*A练习2.31.设G标识符的规则是 ：标识符:=a|b|c|标识符a|标识符c|标识符0|标识符1试写出VT和VN，并对下列符号串a,ab0,a0c01,0a,11,aaa给出可能的一些推导。解：VT =a,b,c,0,1， VN =标识符(1) 不能推导出ab0,11,0a(2)标识符=a(3)标识符=标识符1=标识符01=标识符c01=标识符0c01= a0c01(4)标识符=标识符a=标识符aa=aaa2写一文法，其语言是偶整数的集合解：G：:= | := + | |:= | := | 1 | 3 | 5 | 7 | 9 :=0 | 2 | 4 | 6 | 84. 设文法G的规则是：A:=b| cc试证明：cc, bcc, bbcc, bbbccLG证：（1）A=cc（2）A=bA=bcc（3）A=bA=bbA=bbcc（4）A=bA=bbA=bbbA=bbbcc又cc, bcc, bbcc, bbbccVt*由语言定义，cc, bcc, bbcc, bbbccLG5 试对如下语言构造相应文法：（1） a(bn)a | n=0,1,2,3,其中左右圆括号为终结符。（2） （an）（bn） | n=1,2,3, 解：（1）文法GS：S:= a(B)aB:= bB |( 2 ) 文法GS：-错了，两个n不等S := (A)(B)A:= aA|aB:= bB|b7.对文法G3表达式表达式:=项|表达式+项|表达式-项项:=因子|项*因子|项/因子因子:=（表达式）| i列出句型表达式+项*因子的所有短语和简单短语。 = + = + * 短语有：表达式+项*因子和项*因子简单短语是：项*因子8 文法V:= aaV | bc的语言是什么？解：L（GV）= a2nbc | n=0,1,2,V aaV aaaaV . a2nbc (n 1)V bc (n=0)练习2.45.已知文法GE：E:=ET+ | TT:=TF* |FF:=FP |PP:=（E）| i有句型TF*PP+，问此句型的短语，简单短语，和句柄是什么？解：此句型的短语有：TF*PP+，TF*，PP，P简单短语有：TF*，P句柄是：TF*8.证明下面的文法G是二义的：S:= iSeS | iS | i证：由文法可知iiiei是该文法的句子，又由文法可知iiiei有两棵不同的语法树。所以该文法是二义性文法。第三章练习3.11画出下述文法的状态图Z:=BeB:=AfA:= e |Ae使用该状态图检查下列句子是否是该文法的合法句子f，eeff，eefe2、有下列状态图，其中S为初态，Z为终态。（1） 写出相应的正则文法：（2） 写出该文法的V，Vn和Vt；（3） 该文法确定的语言是什么？解：（1） ZA1|0 AA0|0（2） V=A,Z,0,1Vn=A,ZVt=0,1（3） L (GS)= 0或0n1,n1L (GS)= 0|00*1练习3.21令A，B，C是任意正则表达式，证明以下关系成立：A|A=A（A*）*= A*A*=| AA*（AB）*A = A（BA）*（A|B）* =（A*B*）*=（A*|B*）证明：AAxxL(A)或xL(A)xxL(A)A（A*）*（A*）0（A*）1（A*）2（A*）n(A0A 1A2An) (A1)A0A 1A2AnA*AA*所表示的语言是:LALA*LA0LA（LA0LA1LA2）LA0LA1LA2LA*故AA*A*(LALB)*LA=(L(A)LBLALBLALBLALBLALBLALB) LA=LALALBLALALBLALBLALALBLALBLALBLA= LA(LBLALBLALBLA)= LA(LBLA)(AB)*A=A(BA)*三个表达式所描述的语言都是LALB中任意组合（A|B）*=(A*B*)=(A*|B*)*2. 构造下列正则表达式相应的DFA（1） 1（0|1）*|0（2） 1（1010*|1（010）*1）*04. 5. 构造一DFA，它接受=0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。第四章练习4.22. 有文法GA: A:= (B) | dBeB:= c | Bc试设计自顶向下的语法分析程序。解：消除左递归：A:= (B) | dBeB:= ccprocedure B;if CLASS = c thenbeginnextsym;while CLASS = c do nextsym;end;elseerror; program G;beginnextsym;A;end;procedure A;if CLASS = ( thenbeginnextsym;B;if CLASS = ) thennextsym；elseerrorend；elseif CLASS = d thenbeginnextsym;B;if CLASS = e thennextsym;elseerror;end;elseerror;3. 有文法GZ: Z:= AcB| BdA:=AaB|cB:= aA|a(1) 试求各选择（候选式）的FIRST集合；(2) 该文法的自顶向下的语法分析程序是否要编成递归子程序？为什么？(3) 试用递归下降分析法设计其语法分析程序。解: (1) FIRST(B)=a FIRST(A)=c FIRST(Z)=a,cFIRST(AcB)=c FIRST(Bd) =aFIRST(AaB)=c FIRST(c) =cFIRST(aA) =a FIRST(a) =a(2) 要编成递归子程序，因为文法具有递归性(3) 改写文法：Z:= AcB| BdA:= caBB:= aA 练习4.31 . 对下面的文法GE: E TE E + E |T FTT T |F PFF * F |P (E)| a | b | (1) 计算这个文法的每个非终结符号的FIRST和FOLLOW集合(2) 证明这个文法是LL(1)的(3) 构造它的预测分析表解：(1)FIRST( E ) = (, a, b, FOLLOW( E ) = #, ) FIRST( E ) = +,FOLLOW( E ) = #, )FIRST( T ) = (, a, b, FOLLOW( T ) = #, ),+FIRST( T ) = (, a, b, ,FOLLOW( T) = #, ),+ FIRST( F ) = (, a, b, FOLLOW( F ) = (, a, b, ,#, ),+FIRST( F ) = *,FOLLOW( F ) = (, a, b, ,#, ),+FIRST( P ) = (, a, b, FOLLOW( P ) = *,(, a, b, ,#, ),+ (2) 证明：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)文法2. 对于文法GS：S aABbcd | A ASd | B SAh | eC | C Sf | Cg | D aBD | （1) 对每一个非终结符号，构造FOLLOW集；（2) 对每一产生式的各侯选式，构造FIRST集；（3) 指出此文法是否为LL（1）文法。解：（1）FIRST(S) = a, FIRST(A) = a,d, FIRST(B) = a,d,h,e, FIRST(C) = a,f,g, FIRST(D) = a, FOLLOW(S) = d,a,f,h#FOLLOW(A) = a,h,e,b,dFOLLOW(B) = b,aFOLLOW(C) = g,b,a(2) FIRST(aABbcd) = aFIRST() = FIRST(ASd) = a,dFIRST() = FIRST(SAh) = a,d,hFIRST(eC) = eFIRST() = FIRST(Sf) = a,fFIRST(Cg) = a,f,gFIRST() = (3) 不是LL(1)文法，因FIRST(Sf) FIRST(Cg) = a,f a,f,g或FOLLOW(S) FIRST(aABbcd)d,a,f,h# a或FOLLOW(A) FIRST(ASd) a,h,e,b,d a,d 或FOLLOW(B) FIRST(SAh) a,b a,d,h 或FOLLOW(C) FIRST(Sf) g,a,b a,f 或FOLLOW(C) FIRST(Cg) g,a,b a,f ,g6. 一个文法G是LL(1)的必要与充分条件是什么？试证明之。充要条件是：对于G的每一个非终结符A的任何两条不同规则A:= |, 有：(1) FIRST()FIRST()= (2) 假若=*=, 则FIRST()FOLLOW(A)= 证明：充分性：条件（证明：充分性：条件（1）（2）成立反证：若分析表中存在多重入口，即）成立反证：若分析表中存在多重入口，即MB,a = B:= 1, B:= 2 ,表明FIRST(1)FIRST(2) 或MB,a = B:= 1, B:= 2，其中2= 或2=+= 表明FIRST(1)FOLLOW(B) 与条件（1）（2）矛盾。必要性：文法是）矛盾。必要性：文法是LL(1)文法，即分析表中不含多重入口若条件文法，即分析表中不含多重入口若条件(1)不成立，即存在某非终结符B的两条规则B:= 1|2，FIRST(1)FIRST(2) 则对任意的aFIRST(1)FIRST(2)，有MB,a = B:= 1, B:= 2,矛盾若条件（矛盾若条件（2）不成立，即存在某非终结符B的两条规则B:= 1|2，2=*= 有FIRST(1)FOLLOW(B) 则对任意的aFIRST(1)FOLLOW (B)，有MB,a = B:= 1, B:= 2,矛盾练习4.44.有文法GE: E:= E+T | TT:= T*F | FF:= (E) | i列出下述句型的短语和素短语：E、T、i、T*F、F*F、i*F 、F* i、F+F+F练习4.51. 考虑具有下列规则的文法SE# ET|E+T TP| PT PF|P*F Fi|(E)(a) 下列句型的最右推导步骤中，其活前缀的集合是什么？(1) E+i*i#(2) E+P(ii)(b)为下列输入串构造最右推导的逆：(1) i+i*i#(2) i+i(i+i)#解：(a)（1）句柄为i，所以活前缀集合为：E，E，Ei（2）句柄为i，所以活前缀集合为：E，E+, E+P, E+P, E+P(, E+P(I(b) （1）i+i*i# =F+i*i# =P + i*i# =T+i*i# =E+i*i# =E+F*i# =E+P*i# =E+P*F# =E+P# =E+T# =E# +E+TE-T T-*T*FT-FF-(E)F-ii翻译为波兰后缀表达式的文法为：E-E+T+E-T T-T*F*T-FF-(E)F-ii2 构造一符号串翻译文法，它将接受由0和1组成的任意输入符号串，并产生下面的输出符号串： (a) 输入符号串倒置 (c) 输入符号串本身。（a）S-0S0 或 S-0S0S-1S1 S-1S1S-S-（ c）E-00EE-11EE-3. 以下的符号串翻译文法能做什么？-C EN HI GL N