编译原理习题解答(28页).doc-淘文阁

资源描述

《编译原理习题解答(28页).doc》由会员分享，可在线阅读，更多相关《编译原理习题解答(28页).doc（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、-编译原理习题解答-第 27 页第二章：习题2-4 Table表var x,y;procedure p; var a; procedure q; var b; begin b:=10; end; procedure s; var c,d; procedure r; var e,f; begin call q; end; begin call r; end; begin call s; end;begin call p;end根据：Page289，变量table:array0.txmax of record 结构体以及block函数得到下表，而表中各部分的含义，见教材Page18,Page19N

2、ameKinkVal /LevelAdrSizexvariable030yvariable040pprocedur010avariable130qprocedur134sprocedur170cvariable230dvariable240rprocedur200第三章文法和语言5. 写一文法，使其语言是偶正整数的集合要求：(1) 允许0打头(2) 不允许0打头解：(1) GS=(S,P,D,N,0,1,2,9,P,S)P:SPD|DP-NP|ND0|2|4|6|8N-0|1|2|3|4|5|6|7|8|9(2) GS=(S,P,R,D,N,Q ,0,1,2,9,P,S)P:SPD|P0|D

3、P-NR|NR-QR|QD2|4|6|8N-1|2|3|4|5|6|7|8|9Q-0|1|2|3|4|5|6|7|8|96. 已知文法G：:=|+|-:=|*|/:=()|i。试给出下述表达式的推导及语法树。(1)i; (2)(i)(3)i*i;(4)i*i+i; (5)i+(i+i);(6)i+i*i。解：(1) v=i=w(2) v=()=()=()=(i)=w(3) v=*=*=i*i=w(4) v=+=+=*+=*+=i*i+i=w(5) v=+=+=+=i+()= i+(+)=i+(+)= i+(+)=i+(i+i)=w(6) v=+=+=+=i+=i+*= i+*= i+i*i=w

4、语法树见下图:7. 为句子i+i*i构造两棵语法树，从而证明下述文法G是二义的。i( )i * ii + * iii + i( ) + ii + i * ii(1)i(2)(i)(3)i*i(4) i*i+i(5) i+(i+i)(6) i+i*i:=i|()|:=+|-|*|/解：为句子i+i*i构造的两棵语法树如下： + i * ii * + iii所以，该文法是二义的。8. 习题1中的文法GS是二义的吗？为什么？答：是二义的。因为对于句子abc可以有两种不同的生成树，即：S=Ac=abc和S=aB=abc11. 令文法GE为：ET|E+T|E-TTF|T*F|T/FF(E)|i证明E+T

