编译原理考试习题及答案实用教案

1、2021-12-15CH.3.CH.3.练习题8(8(P64.)P64.) 8. 给出下面的正规表达式。 (1) 以01结尾的二进制数串; 正规式 (0|1)*01 (2) 能被5整除的十进制整数(zhngsh); 允许任意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)第1页/共64页第一页，共65页。2021-12-15CH.3.CH.3.练习题7(7(P64.)P64.) 7. (1) 1(0|1)*101 构造DFA。 解1: 正规(zhnggu)式对应的NFA:XY34511

2、011210 I I0 I1X 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,23,Y,4,23,5,2 3,4,2 I I0 I1初初0 1 1 2 3 2 2 3 3 4 3 4 2 5终终5 4 3第2页/共64页第二页，共65页。 (1) 正规(zhnggu)式 1(0|1)*101DFA:x3,Y,4,23,4,23,5,211011,3,23,20100101 I I0 I1X 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,

3、5,2 3,2 3,Y,4,23,Y,4,23,5,2 3,4,2 I I0 I1初初0 1 1 2 3 2 2 3 3 4 3 4 2 5终终5 4 3第3页/共64页第三页，共65页。 (1) 正规(zhnggu)式 1(0|1)*101DFA: I I0 I1X 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,23,Y,4,23,5,2 3,4,2 I I0 I1初初0 1 1 2 3 2 2 3 3 4 3 4 2 5终终5 4 305341101120100101第4页/共64页第四页，共65

4、页。2021-12-15CH.3.CH.3.练习题7(7(P64.)P64.) 7. 构造下列(xili)正规式相应的DFA。 (1) 1(0|1)*101 解2: 正规式对应的NFA:04123110110 I I0 I10 初初01 11 11 11,2 21,2 21,3 31,2 21,3 31 11,2,4 41,2,4终终4 1,3 31,2 210423110110010DFA:第5页/共64页第五页，共65页。2021-12-15 7. 构造(guzo)下列正规式相应的NFA。(P64.) (2) 1(1010*|1 (010)*1)*0XY201131010*1 (010)*

5、1XY201136451100*7811(010)*第6页/共64页第六页，共65页。2021-12-15 7. 构造下列(xili)正规式相应的NFA。(P64.) (2) 1(1010*|1 (010)*1)*0XY201136451100*7811(010)*XY2011364511007811910010第7页/共64页第七页，共65页。XY2011364511007811910010XY201136451100781191001211017. (2) 1(1010*|1 (010)*1)*0的NFA。第8页/共64页第八页，共65页。2021-12-15CH.3.CH.3.练习题14

6、(14(P64.)P64.) (1) 正规(zhnggu)式: (10|0)* (2) NFA: 确定化:YX1001201001012 I I0 I1X,1,Y 1,Y2 1,Y1,Y2 21,Y I I0 I1初终初终0 1 2 终终 1 1 2 2 1 DFA:第9页/共64页第九页，共65页。2021-12-15CH.3.CH.3.练习题14(14(P64.)P64.) (1) 正规(zhnggu)式: (10|0)* (2) NFA:YX1001201001012DFA:构造一个DFA，它接受(jishu) S0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。10010DF

7、A:(最简)第10页/共64页第十页，共65页。程 序 设 计 语 言 Chapter 2.高级语言及其语法(yf)描述第11页/共64页第十一页，共65页。CH.2.CH.2.练习题6(6(P36.)P36.) 6.令文法G6为: N D|ND D 0|1|2|3|4|5|6|7|8|9 (1) G6的语言L(G6)是什么? 注意：集合(jh)的写法不正确 解：L(G6)=0,1,2,3,4,5,6,7,8,9+ =09数字构成的所有数字串，可以0开头 (2) 给出句子0127、34和568的最左和最右推导。 注意：1)步骤，和 的区别；2) 不能写为 解：0127的最左推导：NNDNDDN

8、DDDDDDD 0DDD01DD012D0127 0127的最右推导：NNDN7ND7N27ND27 N127D1270127+第12页/共64页第十二页，共65页。CH.2.CH.2.练习题8(8(P36.)P36.) 8. 令文法(wnf)为 E T|E+T|E-T T F|T*F|T/F F (E)|i (1) 给出 i+i*i、i*(i+i)的最左推导(tudo)和最右推导(tudo)。解：此处仅以 i*(i+i) 为例给出答案(d n)最左推导E E T T T T* *F F F F* *F F i i* *F F i i* *(E) (E) i i* *(E+T)(E+T) i

