编译原理考试习题及答案

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,64,程 序 设 计 语 言,Chapter 3.,词法分析,编译原理参考答案,2024/9/23,CH.3.,练习题8(,P64.),8.,给出下面的正规表达式,。,(1) 以01结尾的二进制数串;,正规式,(0|1)*01,(2) 能被5整除的十进制整数;,允许任意,0,开头：,(0|1|2|3|4|5|6|7|8|9)*(0|5),不允许,0,开头（,0,本身除外）：,(0|5)|(1|2|3|9)(0|1|2|3|9)*(0|5),2024/9/23,CH.3.,练习题7(,P64.),7.,(1),1(0|1)*101,构造,DFA。,解,1,:,正规式对应的,NFA,:,X,Y,3,4,5,1,1,0,1,1,2,1,0,I,I,0,I,1,X,1,3,2,1,3,2,3,2,3,4,2,3,2,3,2,3,4,2,3,4,2,3,5,2,3,4,2,3,5,2,3,2,3,Y,4,2,3,Y,4,2,3,5,2,3,4,2,I,I,0,I,1,初,0,1,1,2,3,2,2,3,3,4,3,4,2,5,终,5,4,3,2024/9/23,(1) 正规式,1(0|1)*101,DFA,:,x,3,Y,4,2,3,4,2,3,5,2,1,1,0,1,1,3,2,3,2,0,1,0,0,1,0,1,I,I,0,I,1,X,1,3,2,1,3,2,3,2,3,4,2,3,2,3,2,3,4,2,3,4,2,3,5,2,3,4,2,3,5,2,3,2,3,Y,4,2,3,Y,4,2,3,5,2,3,4,2,I,I,0,I,1,初,0,1,1,2,3,2,2,3,3,4,3,4,2,5,终,5,4,3,2024/9/23,(1) 正规式,1(0|1)*101,DFA,:,I,I,0,I,1,X,1,3,2,1,3,2,3,2,3,4,2,3,2,3,2,3,4,2,3,4,2,3,5,2,3,4,2,3,5,2,3,2,3,Y,4,2,3,Y,4,2,3,5,2,3,4,2,I,I,0,I,1,初,0,1,1,2,3,2,2,3,3,4,3,4,2,5,终,5,4,3,0,5,3,4,1,1,0,1,1,2,0,1,0,0,1,0,1,2024/9/23,CH.3.,练习题7(,P64.),7.,构造下列正规式相应的,DFA。,(1),1(0|1)*101,解2,: 正规式对应的,NFA,:,0,4,1,2,3,1,1,0,1,1,0,I,I,0,I,1,0,初0,1,1,1,1,1,1,1,2,2,1,2,2,1,3,3,1,2,2,1,3,3,1,1,1,2,4,4,1,2,4,终4,1,3,3,1,2,2,1,0,4,2,3,1,1,0,1,1,0,0,1,0,DFA,:,2024/9/23,7.,构造下列正规式相应的,NFA。,(,P64.),(,2),1(1010*|1 (010),*,1)*0,X,Y,2,0,1,1,3,1,010*,1 (010),*,1,X,Y,2,0,1,1,3,6,4,5,1,1,0,0*,7,8,1,1,(010),*,2024/9/23,7.,构造下列正规式相应的,NFA。,(,P64.),(,2),1(1010*|1 (010),*,1)*0,X,Y,2,0,1,1,3,6,4,5,1,1,0,0*,7,8,1,1,(010),*,X,Y,2,0,1,1,3,6,4,5,1,1,0,0,7,8,1,1,9,10,010,2024/9/23,X,Y,2,0,1,1,3,6,4,5,1,1,0,0,7,8,1,1,9,10,010,X,Y,2,0,1,1,3,6,4,5,1,1,0,0,7,8,1,1,9,10,0,12,11,0,1,7.,(2),1(1010*|1 (010)*1)*0,的,NFA,。,2024/9/23,CH.3.,练习题14(,P64.),(1,),正规式:,(10|0)*,(2),NFA:,确定化:,Y,X,1,0,0,1,2,0,1,0,0,1,0,1,2,I,I,0,I,1,X,1,Y,1,Y,2,1,Y,1,Y,2,2,1,Y,I,I,0,I,1,初终0,1,2,终 1,1,2,2,1,DFA:,2024/9/23,CH.3.,练习题14(,P64.),(1,),正规式:,(10|0)*,(2),NFA:,Y,X,1,0,0,1,2,0,1,0,0,1,0,1,2,DFA:,构造一个,DFA,，它接受,S,0,1,上所有满足如下条件的字符串：每个,1,都有,0,直接跟在右边。,1,0,0,1,0,DFA,:(,最简,),2024/9/23,程 序 设 计 语 言,Chapter 2.,高级语言及其语法描述,编译原理参考答案,2024/9/23,CH.2.,练习题6(,P36.),6.,令文法,G6,为:,N D|ND D 0|1|2|3|4|5|6|7|8|9,(1),G6,的语言,L(G6),是什么?,注意,：集合的写法不正确,解：,L(G6)=0,1,2,3,4,5,6,7,8,9,+,=0,9,数字构成的所有数字串，可以0开头,(2) 给出句子0127、34和568的最左和最右推导。,注意,：,1),步骤，,和,的区别,；,2),不能写为,解：,0127,的最左推导：,NNDNDDNDDDDDDD,0DDD,01,DD,012,D0127,0127,的最右推导：,NNDN7ND7N27ND27,N127,D1270127,+,CH.2.,练习题8(,P36.),8.,令文法为,E T|E+T|E-T,T F|T*F|T/F,F (E)|i,(1) 给出,i+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,),最右推导,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,),CH.2.,练习题8(,P36.),8.,令文法为,E T|E+T|E-T,T F|T*F|T/F,F (,E)|i,E,E - T,E - T,T,F,F,i,F,i,i,i-i-i,的语法树,(2) 给出,i+i+i、i+i,*i,和,i-i-i,的语法树。,E,E + T,E + T,T,F,F,i,F,i,i,i+i+i,的语法树,i+i,*i,的语法树,E,E + T,T,T,F,F,i,F,i,i,*,注意,：树枝和符号均不可随意增减！,CH.2.,练习题9(,P36.),9.,证明下面的文法是二义的：,S ,iSeS|iS|i,证明: 因为存在句子,iiiei,，它对应两棵不同的语法树,如右图:,所以该文法是二义文法。,说明,：按定义只要能给出一个反例即可，,iiiei,不是唯一的反例。,S,i S,i S e S,i,i,i,S,i S e S,i S,i,2024/9/23,编译原理参考答案,程 序 设 计 语 言,Chapter 5.,自下而上语法分析,2024/9/23,CH.5.,练习题1(,P133.),1.,令文法,G1,为：,EE+T|T TT*F|F F(E)|i,证明,E+T*F,是它的一个句型,指出这个句型的所有短语、直接短语和句柄。,证明,1:,存在从开始符号,E,出发到,E+T*F,的推导：,E,E+T, E+,T*F,E+T*F,是,G1,的一个句型。,短语:,E+T*F,是句型相对于非终结符,E,的短语;,T*F,是句型相对于非终结符,T,的短语,。,直接短语:,T*F,是句型相对于规则,TT*F,的直接短语,句柄:,T*F,E,E + T,T * F,语法树,2024/9/23,CH.5.,练习题1(,P133.),1.,令文法,G1,为：,EE+T|T TT*F|F F(E)|i,证明,E+T*F,是它的一个句型,指出这个句型的所有短语、直接短语和句柄。,证明,2:,可构造出,E+T*F,的,语法树，如右图所示,，,E+T*F,是,G1,的一个句型。,证明,3:,(,也可用归约来证明,),（概念熟悉后，短语、直接短语和句柄可直接列出而不用说明）,短语:,E+T*F,，,T*F,直接短语:,T*F,句柄:,T*F,E,E + T,T * F,语法树,2024/9/23,CH.5.,练习题2(,P133.),2.,考虑下面的表格结构文法,G2,：,Sa|,|(T) TT,S|S,(1),给出(,a,(a,a),的最左和最右推导。,(1) 解:,(,a,(a,a),的,最左推导：,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)(T,(T),(T,(T,S),(T,(T,a)(T,(S,a)(T,(a,a),(S,(a,a)(a,(a,a),2024/9/23,CH.5.,练习题2(,P133.),2.(2),指出(,a,(a,a),的规范归约及每一步的句柄。根据这个规范归约，给出“移进-归约”的过程，并给出它的语法树自下而上的构造过程。,(2) 解:,(,a,(a,a),的规范归约及每一步的句柄:,(,a,(a,a) (,S,(a,a) (T,(,a,a), (T,(,S,a) (T,(T,a,), (T,(,T, S,) (T,(T),), (,T,S,) ,(T),S,.,.,.,.,.,.,.,.,.,2024/9/23,CH.5.,练习题2(,P133.),2.(2).,给出(,a,(a,a),“移进-归约”的过程。,(2) 解:,(,a,(a,a),的“移进-归约”过程:,步骤 符号栈 输入串 动作 句柄,1 #,(,a,(a,a)# a,2 #(,a,(a,a)#,移进 (,3 #(,a,(a,a)#,移进,a,4 #(,S,(a,a)#,归约,S a S,5 #( T ,(,a,a)#,归约,T S a,6 #( T , (,a,a),#,移进 ,7 #(T,(,a,a)#,移进 (,8 #(T,(,a,a)#,移进,a,2024/9/23,CH.5.,练习题2(,P133.),2.(2).,给出(,a,(a,a),“移进-归约”的过程。,(2) 解:,(,a,(a,a),的“移进-归约”过程:,步骤,符号栈 输入串 动作 句柄,9 #(,T,(,S,a)#,归约,S a S,10 #(T,(T ,a,)#,归约,T S a,11 #(,T,(T,a,)#,移进 ,12 #(T,(T,a,)#,移进,a,13 #(T,(,T,S,)#,归约,S a T,S,14 #(T,(T,),),#,归约,T T,S (T),15 #(T,(T),)#,移进 ),16 #(,T, S,)#,归约,S (T) T,S,2024/9/23,CH.5.,练习题2(,P133.),2.(2).,给出(,a,(a,a),“移进-归约”的过程。,(2) 解:,(,a,(a,a),的“移进-归约”过程:,步骤 符号栈 输入串 动作 句柄,17 #,(,T,),#,归约,T T,S (T),18 #,(T),#,移进 ),19 #,S #,归约,S (T),20,成功,分析结束,接受输入串,2024/9/23,CH.5.,练习题2(,P133.),2.(2).,给出(,a,(a,a),的语法树自下而上构造过程。,(2) 解:,(,a,(a,a),的语法树自下而上构造过程: 用序号表示,S,( T ),T , S,( T ),T , S,S,a,S,a,a,2024/9/23,CH.5.,练习题3(,P133.),3.(1),计算练习2文法,G2,的,FIRSTVT,和,LASTVT。,Sa|,|(T) TT,S|S,(1) 解: （执行相应的算法可求得）,FIRSTVT(S)= a,( ,FIRSTVT(T)=,a,( ,LASTVT(S)= a,) ,LASTVT(T)= ,a,) ,2024/9/23,CH.5.,练习题3(,P133.),3.(2),计算文法,G2,的优先关系,G2,是一个算符优先文法吗?,Sa|,|(T) TT,S|S,(2) 解:,FIRSTVT(S)= a,( ,FIRSTVT(T)= ,a,( ,LASTVT(S)= a,) ,LASTVT(T)= ,a,) ,逐一考察,S(T),和,TT, S,两两相邻的符号，,得到算符优先关系, 如右图；,G2,是算符优先文法 。,a,(,),#,a,(,=,#,=,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,2024/9/23,3.(4),给出输入串(,a,(a,a,),的算符优先分析过程。,Sa|,|(T,) TT,S|S,序号,符号栈,输入串,优先关系,下一步的动作,0,#,(,a,(a,a)#,#(,移进 (,1,#(,a,(a,a)#,(,a,移进,a,2,#(,a,(,a,a)#,(,归约,S,a,3,#(,S,(,a,a)#,(,移进 ,4,#(,S,(,a,a)#,(,移进 (,5,#(,S,(,a,a)#,(,a,移进,a,6,#(,S,(,a,a)#,(,归约,S,a,7,#(,S,(S,a)#,(,移进 ,8,#(,S,(S,a)#,(,=,#,=,最左素短语,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,2024/9/23,序号,符号栈,输入串,优先关系,下一步的动作,9,#(,S,(S,a,)#,),归约,S,a,10,#(,S,(,S,S,)#,(),归约,T,S,S,11,#(,S,(T,),)#,(=),移进 ),12,#(,S,(T),)#,),归约,S,(T),13,#(,S,S,)#,(),归约,T,S,S,14,#(,T,)#,(=),移进 ),15,#,(,T),#,*#,归约,S,(T),16,#,S,#,#=#,接受,17,#,S,#,停,.,.,.,.,.,.,.,.,.,.,.,.,.,3.(4),给出输入串(,a,(a,a,),的算符优先分析过程。,Sa|,|(T,) TT,S|S,a,(,),#,a,(,=,#,=,最左素短语,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,2024/9/23,5.(1),考虑文法,SAS|b ASA|a,列出这个文法的所有,LR(0),项目,。,CH.5.,练习题5(,P134.),解(1):,拓广文法，加入,SS,拓广文法的,LR(0),项目有:,S.S SS.,S.AS SA.S,SAS. S.b Sb. A.SA,AS.A ASA. A.a Aa.,2024/9/23,5.(2),构造文法,SAS|b ASA|a,的,LR(0),项目集规范族及识别活前缀的,DFA。,1,）拓广文法，加入,SS,2,）画出,DFA,2024/9/23,5.(2),构造文法,SAS|b ASA|a,的,LR(0),项目集规范族及识别活前缀的,DFA。,0:,S.S,S.AS S.b,A.SA A.a,5:,ASA.,SA.S,S.AS,S.b A.SA,A.a,7:,SAS.,AS.A,A.SA,A.a S.AS,S.b,1:,SS.,AS.A,A.SA,A.a S.AS,S.b,3:,Sb.,4:,Aa.,2:,SA.S,S.AS S.b,A.SA A.a,6:,AS.A,A.SA A.a,S.AS S.b,S,b,a,A,A,S,b,a,A,S,a,b,S,a,b,A,S,A,b,a,S,a,b,A,2024/9/23,5.(,3),文法,SAS|b ASA|a,是,LR(0),文法吗？,0:,S.S,S.AS S.b,A.SA A.a,5:,ASA.,SA.S,S.AS,S.b A.SA,A.a,7:,SAS.,AS.A,A.SA,A.a S.AS,S.b,1:,SS.,AS.A,A.SA,A.a S.AS,S.b,3:,Sb.,4:,Aa.,2:,SA.S,S.AS S.b,A.SA A.a,6:,AS.A,A.SA A.a,S.AS S.b,S,b,a,A,A,S,b,a,A,S,a,b,S,a,b,A,S,A,b,a,S,a,b,A,不是,LR(0),文法,！,因为存在冲突，例如状态,1,、状态,5,2024/9/23,编译原理参考答案,程 序 设 计 语 言,Chapter 4.,自上而下语法分析,2024/9/23,CH.4.,练习题1(,P81.),1.,考虑下面文法,G,1,:,Sa|(T),TT，S|S,(1),消去,G,1,的左递归。然后对每个非终结符,写出不带回溯的递归子程序,。,解(1),消左后的文法,G,1,:,Sa|(T),TST,T ,ST|,2024/9/23,CH.4.,练习题1,(P81.),解(1),不带回溯的递归子程序:,Sa|(T),Procedure S;,Begin,if sym=a or sym= then advance,else if sym=( then,begin advance;,T;,if sym=) then advance,else error,end,else error,End;,CH.4.,练习题1,(P81.),解(1),不带回溯的递归子程序:,TST,Procedure T;,Begin,S;,T,end;,解(1),不带回溯的递归子程序:,T,ST|,procedure T;,begin,if sym=, then,begin,advance;,S;,T,end,End;,CH.4.,练习题1(,P81.),(2),经改写后的文法是否是,LL(1),的? 给出它的预测分析表。,消左后的文法,G,1,:,Sa|(T),TST T ,ST|,(2),因为,G,1,:, 文法不含左递归;, 对,Sa|(T,),FIRST(,a,)=a, FIRST(,)=, FIRST(,(T),)= ( ,集合互不相交且不含,;, 对,T,ST|,FIRST( ,ST )= , ,FIRST(,)=,其交集为空。,但,FIRST(T,)=,FIRST( ,ST ),FIRST(,)=,，,然而，,FOLLOW(T)= ) FIRST(T)=，,，两者 不相交。,所以，,G,1,是,LL(1),文法。,CH.4.,练习题1(,P81.),(2),构造,G,1,的,预测分析表:, 对,Sa|(T), 对,TST,FIRST(a)=a FIRST(ST)=a,(,FIRST()=, 对,T,ST|,FIRST(T)=( FIRST(,ST)=,预测分析表:,FOLLOW(T)=),a,(,),#,S,Sa,S,S(T),T,TST,TST,TST,T,T,T ,ST,2024/9/23,CH4.,1.(3),给出对符号串(,a，),的分析过程,步骤 符号栈 输入串 动作, 所用产生式 .,0 #S (a,)#,初始；,用,S,(,查表,1 #)T( (a,)# S(T),展开,S,2 #)T a,)#,匹配(；,用,T , a,查表,3 #)TS a,)# TST ,展开,T;,用,S ,a,查表,4 #)Ta a,)# S a,展开,S,5 #)T ,)#,匹配,a;,用,T,查表,6 #)TS, ,)# T ,ST,展开,T,7 #)TS )#,匹配, ；,用,S , ,查表,8 #)T )# S ,展开,S,9 #)T )#,匹配 ；,用 T,),查表,10 #) )# T,展 开,T,11 # #,匹配 ),12 # #,分析成功, 结束分析,CH.4.,练习题3(,P82.),3.,下面文法中, 哪些是,LL(1),的, 说明理由。,(1),SABc,A a| B b|,。,解，,因为,FOLLOW(S)=#,文法不含左递归;,FIRST(S)=a,b,c, 对,Aa|,候选式的,FIRST,集合互不相交;,FIRST(A),但, FOLLOW(A)=,b,c, FIRST(A)=,a,两者不相交。,Bb|,其候选式的,FIRST,集合互不相交;,FIRST(B),但，,FOLLOW(B)=c FIRST(B)=,b,两者也不相交。,所以，文法是,LL(1),文法。,CH.4.,练习题3(,P82.),3.,下面文法中, 哪些是,LL(1),的, 说明理由。,(2),SAb,A a|B| B b|,。,解(,1),因为,FOLLOW(S)=#,对,Aa|B|,;,FIRST(S)=a,b,FIRST(B)=b,与,FIRST()=,相交;,所以文法不是,LL(1),文法。,解(,2),对,Aa|,因为,FIRST(A,)=,a,b,，,FOLLOW(A)=b,FOLLOW,和,FIRST,两者相交。,所以文法不是,LL(1),文法。,CH.4.,练习题3(,P82.),3.,下面文法中, 哪些是,LL(1),的, 说明理由。,(3),SABBA A a| B b|,。,解，,虽然,FOLLOW(S)=#,文法不含左递归;,FIRST(S)=a, b, 对,Aa|,，其候选式的,FIRST,集合不相交;,对,Bb|,，其候选式的,FIRST,集合也不相交;,但 对,Aa|,（由,Bb|,出发证明也可）,FOLLOW(A)= a, b, # , FIRST(A)=,a,两者相交。,所以，文法不是,LL(1),文法。,CH.4.,练习题3(,P82.),3.,下面文法中, 哪些是,LL(1),的, 说明理由。,(4),SaSe|B,BbBe|C,CcCe|d,。,解，,因为,文法不含左递归;, 对,SaSe|B、BbBe|C,和,CcCe|d,各产生式的候选式的,FIRST,集合均不相交; 即,FIRST(aSe,),FIRST(B)=,；,FIRST(bBe,),FIRST(C)=,；,FIRST(cCe,),FIRST(d,)=,；,FIRST(S)=,a,b,c,d,，,FIRST(B)=,b,c,d,FIRST(C)=,c,d,均不含,。,所以，文法是,LL(1),文法。,编译原理参考答案,程 序 设 计 语 言,Chapter 7.,语义分析和中间代码产生,2024/9/23,P217-1,a*,（,-,b+c,） 后缀式：,ab-c,+*,a+b,*,（,c+d/e,） 后缀式：,abcde,/+*+,-,a+b,*,（,-,c+d,） 后缀式：,a-,bc-d,+*+,not A or not,（,C or not D,）,后缀式：,A not C D not or not or,（,A and B,）,or,（,not C or D,）,后缀式：,A B and C not D or,or,2024/9/23,P217-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),2024/9/23,P218-4,自下而上分析过程中把赋值语句,A := B *,（,-C + D,）翻译成三地址码的步骤：,（参看,p179,的语义子程序）,2024/9/23,语法分析翻译过程：,A := B * (-C + D),A := E,1,* (-C + D) E,1.,place=k,2,A := E,1,* (-E,2,+ D) E,2.,place=k,3,A := E,1,* (E,3,+ D),A := E,1,* (E,3,+ E,4,),A := E,1,* (E,5,),A := E,1,* E,6,A := E,7,S,.,.,.,.,.,.,.,.,产生一个新的中间变量,T,1,E,3.,place=k,5,产生代码,k,5,:=,uminus,k,3,名字,属性,地址,A,B,C,D,T,1,T,2,T,3,k,1,K,2,k,3,k,4,k,5,k,6,k,7,符号表,2024/9/23,A := B * (-C + D),的三地址码,k,5,:=,uminus,k,3,k,6,:= k,5,+ k,4,k,7,:= k,2,* k,6,k,1,:= k,7,名字,属性,地址,A,B,C,D,T,1,T,2,T,3,k,1,K,2,k,3,k,4,k,5,k,6,k,7,符号表,（参看,p179,的语义子程序）,2024/9/23,P218-6,：,用,7.4.2,节的办法，把,A or,（,B and not,（,C or D,）,翻译成四元式序列,100,：（,jnz,，,A,，,-,，,0,）,101,：（,j,，,-,，,-,，,102,）,102,：（,jnz,，,B,，,-,，,104,）,103,：（,j,，,-,，,-,，,0,）,104,：（,jnz,，,C,，,-,，,.,）,105,：（,j,，,-,，,-,，,106,）,106,：（,jnz,，,D,，,-,，,.,）,107,：（,j,，,-,，,-,，,.,）,TC,FC,2024/9/23,P218-7,100,：（,j,，,A,，,C,，,102,）,101,：（,j,，,-,，,-,，,115,）,102,：（,j,，,B,，,D,，,104,）,103,：（,j,，,-,，,-,，,115,）,104,：（,j=,，,A,，,1,，,106,）,105,：（,j,，,-,，,-,，,109,）,106,：（,+,，,C,，,1,，,T1,）,107,：（,:=,，,T1,，,-,，,C,）,108,：（,j,，,-,，,-,，,100,）,109,：（,j,，,A,，,D,，,111,）,110,：（,j,，,-,，,-,，,100,）,111,：（,+,，,A,，,2,，,T2,）,112,：（,:=,，,T2,，,-,，,A,）,113,：（,j,，,-,，,-,，,109,）,114,：（,j,，,-,，,-,，,100,）,115,：,用,7.5.1,节的办法，把下面的语句翻译成四元式序列：,while A C and B D do,if A=1 then C:=C+1,else,while A D do,A:=A+2;,2024/9/23,编译原理参考答案,程 序 设 计 语 言,Chapter 8. Chapter 11.,2024/9/23,CH8. CH11.,1.,什么是符号表？符号表有哪些重要作用？,2.,符号表的表项常包括哪些部分？各描述什么？,3.,有哪些存储分配策略？并叙述何时用何种存储分配策略？,4.,代码优化的常用措施和优化的三个层次。,2024/9/23,编译原理参考答案,程 序 设 计 语 言,补充题,2024/9/23,补充题,1.,画出编译程序的总体逻辑结构图，简述各部分的主要功能。,2024/9/23,补充题,2.,已知文法,GZ:,Z0U|1V,U1Z|1,V0Z|0,请写出此文法描述的只含有个符号的全部句子。,GZ,产生的语言是什么？,该文法在,Chomsky,文法分类中属于几型文法？,2024/9/23,【,解,】,（,1,）,0101,，,0110,，,1010,，,1001,（,2,）分析,GZ,所推导出的句子的特点：由,Z,开始的推导不外乎图,1,所示的四种情形。,由,Z,推导出,10,或,01,后就终止或进入递归，而,Z,的每次递归将推导出相同的符号串：,10,或,01,。所以,GZ,产生的语言,L(GZ)=x|x(10|01),+,(3),该文法属于,3,型文法。,Z0U|1V U1Z|1,V0Z|0,2024/9/23,补充题,3.,已知文法和它的,LR,分析表如下，给出串,dbdb,#,的,LR,分析过程。,GS,：,(1),SAdB,(2)Aa (3),A,(4),Bb,(5)BBdb (6)B,ACTION,GOTO,a,d,b,#,S,A,B,0,s3,r3,1,2,1,acc,2,s4,3,r2,4,r6,s5,r6,6,5,r4,r4,6,s7,r1,7,s8,8,r5,r5,LR,分析表,2024/9/23,【,解,】,串,dbdb,#,的,LR,分析过程如下：,步骤,状态,符号,输入串,下一步,的动作,0,0,#,dbdb,#,r3,归约,1,02,#A,dbdb,#,s4,移进,2,024,#Ad,bdb,#,s5,移进,3,0245,#,Adb,db#,r4,归约,4,0246,#,AdB,db#,s7,移进,5,02467,#,AdBd,b#,s8,移进,6,024678,#,AdBdb,#,r5,归约,9,0246,#,AdB,#,r1,归约,10,01,#S,#,acc,11,停,2024/9/23,补充题,4 .,给定文法和语义动作如下：,A,aB,print “0”,A, c print “1” B,Ab,print “2”,问：按照以上的语义子程序，,aacbb,经翻译后的输出结果是什么？请给出翻译过程。,aacbb,翻译后的输出结果是,打印出下面的字符串：,12020,b,B,c,A,A,a,B,A,a,b,A,aB,print “0”,A, c print “1”B,Ab,print “2”,翻译过程和翻译结果,语法分析,：,aacbb,aaAbb,(1),aaBb,(2),aAb,(3),aB,(4),A (5),.,.,.,.,.,翻译过程,：,(1),print “1”,(2),print “2”,(3),print “0”,(4),print “2”,(5),print “0”,A,aB,print “0”,A, c print “1”B,Ab,print “2”,翻译结果：,打印出字符串,12020,2024/9/23,补充题,5.,课堂上讲过的以及课件中给出的有代表性的例题都要,亲自动手独力做一遍,。,6.,参阅“编译原理,_(,V_jx_Summary,_,精简,=,完全,)”,2024/9/23,