编译原理习题答案.ppt

《编译原理习题答案.ppt》由会员分享，可在线阅读，更多相关《编译原理习题答案.ppt（62页珍藏版）》请在三一办公上搜索。

1、习题16试用各种不同的形式表示法描述1的一切精度 的近似值集合。解：省略表示法 1.3,1.33,1.333,描述表示法 1.3i|i1或1.3i|i=1 错误：x|x=1+310-i|i=1,因为形式表示不应涉及任何含义。错误：GN:N:=1.M M:=M3 M:=3,因为文法仅一组重写规则，不是语言。若给出答案：L(GN)，正确，但不简洁,7.设字母表x=0,1,2,3,4,5,6,7,X+与X*各是什么？各举出4个不同长度的符号串作为例子。解：X是字母表x的正闭包，X*是字母表的闭包，X*=X+X+=0,1,00,01,123,345,1234,2345，因此是一切可能带前导0的八进制数

2、的集合 X*=,0,1,00,01,12,345,3456,X+:0,1,00,123 X*:,1,00,123,习题22设文法G的规则是:=a|b|c|a|c|0|1 试写出VT与VN,并对下列符号串a、ab0、a0c01、0a、11与aaa给出可能的推导。解：VT=a,b,c,0,1 VN=a:=a ab0:=0 不能直接推导出 b0,因此不能直接推导出ab0(不能写:=0=b0 不能推导出ab0)a0c01:=1=01=c01=0c01=a0c01 0a:=a 不能直接推导出0a(不能写:=a=0a 不能推导出0a）11:=1 不能直接推导出11(不能写：=1=11 不能推导出11)aa

3、a:=a=aa=aaa,3设GE:E:=T|E+T|E-T T:=F|T*F|T/F F:=(E)|i 1)试给出关于(i)、i*i-i与(i+i)/i的推导。2)证明E+T*F*i+I 是该文法的句型，然后列出它的一切短语与简单短语。解：1）给出推导 E=T=F=(E)=(T)=(F)=(i)不能写：E=T=F=(E)=(i)可以写:E=T=F=(E)=+(i)E=E-T=T-T=T*F-T=F*F-T=i*F-T=i*i-T=i*i-F=i*i-i(最左推导)或 E=E-T=E-F=E-i=T-i=T*F-i=T*i-i=F*i-i=i*i-i(最右推导),E=T=T/F=F/F=(E)/

4、F=(E+T)/F=(T+T)/F=(F+T)/F=(i+T)/F=(i+F)/F=(i+i)/F=(i+i)/i(最左推导)或 E=T=T/F=T/i=F/i=(E)/i=(E+T)/i=(E+F)/i=(E+i)/i=(T+i)/i=(F+i)/i=(i+i)/i(最右推导),2)证明E+T*F*i+i是该文法的句型：E=E+T=E+T+T=E+T*F+T=E+T*F*F+T=E+T*F*i+T=E+T*F*i+F=E+T*F*i+i或E=E+T=E+F=E+i=E+T+i=E+T*F+i=E+T*i+i=E+T*F*i+i即，E=*E+T*F*i+i，所以是该文法的句型。因为 E=*E

5、E=+E+T*F*i+i E=*E+i E=+E+T*F*i E=*E+T+i T=+T*F*i E=*E+T*F*i+T T=+i E=*E+T*i+i T=T*F E=*E+T*F*F+F F=i(=+包括=)所以 句型E+T*F*i+i中 相对于E的短语有 E+T*F*i+i和E+T*F*i 相对于T的短语有T*F*i、T*F和i 相对于F的短语有i所以 句型E+T*F*i+i中 相对于T的简单短语有T*F 相对于F的简单短语有i,不能用画语法分析树的方法来寻找短语，因按教学进度，还未讲到语法分析树。简单短语可如下寻找：首先寻找与规则右部相同的子符号串，把它归约成相应的非终结符号后,看是

