编译原理作业题答案080104 - 编译原理课后题答案.doc

第二章 高级语言的语法描述6、令文法G6为：N D|ND D 0|1|2|3|4|5|6|7|8|9 （1）G6 的语言L（G6）是什么？ （2）给出句子0127、34和568的最左推导和最右推导。解答：思路：由N D|ND可得出如下推导NNDNDDDn（n=1） 可以看出，N最终可以推导出1个或多个（也可以是无穷）D，而D 0|1|2|3|4|5|6|7|8|9可知，每个D为09中的任一个数字，所以，N 最终推导出的就是由09这10个数字组成的字符串。（1）G6 的语言L（G6）是由09这10个数字组成的字符串,或0，1,9+。(2)句子0127、34和568的最左推导分别为:NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568句子0127、34和568的最右推导分别为:NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D685687、写一个文法，使其语言是奇数集，且每个基数不以0开头。解答：G（S）：S CD|D D1|3|5|7|9 C CB|A A2|4|6|8|D B A|0 或： G（S）：S MWN|N N 1|3|5|7|9 M 1|2|3|4|5|6|7|8|9 W WV| V M|08、令文法为 ： ET|E+T|E-T TF|T*F|T/F F（E）|i（1）i+i*i、i*（i+i）的最左推导和最右推导；（2）给出i+i+i、i+i*i和i-i-i的语法树。解答：（1）i+i*i、i*（i+i）的最左推导分别为：ETE+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iETT*FF*Fi*Fi*（E）i*（E+T）i*（T+T）i*（F+T）i*（i+T）i*（i+F）i*（i+i）i+i*i、i*（i+i）的最右推导分别为：ETE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iETT*FT*（E+T）T*（E+F）T*（E+i）T*（T+i）T*（F+i）T*（i+i）F*（i+i）i*（i+i）（2） E E E E + T E + T E - T T T * F T T * F E - T F F F i F F i T F i i i i i F i i+i+I i+i*i i i-i-i 9、证明下面的文法是二义的： SiSeS|iS|i证明： 思路：要证明该文法是二义的，必须找到一个句子，使得该句子具有两个不同的最右推导或两个不同的语法树。 对于句子iiiei，存在如下两个最右推导： SiSeSiSeiiiSeiiiiei SiSiiSeSiiSeiiiiei 由此，该文法是二义的。10、把下面文法改写为无二义的：SSS|（S）|（）解答：思路：对于句子（）（）（），存在如下两棵语法树，所以该文法是二义性文法，引起 S S S S S S S S （ ） （ ）S S（ ）（ ） （ ）（ ） 二义性的原因在于SSS，可将其改造成等价的递归结构，消除二义性。 改造后的文法为：STS|T T（S）|（）11、给出下面语言的相应文法： L1=anbnci|n=1,i=0 L2=aibncn|n=1,i=0 L3=anbnambm|n,m=0 L4=1n0m1m0n|n,m=0解答: 分析:L1:要求a和b的个数一样多,并至少为1个,c的个数为0个以上,可用一个非终结符去生成anbn 串,一个非终结符生成ci;L2同L1。L3:将anbnambm分为两段考虑, anbn和ambm,然后使用两个终结符分别产生。L4:采用从里往外扩展的方式,先用一个非终结符生成中间的m个0和m个1,然后，再用另一个非终结符在该串的基础上扩充前后的n个0和n个1。 L1的文法: SAC AaAb|ab CCc|L2的文法: SAB AAa| BbBc|bcL3的文法: SAB AaAb| BaBb|L4的文法: S1A0|A A0A1|第三章 词法分析7、构造下列正规式相应的DFA： (1) 1（0|1）*101 (2) 1(1010*|1(010)*1)*0 (3) 0*10*10*10* 解答：210（1）第1步：根据正规式构造NFA，引入初态X和终止态Y。314051yx11 （2）第2步：对上NFA进行确定化，得到如下状态转化矩阵。状态I0I1X1，2，31，2，32，32，3，42，32，32，3，42，3，42，3，52，3，42，3，52，32，3，4，Y2，3，4，Y2，3，52，3，401011204511000311根据上面的状态转换矩阵，重新命名，得到相应的DFA (3)第3步 化简该DFA，获得最简的DFA，即为所求的DFA。首先初始分为终态集和非终态集两个集合：0,1,2,3,4和5考察0,1,2,3,4 0,1,2,3,40 = _ 2,4 0状态不能接受0字符,0把0,1,2,3,4分为0,1,2,3,4考察1,2,3,4 1,2,3,40=2,4,2和4目前等价,1,2,3,41=3,5 ,3和5不等价 1把1,2,3,4分为1,2,3和4考察1,2,3 1,2,30=2,4,2和4不等价,所以1,2,3可分为1,2,3考察1,2 1,20=2 1,21=3 1,2不可再细分最终分为5个小组:0,1,2,3,4,5 保留状态1,删除状态2,1状态经0弧到2,改为1经0到1;4经0到2,改为4经0到134100112111000为化简后的DFA为8、给出下面正规表达式： （1）以01结尾的二进制数串; (2) 能被5整除的十进制整数； （3）包含奇数个1或奇数个0的二进制数串；解答：分析：（1）分两部分考虑，一部分实现由0和1构成的任意串，一部分01，两部分连接到一起就可以了。本题答案为（0|1）*01 （2）要求由09这10个数字组成的字符串，并且不能以0开头，要能被5整除。要被5整除则需以0或5结尾。分两种情况考虑，一是1位整数，那么该整数是0和5；另外一种情况是多位整数。分3部分考虑：末尾必须是0或5，第1位必须不为0，中间部分任意。本题答案为（1|2|3|4|5|6|7|8|9）(0|1|2|3|4|5|6|7|8|9)*(0|5)|(0|5) （3）12、将图3.18的(a)和(b)分别确定化和最少化。bb解答:a3201a0a,babaaaabb5a41bb (a) (b)解答:(1) a图是一个NFA,要对它进行确定化。 第1步:确定化,得到DFA。 确定化后得到的状态转换矩阵为下图:状态IaIb00,110,10,1110给状态重新编号,得到新的状态转换矩阵:状态IaIb0+-121-1220aa10bba2第2步:最小化 首先将状态划分为两个集合0,1和2 0,1a=1 0,1b=2 不可再分 取状态0做代表,删除1 得到新的DFA,aba20(2)图b所示为一DFA,需要把它进行最小化。 首先将状态初始划分为终态集和非终态集两部分:2,3,4,5,0,1 首先考察处理0,10,1a=1 0,1b=2,4, 2和4等价,2,4目前不可再分考察处理2,3,4,52,3,4,5a=1,3,0,5 1,0和3,5是可区别的, 2,3,4,5可细分为2,4,3,5考察2,4 2,4a=0,1 2,4b=3,5 0和1, 3和5等价, 2,4不可再分 3,5a=3,5 3,5b=2,4 2和4, 3和5等价, 3,5不可再分最终分组为0,1 2,4 3,5 取0,2,3做为代表,删除1,4,5a最小化后的DFA为: bbaab32014.构造一个DFA,它接受=0,1上满足如下条件的字符串:每个0都有1直接跟在右边。解答:第1步:写出正规式,为(0|10)*。第2步:构造NFA。1 01Y0X0第3步:确定化。 状态转换矩阵为: 状态I0I1X,0,Y0,Y10,Y0,Y11 0,Y重命名的状态转换矩阵为:状态I0I10+-121-1221化简后的DFA为:001001120第4步:对该确定化后的DFA进行最小化。首先初始划分为:0,1,2考察0,1 0,10=1 0,11=2 所以0,1不可再细分0保留0,删除1后,得到化简后的DFA即为所求得的DFA。 100215.给定右线性文法G: S0S|1S|1A|0B A1C|1 B0C|0 C0C|1C|0|1 求出一个与G等价的左线性文法。解答: 分析:将右线性文法改为左线性文法,没有直接的方法,可以通过状态转换图来实现.先求得右线性文法对应的NFA,即状态转换图,然后确定化为DFA,再根据DFA,求出左线性文法。0,1第1步:求文法G所对应的NFA.如下图0,1 1,1,CAS1,0,0,10,0,BT第2步:对该NFA进行确定化和最小化 状态转换矩阵为: 状态I0I1SS,BS,AS,BS,B,C,TS,AS,AS,BS,A,C,TS,B,C,TS,B,C,TS,A,C,TS,A,C,TS,B,C,TS,A,C,T重命名后的状态转换矩阵为:状态I0I10+121322143-344-34 确定化后的DFA为0, 030,0,11,1,1,0,0,421,1, 最小化: 初始划分为:0,1,2,3,4 考察3,4 3,40=3 3,41=4 3,4不可再分. 考察0,1,2 0,1,20=1,3 0,1,2可再分为0,2和1 考察0,2 0,21=2,4 0,2可再分为0和2 最终分组为:0,1,2,3,4 保留3,删除4最小化后的DFA为:SABT0 0,1,1,0,0,11,根据该DFA,与它对应的左线性文法为: T A1|B1|T0|T1 A B0|0B A1|1第四章 自上而下语法分析1.考虑下面文法G1: Sa|(T) TT,S|S(1)消去G1的左递归.然后对每个非终结符,写出不带回溯的递归子程序。(2)经改写后的文法是否是LL(1)的?给出他的预测分析表。解答:(1)消去左递归后: Sa|(T) TST T ,ST|(2)计算每个非终结符的FIRST集合和FOLLOW集合: FIRST(S)=a,( FIRST(T)= a,( FIRST(T)=, FOLLOW(S)=,# FOLLOW(T)= ) FOLLOW(T)= )预测分析表如下:a(),#SSaSS(T)TTSTTSTTSTTT T ,ST构造的预测分析表中没有多重入口,所以改造后的文法是LL(1)文法。2.对下面的文法G: ETE E+E| TFT T T| FPF F *F| P(E)|a|b|(1)计算这个文法的每个非终结符的FIRST和FOLLOW集合。(2)证明这个文法是LL(1)的。(3)构造它的预测分析表。(4)构造它的递归下降分析程序。解答:(1)计算每个非终结符的FIRST集合和FOLLOW集合: FIRST(E)= (,a,b, FIRST(E)=+， FIRST(T)= (,a,b, FIRST(T)= (,a,b,， FIRST(F)= (,a,b, FIRST(F)=*， FIRST(P)=(,a,b, FOLLOW(E)= )，# FOLLOW(E)= )，# FOLLOW(T)= )，#，+ FOLLOW(T)= )，#，+ FOLLOW(F)= (,a,b,，)，#，+ FOLLOW(F)= (,a,b,，)，#，+ FOLLOW(P)=*，(,a,b,，)，#，+对于产生式E+E| FIRST(+E)=+ FOLLOW(E)= )，# ，交集为空；产生式T T| FIRST(T)= (,a,b, FOLLOW(T)= )，#，+ ,交集为空 ；产生式F *F| FIRST(*F)=* FOLLOW(F)= (,a,b,，)，#，+,交集为空； 产生式P(E)|a|b| FIRST(E)=( FIRST(a)=a FIRST(b)=b FIRST()= 交集为空，由上可知满足LL(1)分析条件，该文法是LL(1)的。（3）预测分析表为：+*()abEETEETEETEETEEE+EEETTFTTFTTFTTFTTT T TT T TT TT TT FFPFFPFFPFFPFFF F *FF F F F F F PP(E)|a|b|P(E)|a|b|P(E)|a|b|P(E)|a|b|3下面文法中，哪些试LL(1)的，说明理由。（1）SAbc Aa| Bb| (2) SAb Aa|B| Bb| (3) SABBA Aa| Bb| (4) SaSe|B BbBe|C CcCe|d解答： （1） FIRST(S)=a,b 对于Aa| FIRST(a)=a FIRST()= FOLLOW(A)=b 交集为空 Bb| FIRST(b)=b FIRST()= FOLLOW(B)=c 交集为空 由上可知,满足LL(1)分析条件,所以该文法是LL(1)文法。 (2) FIRST(S)=a,b, 对于Aa|B| FIRST(a)=a FIRST(B)=b, FIRST()= FOLLOW(A)=b 而 FIRST(B)FOLLOW(A)=b对于Bb| FIRST(b)=b FIRST()= FOLLOW(B)=b 而 FIRST(b) FOLLOW(B)=b 不满足LL(1)分析条件,所以该文法不是LL(1)文法。 (3) FIRST(ABBA)=a, 对于Aa| FIRST(a)=a FIRST()= FOLLOW(A)=b,a 而 FIRST(a)FOLLOW(A)=a 对于Bb| FIRST(b)=b FIRST()= FOLLOW(B)=b,a 而FIRST(b) FOLLOW(B)=b 不满足ll(1)分析条件,所以该文法不是ll(1)文法。(4) 对于SaSe|B FIRST(aSe)=a FIRST(B)=b,c,d 交集不为空； 对于BbBe|C FIRST(bBe)=b FIRST(C)=c,d 交集不为空； 对于CcCe|d FIRST(cCe)=c FIRST(d)=d 交集不为空。 满足ll(1)分析条件,所以该文法是LL(1)文法。第五章 语法分析-自下而上分析1.令文法G1为: EE+T|T TT*F|F F(E)|i 证明E+T*F是它得一个句型,指出这个句型的所有短语,直接短语和句柄。解答: 因为对于E+T*F,其对应的语法树为:E E + T T T * F 所以E+T*F是句型. T是句型E+T*F相对于E的短语 T*F 是句型E+T*F相对于T的短语 E+T*F是句型E+T*F相对于E的短语 T,T*F是直接短语,T是句柄。2.考虑下面的表格结构文法G2: Sa|(T) TT,S|S (1)给出(a,(a,a)和(a,a),(a),a)的最左和最右推导。 (2)指出(a,a),(a),a)的规范规约及每一步的句柄,根据这个规范规约,给出”移进-规约”的过程,并给出它的语法树自下而上的构造过程。解答:(1)最左推导:S=(T)=(T，S)=(S，S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)S=(T)=(T，S)=(S，S)=(T),S)=(T,S),S)=. 略3（1）计算练习2文法G2的FIRSTVT和LASTVT。 （2）计算G2的优先关系。G2是一个算符优先文法吗？ （3）给出输入串（a,(a,a)）的算符优先分析过程。解答：（1）各个终结符的FIRSTVT和LASTVT集合： FIRSTVT(S)=a，（ FIRSTVT(T)=，a，（ LASTVT（S）= a，) LASTVT（T）=，a，)(2) 构造优先关系表为a()，#a(=，#=表中没有多重入口，所以该文法是算法优先文法。（3）输入串（a,(a,a)）的算符优先分析过程为：步骤栈输入串动作0（a，(a，a)）预备1（ a，(a，a)） 移进2（a ，(a，a)） 移进3（S ，(a，a)） 规约Sa4（S， (a，a)） 移进5（S，（ a，a)） 移进6（S，（a ，a)） 移进7（S，（S ，a)） 规约Sa8（S，（S， a)） 移进9（S，（S，a )） 移进10（S，（S，S )） 规约Sa11（S，（T )） 规约TT,S12（S，（T） 移进13（S，S） 规约S (T)14（T） 规约TT,S15（T） 移进16S 规约S (T) 结束5考虑文法 SAS|b ASA|a（1）列出这个文法的所有LR(0)项目。（2）构造这个文法的LR(0)项目集规范族及识别活前缀的DFA。（3）这个文法是SLR的吗？若是，构造出它的SLR分析表。（4）这个文法是LALR或LR(1)的吗？解答： 对该文法进行拓广后得： SS SASSb ASAAa（1）文法的所有LR(0)项目有：S.S S S. S.ASSA.SSAS.S.bSb.A.SAAS.AASA.A.aAa.(2)文法的识别活前缀的DFA为:I5:AS.AA.SAA.aS.ASS.bSI1:S S.AS.AA.SAA.aS.ASS.bAbASAaI0:S.SS.ASA.SAA.aS.bI6:ASA.SA.SS.ASS.bA.SAA.aAAI2:SA.SS.ASA.SAA.aS.bAababaASbSI3:Aa.bI7:SAS.AS.AA.SAA.aS.ASS.bI4:Sb.Saba该DFA的所有状态构成的集合I0,I1,I2,I3,I4,I5,I6,I7是文法的项目集规范族。(3)I1,I6,I7有移进-规约冲突 对于I1:FOLLOW(S)=#,所以当识别字符为#时才可以进行规约,不会发生冲突; 对于I6:FOLLOW(A)=a,b,当识别字符为a或b时,就不能确定是移进还是规约,发生冲突; 对于I6:FOLLOW(S)=#,a,b,当识别字符为a或b时,就不能确定是移进还是规约,发生冲突. 所以该文法不是SLR文法。(4)比较麻烦,就不构造了,但是该文法不是LR(1)文法,也不是LALR(1)文法。8.证明下面的文法是LL(1)的,但不是SLR(1)的。 SAaAb|BbBa A B 解答: (1)首先该文法无左递归存在,没有公共左因子。 其次:对于SAaAb|BbBa FIRST(AaAb)=aFIRST(BbBa)=b FIRST(AaAb)FIRST(BbBa)= 所以该文法是LL(1)文法。 (2)证明该文法不是SLR的。 文法的LR(0)项目集规范族为: I0=S.SS.AaAbS.BbBa A.B. I1= S S. I2= SA.aAb I3= SB.bBa I4= SAa.Ab A. I5= SBb.BaB. I6= SAaA.b I7= SBbB.a I8= SAaAb. I9= SBbBa. 考察I0:FOLLOW(A)=a,b FOLLOW(B)=a,bFOLLOW(A)FOLLOW(B)= a,b产生规约-规约冲突。所以该文法不是SLR(1)文法。第六章 属性文法和语法制导翻译7.下列文法由开始符号S产生一个二进制数,令综合属性val给出该数的值: SL.L|L LLB|B B0|1试设计求S.val的属性文法,其中,已知B的综合属性c,给出由B产生的二进位的结果值。例如，输入101.101时, S.val=5.625,其中,第一个二进位的值是4,最后一个二进位的值是0. 125。解答：对于101.101的语法树为：S L . L1 L B L B L B 1 L B 1 B 0 B 0 1 1假设一个二进制数为： am.a1a0.bn.b1b0其中，ai(i=0，1，m)和bj(j=0,1,n)为二进制数字，则该二进制数的十进制数为： am*2m +a1*21+a0*20+bn*2-1+b1*2-n+b0*2-n-1= am2m +a1*21+a0*20+ (bn*2n+b1*2-1+b0*20)/2n+1基于此公式，在语法制导翻译时，对二进制数串L,不仅要计算其值L.val，还要计算其长度L.length（二进制数字个数）。如果L为小数部分，则其值L.val要除以2L.length。上面的语法树，二进制数的左右子树的形状一样，那么他们的结果也是一样，关键是利用SL.L1规约时，可看出，S的值实际上是L的值加上L.val/2N,其中，N为L的长度。属性文法为：SS print(S.val)SL1.L2 S.val=L1.val+L2.val/2L2.lengthSL S.val=L.valLL1B L.val=L1.val*2+B.val ; L.length=L1.length+1LB L.val=B.val; L.length=1B0 B.val=0B1 B.val=1第七章 语义分析和中间代码生成1给出下面表达式的逆波兰表示（后缀式）： (1) a*(-b+c) (2) not A or not (C or not D) (3) a+b*(c+d/e) (4) (A and B) or (not C or D) (5) a+b*(-c+d) (6) (A or B) and (C or not D and E ) (7) if (x+y)*z=0 then (a+b)c else abc解答： 以上表达式的后缀式为： （1）a b c + * (2) A not C D not or not or (3) a b c d e / + * + (4) A B and C not D or or (5) a b c d + * + (6) A B or C D not E and or and (7) 将后缀式放到数组post 中：xy+z*p1BZab+cP2BRabc P1 p2说明：e p1 BZ e为0跳转到p1 p2 BR 无条件跳转到p2。3请将-(a+b)* (c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。解答： 四元式序列为： （1）（，a，b，T1） （2）（，T1，-，T2） （3）（+，c，d，T3） （4）（*，T2，T3，T4） （5）（+，a，b，T5） （6）（+，T5，c，T6） （7）（-，T4，T6，T7） 三元式序列为： （1）（+，a，b） （2）（，（1），-） （3）（+，c，d） （4）（*，（2），（3） （5）（+，a，b） （6）（+，（5），c） （7）（-，（4），（6）间接三元式为： 三元式表为： 间接码表: （1）（+，a，b） (1) （2）（，（1），-） (2) （3）（+，c，d） (3) （4）（*，（2），（3） (4) （5）（+，（1），c） (1) （6）（-，（4），（5） (5) (6)4按7.3节所说的方法，写出下面赋值语句的自下而上语法制导翻译过程，给出所产生的三地址代码。A：=B*（-C+D）解答：语法树为 S id ：= E E * E id E + E - E id id分析过程：步骤符号栈输入符号串动作语义值 产生式 三地址代码1#A：=B*（-C+D）# 预备2#id ：=B*（-C+D）# 移进A 3#id:=B*（-C+D）# 移进 A_4#id:=id *（-C+D）# 移进 A_B5#id:=E *（-C+D）# 规约 A_B Eid6#id:=E* （-C+D）# 移进 A_B_7#id:=E*( -C+D）# 移进 A_B_ _8#id:=E*(- C+D）# 移进 A_B_ _ _9#id:=E*(-id +D）# 移进 A_B_ _ _C10 # id:=E*(-E +D）# 规约 A_B_ _ _C Eid11 # id:=E*(E +D）# 规约 A_B_ _T1 E-E T1:=-C12 # id:=E*(E+ D)# 移进 A_B_ _T1_ 13 # id:=E*(E+id )# 移进 A_B_ _T1_ D 14 # id:=E*(E+E )# 规约 A_B_ _T1_ D Eid15 # id:=E*(E )# 规约 A_B_ _T2 EE+E T2:=T1+D16 # id:=E*(E) # 移进 A_B_ _T2_ 17 # id:=E*E # 规约 A_B_T2 18 #id:=E # 规约 A_T3 EE*E T3:=B*T219 #S # 规约 T3 Sid:=E A:=T36按742节的办法，写出布尔式A or （B and not （C or D）的四元式序列。解答： 100（jnz，A，0）E。T 101（j，102）102（jnz，B，104）103（j，0）E。F104（jnz，C，103）E。F105（j，106）106（jnz，D，104）E。F107（j，100）E。T 真出口为： E.truelist=100，107 假出口为： E.falselist=103，104，1067用7.5.1节的办法，把下面的语句翻译成四元式序列： While A C and B D do if A=1 then C:=C+1 else while AD do A:=A+2;解答: 采用拉链-回填技术翻译，得到下面的四元式序列：100 (j，102)101 (j，115 )102（j，104）103（j，115）104 (j=，106)105 (j，109)106(+，T1)107(:=，T1，C)108(j，100)109(j，111)110(j，100)111(+,A,2,T2)112(:=,T2,_,A)113(j,_,_,109)114(j,_,_,100)115第八章 符号表1.什么是符号