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

1、第一章练习12、典型的编译程序可划分为哪几个主要的逻辑部分？各部分的主要功能是什么？典型的编译程序具有7个逻辑部分:符号表管理词法分析程序语法分析程序语义分析、生成中间代码代码优化出错处理第二章练习2.24. 试证明：A+ =AA*=A*A证：T A*=A0UA+, A+=A1UA2U-U AnU得: A*=A0U A1UA2U-U AnUAA*=A (A0U A1U A2U-U An U)=AA0UAA1U AA2U-U A AnU =AU A2U A3U An +1U = A+同理可得：A*A =(A0U A1U A2U-U An U )A=A0 AU A1AU A2AUU An AU =

2、AU A2U A3U An+1U = A+因此： A+ =AA*=A*A练习 2.3 1设G标识符的规则是：标识符 :=a|b|c|标识符 a| 标识符 c|标识符 0| 标识符 1试写出 VT 和 VN，并对下列符号串a,abO,aOcO1,Oa,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写一文法，其语言是偶整数的集合解：Gv偶整数:偶整数:

3、= 符号 偶数字| 符号数字串偶数字符号 :二 + | | £数字串:= 数字串数字|数字数字 := 偶数字| 1 | 3 | 5 | 7 | 9偶数字 :=0 | 2 | 4 | 6 | 84. 设文法 G 的规则是：A:=bA| cc试证明：cc, bcc, bbcc, bbbc& LG证：（1） A =cc（ 2） A =b A =bcc（ 3） A =b A =bb A =bbcc（ 4） A =b A =bb A =bbb A =bbbcc又 t cc, bcc, bbcc, bbbccE Vt*二由语言定义，cc, bcc, bbcc, bbbcdE LG5 试对

4、如下语言构造相应文法：（1） a（bn）a | n=0,1,2,3,，其中左右圆括号为终结符。(2) (an) (bn)| n=1,2,3,解：(1)文法G S :S:= a(B)aB:= bB |&(2 )文法G S :-错了，两个n不等S :二(A)(B)A:= aA|aB:= bB|b7对文法G3表达式表达式：:二项|表达式+项|表达式-项项:=因子|项*因子|项/因子因子:=(表达式)| i列出句型表达式+项*因子的所有短语和简单短语表达式 = 表达式 + 项= 表达式 + 项 * 因子表达式表达式+项项 * 因子短语有： 表达式 +项 * 因子和项 * 因子 简单短语是：项

5、* 因子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*PPf +, 问此句型的短语，简单短语，和句柄是什么？ 解：此句型的短语有：TF*PPf +, TF*, PPf, P 简单短语有： TF*， P 句柄是： TF*8.证明下面的文法G是二义的：S:= iSeS | iS | i证：由文法可知 iiiei 是该文法

6、的句子，又由文法可知iiiei有两棵不同的语法树 所以该文法是二义性文法。第三章练习3.11画出下述文法的状态图Z> :二B> eB> :=A> fA> :=:e | A> e使用该状态图检查下列句子是否是该文法的合法句子f, eeff,eefe解：J*">1.、"s.:S->AVB1MZ 'eeff不是该文法的合法句子，eefe是该文法的合法句子2、有下列状态图，其中S为初态，Z为终态。(1) 写出相应的正则文法：(2) 写出该文法的V, Vn和Vt;(3) 该文法确定的语言是什么？解：(1) Z A1|0A A0|

7、0(2)V=A,Z,0,1Vn=A,ZVt=0,1(3) L (GS)= 0或 On 1,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* )证明：A I A= x I x L(A咸 x L(A) = x I x L(A)= AA*) * =(A*) 0U(A*) 1U(A*) 2U-U( A*) n=& U (AOU A 1U A2U-U An) U (A1 )=& U AO