6、否是句型,如果仍是，则此子符号串是简单短语，否则不是。例如，子符号串E+T,可归约成E,但归约后成为E*F*i+i,显然不是句型，所以，E+T不是简单短语。对于短语，类似地寻找，即，先找子符号串,看它能否归约到某个非终结符号,再看归约后得到的新符号串是否是句型，是，则是短语，否则，不是短语。当在学习了语法分析树之后，可以也应该使用语法分析树来寻找短语与简单短语。,2)ambn|nm0解：可把ambn(nm0)写成ambmbn-m。易见可有文法GS：S:=Sb|Ab A:=ab|aAb 也可以写出下列文法：GS：S:=ab2|Sb|aSb 或GS：S:=aSbaBb B:=Bbb 可见给定一个语

7、言，可以为它构成若干个不同的文法。,习题34通常程序设计语言包含一些嵌套结构，例如，平衡的括号对，以及对应的if与else等。试简要说明为什么这些结构不能用正则文法描述。答：通常程序设计语言必定包含一些嵌套结构,例如，平衡的括号对，以及对应的if与else等。它们的存在必定因下列规则的必定存在：E:=E+T|T T:=T*F|F F:=(E)|i 以及 S:=if(E)S else S 因此，E=*xEy x,y 与 S=*uSv u,v,即,E与S等必定是具有自嵌套特性的非终结符号。因此通常的程序设计语言的文法必具有自嵌套特性的非终结符号，也就是说不可能是正则文法。,5下列文法中哪一个是自嵌

8、套的，请说明理由。对于非自嵌套文法给出等价的正则文法。G1=(A,B,C,a,b,P1,A)P1：A:=CB|b B:=CA C:=AB|a答：因存在自嵌套的非终结符号B：B=CA=ABA 即，B=*ABA，A,所以文法G1是自嵌套的。G2=(A,B,C,a,b,P2,A)P2：A:=CB|Ca B:=bC C:=aB|b答：因不可能得到推导：A=*xAy,其中，对于B与C，情况类似，所以A、B与C都不是自嵌套的非终结符号，文法G2是非自嵌套的文法。为构造等价的正则文法，首先确定相应语言。,C=aB=abC=abaB=ababC=(ab)iC=(ab)ib，即，C=*(ab)ibB=bC=ba

9、B=(ba)iB=(ba)ibC=*(ba)ib(ab)jb 即，B=*(ba)ib(ab)jb A=CB=*(ab)ib(ba)jb(ab)kb 又，A=Ca=(ab)iba 即,A=*(ab)iba,所以,L(G2)=(ab)ib(ba)jb(ab)kb|i,j,k0(ab)i ba|i0对于文法G2,可以采用图示法给出相应的正则文法a b a bab b a 可给出如下的规则：A A:=a A:=Ba B:=Ab B C:=Bb S:=Ca A B C S,显然，S=Ca=Bba=Abba=Babba=Ababba=Bababba=B(ab)i-1ba=(ab)iba即，S=*(ab)i

10、ba(i=1)。为使i=0,让C:=b，因此，对于(ab)iba|i=0有下列规则：S:=Ca C:=Bb|b B:=Ab A:=Ba|a 对于(ab)ib(ba)jb(ab)kb|i,j,k=0可类似地给出一组规则，这里不拟详细给出。只是请注意：可利用前面的规则以减少规则的个数。,习题44试用不同的方法消去文法G：I:=Ia|Ib|c 的 规则左递归。解:步骤1 判定文法是规则左递归 步骤2 消去规左递归。步骤3 方法1 改写规则左递归成右递归。等价文法G为：I:=cI I:=(a|b)I|方法2 改写成扩充BNF表示法.应用规则1提因子有：I:=I(a|b)|c，应用规则2有I:=ca|b

