资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,习题及解答：,第一章,什么是,编译程序,？什么是,解释程序,？二者的,区别,？,1,、编译程序：,是一种翻译程序，它特指把某种高级程序设计语言翻译成具体计算机上的低级程序设计语言。,2,、解释程序：,解释程序,(interpreter),也是一种翻译程序，将某高级语翻译成具体计算机上的低级程序设计语言,.,两者区别：,（,1,）前者有目标程序而后者无目标程序；,（,2,）前者运行效率高而后者便于人机对话,2,、叙述编译程序的,逻辑结构,和,实现机制,根据语言和环境的不同，编译程序实现时是把,图中,的各阶段划分成若干遍；典型的情况是两遍的编译程序：,第一遍,:,词法分析、语法分析和语义分析。即前端完成分析，一般与机器无关。,第二遍,:,目标代码生成和目标代码优化。即后端完成综合，一般与机器有关。每遍中的各阶段的工作是穿插进行的，,例如：,使语法分析器处于核心位置,而把词法分析器作为子程序；当语法分析需要下一个单词时，就调用词法分析器，识别一个单词。,词法,分析,语法,分析,语义,分析,代码生成,源语言,目标语言,错 误 处 理,符 号 表 管 理,优化,处理,第二,章,1,、,P36:8;,i+i*i,最左,E-E+T,-T+T,-F+T,-i+T,-i+T*F,-i+F*F,-i+i*F,-i+i*i,i+i*i,最右,E-E+T,-E+T*F,-E+T*i,-E+F*i,-E+i*i,-T+i*i,-F+i*i,-i+i*i,i*(i+i),最左,E-T,-T*F,-F*F,-i*F,-i*(E),-i*(E+T),-i*(T+T),-i*(F+T),-i*(i+T),-i*(i+F),-i*(i+i),i*(i+i),最右,E-T,-T*F,-T*(E),-T*(E+T),-T*(E+F),-T*(E+i),-T*(T+i),-T*(F+i),-T*(i+i),-F*(i+i),-i*(i+i),2,、试构造下述语言,L,的文法：,L=a,m,b,n,|m0,n1;,S,-AB A-Aa|,B-Bb,|b,or,S,-AB A-aA|,B-bB|b,3,、试求下述文法,G(Z),所定义的语言：,G(Z):Z-b|bB,B-bZ,Z=b,Z=bB=bbZ=bbb,Z=bB=bbZ=bbbB=bbbbZ=bbbbb,Z=b,2n-1,n,1,第三章,1.P64,，,8(1),(3),给,出正规表达式：,以,01,结尾的二进制数串,分析题意，要求的是二进制小，即由,0,和,1,构成的串，并且必须以,01,结尾，所以本题可以分两部分去完成，一部分实现由,0,和,1,构成的任意串，一部分即,01,，然后将它们连接到一起就可以了，所以本题的解答是,:(0|1)*01,。,（,3,）包含奇数个,1,或奇数个,0,的二进制数串。,本题求二进制串，并且要求包含奇数个,0,或奇数个,1,，由于,0,和,1,都可以在二进制串中任何地方出现，所以本题只需要考虑一种情况，另外一种情况也可以类似求得。考虑包含奇数个,0,的字符串,:,由于只关心,0,的个数的奇偶数，我们可以把二进制串分成多段来考虑，第,1,段为二进制串的开始到第,1,个,0,为止，这一段包含,1,个,0,，并且,0,的前面有,0,个或多个,1,，对于剩下的二进制串按照每段包含两个,0,的方式去划分，即以,0,开始，以,0,结尾，中间可以有,0,个或多个,1,，和果一个二进制串被这样划分完后，剩下的部分如果全部是全,1,串,(,这些全,1,串在前面划分的串之间或最后,),，则该二进制串就具有奇数个,0,，所以该二进制串可以这样描述,:,以第,1,段,(1*0),开始，后面由全,1,串,(1*),以及包含两个,0,的串,(01*0),组成，所以包含奇数个,0,的正规表达式为,:1*0(1|01*0)*,，本题的解答则是,:1*0(1|01*0)*|0*1(0|10*1)*,。,2.,给定正规式,(a|b)*a(a|b),，构造其最小,DFA M,。,(,参见书图,3.7),首先,将其分为终态,集,3,4,和,非终态集,0,1,2,，,由于,0 a,=1,，,0,b=,2,，,2a=1,，,2,b=2,都是集合,0,1,2,的子集,，,但,1,a,=3,，,1,b=4,，属于,3,4,的子集,，,故将其划分为,0,2,，,1,。对,3,、,4,也是如此，即最后划分为：,0,2,、,1,、,3,、,4,，按顺序重新命名为,1,、,2,、,3,、,4,。,(,见书,p57,页,),第四章,1.,考虑下面文法,G1:S-a|(T),T-T,S|S,(,1),消去,G1,的左递归,。,（书上,p69,）,（,2,）改写后的文法是否为,LL(1),文法,？,(,书,P73),给,出预测分析,表,(,书,P76),。,（,1,）消除左递归,:,S-a|(T),T-ST,T-,S T|,（,2,）,FIRST(S,)=a,(,FIRST(T,)=a,(,FIRST(T,)=,First(a)=a,First()=,First(T)=(,S,的所有候选的首符集不相交,(First,和,Follow,集的构造方法见书,P78),First(,ST)=,First()=,T,的所有候选的首符集不相交,Follow(T)=Follow(T)=),Follow(S)=),#,first(T,),Follow(T,)=,a,(,),#,S,Sa,S,S(T),T,TST,TST,TST,T,T,T,ST,2.P82,，第,4,题。,对文法,S,-S,S(S)|AB,B-S|,A aC,C(S)|,(1),构造,LL(1),分析表,(2),给出对句子,a-a(a),的分析过程。,(1),First(S)=-(a,First(A)=a,First(B)=-,First(C)=(,Follow(S)=)#,Follow(B)=)#,Follow(A)=-)#,Follow(C)=-)#,LL(1),分析表,-,a,(,),#,S,S-S,S-AB,S-(S),B,B-S,B-,B-,A,A-aC,C,C-,C-(S),C-,C-,步骤,符号栈,输入串,所用产生式,0,#S,a-a(a)#,1,#BA,a-a(a)#,S-AB,2,#BCa,a-a(a)#,A-aC,3,#BC,-a(a)#,4,#B,-a(a)#,C-,5,#S-,-a(a)#,B-S,6,#S,-a(a)#,7,#S-,-a(a)#,S-S,8,#S,a(a)#,9,#BA,a(a)#,S-AB,10,#BCa,a(a)#,A-aC,11,#BC,(a)#,12,#B)S(,(a)#,C-(S),13,#B)S,(a)#,14,#B)S(,(a)#,15,#B)S,a)#,16,#B)BA,a)#,S-AB,17,#B)BCa,a)#,A-aC,18,#B)BC,)#,19,#B)B,)#,C-,20,#B),)#,B-,21,#B),)#,22,#B,#,23,#,#,B-,P133.1,令文法,G,1,为：,E-E+T|T,T-T*F|F,F-(E)|I,证明,E+T*F,是它的一个句型，指出这个句型的所有短语，直接短语和句柄,答案：,因为,E=E+T=E+T*F,所以,E+T*F,是该文法的一个句型。,短语,:E+T*F,T*F,直接短语,:T*F,句柄,:T*F,第五章,P133.3,S-a|,|(T),T-T,S|S,(1),计算,FIRSTVT,和,LASTVT.,(2),计算优先关系。以上文法是一个优先文法吗？,(3),给出输入串,(a,(a,a),的算符优先分析过程。,答案：,(1),FIRSTVT(S)=a (,FIRSTVT(T)=,A (,LASTVT(S)=A ),LASTVT(T)=,A ),(2),a,(,),a,(,=,(3),第七章,1.,给出下面表达式的逆波兰表示,a*(-b+c),ab-c+*,a+b*(c+d/e),abcde/+*+,2.,请将表达式,-(a+b)*(c+d)-(a+b+c),分别表示成三元式、间接三元式和四元式序列。,三元式序列：,(1)(+,a,b,）,(2)(,(1),-),(3)(+,c,d),(4)(*,(2),(3),(5)(+,a,b),(6)(+,(5),c),(7)(-,(5),(6),三元式表,间接码表,(+,a,b)(1),(,(1),-)(2),(+,c,d)(3),(*,(2),(3)(4),(+,(1),c)(1),(-,(4),(5)(5),(6),四元式序列：,(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),P218.4:,写出下面赋值语句：,A:=B*(-C+D),的三地址代码。,答案：,T1:=-C,T2:=T1+D,T3:=B*T2,A:=T3,P218.6,写出布什尔,A or(B and not(C or D),的四元式序列,(1)(jnz,A,-,0),(2)(j,-,-,3),(3)(jnz,B,-,5),(4)(j,-,-,0),(5)(jnz,c,-,4),(6)(j,-,-,7),(7)(jnz,d,-,5),(8)(j,-,-,1),最后,E.turelist=1,8,E.falelish=4,5,7,P218.7:,把下面的语句翻译成四元式序列：,While AC and BD do,If A=1 then C:=C+1 else,while A=D do A:=A+2;.,(1)(j,A,C,3),(2)(j,-,-,16),(3)(j,B,D,5),(4)(j,-,-,16),(5)(j=,A,1,7),(6)(j,-,-,10),(7)(+,C,1,T1),(8)(:=,T1,-,C),(9)(j,-,-,1),(10)(j=,A,D,12),(11)(j,-,-,1),(12)(+,A,2,T2),(13)(:=,T2,-,A),(14)(j,-,-,10),(15)(j,-,-,1),(16),第十章,P306.3:,试对以下基本块,B1,和,B2,：,B1,：,B2:,A:=B*CB:=3,D:=B/CD:=A+C,E:=A+DE:=A*C,F:=2*EF:=D+E,G:=B*CG:=B*F,H:=G*GH:=A*C,F:=H*GI:=A*C,L:=FJ:=H+I,M:=LK:=B*5,L:=K+J,M:=L,分别应用,DAG,对他们进行优化，并就以下两种情况分别写出优化后的四元式序列。,（,1,）假设只有,G,L,M,在基本块后面还要被引用。,（,2,）假设只有,L,在基本块后面还要被引用。,P306.3:,（,1,）假设只有,G,L,M,在基本块后面还要被引用。,B1,：,B2:,G:=B*CD:=A+C,H:=G*GE:=A*C,L:=H*GF:=D+E,M:=LG:=3*F,L:=15+F,M:=L,（,2,）假设只有,L,在基本块后面还要被引用。,B1:B2:,G:=B*CD:=A+C,H:=G*GE:=A*C,L:=H*GF:=D+E,L:=15+F,B,A,*,/,A,G,D,H,*,*,*,F,L,M,F,E,+,2,B1,的,DAG,图,C,C,D,H,G,F,J,K,L,M,B,E,J,+,*,*,+,+,3,15,B2,的,DAG,图,
展开阅读全文