8、U A 1U A2U-U An=A*e | AA*所表示的语言是： £ U LA LA*=LAOU LA ( LAOU LA1U LA2U )=LAOU LA1U LA2U-= LA*故 £ | AA*= A*(LALB)*LA=(£ U L(A)LBU LALBLALBU LALBLALBLALBU)LA=LAU LALBLAU LALBLALBLUA LALBLALBLALBU LA=LAU (£ U LBLAU LBLALBLAJ )= LA(LBLA) (AB)*A=A(BA)*三个表达式所描述的语言都是 LALB中任意组合 (A|B)*=(A*

9、B*)=(A*|B*)*2. 构造下列正则表达式相应的 DFA(1) 1(O|1 )*|O( 2) 1 (1O1O*|1 (O1O) *1 ) *O与1 (0|1 ) *|0对应的NFA为:4.4fl屮1OJ ；i |0J!(OJ!i n Ib(T每个15. 构造一 DFA它接受艺=0,1上所有满足如下条件的字符串: 都有0直接跟在右边。01A* -L Jj 0第四章练习4.22.有文法GA:A:= (B) | dBeB:= c | Bc试设计自顶向下的语法分析程序解：消除左递归：A:= (B) | dBeB:= cc procedure B;if CLASS = 'c' th

10、e n begi n n extsym;while CLASS = 'c' do nextsym;end;else error; program G;beginnextsym;A;end;procedure A;if CLASS = '(' then begin nextsym;B;if CLASS = ')' then nextsym； else error end； elseif CLASS = 'd' then begin nextsym;B;if CLASS = 'e' then nextsym;else

11、error; 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,c FIRST(AcB)=cFIRST(Bd) =aFIRST(AaB)=cFIRST(c) =cFIRST(aA) =aFIRST(a) =a(2) 要编成递归子程序，因为文法具有递归性(3) 改写文法：Z:= AcB| BdA:= ca

12、BB:= aAvoid Z() Z:=AcB| BdA：= caBif( sy m =4c,)jB:= a|A|iAO;if( sym =叱Jvoid A()void BO ”KctsymO;iff sym = P")iff sym!=4ha,)B();error();1getsyniQ;elseJekewhilef sym 妝)crror();getsym();geteymO；iR sym =Jelse iff sym = W)B()；A();1B()；Iif( sv in !-elseerror();errorO;iviseivoid main()getsymO;igetnym(

13、);elseZ()；errorO;* 练习4.31 .对下面的文法GE:E f TE 'E' f + E | £T f FT'T' f T | £F f PF'F' f * F' | £P f (E)| a | b | A(1) 计算这个文法的每个非终结符号的FIRST和FOLLOW集合 证明这个文法是LL(1的(3) 构造它的预测分析表 解：(1)FIRST( E ) = (, a, bA FOLLOW( E ) = #, ) FIRST( E' ) = +,门FOLLOW( E' ) =

14、#, )FIRST( T ) = (, a, bA, FOLLOW( T ) = #, ),+FIRST( T' ) = (, a, bA , £ FOLLOW( T') = #, ),+ FIRST( F ) = (, a, bA, FOLLOW( F ) = (, a, bA, ,#, ),+FIRST( F' ) = *,£FOLLOW( F' ) = (, a, bA, ,#, ),+FIRST( P ) = (, a, bA, FOLLOW( P ) = *,(, a, b,A,#, ),+ (2) 证明：FIRST( +E)A F

15、IRST£ ) = +A & = /FIRST( +E)A FOLLOW( E' )= +A #, ) = /FIRST( T )A FIRST£ ) = (, a, b, A A £ = /FIRST( T )A FOLLOW( T') = (, a, bA 门倂,),+ = /FIRST( *F' )A FIRST£ )= * A & = /FIRST( *F' ) A FOLLOW( F' ) = *(, a, b, A ,#,),+ = /FIRST( (E) A FIRST(a)A FIR

16、ST(b)A FIRSTA)二 /所以此文法是LL(1)文法(3)分析表+*(）abA#EEtTE'E-kTEE >TEhEt TE'ErE1 t + EEE J eTT ITT FT1TtFTTtFTTJ;T1 ->TT sTJT丁 JTTJTTJeFFt PFFt PFF t ppFt PFFF JeF' T* FF' ->eF jF ->eFTF' TEFJeFPt(E)P->bP >A2.对于文法 GS: S aABbcd | &A ASd| £B SAh|eC | £C Sf |

17、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(

18、 £ ) = £FIRST(ASd) = a,dFIRST(£ ) = £FIRST(SAh) = a,d,hFIRST(eC) = eFIRST(£ ) = £FIRST(Sf) = a,fFIRST(Cg) = a,f,gFIRST(£ ) = £ 不是LL(1文法，因FIRST(Sf)A FIRST(Cg) = a,f a,f,g/或 FOLLOW(S)A FIRST(aABbcd)d,a,f,h# A a/ 或 FOLLOW(A) A FIRST(ASd) a,h,e,b,d A a,d 或 FOLLOW(

19、B)A FIRST(SAh) a,b A a,d,h * 或 FOLLOW(C)A FIRST(Sf) g,a,b A a,f H或 FOLLOW(C)Q FIRST(Cg) g,a,b A a,f ,g/6. 一个文法G是LL(1的必要与充分条件是什么？试证明之。充要条件是：对于G的每一个非终结符A的任何两条不同规则A:= a| B ,有：(1) FIRSTa )A FIRST0 )= / 假若 B =*=> £ ,贝卩 FIRSTa) A FOLLOW(A)二证明：充分性：条件(证明：充分性：条件( 1 )(2)成立 反证：若分析表中存在多重入口，即)成立反证：若分析表中存