9、i* *(T+T)(T+T) i i* *(F+T)(F+T) i i* *(i+T)(i+T) i i* *(i+F )(i+F ) i i* *(i+i)(i+i) 最右推导E E T T T T* *F F T T* *(E) (E) T T* *(E+T) (E+T) T T* *(E+F)(E+F) T T* *(E+i) (E+i) T T* *(T+i) (T+i) T T* *(F+i)(F+i) T T* *(i+i)(i+i) F F* *(i+i)(i+i) i i* *(i+i)(i+i) 第13页/共64页第十三页，共65页。CH.2.CH.2.练习题8(8(P36.

10、)P36.) 8. 令文法(wnf)为 E T|E+T|E-T T F|T*F|T/F F (E)|iEE - TE - TTF F iF iii-i-i i-i-i 的语法(yf)(yf)树(2) 给出 i+i+i、i+i*i和i-i-i的语法(yf)树。EE + TE + TTF F iF iii+i+i i+i+i 的语法树i+ii+i* *i i 的语法树EE + TTTF F iF ii*n注意：树枝和符号均不可随意增减！第14页/共64页第十四页，共65页。2021-12-15CH.2.CH.2.练习题9(9(P36.)P36.) 9. 证明下面的文法是二义的： S iSeS|iS

11、|i 证明: 因为存在句子 iiiei，它对应两棵不同的语法树,如右图: 所以该文法是二义文法。 说明：按定义只要(zhyo)能给出一个反例即可，iiiei不是唯一的反例。S i S i S e SiiiSi S e S i Si第15页/共64页第十五页，共65页。程 序 设 计 语 言 Chapter 5.自下而上(z xi r shn)语法分析第16页/共64页第十六页，共65页。2021-12-15CH.5.CH.5.练习题1(1(P133.)P133.) 1.令文法G1为：EE+T|T TT*F|F F(E)|i 证明E+T*F是它的一个句型,指出这个(zh ge)句型的所有短语、直

12、接短语和句柄。n证明证明1: 存在从开始符号存在从开始符号E出发到出发到E+T*F的的推导：推导： E E+T E+T*F n E+T*F是是G1的一个句型。的一个句型。n短语短语(duny): E+T*F是句型相对于非终结符是句型相对于非终结符E的短语的短语(duny); T*F是句型相对于非终结是句型相对于非终结符符T的短语的短语(duny)。n直接短语直接短语(duny): T*F是句型相对于规则是句型相对于规则TT*F的直接短语的直接短语(duny)n句柄句柄: T*FEE + TT * F语法树第17页/共64页第十七页，共65页。2021-12-15CH.5.CH.5.练习题1(1

13、(P133.)P133.) 1.令文法G1为：EE+T|T TT*F|F F(E)|i 证明E+T*F是它的一个句型,指出这个句型的所有(suyu)短语、直接短语和句柄。n证明证明2: 可构造可构造(guzo)出出E+T*F的语法树，的语法树，如右图所示，如右图所示， E+T*F是是G1的一个句型。的一个句型。n证明证明3: (也可用归约来证明也可用归约来证明)n（概念熟悉后，短语、直接短语和句柄可直（概念熟悉后，短语、直接短语和句柄可直接列出而不用说明）接列出而不用说明）n 短语短语: E+T*F，T*Fn 直接短语直接短语: T*Fn 句柄句柄: T*FEE + TT * F语法树第18页