5、*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。解：可为E+T*F构造一棵语法树（见下图），所以它是句型。EE + TT * F从语法树中容易看出，E+T*F的短语有：T*F是句型E+T*F的相对于T的短语，也是相对于规则TT*F的直接短语。E+T*F是句型E+T*F的相对于E的短语。句型E+T*F的句柄（最左直接短语）是T*F。12. 下述文法GE生成的语言是什么？给出该文法的一个句子，该句子至少含五个终结符，构造该句子的语法树。证明：是G的句型，并指出该句型的所有短语、直接短语和句柄。|a|b|c+|-*|/解：(1)计算文法GE的语言：由于L(T)=(a|b|c)(a|b|c

6、)(*|/)n|n=0所以L(E)=L(T)(L(T)(+|-)n|n=0(2)该文法的一个句子是aab*+,它的语法树是： aab*+(3) 证明：是G的句型，并指出该句型的所有短语、直接短语和句柄。由于下面的语法树可以生成，所以它是G的句型。由于 = ,且 = ,所以是句型相对于的短语，也是相对于规则的直接短语。由于 = 且 = ,所以是句型相对于的短语。显然，句型的句柄是。14. 给出生成下述语言的上下文无关文法：（1）anbnambm|n,m=0（2）1n0m1m0n|n,m=0（3）WaWt|W属于0|a*,W表示Wt的逆解：（1）所求文法为GS=(S,A,a,b,P,S),其中

7、P为：SAAAaAb|（2）所求文法为GS=(S,A,0,1,P,S),其中P为：S1S0|AA0A1|（3）W属于0|a*是指W可以的取值为,0,a,00,a0,aa0,00aa,a0a0,如果W=aa0a00,则Wt=00a0aa。所求文法为GS=(S,P,Q,0,a,P,S),其中P为：S0S0|aSa|a15. 语言WaW和anbmcndm是上下文无关的吗？能看出它们反映程序设计语言的什么特性吗？答：生成语言WaW的文法非常简单，如GS: SWaWWaW|bW|可见GS是上下文无关的。生成语言anbmcndm的文法非常复杂，用上下文无关文法不可能办到，只能用上下文有关文法。这是因为要在

10、1010361079810011下表由子集法将NFA转换为DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)A0B1,6B1,6C10D2,5,7C10D2,5,7E3,8B1,6E3,8F1,4,6,9F1,4,6,9G1,2,5,6,9,10D2,5,7G1,2,5,6,9,10H1,3,6,9,10I1,2,5,6,7H1,3,6,9,10J1,6,9,10K2,4,5,7I1,2,5,6,7L3,8,10I1,2,5,6,7J1,6,9,10J1,6,9,10D2,5,7K2,4,5,7M2,3,5,8B1,6L3,8,10F