20、在多重入口，即MB,a = B:= a 1, B:= a 2，表明 FIRSTS 1) A FIRSTa 2) T 或 MB,a = B:= a 1, B:= a 2,其中 a 2= £ 或 a 2=+=> £ 表明 FIRSTa 1)A FOLLOW(B)/与条件( 1 )( 2)矛盾。必要性：文法是)矛盾。必要性：文法是LL(1)文法，即分析表中不含多重入口若条件文法,即分析表中不含多重入口若条件(1)不成立，即存在某非终结符 B的两条规则B：= a 1| a 2,FIRST® 1)n FIRST® 2)/则对任意的 a FIRST®

21、 1)n FIRST® 2),有MB,a = B:= a 1, B:= a 2,矛盾若条件(矛盾若条件(2)不成立，即存在某非终结符 B的两条规则B：= a 1| a 2,a 2=*=> e有 first® 1)n FOLLOW(B)M则对任意的 a FIRST® 1)n FOLLOW (B)有MB,a = B:= a 1, B:= a 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解：句型短语素短语ETT«

22、11V1t*fT*FT*FF*FRFi*Fi, i*F1F*iF, i, F* i1F+F+FF,F,F,F+F, F+F+FF+F练习4.51.考虑具有下列规则的文法S E# E T|E+T T P| P f T P F|P*F F i|(E)(a) 下列句型的最右推导步骤中，其活前缀的集合是什么？(1) E+i*i#(2) E+P f (i i) (b)为下列输入串构造最右推导的逆：(1) i+i*i#(2) i+i f (i+i)#解： (a) (1)句柄为 i ，所以活前缀集合为： E， E， E i(2)句柄为 i ，所以活前缀集合为： E，E+, E+P, E+Pf , E+Pf

23、(, E+Pf (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#S练习 4.61. 给定具有如下产生式的文法S E# E tE-T|T T tF|F f T F i|(E)试求下列活前缀的有效项目集：(a) F f (b) E-(c) E-T解： (a)E f T t.F T tFf .T T t.F f T F t.i F t.(E) (b) E-(Ft (.E), Et.E-T, E t.T,

24、 T t.F, T t.Ff T, T t.i, Tt.(E)(c) E - TE tE-T. 练习 4.71. 给定下列产生式的文法：StE E t T|E+T T t P|T*P P t F|Ff P F ti|(E)(1) 为该文法构造 SLR( 1)分析表。状 态SETPF+Ti()coClC2C3C4S5S6ClS7AC2rlS8rlrlC3r3r3r3r3C4r5r5S9r5r5C5r7r7r7r7r7C6CIOC2C4S5S6C7CllC3C4S556C8C12C4S5S6C9C3C4S5S6CIOS7Cllr2S8r2r2C12r4r4r4r4C13r6r6r6r6C14rSr

25、SrSrX第五章练习53.如下非分程序结构语言的程序段，画出编译该程序段时将生成的 有序符号表。BLOCKREAL X,Y ,Z1,Z2,Z3;INTEGER IJKLASTI;STRING LIST-OF-NAMES;LOGICAL ENTR Y-ON EXIT-OFF;ARRAY REAL VAL(20);ARRAY INTEGER MIN-VAL-IND(20);END OF BLOCK;变量名类型维数ETRY-()LOGICAL0EXIT-OFFLOGICAL0IINTEGER0JINTEGER0KINTEGER0LASTIINTEGER0LIST'OF NAMESSTRING

26、0MTN-VAI.-INDINTEGER1VALREAL1XREAL0YREAL0Z1REAL0Z2REAL0Z3REAL05.画出下面的分程序结构的程序段当程序段3和4的编译即将完成以前的栈式符号表的图形（包括有效部分和失效部分）。第六章练习6.22考虑下面的类ALGO程序，画出当程序执行到和时，运行栈内容的图像。第七章练习7转换成三元式，间接2.将下面的语句 A:= (B+C) f E+(B+C)*F三元式和四元 式序列三元式四元式 + B, C(1) + B, C, T1(2) t (l)kE(2) T Tb E, T2(3) + B, C(3) + B. C T3(4) *(3),卩(4) *T3, F, T4(5) +(2),(5) +T2, T冬 T5：二 A, (5)(6) := A, T5间接三元式操作K(I)2、(2)3>(I)4.(3)5、6.+C(2) T(1) tE*(1),F(4) +(2),(3)(5)