编译原理课后习题解答.doc

4a127bc8a3b06af203f32b386ef05472.pdf1/27/2020 Page 23 of 23第一章 引言1解释下列名词 源程序，目标程序，翻译程序，汇编程序，编译程序，遍 答： 源程序： 由汇编语言或高级程序语言编写的程序。 目标程序：由目标语言编写的程序。 翻译程序：把源程序转化为目标程序的程序。 汇编程序：把由汇编语言编写的源程序转换成目标程序(由机器语言编写)的翻译程序。 编译程序：把由高级程序语言编写的源程序转换为一台具体计算机的机器语言或汇编语言程序的翻译程序。 遍：对源程序或源程序的中间形式从头到尾扫描一遍，并做有关的加工处理，生成新的源程序的中间形式或目标程序。2典型的编译程序可划分为哪几个主要的逻辑部分？各部分的主要功能是什么？ 答：典型的编译程序可划分7个主要的逻辑部分（模块）。 词法分析 将字符串形式的源程序分解为具有独立语法语意的单词符 号（Token）; 语法分析 从词法分析程序取得源程序，并将一个或多个单词组合为 语言的各种语法类。 语义分析 确定源程序的意义（语义）。 代码生成 将源程序的中间形式转化为汇编语言或机器语言。 代码优化 获得更高效的目标程序。 出错出理 对源程序的错误精确定位并能够跳过错误继续编译。 符号表管理 保存每个标志符及其属性，并保存过程名及其参数。 注意：区分编译过程的5个阶段和编译程序的7个逻辑组成部分。第二章 文法和语言的概念和表示设关于句子的一组规则为：句子：=主语谓语主语：=名词短语名词短语：=名词名词短语：= 形容词名词短语形容词：=big形容词：=brown形容词：=roasted名词：=John名词：=peanut谓语：=动词直接宾语动词：=ate直接宾语：=冠词名词短语冠词：=the给出下述句子的推导，并画出语法树。解：（A） 句子=主语谓语=主语动词直接宾语=主语动词冠词名词短语=主语动词冠词形容词名词短语=主语动词冠词形容词名词=主语动词冠词形容词peanut=主语动词冠词big peanut=主语动词the big peanut=主语ate the big peanut=名词短语ate the big peanut=名词ate the big peanut= John ate the big peanut (语法树略) (B) 句子=主语谓语=名词短语谓语=名词谓语= John谓语= John动词直接宾语= John ate直接宾语= John ate冠词名词短语= John ate the名词短语= John ate the形容词名词短语= John ate the big名词短语= John ate the big形容词名词短语= John ate the big brown名词短语= John ate the big brown名词= John ate the big brown peanut （语法树略） (C) 句子=主语谓语=名词短语谓语=名词谓语= John谓语= John动词直接宾语= John ate直接宾语= John ate冠词名词短语= John ate the名词短语= John ate the形容词名词短语= John ate the big名词短语= John ate the big形容词名词短语= John ate the big roasted名词短语= John ate the big roasted名词= John ate the big roasted peanut（语法树略）2.利用规则2-1，除最左推导外，给出句子the big elephant ate the peanut的另外两种推导（其中一种为最右推导）。 答：(A) 最右推导 句子=主语谓语=主语动词直接宾语=主语动词冠词名词=主语动词冠词peanut=主语动词the peanut=主语ate the peanut=冠词形容词名词ate the peanut=冠词形容词 elephant ate the peanut=冠词big elephant ate the peanut= the big elephant ate the peanut (B) 句子=主语谓语 =主语动词直接宾语 =冠词形容词名词动词直接宾语 =冠词形容词名词动词冠词名词 = the形容词名词动词冠词名词 = the big名词动词冠词名词 = the big elephant动词冠词名词 = the big elephant ate冠词名词 =the big elephant ate the名词=the big elephant ate the peanutP191.令A=$,又令Z=$,写出如下的符号串以及它们的长度：Z，ZZ，Z2 ，Z3，Z0，A*=？ 解：Z=$ |Z|=1 ZZ=$ |ZZ|=2 Z2=ZZ=$ | Z2|=2 Z3=$ | Z3|=3 Z0= | Z0|=1 A*=,$,$,$, |A*|= 2.令A=0,1,2,又令x=01，y=2，z=001，写出如下符号串及它们的长度： xy, xyz, x4, (x3)(y2), (xy)2 解：xy=012, |xy|=3xyz =012001, | xyz |=6 x4=xxxx=01010101, | x4 |=8 (x3)(y2)=01010122, | (x3)(y2)|=8 (xy)2=012012, |(xy)2 |=6令A=0,1,2,写出集合A+和集合A*的7个最短的符号串。解：A+的7个最短的符号串为： 0，1，2，00，01，02，10 （答案不唯一）A*的7个最短的符号串为：，0，1，2，00，01，02， （答案不唯一） 4. 试证明：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*AP261.设G标志符的规则是 ：标志符:=a|b|c|标志符a|标志符c|标志符0|标志符1 试写出VT和VN，并对下列符号串a,ab0,a0c01,0a,11,aaa给出可能的一些推导。 解：VT =a,b,c,0,1， VN =标志符 不能推导出ab0,11,0a标志符=a 标志符=标志符1 =标志符01 =标志符c01 =标志符0c01 = a0c01 (4)标志符=标志符a =标志符aa =aaa2. 写一文法，使其语言是偶整数的集合。 解：G偶整数： 偶整数:=符号偶数字|符号数字串偶数字，（作用是一位和多位） 符号:= + | | 数字串:= 数字串数字|数字 数字:= 偶数字| 1 | 3 | 5 | 7 | 9 偶数字:=0 | 2 | 4 | 6 | 83. 写一文法，使其语言是偶整数的集合，但不允许有以0 开头的偶整数。 解：G偶整数： 偶整数:= 符号单偶数|符号首数字数字串尾偶数 符号:= + | | 单偶数:=2 | 4 | 6 | 8 尾偶数:= 0 |单偶数 首数字:= 1 | 3 | 5 | 7 | 9 |单偶数 数字串:= 数字串数字|数字| 数字:= 0 |首数字4. 设文法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. 试对如下语言构造相应文法： a(bn)a | n=0,1,2,3,其中左右圆括号为终结符。 （an）（bn） | n=1,2,3, 解：（1）文法GS： S:= a(B)a B:= bB |b|( 2 ) 文法GS： S := (A)(B) A:= aA|a B:= bB|b6. 文法G3表达式： 表达式:=项|表达式+项|表达式项 项:=因子|项*因子|项/因子 因子:=（表达式）| i 试给出下列符号串的推导： i, (i), i*i, i*i+i, i*(i+i)解：（1）表达式=项=因子= i ( 2 ) 表达式=项=因子=（表达式）=（项）=（因子）=（i） （3）表达式=项 =项*因子=项* i=因子* i= i*i（4）表达式=表达式+项=表达式+因子=表达式+ i=项+ i=项*因子+ i=项* i + i=因子* i + i= i * i + i （5）表达式=项=项*因子=项*（表达式）=项*（表达式+项）=项*（表达式+因子）=项*（表达式+ i）=项*（项+ i）=项*（因子+ i）=项*（i+ i）=因子*（i+ i）= i *（i+ i）7. 对文法G3表达式（见上题），列出句型表达式+项*因子的所有短语和简单短语。解：句型表达式+项*因子的短语有： 表达式+项*因子和项*因子 简单短语是：项*因子 注意：求短语，简单短语和句柄尽量用语法树。8. 文法V:= aaV | bc的语言是什么？ 解：L（GV）= a2nbc | n=0,1,2, 9. 设文法G为： N:=D|ND D:=0|1|2|3|4|5|6|7|8|9G的语言是什么？给出句子0125和783的最右推导（规范推导）和最左推导。 解：（1）L（G）=所有无符号整数 （2）N=ND=N5=ND5=N25=ND25=N125=0125（最右推导（规范推导） N=ND=NDD=DDD=7DD=78D=783（最左推导）P331.给定文法GE为： E:=RP|P P:=（E）| iR:=RP+ | RP* | P + | P*证明 （1）i+i* (i+i)是文法G的句子。 （2） 画出该句子的语法树。 证：（1）E=RP=RP* P=RP*（E）=RP*（RP）=RP*（P+P）=RP*（P+i）= RP*（i+i）=P+P*（i+i）= P+i*（i+i）= i+i*（i+i）Vt* i+i* (i+i)是文法G的句子（对应的语法树略）2.画出下列推导的语法树。（1）123123 (2) 由上图可知两种推导的语法树是相同的。4. 由下述语法树构造推导：（语法树书上P34上，未画）。解：（1）表达式=项 =项*因子 =因子*因子 = i*因子 = i* i ( 2 ) 表达式=项=项*因子 =因子*因子= i*因子= i * (表达式)= i * (表达式+项)= i * (项+项)= i * (因子+项)= i * ( i +项)= i * ( i +因子)= i * ( i + i )5 已知文法GE：E:=ET+ | TT:=TF* |FF:=FP |PP:=（E）| i 有句型TF*PP+，问此句型的短语，简单短语，和句柄是什么？解：此句型的短语有：TF*PP+，TF*，PP，P简单短语有：TF*，P句柄是：TF* 注意：求短语，简单短语和句柄尽量用语法树。6. 分别对i+i*i和i+i+i中的每一个句子构造两棵语法树，从而证明下列文法G表达式是二义的。 表达式:= i | (表达式) |表达式运算符表达式 运算符:= + | | * | / 解：以i+i*i为例: 8 证明下面的文法G是二义的：S:= iSeS | iS | i证：由文法可知iiiei是该文法的句子，又由文法可知iiiei有两棵不同的语法树。所以该文法是二义性文法。7 文法G3表达式为： 表达式:=项|表达式+项|表达式项 项:=因子|项*因子|项/因子 因子:=（表达式）| i证明此文法的句子i+i*i和i+i+i是无二义性的。在句子i+i*i中，哪种运算符是优先的？在句子i+i+i中，又是哪种运算符？证：J（容易证明文法规则右边出现有选折项时，各项首符号集不相交，且该文法不是左递归文法）。 在句子i+i*i中，运算符*是优先的在句子i+i+i中，第一个+运算符是优先的9有文法GN：N:=SE|EE:=0|2|4|6|8|10S:=SD|DD:=0|1|2|9举例说明文法GN 是二义的。此文法描述的语言是什么？试写出另一文法G，使L（G）=L（G），且G是无二义性的。解：由文法可知10是该文法的句子，又由文法可知10有两棵不同的语法树。 此文法描述的语言L（G）=无符号偶数 所求文法G无符号偶数： 无符号偶数:=偶数字|数字串偶数字 数字串:= 数字串数字|数字 数字:= 偶数字| 1 | 3 | 5 | 7 | 9 偶数字:=0 | 2 | 4 | 6 | 8 （*上述提供文法中的第二条规则右部的10选折项去掉似乎就符合要求了行*） 第三章P671解： 其状态图为： start e由状态图知： f ,eeff不是合法的句子 eefe是该文法的句子。2解：正则文法为GZ： ZA10 AA00该文法的 V=Z,A,1,0 Vn=Z,A Vt=1,0该文法所确定的语言为：LGZ0n1或0n15证明：AAxxLA或xLAxxLAA（A*）*（A*）0（A*）1（A*）2（A*）n(A0A1A2An) (A1) A0A1A2An AAA*所表示的语言是LALA*LA0LA（LA0LA1LA2）LA0LA1LA2LA*故AA*A*(LALB)*LA=(LALBLALBLALBLALBLALBLALB) LA =LALALBLALALBLALBLALALBLALBLALBLA = LA(LBLALBLALBLA) = LA(LBLA) (AB)*=A(AB)*三个表达式所描述的语言都是LALA中任意组合 （A|B）*=(A*B*)=(A*|B*)*6解： R1=01对应的自动机为 (R1)*=(0|1)* 对应的自动机为M2将M2确定化start01P0P1P2P3start10P1 P2eefeSABZ状态 输入 01 P0P1,P3 P1P2P2 P2P1,P3 P3 I I0 I1(空)状态 输入 0 1P0,P1,P3P1,P2,P3P1,P2,P3 P0P1P1P1,P2,P3P1,P2,P3P1,P2,P30,1start01q2q1q0start0P0P11 P1P1P11000000100111S0S1S2S8S4S14S7S5S6S11S31110001S10S12S130startS9010P1P2P401P0start111100100P10P12P13P30105P6P7P8P11P9P141110011q2q7q1startq0q9q100000011q6q5q4q3q8P00,1（注：上图中的（空）列表示没有该列。即上图为两个独立的表）状态转换图为：简化为：R=1(0|1)*|0 的DFA M为： R1=1010*|1(010)*1对应的DFA M为：R2=(1010*|1(0|0)*1)* 对应的DFA M为：对应R=1(1010*|1(010)*1)*0 的DFA M为：8.解：(a) I Ia Ib 0 0,1 1 0,1 0,1 1 1 0 DFA的状态转换矩阵为： 状态 输入 a b q0 q1 q2 q1 q1 q2 q2 q0 YNSym=(?)nextsymNSym=d(?) BNSym=)(?)errornextsym BSym=e(?)nextsymerrorYerrorNSym=c(?)nextsymnextsymNSym=c(?) 化简：p0= q0= q1 p1= q2a 状态图为 ：abstartP1P0 10解：它所识别的语言为：(1010)*第四章 语法分析P801. 解：（见课本）2解：文法有左递归，故先改写文法：A A=(B)|dBe B=cc下面给出两个分析子程序的框图： BY YYNY两分析子程序如下：procedure A; IF sym=( THEN Begin Nextsym; B; If sym=) Then Nextsym; Else Error End; ELSE If sym=d Then Begin Nextsym; B; if sym=e then Nextsym else Error End; Else Error; Procedure B;NYYNSym=c(?)NSym=a(?) A BSym=c(?)Sym=d(?) B nextsym errorZNYYNSym=c(?)errror nextsymSym=a(?) BAYYSym=a(?)NerrrornextsymSym=c(?)ANB IF sym=c THEN Begin Nextsym; While sym=c do Nextsym End ELSE Error;/*程序中nextsym为读字符子程序，error为出错处理子程序*/*主程序*/ program G; VAR sym:CHAR; BEGIN Nextsym; A; END3解：（1）。 FIRST(AcB)=c FIRST(Bd)=a FIRST(AaB)=c FIRST(c)=c FIRST(aA)=a FIRST(a)=a(2). 若用不带回溯的自顶向下的语法分析程序，必须改写文法： ZAcB|Bd AcaB BaA 因为调用分析子程序A的过程中，调用了B子程序，在B中又调用了A，相当于A间接的调用了A，所以该文法应编写成递归子程序。(3). 三个分析子程序框图如下： YY三个分析子程序为：Created by ITLearner-2004 1/27/2020- 23 -procedure Z; if sym=c thenbegin A; If sym=c then B; Else ErrorEnd; ElseIf sym=a then Begin B; If sym=d then Nextsym; Else Error End;Else Error;Procedure A;If sym=c then Begin Nextsym; While sym=a do B; End;Else Error;Procedure B;If sym=a then Begin Nextsym; If sym=c then A; End;Else Error;4解：首先改写文法如下：语句变量表达式 if表达式then语句else语句变量i()|)表达式项+项项因子*因子因子变量|()语法分析程序(pascal)共有五个子程序statement,expr,item,factor,varprocedure statement;if sym=if then begin nextsym; expr; if sym=then then begin nextsym; statement; if sym=else then begin nextsym; statement; end; end; else error; end;else begin var; if sym=:= then begin nextsym; expr; end; else error; end;procedure expr;item;while sym=+ do begin nextsym; item; end;procedure item;factor;while sym=* do begin nextsym; factor; end;procedure var;if sym=i then begin nextsym; if sym=( then begin nextsym; expr; if sym=) then nextsym; else error; end; end;else error;procedure factor;if sym=( then begin nextsym; expr; if sym=) then nextsym; else error; end;else var;P871.解：（1）。FIRST(P)=(,a,b,) FOLLOW(E)=#, ) FIRST(F)=, FOLLOW(E)= #,) FIRST(F)=(,a,b,) FOLLOW(T)= #,+ FIRST(T)= (,a,b, ) FOLLOW(T)= #,+ FIRST(T)= (,a,b, FOLLOW(F)= (,a,b, ),+,# FIRST(E)=+, FOLLOW(F)= (,a,b, ),+# FIRST(E)= (,a,b,) FOLLOW(P)= (,a,b, ),+,#,*(2)证明：对于E+E| FIRST(+E)=+ FIRST()= FOLLOW(E)=#, FIRST(+E)FIRST()= FIRST(+E)FOLLOW(E)= 对于TT| FIRST(T)FOLLOW(T)= 对于F*F| FIRST(*F)FOLLOW(F)= 对于P(E)|a|b| FIRST(E)=() FIRST(a)=a FIRSTb=b FIRST= 根据LL(1)文法的充要条件可以断定该文法是LL(1)文法.(3).构造其分析表如下： a b ( ) * + # EETEETEETEETE EEE+EE TTFTTFTTFTTFT TTTTTTTTTTTT FFPFFPFFPFFPF FFFFFFF*FFF PPaPbPP(E) (注：空白处均为ERROR)2解： （2）FIRST（aABbcd）=a;FIRST(e)=e;FIRST(Asd)=a,d;FRIST(SAh)=a,h;FIRST(eC)=e; FRIST(Sf)=a,f;FIRST(Cg)=g,a,f;FRITS(aBD)=a; （3）对于CSf | Cg，FIRST（Sf） FIRST（Cg）=a,f此文法不是LL（1）文法。解：本题错误。6解：一个文法是文法的充要条件是：AVn,A的任何两条不同的规则A:=|有下列条件成立：* FIRST()FIRST()= =，则FIRST()FOLLOW(A)= 证明：充分性：*对于任意非终结符A 若A:=|满足上述条件，取分析表项MA,a,aVt若A=a假设=a即aFIRST() FIRST()FIRST()= * aFIRST() 分析表项MA,a= A:= 若=,且aFOLLOW (A) aFIRST() MA,a= A:= 否则 MA,a=error 综上，分析表的元素无多重定义，符合LL(1)文法定义,是LL(1)文法必要性： 令对于LL(!)文法G的 AVn, A:=|条件不成立 FIRST()FIRST()=B FIRST()FIRST()=C* 若a,则MA,a中，可同时存在 A:=及A:= 若=则MA,a中,可同时存在A:= A:= 两条规则 这与定义相矛盾，假设错误必要性得证。P1003.解：procedure INSERT(u,a) if not Lu,a then begin Lu,a:=true; 将(u,a)压入栈STACK end;program MAIN; begin for 每个非终结符U和终结符a do Lu,a:=false; For 每条形如U:=a或U:= aV规则 do INSERT(U,a); While STACK 非空 DO Begin 将STACK栈顶弹出，记为(V,a); for 每条形如U:=V规则 do INSERT(U,a); End; EndP1092.解：I0=closure(S.E#)=S.E#,E.wX,E.xYI1=goto(I0,E)=closure(SE.#)=SE.#I2=goto(I0,w)=closure(Ew.X)=Ew.X,X.yX,X.zI3=goto(I0,x)=closure(Ex.Y)=Ex.Y,Y.yY,Y.zI4=goto(I1,#)=closure(SE#.)= SE#.I5=goto(I2,X)=closure(EwX.)= EwX.I6=goto(I2,y)=closure(Xy.X)= Xy.X, X.yX,X.z I7=goto(I2,z)=closure(X.z)= Xz.I8=goto(I3,Y)=closure(ExY.)= ExY.I9=goto(I3,y)=closure(Yy.Y)= YyY.I10=goto(I3,z)=c