14、/共64页第十八页，共65页。2021-12-15CH.5.CH.5.练习题2(2(P133.)P133.) 2.考虑下面的表格结构文法(wnf)G2： Sa|(T) TT,S|S (1)给出(a,(a,a)的最左和最右推导。 n(1) 解解: (a,(a,a)的的n最左推导最左推导(tudo)： S (T) (T,S)(S,S) (a,S)n (a,(T) (a,(T,S) (a,(S,S)n (a,(a,S)(a,(a,a) n最右推导最右推导(tudo)： S (T) (T,S)(T,(T) (T,(T,S)n (T,(T,a)(T,(S,a)(T,(a,a) n (S,(a,a)(a,

15、(a,a) 第19页/共64页第十九页，共65页。2021-12-15CH.5.CH.5.练习题2(2(P133.)P133.) 2.(2)指出(a,(a,a)的规范归约及每一步的句柄。根据这个规范归约，给出“移进-归约”的过程(guchng)，并给出它的语法树自下而上的构造过程(guchng)。n(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.第20页/共64页第二十页，共65

16、页。2021-12-15CH.5.CH.5.练习题2(2(P133.)P133.) 2.(2).给出(a,(a,a)“移进-归约”的过程(guchng)。n(2) 解解: (a,(a,a)的的“移进移进-归约归约”过程过程(guchng):n步骤步骤 符号栈符号栈 输入串输入串 动作动作 句柄句柄n 1 # ( a ,(a,a)# an 2 #( a ,(a,a)# 移进移进 (n 3 #( a ,(a,a)# 移进移进 an 4 #( S ,(a,a)# 归约归约 S a Sn 5 #( T ,( a ,a)# 归约归约 T S an 6 #( T , ( a ,a)# 移进移进 ,n 7

17、#(T,( a ,a)# 移进移进 (n 8 #(T,( a ,a)# 移进移进 a第21页/共64页第二十一页，共65页。2021-12-15CH.5.CH.5.练习题2(2(P133.)P133.) 2.(2).给出(a,(a,a)“移进-归约”的过程(guchng)。n(2) 解解: (a,(a,a)的的“移进移进-归约归约”过程过程:n步骤步骤 符号符号(fho)栈栈 输入串输入串 动作动作 句柄句柄n 9 #(T,( S ,a)# 归约归约 S a Sn 10 #(T,(T , a )# 归约归约 T S an 11 #(T,(T, a )# 移进移进 ,n 12 #(T,(T, a

18、 )# 移进移进 an 13 #(T,( T,S )# 归约归约 S a T,Sn 14 #(T, (T ) )# 归约归约 T T,S (T)n 15 #(T, (T) )# 移进移进 )n 16 #( T, S )# 归约归约 S (T) T,S第22页/共64页第二十二页，共65页。2021-12-15CH.5.CH.5.练习题2(2(P133.)P133.) 2.(2).给出(a,(a,a)“移进-归约”的过程(guchng)。n(2) 解解: (a,(a,a)的的“移进移进-归约归约”过程过程:n步骤步骤 符号栈符号栈 输入输入(shr)串串 动作动作 句柄句柄 n 17 # (T

19、) # 归约归约 T T,S (T)n 18 # (T) # 移进移进 )n 19 # S # 归约归约 S (T)n 20 成功成功,分析结束分析结束,接受输入接受输入(shr)串串第23页/共64页第二十三页，共65页。2021-12-15CH.5.CH.5.练习题2(2(P133.)P133.) 2.(2).给出(a,(a,a)的语法(yf)树自下而上构造过程。n(2) 解解:n (a,(a,a)的语法的语法树自下而上构造树自下而上构造(guzo)过程过程: 用用序号表示序号表示S( T ) T , S ( T ) T , SSaSaa第24页/共64页第二十四页，共65页。2021-1

20、2-15CH.5.CH.5.练习题3(3(P133.)P133.) 3.(1) 计算(j sun)练习2文法G2的FIRSTVT和LASTVT。 Sa|(T) TT,S|Sn(1) 解解: （执行相应（执行相应(xingyng)的算的算法可求得）法可求得）n FIRSTVT(S)= a, , ( n FIRSTVT(T)= , a, , ( n LASTVT(S)= a, , ) n LASTVT(T)= , , a, , ) ,第25页/共64页第二十五页，共65页。2021-12-15CH.5.CH.5.练习题3(3(P133.)P133.) 3.(2)计算(j sun)文法G2的优先关系

21、,G2是一个算符优先文法吗? Sa|(T) TT,S|Sn(2) 解: n FIRSTVT(S)= a, , ( n FIRSTVT(T)= , , a, , ( n LASTVT(S)= a, , ) n LASTVT(T)= , , a, , ) n逐 一 考 察 S ( T ) 和 TT, S 两两相邻(xin ln)的符号，得到算符优先关系, 如右图；nG2是算符优先文法 。 a ( ) ,# a ( = , #=.第26页/共64页第二十六页，共65页。2021-12-153.(4)3.(4)给出输入串给出输入串(a,(a,a)(a,(a,a)的算符优先分析的算符优先分析(fnx)(

22、fnx)过过程。程。 Sa|(T) TT,S|S序号序号符号栈符号栈输入串输入串优先关系优先关系下一步的动作下一步的动作0#(a,(a,a)#(移进移进 (1#( a,(a,a)#(a移进移进 a2#(a ,(a,a)#(,归约归约 Sa3#(S ,(a,a)#(,移进移进 ,4#(S, (a,a)#,(移进移进 (5#(S,( a,a)#(a移进移进 a6#(S,(a ,a)#(,归约归约 Sa7#(S,(S ,a)#(,移进移进 ,8#(S,(S, a)#, ( = , #=最左素短语(duny).第27页/共64页第二十七页，共65页。2021-12-15序号序号符号栈符号栈输入串输入串

23、优先关系优先关系下一步的动作下一步的动作9#(S,(S,a )#,)归约归约 Sa10#(S,(S,S )#()归约归约 TS,S11#(S,(T )#(=)移进移进 )12#(S,(T) )#,)归约归约 S(T)13#(S,S )#()归约归约 TS,S14#(T )#(=)移进移进 )15#(T) #*#归约归约 S(T)16#S #=#接受接受17#S #停停.3.(4)3.(4)给出输入串给出输入串(a,(a,a)(a,(a,a)的算符优先的算符优先(yuxin)(yuxin)分析过分析过程。程。 Sa|(T) TT,S|S a ( ) ,# a ( = , #=最左素短语(duny

24、).第28页/共64页第二十八页，共65页。2021-12-15 5.(1) 考虑文法 SAS|b ASA|a 列出这个(zh ge)文法的所有LR(0)项目。 CH.5.CH.5.练习题5(5(P134.)P134.)n解(1): (1): 拓广文法，加入(jir) S(jir) SSSn 拓广文法的LR(0)LR(0)项目有: :n S S.S S.S SS. S.AS SA.SS. S.AS SA.Sn SAS. S.b Sb. A.SA SAS. S.b Sb. A.SAn AS.A ASA. A.a Aa. AS.A ASA. A.a Aa. 第29页/共64页第二十九页，共65页。

25、2021-12-155.(2) 构造文法 SAS|b ASA|a 的LR(0)项目集规范族及识别(shbi)活前缀的DFA。 1）拓广文法(wnf)，加入 SS2）画出 DFA第30页/共64页第三十页，共65页。 5.(2) 构造文法 SAS|b ASA|a 的LR(0)项目集规范(gufn)族及识别活前缀的DFA。 0: S.S S.AS S.b A.SA A.a 5: ASA.SA.S S.ASS.b A.SAA.a7: SAS.AS.A A.SAA.a S.ASS.b 1: SS. AS.A A.SA A.a S.AS S.b 3: Sb. 4: Aa. 2: SA.S S.AS S.

26、b A.SA A.a 6: AS.A A.SA A.a S.AS S.b SbaAASbaASabSabASAbaSabA第31页/共64页第三十一页，共65页。2021-12-15 5.(3) 文法(wnf) SAS|b ASA|a 是LR(0)文法(wnf)吗？ 0: S.S S.AS S.b A.SA A.a 5: ASA.SA.S S.ASS.b A.SAA.a7: SAS.AS.A A.SAA.a S.ASS.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

27、 S.AS S.b SbaAASbaASabSabASAbaSabA不是LR(0)文法！因为存在(cnzi)冲突，例如状态1、状态5第32页/共64页第三十二页，共65页。程 序 设 计 语 言 Chapter 4. 自上而下(z shn r xi)语法分析第33页/共64页第三十三页，共65页。2021-12-15CH.4.CH.4.练习题1(1(P81.)P81.) 1.考虑下面文法G1: Sa|(T) TT，S|S (1) 消去G1的左递归。然后(rnhu)对每个非终结符,写出不带回溯的递归子程序。n解解(1) 消左后的文法消左后的文法(wnf)G1: n Sa|(T)n TSTn T

28、,ST|第34页/共64页第三十四页，共65页。CH.4.CH.4.练习题1 1(P81.)(P81.)n解(1) 不带回溯(hu s)的递归子程序: Sa|(T)n Procedure S;n Beginn if sym=a or sym= then advance n else if sym=( thenn begin advance;n T;n if sym=) then advancen else errorn endn else errorn End;第35页/共64页第三十五页，共65页。CH.4.CH.4.练习题1 1(P81.)(P81.)n解(1) 不带回溯(hu s)的递归

29、子程序: nTSTn Procedure T;n Beginn S;n Tn end;n n解(1) 不带回溯(hu s)的递归子程序: nT,ST|n procedure T;n begin n if sym=, then n begin n advance;n S;n Tn endn End;第36页/共64页第三十六页，共65页。CH.4.CH.4.练习题1(1(P81.)P81.)(2) 经改写(gixi)后的文法是否是LL(1)的? 给出它的预测分析表。消左后的文法G1 : Sa|(T) TST T ,ST|(2) 因为G1 : 文法不含左递归; 对 Sa|(T) FIRST(a)=

30、a, FIRST()=, FIRST( (T) )= ( , 集合(jh)互不相交且不含; 对 T,ST| FIRST( ,ST )= , , FIRST()=, 其交集为空。 但FIRST(T)=FIRST( ,ST )FIRST()=，, 然而，FOLLOW(T)= ) FIRST(T)=，, ，两者 不相交。 所以，G1是LL(1)文法。 第37页/共64页第三十七页，共65页。2021-12-15CH.4.CH.4.练习题1(1(P81.)P81.)(2)构造G1的预测(yc)分析表: 对Sa|(T) 对TST FIRST(a)=a FIRST(ST)=a,( FIRST()= 对 T

31、,ST| FIRST(T)=( FIRST(,ST)=,预测(yc)分析表: FOLLOW(T)=) a ( ) , # SSaSS(T) TTSTTSTTST TTT ,ST第38页/共64页第三十八页，共65页。CH4.1.(3) CH4.1.(3) 给出对符号串(a(a，) ) 的分析(fnx)(fnx)过程步骤 符号栈 输入串 动作, 所用产生式 . 0 #S (a,)# 初始(ch sh)；用 S , ( 查表 1 #)T( (a,)# S(T), 展开S 2 #)T a,)# 匹配(；用 T , a 查表 3 #)TS a,)# TST , 展开T; 用 S ,a 查表 4 #)T

32、a 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 # # 分析成功, 结束分析第39页/共64页第三十九页，共65页。CH.4.CH.4.练习题3(3(P82.)P82.) 3.下面文法(wnf)中, 哪些是LL(1)的, 说明理由。 (1) SABc A a| B b|。n解，因为(yn wi) FOLLOW(S)=#n 文法不

33、含左递归; FIRST(S)=a,b,c n 对 Aa|n 候选式的FIRST集合互不相交; FIRST(A) n 但, FOLLOW(A)=b,c FIRST(A)=a, 两者不相交。n Bb|n 其候选式的FIRST集合互不相交; FIRST(B)n 但， FOLLOW(B)=c FIRST(B)=b, 两者也不相交。n n所以，文法是LL(1)文法。第40页/共64页第四十页，共65页。CH.4.CH.4.练习题3(3(P82.)P82.) 3.下面文法(wnf)中, 哪些是LL(1)的, 说明理由。 (2) SAb A a|B| B b|。n解(1) 因为 FOLLOW(S)=#n 对

34、 Aa|B| ; FIRST(S)=a,b n FIRST(B)=b,与FIRST()=相交;n所以文法(wnf)不是LL(1)文法(wnf)。n解(2) 对 Aa|n 因为FIRST(A)= a,b, ，FOLLOW(A)=b, n FOLLOW和FIRST两者相交。n 所以文法(wnf)不是LL(1)文法(wnf)。第41页/共64页第四十一页，共65页。CH.4.CH.4.练习题3(3(P82.)P82.) 3.下面(xi mian)文法中, 哪些是LL(1)的, 说明理由。 (3) SABBA A a| B b|。n解，虽然 FOLLOW(S)=#n 文法不含左递归; FIRST(S)

35、=a, b, n 对 Aa|，其候选(hu xun)式的FIRST集合不相交;n 对 Bb|，其候选(hu xun)式的FIRST集合也不相交;n 但 对 Aa| （由 Bb|出发证明也可）n FOLLOW(A)= a, b, # , FIRST(A)= a, n 两者相交。n 所以，文法不是LL(1)文法。第42页/共64页第四十二页，共65页。CH.4.CH.4.练习题3(3(P82.)P82.) 3.下面文法(wnf)中, 哪些是LL(1)的, 说明理由。 (4) SaSe|B BbBe|C CcCe|d。n解， 因为 文法不含左递归; n 对 SaSe|B、BbBe|C 和 CcCe|

36、dn 各产生式的候选(hu xun)式的FIRST集合均不相交; 即n FIRST(aSe) FIRST(B)= ；n FIRST(bBe) FIRST(C)= ；n FIRST(cCe) FIRST(d)= ；n FIRST(S)= a,b,c,d ，FIRST(B)= b,c,d n FIRST(C)= c,d 均不含。n 所以，文法是LL(1)文法。第43页/共64页第四十三页，共65页。程 序 设 计 语 言 Chapter 7. 语义分析(fnx)和中间代码产生第44页/共64页第四十四页，共65页。2021-12-15P217-1 a*（-b+c） 后缀(huzhu)式：ab-c+

37、* a+b*（c+d/e） 后缀(huzhu)式：abcde/+*+ -a+b*（-c+d） 后缀(huzhu)式：a-bc-d+*+ not A or not（C or not D） 后缀(huzhu)式：A not C D not or not or （A and B）or（not C or D） 后缀(huzhu)式：A B and C not D or or第45页/共64页第四十五页，共65页。2021-12-15P217-3 -（a+b）*（c+d）-（a+b+c） 的四元(s yun)式序列： （1）(+，a，b，T1) （2）(-，T1，-，T2) （3）(+，c，d，T3)

38、（4）(*，T2，T3，T4) （5）(+，a，b，T5) （6）(+，T5，c，T6) （7）(-，T4，T6，T7)第46页/共64页第四十六页，共65页。2021-12-15P218-4自下而上分析过程中把赋值语句(yj) A := B * （-C + D）翻译成三地址码的步骤： （参看p179的语义子程序）第47页/共64页第四十七页，共65页。 语法分析翻译(fny)过程： A := B * (-C + D) A := E1 * (-C + D) E1.place=k2 A := E1 * (-E2 + D) E2.place=k3 A := E1 * (E3 + D) A := E

39、1 * (E3 + E4) A := E1 * (E5) A := E1 * E6 A := E7 S.产生一个新的中间产生一个新的中间(zhngjin)变量变量T1E3.place=k5产生代码产生代码 k5:=uminus k3名字名字属性属性地址地址ABCDT1T2T3k1K2k3k4k5k6k7符号表第48页/共64页第四十八页，共65页。2021-12-15A := B * (-C + D)的三地址码k5:=uminus k3k6:= k5+ k4k7:= k2* k6k1:= k7名字名字属性属性地址地址ABCDT1T2T3k1K2k3k4k5k6k7符号表（参看(cnkn)p17

40、9的语义子程序）第49页/共64页第四十九页，共65页。2021-12-15P218-6：用7.4.2节的办法(bnf)，把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，-，-，.）TCFC第50页/共64页第五十页，共65页。2021-12-15P218-7100：（j，A，C，102）101：（j，-，-，115）102：（j，B，D，104）103：（

41、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节的办法，把下面的语句翻译成四元(s yun)式序列：while A C and B D do if A=1 then C:=C+1 else while A D do A:=A+2;第51页/共64页第五十一页，共65页。程 序

42、设 计 语 言 Chapter 8. Chapter 11.第52页/共64页第五十二页，共65页。2021-12-15CH8.CH8. CH11. CH11. 1. 什么(shn me)是符号表？符号表有哪些重要作用？ 2. 符号表的表项常包括哪些部分？各描述什么(shn me)？ 3. 有哪些存储分配策略？并叙述何时用何种存储分配策略？ 4. 代码优化的常用措施和优化的三个层次。第53页/共64页第五十三页，共65页。程 序 设 计 语 言 补充(bchng)题第54页/共64页第五十四页，共65页。2021-12-15补充(bchng)题 1. 画出编译程序(bin y chn x)的总

43、体逻辑结构图，简述各部分的主要功能。第55页/共64页第五十五页，共65页。2021-12-15补充(bchng)题 2. 已知文法GZ: Z0U|1V U1Z|1 V0Z|0 请写出此文法描述的只含有个符号的全部句子。 GZ产生的语言是什么？ 该文法在Chomsky文法分类(fn li)中属于几型文法？第56页/共64页第五十六页，共65页。2021-12-15【解】 （1）0101，0110，1010， 1001 （2）分析GZ所推导出的句子的特点：由Z开始(kish)的推导不外乎图1所示的四种情形。 由Z推导出10或01后就终止或进入递归，而Z的每次递归将推导出相同的符号串：10或01。所以GZ产生的语言L(GZ)=x|x(10|01)+ (3) 该文法属于3型文法。 图 1 文法GZ可能的几种推导 Z 0 1 U Z U 0 Z 1 Z 1 V 0 Z Z 1 0 V Z0U|1V U1Z|1V0Z|0第57页/共64页第五十七页，共65页。2021-12-15补充(bchng)题 3. 已知文法和它的LR分析表如下(rxi)，给出串dbdb# 的LR分析过程。 GS：(1) SAdB (2)Aa (3) A (4) Bb (5)BBdb (6)BACTIONACTIONGOTOGOTOa