11、1,4,6,9M2,3,5,8N3F1,4,6,9N3O4O4P2,5P2,5N3B1,6AB1C0D1E01F101H0G1I0K1J10L01M0011NOP011001(3)a(a|b)*|ab*a)* b (略)(4)b(ab)* | bb)* ab (略)2已知NFA=（x,y,z,0,1,M,x,z）其中：M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x, M(y,1)=,M(z,1)=y,构造相应的DFA。xy0z010010解：根据题意有NFA图如下下表由子集法将NFA转换为DFA：II0 = -closure(MoveTo(I,0)I1 = -c

12、losure(MoveTo(I,1)AxBzAxBzCx,zDyCx,zCx,zEx,yDyEx,yEx,yFx,y,zAxFx,y,zFx,y,zEx,y01100BCEF00DA1101下面将该DFA最小化：(1) 首先将它的状态集分成两个子集：P1=A,D,E,P2=B,C,F(2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21=C,F,P22=B。(3) 区分P1:由于A，E输入0到终态，而D输入0不

13、到终态，所以D与A，E可以区分，有P11=A,E,P12=D。(4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。(5) 综上所述，DFA可以区分为P=A，B，D，E，C，F。所以最小化的DFA如下：11010F0BE10DA03.将图4.16确定化：S0，1Z1V11U0Q0，1001图4.16解：下表由子集法将NFA转换为DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)ASBQ,VCQ,UBQ,VDV,ZCQ,UCQ,UEVFQ,U,ZDV,ZGZGZEVGZFQ,U,ZDV,ZFQ,U,ZGZG

14、ZGZAGDB0，10C110E010F010，14.把图4.17的(a)和(b)分别确定化和最小化：12435bbbbaaa0abaab01aa,ba(a) (b)解：(a):下表由子集法将NFA转换为DFA：IIa = -closure(MoveTo(I,a)Ib = -closure(MoveTo(I,b)A0B0,1C1B0,1B0,1C1C1A0可得图（a1），由于F(A,b)=F(B,b)=C,并且F(A,a)=F(B,a)=B,所以A,B等价，可将DFA最小化，即：删除B，将原来引向B的引线引向与其等价的状态A，有图(a2)。（DFA的最小化，也可看作将上表中的B全部替换为A，然

15、后删除B所在的行。）AabCaBbaAbCaa（a1）确定化的DFA （a2）最小化的DFA（b）:该图已经是DFA。下面将该DFA最小化：(6) 首先将它的状态集分成两个子集：P1=0,P2=1,2,3,4,5(7) 区分P2：由于F(4,a)=0属于终态集，而其他状态输入a后都是非终态集，所以区分P2如下：P21=4,P22=1,2,3,5。(8) 区分P22:由于F(1,b)=F(5,b)=4属于P21,而F(2,b)与F(3,b)不等于4,即不属于P21，所以区分P22如下：P221=1,5,P222=2,3。(9) 区分P221:由于F(1,b)=F(5,b)=4,即F(1,a)=1

16、,F(5,a)=5,所以1,5等价。(10) 区分P222:由于F(2,a)=1属于P221，而F(3,a)=3属于P222,所以2，3可区分。P222区分为P22212，P22223。1243bbaa0abaabb(11) 结论：该DFA的状态集可分为：P= 0,1,5,2,3,4 ,其中1,5等价。删去状态5，将原来引向5的引线引向与其等价的状态1，有图(b1)。(b1)最小化的DFA5构造一个DFA，它接收=0，1上所有满足如下条件的字符串：每个1都有0直接跟在右边。然后再构造该语言的正则文法。解：根据题意，DFA所对应的正规式应为：(0|(10)*。所以，接收该串的NFA如下：0121

17、00下表由子集法将NFA转换为DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)A0B0,2C1B0,2B0,2C1C1B0,211000BCA显然，A，B等价，所以将上述DFA最小化后有：0C1A0对应的正规文法为：GA：A1C|0A|C0A6设无符号数的正规式为：=dd*|dd*.dd*|.dd*|dd*e(s|)dd*|e(s|)dd*|.dd*e(s|)dd*|dd*.dd*e(s|)dd* 化简,画出的DFA，其中d=0,1,2,9,s=+,-解：把原正规式的每2，3项，4，5项，6，7项分别合并后化简有：=dd*|d*.d

18、d*|d*e(s|)dd*|d*.dd*e(s|)dd*=dd*|d*.dd*|(d*|d*.dd*)e(s|)dd*=(|d*.|(d*|d*.dd*)e(s|)dd*=(|d*.|d*(|.dd*)e(s|)dd*下面构造化简后的对应的NFA：57ed421.3dd6sdd.0 下表由子集法将NFA转换为DFA：IId =-closure(MoveTo(I,d)Ie=-closure(MoveTo(I,e)Is=-closure(MoveTo(I,s)I.=-closure(MoveTo(I,.)A0,1,4,6B1,7C5,6D2,6B1,7B1,7D2,6C5,6E7F6D2,6G3,

20、D2A7B7B3Q6D由上表可知：(1)因为4，5是DFA的终态，其他是非终态，可将状态集分成两个子集：P1=1，2，3，6，7，P2=4，5 (2)在P1中因为2,3输入b后是终态，而1，6，7输入b后是非终态，所以P1可区分为：P11=1，6，7，P12=2，3 (3)在P11中由于1输入b后为3，6输入b后为7，而3，7分属P11和P12，所以1与6不等价，同理，1与7不等价。所以P11可区分为：P111=1，P112=6，7(4)查看P112=6，7，由于输入a后为2，3，所以6，7是否等价由2，3是否等价决定。(5)查看P12=2，3，由于输入b后为4，5，所以2，3是否等价由4，5

21、是否等价决定。(6)查看P2=4，5 ，显然4，5是否等价由2，3与6，7是否同时等价决定。由于有（4）即6，7是否等价由2，3是否等价决定，所以，4，5是否等价由2，3是否等价决定。由于有（5）即2，3是否等价由4，5是否等价决定，所以有4，5等价，2，3等价,进而6，7也等价。(7)删除上表中的第3，5，7行，并将剩余行中的3，5，7分别改为对应的等价状态为2，4，6有下表：IIa Ib 1S2A2A2A2A4B,Z4B,Z2A6D6D2A6D这样可得最小化的DFA如下：a41b2aaabb6b8给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0解：把后两个产生式代入第一个产生

22、式有：S=01|01SS=10|10S有:S=01S|10S|01|10=(01|10)S|(01|10)=(01|10)*(01|10)即:(01|10)*(01|10)为所求的正规式。9将图4.18的DFA最小化，并用正规式描述它所识别的语言：a72bcbdb134c6aabbd5b图 4.18解：(1) 因为6，7是DFA的终态，其他是非终态，可将状态集分成两个子集：P1=1，2，3，4，5，P2=6，7。(2) 由于F(6,b)=F(7,b)=6,而6，7又没有其他输入，所以6，7等价。(3) 由于F(3,c)=F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)=6,F(4

23、,b)=7,而6，7等价，所以3,4等价。(4) 由于F(1,b)=F(2,b)=2,F(1,a)=3,F(2,a)=4,而3，4等价，所以1,2等价。(5) 由于状态5没有输入字符b,所以与1，2，3，4都不等价。(6) 综上所述，上图DFA的状态可最细分解为：P=1，2，3，4，5，6，7。abb13c6bd5a该DFA用正规式表示为：b*a(c|da)*bb*10构造下述文法GS的自动机：SA0AA0|S1|0该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么？解：由于该文法的产生式SA0，AA0|S1中没有字符集VT的输入，所以不是确定的自动机。要将其他确定化，必须先

24、用代入法得到它对应的正规式。把SA0代入产生式AS1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。代入SA0有该文法的正规式：0(0|01)*0，所以，改写该文法为确定的自动机为：0WX0Z00Y1由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化：下表由子集法将NFA转换为DFA：II0 = -closure(MoveTo(I,0)Ib = -closure(MoveTo(I,1)AWBXBXCX,Y,ZCX,Y,ZCX,Y,ZBX100CBA0由上表可知DFA为：第五章自顶向下语法分析方法1对文法GSSa|(T)TT,S|S(1) 给出(a,(a,a)

25、和(a,a),(a),a)的最左推导。(2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。(3) 经改写后的文法是否是LL(1)的？给出它的预测分析表。(4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。解：(1) (a,(a,a)的最左推导为S(T)(T,S)(S,S)(a,(T)(a,(T,S)(a,(S,a)(a,(a,a)(a,a),(a),a)的最左推导为S(T)(T,S)(S,a)(T),a)(T,S),a)(T,S,S),a)(S,(T),a)(T),(S),a) (T,S),(a),a)(S,a),(a),a)(a,a),(a),a)(2)由

26、于有TT,S的产生式，所以消除该产生式的左递归，增中一个非终结符U有新的文法G/S:Sa|(T)TSUU，SU|分析子程序的构造方法对满足条件的文法按如下方法构造相应的语法分析子程序。(1) 对于每个非终结号U，编写一个相应的子程序P(U)；(2) 对于规则U:=x1|x2|.|xn,有一个关于U的子程序P(U),P(U)按如下方法构造：IF CH IN FIRST(x1) THEN P(x1)ELSE IF CH IN FIRST(x2) THEN P(x2)ELSE .IF CH IN FIRST(xn) THEN P(xn)ELSE ERROR其中，CH存放当前的输入符号，是一个全程变量

27、；ERROR是一段处理出错信息的程序；P(xj)为相应的子程序。(3) 对于符号串x=y1y2.yn;p(x)的含义为：BEGIN P(y1);P(y2);P(yn);END如果yi是非终结符，则P(yi)代表调用处理yi的子程序；如果yi是终结符，则P(yi)为形如下述语句的一段子程序IF CH=yi THEN READ(CH) ELSE ERROR即如果当前文法中的符号与输入符号匹配，则继续读入下一个待输入符号到CH中，否则表明出错。(4) 如果文法中有空规则U:=EPSILON,则算法中的语句IF CH IN FIRST(xn) THEN P(xn)ELSE ERROR改写为：IF CH

28、 IN FIRST(xn) THEN P(xn)ELSE IF CH IN FOLLOW(U) THEN RETURN ERROR(5) 要分析一个OrgStr,应在该串的后面加上一个串括号#,并从子程序P(S)(S为文法的开始符号)开始，如果中途没有产生错误，并且最后CH=#,则说明OrgStr串合法，否则该串不合法。对每个非终结符写出不带回溯的递归子程序如下：char CH;/存放当前的输入符号void P_S()/非终结符S的子程序if(CH=a) READ(CH);/产生式Saelse if(CH=) READ(CH);/产生式Selse if(CH=()/产生式S(T)READ(CH

29、);P_T();IF (CH=) THEN READ(CH) else ERRORelse ERR;void P_T()/非终结符S的子程序if(IsIn(CH,FIRST_SU) /FIRST_SU为TSU的右部的FIRST集合P_S();P_U();void P_U()/非终结符U的子程序if(CH=,)/产生式U，SUREAD(CH);P_S();P_U();else/产生式Uif(IsIn(CH,FOLLOW_U) /FOLLOW_U为U的FOLLOW集合return ;else ERR;(3)判断文法G/S是否为LL(1)文法。各非终结符的FIRST集合如下：FIRST(S)=a,（

30、FIRST(T)=FIRST(S)=a,（FIRST(U)=，,各非终结符的FOLLOW集合如下：FOLLOW(S)=# FIRST(U) FOLLOW(T) FOLLOW(U)=#,，,)FOLLOW(T)=)FOLLOW(U)=FOLLOW(T)=)每个产生式的SELECT集合如下：SELECT(Sa)=aSELECT(S)=SELECT(S(T)=(SELECT(TSU)=FIRST(S)=a,（SELECT(U，SU)=，SELECT(U)=FOLLOW(U)=)可见，相同左部产生式的SELECT集的交集均为空，所以文法G/S是LL(1)文法。文法G/S的预测分析表如下：a()，#Sa

31、(T)TSUSUSUU，SU(5) 给出输入串(a,a)#的分析过程步骤分析栈剩余输入串所用产生式123456789101112#S#)T(#)T#)US#)Ua#)U#)US,#)US#)Ua#)U#)#(a,a)#(a,a)#a,a)#a,a)#a,a)#,a)#,a)#a)#a)#)#)#S(T)( 匹配TSUSaa匹配U，SU,匹配Saa匹配U)匹配接受2对下面的文法G：ETE/E/+E|TFT/T/T|FPF/F/*F/|P(E)|a|b|(1) 计算这个文法的每个非终结符的FIRST集和FOLLOW集。(2) 证明这个方法是LL(1)的。(3) 构造它的预测分析表。(4) 构造它的

32、递归下降分析程序。解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(E/)=+,FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(T/)=FIRST(T)=(,a,b,;FIRST(F)=FIRST(P)=(,a,b,;FIRST(F/)=FIRST(P)=*,;FIRST(P)=(,a,b,;FOLLOW集合有：FOLLOW(E)=),#;FOLLOW(E/)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E/)FO

33、LLOW(E)=+,),#;/不包含FOLLOW(T/)=FOLLOW(T)=FIRST(E/)FOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T/)FOLLOW(T)=(,a,b,+,),#;/不包含FOLLOW(F/)=FOLLOW(F)=FIRST(T/)FOLLOW(T)=(,a,b,+,),#;FOLLOW(P)=FIRST(F/)FOLLOW(F)=*,(,a,b,+,),#;/不包含(2)证明这个方法是LL(1)的。各产生式的SELECT集合有：SELECT(ETE/)=FIRST(T)=(,a,b,;SELECT(E/+E)=+;SELECT(E/)=FOLLOW(E/)=),#SELECT(TFT/)=FIRST(F)=(,a,b,;SELECT(T/T)=FIRST(T)=(,a,b,;SELECT(T/)=FOLLOW(T/)=+,),#;SELECT(FPF/)=FIRST(P)=(,a,b,;SELECT(F/*F/)=*;SELECT(F/)

展开阅读全文