11、 等价文法G 为：I:=ca|b,5试消去文法GW：W:=A0 A:=A0|W1|0 的 文法左递归与规则左递归。解:步骤1 判定文法是文法左递归还是规则左递归 步骤2 判定文法是文法左递归，所以按相应算 法消去文法左递归如下。步骤2.1：把终结符排序成U1=W,U2=A(n=2)步骤2.2：执行循环 i=1 j=1:ji 1 不执行关于j的循环，且关于U1=W 不存在规则左递归。i=2 j=1,有规则 A:=W1|A0|0形如U2:=U1,把U1:=r1，即，把W:=A0代入得：A:=A01|A0|0 即，A:=A(01|0)|0 j=2,ji-1 消去关于U2=A的规则左递归有 A:=0A

12、,A:=(01|0)A|,步骤3 最后得到消去左递归的等价文法GW：W:=A0 A:=0A A:=(01|1)A|说明：如果在第二步中，把原文法等价变换成扩充表示法，则最终的等价文法是 GW:W:=A0 A:=001|0,6试消去文法GS：S:=Qc|Rd|c Q:=Rb|Se|b R:=Sa|Qf|a解:步骤1 首先判定是文法左递归还是规则左递归 步骤2 是文法左递归，按相应算法处理如下。步骤2.1 把非终结符号排序成 U1=S U2=Q U3=R(n=3)步骤2.2 执行循环：i=1 j=1:ji 1，不执行关于j的循环,且关于U1=S 不存在规则左递归。i=2 j=1,有规则Q:=Se|

13、Rb|b,形如U2:=U1,把U1:=r1即，把S:=Qc|Rd|c 代入，得：Q:=(Qc|Rd|c)e|Rb|b，整理后 Q:=Qce|Rde|Rb|ce|b j=2,ji-1 对U2其消去规则左递归，得 Q:=(R(de|b)|ce|b)Q Q:=ceQ|,(按扩充表示法，有 Q:=（Rb|Rde|ce|b）ce)i=3 j=1,有规则R:=Sa|Qf|a，形如U3:=U1形，把U1:=r1,即，S:=Qc|Rd|c代入:R:=(Qc|Rd|c)a|Qf|a，整理后，R:=Rda|Qca|Qf|ca|a 注意:j循环还未结束,不能消去Ui=R的规则左递归!j=2,有规则R:=Rda|Qc

14、a|Qf|ca|a，形如U3:=U2，把 U2:=r2,即，把Q:=(R(b|de)|ce|b)Q 代入，(按扩充表示法代入的是 Q:=(Rb|Rde|ce|b)ce)所以 R:=Rda|(R(b|de)|ce|b)Q(ca|f)|ca|a，整理:R:=R(b|de)Q(ca|f)|da)|(ce|b)Q(ca|f)|ca|a j=3,ji-1 消去关于U3=R的规则左递归,得：R:=(ce|b)Q(ca|f)|ca|a)R R:=(b|de)Q(ca|f)|da)R|(当按扩充表示法时是:R:=(ce|b)Q(ca|f)|ca|a)(b|de)Q(ca|f)|da),步骤3 最后消去了左递归

15、的等价文法GS：S:=Qc|Rd|c Q:=(R(b|de)|ce|b)Q Q:=ceQ|R:=(b|ce)Q(ca|f)|ca|a)R R:=(b|de)Q(ca|f)|da）R|(按扩充表示法时是GS:S:=Qc|Rd|c Q:=(Rb|Rde|ce|b)ce R:=(ce|b)Q(ca|f)|ca|a)(b|de)Q(ca|f)|da),习题51.设有文法GS：S:=aAcB|BdS B:=aScA|cAB|b A:=BaB|aBc|a 试对下列符号串：1）aabcccab 2)ababccbb 进行句型分析，识别是否是文法GS的句子。当是句子时，给出 最左推导、最右推导与相应的语法分析

16、树。解：1）建立最左推导如下：S=aAcB=aaBccB=aabccB=aabcccAB=aabcccaB=aabcccab 即,S=*aabcccab 因此，aabcccab是该文法的句子。最右推导如下:S=aAcB=aAccAB=aAccAb=aAccab=aaBcccab=aabcccab语法分析树：,画语法分析树并不一定要先写出推导，事实上，根据所给符号串的形式来选择合适的规则便可。例如，输入符号串是（i），不包含if，自然选择 I:=E，之后，因有(与)，自然选E:=(E)，等等。对于输入符号串if i then i else(i)，自然选择I:=if B T。其他情况类似。,3.为

17、题2中的状态转换图写出相应的有穷状态自动 机。它能接受字符串0011011吗？解：这是一个确定有穷状态自动机，因此可写出DFA D如下：DFA D=(K,0,1,M,A,E,F)其中 K=A,B,C,D,E,F M：M(A,0)=B M(B,0)=D M(B,1)=C M(C,0)=A M(C,1)=F M(D,0)=A M(D,1)=C M(E,0)=D M(E,1)=C M(F,0)=E M(F,1)=A,M：M(A,0)=B M(B,0)=D M(B,1)=C M(C,0)=A M(C,1)=F M(D,0)=A M(D,1)=C M(E,0)=D M(E,1)=C M(F,0)=E M

18、(F,1)=A 对输入字符串0011011运行该DFA：M(A,0011011)=M(M(A,0),011011)=M(M(B,0),11011)=M(M(D,1),1011)=M(M(C,1),011)=M(M(F,0),11)=M(M(E,1),1)=M(C,1)=F因为FE,F,所以字符串0011011可以被该DFA所接受。注意，在一般情况下，必须首先判别是确定的FA，还是非确定的FA，然后再写出相应的FA。,6.设有NFA，其状态转换图如图所示，试为其构造DFA。解：步骤1 首先写出NFA，然后再确定化。NFA N(S,V,M,U,Z,0,1,M,S,Z）其中:M:M(S,0)=V,M

19、 M(S,1)=M,U M(V,0)=Z M(V,1)=M(M,0)=V,M M(M,1)=M,U M(U,0)=M(U,1)=Z M(Z,0)=Z M(Z,1)=Z,步骤3 构造DFA如下：DFA N=(K,0,1,M,S,F)其中：K=S,MV,MU,MUZ,MVZ M:M(S,0)=VM M(S,1)=MU M(MV,0)=MVZ M(MV,1)=MU M(MU,0)=MV M(MU,1)=MUZ M(MVZ,0)=MVZ M(MVZ,1)=MUZ M(MUZ,0)=MVZ M(MUZ,1)=MUZ F=MVZ,MUZ,注意：1.DFA N的状态名必须用方括号对与括住，且状态名中所包含的

20、字母必须按字典顺序排列（数字也一样）。2.终止状态之名则必须包含原NFA中终止状态名，如，新终止状态名MVZ中包含了原终止状态名Z。,7.设有NFA A=(q0,q1,q2,a,b,M,q0,q1),其中M为:M(q0,a)=q1,q2 M(q0,b)=q0 M(q1,a)=q0,q1 M(q1,b)=M(q2,a)=q0,q2 M(q2,b)=q 试为其构造DFA,它能接受bababab与abababb吗？解：首先写出状态转换矩阵如下。a b q0 q1,q2 q0 q1,q2 q0,q1,q2 q1 q0,q1,q2 q0,q1,q2 q0q1 q1 q0q1 q0,q1 q0,q1,q2

21、 q0,所以 DFA A=(K,a,b,M,q0,F)其中：K=q0,q1,q0q1,q1q2,q0q1q2 M:M(q0,a)=q1q2 M(q0,b)=q0 M(q1q2,a)=q0q1q2 M(q1q2,b)=q1 M(q0q1q2,a)=q0q1q2 M(q0q1q2,b)=q0q1 M(q1,a)=q0q1 M(q0q1,a)=q0q1q2 M(q0q1,b)=q0 F=q1,q1q2,q0q1,q0q1q2,运行DFA A：输入字符串bababab M(q0,bababab)=M(M(q0,b),ababab)=M(M(q0,a),babab)=M(M(q1q2,b),abab)=

22、M(M(q1,a),bab)=M(M(q0q1,b),ab)=M(M(q0,a),b)=M(q1q2,b)=q1因为q1F,所以，输入字符串bababab可为该DFA A所接受。,输入字符串abababbM(q0,abababb)=M(M(q0,a),bababb)=M(M(q1q2,b),ababb)=M(M(q1,a),babb)=M(M(q0q1,b),abb)=M(M(q0,a),bb)=M(M(q1q2,b),b)=M(q1,b)因为M(q1,b)不存在，所以，输入字符串abababb不可为DFA A所接受。运行状态转换图时请注意：1必须说明最终的状态属于终止状态集，才说可接受。2不

23、要写成：M(q1,b)=，只能写成：M(q1,b)不存在（因而不可接受）。,习题7 7.试为文法GS：S:=SaB|bB A:=S|a B:=Ac 构造预测分析表，并识别输入符号串bacaac是否该文法的句子。解：首先判别文法是否满足两个先决条件。因为不满足，进行文法等价变换，消去左递归，得到等价文法如下：S:=bBS S:=aBS|A:=S|a B:=Ac 为其构造预测分析表，现构造如下。a b c#S S:=bBS S S:=aBS S:=S:=A A:=a A:=S B B:=Ac B:=Ac,a b c#S S:=bBS S S:=aBS S:=S:=A A:=a A:=S B B:=

24、Ac B:=Ac,所以输入符号串bacaac 是该文法的句子。,习题8 1.根据下列语法分析树，确定全部简单优先关系（以矩阵形式给出)。解：E 简单优先矩阵如下：E T F i*()E T E T F T T*F i F F(E)i i T*F(I),习题103试为文法GZ：Z:=A()A:=(|Ai|B)B:=i 构造算符优先关系。解：易见()构造优先关系,寻找规则 U:=VT的规则,由规则Z:=A(),因A=*(,A=*i 以及A=*),所以,(,i(,)(。类似地,由A:=Ai以及A:=B),有:(i,()i i i,)i,(,i(,(=)(,以及 i)算符优先矩阵如右所示。i 当然，也

25、可以利用语法分析树寻找优先关系。,习题114.试利用表5-10中的分析表识别符号串(i+i)*i+i是否是文法G5.5的句子。给出识别过程。注意，请指出每步动作。解：题目要求指明每个分析步的动作，因此以表的形式给出分析过程。文法G5.5E：1：E:=E+T 2：E:=T 3：T:=T*F 4：T:=F 5：F:=(E)6：F:=i 分析过程见下面。最终结果表明，输入符号串(i+i)*i+i是文法G5.5的句子。,分析表,所以输入符号串(i+i)*i+i是该文法的句子。,习题121.根据例6.2中所给语法制导定义，关于输入符号串int i,j 构造注释分析数。解：语法制到定义如下：,可画出注释分

26、析树如下。,习题131.为下列类型写出类型表达式：（1）指向实型数据的指针数组，该数组的上下界分别为100与1。（2）一个函数，实参为一个整型数，返回值为一个指针，它指向由一个整型数和一个字符组成的结构体。解：(1)按约定，相应的类型表达式是：array(1.100,pointer(real)(2)按约定，相应的类型表达式是：integerpointer(record(iinteger)(cchar),2.设有C语言程序片段如下：struct cell int a;int b;typedef struct cell*pcell;cell Buf200;pcell handle(int x,ce

27、ll y)试给出标识符Buf与Handle所关联的类型表达式。解：Buf所关联的类型表达式是：array(0.199,cell)其中cell所关联的类型表达式是：record(ainteger)(binteger)Handle所关联的类型表达式是：integercellPcell 其中Pcell所关联的类型表达式是：pointer(cell),习题141.试为下列赋值语句 x=a/(b+c)-d*(e+f)生成目标代码，其中用变量名表示存储地址，且假定有三个寄存器可用。解：目标代码如下。MOV b,r1 ADD c,r1 MOV a,r2 DIV r1,r2 MOV e,r1 ADD f,r1

28、 MOV d,r3 DIV r1,r3 SUB r3,r2 MOV r2,x,3.试应用6.3.3.2节中关于条件语句的翻译方案，给出下列条件语句的目标代码：if(a0)x=b-a;else x=a-b;解：MOV a,t2 MOV a,t4 CMP t5,#1 CMP t2,b CMP t4,#0 CJ=l1 CJ*+8 GOTO L2 GOTO*+12 GOTO*+12 L1:MOV b,t6 MOV#1,t1 MOV#1,t3 SUB a,t6 GOTO*+8 GOTO*+8 MOV t6,x MOV#0,t1 MOV#0,t3 GOTO L3 MOV t1,t5 L2:MOV a,t7

29、 AND t3,t5 SUB b,t7 MOV t7,x L3:,5.试给出赋值语句序列：n=1;while(2*n-1)*(2*n-1)!=399)n=n+1;的目标代码。解：L1：MOV#2，t1 L2：MOV n，t4 MPY n，t1 ADD#1，t4 SUB#1，t1 MOV t4，n MOV#2，t2 GOTO L1 MPY n，t2 L0：ADD#1，t2 MPY t2，t1 MOV t1，t3 CMP t3，#399 CJ L2 GOTO L0,习题152.试把表达式（a+b)*(c-d)-(a*b+c)翻译成：（1）逆波兰表示（2）四元式序列（3）三元式序列解：(1)逆波兰表

30、示：ab+cd-*ab*c+-(2)四元式序列(3)三元式序列+a b t1+a b-c d t2-c d*t1 t2 t3*a b t4*a b+t4 c t5+c-t3 t5 t6-,3.试把逆波兰表示 abc*-de+/f-还原成中缀表达式解：还原成：(a-b*c)/(d+e)-f6.试写出题4中程序片段的四元式表示。解:positive=0;negative=0;先展开循环如下。zero=0;i=1;for(i=1;i100)goto FINISH;if(Ai0)if(Ai0)positive=positive+1;positive=positive+1;else if(Ai=0)el

31、se if(Ai=0)zero=zero+1;zero=zero+1;else else negative=negative+1;negative=negative+1;i=i+1;goto LOOP;FINISH:,四元式序列如下。(1):=0 positive(14)go(18)(2):=0 negative(15)+zero 1 t3(3):=0 zero(16):=t3 zero(4):=1 i(17)go(20)(5)i 100(23)(18)+negative 1 t4(6)=A i t1(19):=t4 negative(7)t1 0(9)(20)+i 1 t5(8)go(12)

32、(21):=t5 i(9)+positive 1 t2(22)go(5)(10):=t2 positive(23)(11)go(20)(12)=A i t2(13)=t2 0(15),9.试给出赋值语句 Ai=Bi+CAk+Di+j 的三元式表示。解：=B i=A k=C+i j=D+=A i&:=,习题171.设有计算z=ab的C程序如下：x=a;y=b;z=1;while(y0)if(y%2=1)z=z*x;y=y/2;x=x*x;其中a和b都是整型变量。(1)试办为其构造四元式序列(2)从四元式序列构造流图，并指明它由哪几个基本块组成。解：先把循环结构展开成由条件语句和goto语句组成的

33、结构。然后再写出四元式序列。,8.设有C程序如下：#define m 30 main()int I,n,t;int A100;n=50;k=1;for(i=k;ik+m-1)goto FINISH;t=Ai;Ai=Ai+n;Ai+n=t;i=i+1;goto LOOP;FINISH:,四元式序列如下。:=50 n:=1 k:=k i+k m t1 和是循环不变表达式可外提-t1 1 t2 i t2 go go(25)*2 i t3 可计算强度削减=A t3 t4:=t4 t+i n t5*2 t5 t6=A t6 t7*2 i t8 公共子表达式可消去(与)=A t8 t9 对t8的复写传播可删除无用代码&:=t7 t9 t9 对t10情况相同+i n t10 公共子表达式可消去(与)*2 t10 t11 可计算强度削减,(20)=A t11 t12(21)&:=t t12 t12(22)+i 1 t13(23):=t13 i(24)go(4)(25),