编译原理考试习题及答案教学内容.ppt

《编译原理考试习题及答案教学内容.ppt》由会员分享，可在线阅读，更多相关《编译原理考试习题及答案教学内容.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1编译原理考试习题及答案2CH.3.CH.3.练习题练习题7(P64.)7(P64.)n7.7.(1)1(0|1)*101 构造构造DFADFA。解解1:正规式对应的正规式对应的NFA:XY34511011210 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 32022/12/15 (1)正规式正规式 1(0|1)*101DFA:x3,Y,4,23,4,23,5

2、,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,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 32022/12/15 (1)正规式正规式 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

3、I0 I1初初0 1 1 2 3 2 2 3 3 4 3 4 2 5终终5 4 3053411011201001012022/12/155CH.3.CH.3.练习题练习题7(P64.)7(P64.)n7.7.构造下列正规式相应的构造下列正规式相应的DFADFA。(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:2022/12/156n7.7.构造下列正规式相应的构造下列

4、正规式相应的NFANFA。(P64.)(P64.)(2)1(1010*|1(010)*1)*0XY201131010*1(010)*1XY201136451100*7811(010)*2022/12/157n7.7.构造下列正规式相应的构造下列正规式相应的NFANFA。(P64.)(P64.)(2)1(1010*|1(010)*1)*0XY201136451100*7811(010)*XY20113645110078119100102022/12/15XY2011364511007811910010XY201136451100781191001211017.7.(2)1(1010*|1(010

5、)*1)*0的的NFANFA。2022/12/159CH.3.CH.3.练习题练习题14(P64.)14(P64.)n(1)正规式正规式:(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:2022/12/1510CH.3.CH.3.练习题练习题14(P64.)14(P64.)n(1)正规式正规式:(10|0)*(2)NFA:YX1001201001012DFA:构造一个构造一个DFA，它接受，它接受 S0,1上所有满足如下条件上所有满足如下条

6、件的字符串：每个的字符串：每个1都有都有0直直接跟在右边。接跟在右边。10010DFA:(最简最简)2022/12/15程程 序序 设设 计计 语语 言言 Chapter 2.Chapter 2.高级语言及高级语言及其语法描述其语法描述2022/12/1512CH.2.CH.2.练习题练习题6(P36.)6(P36.)n6.6.令文法令文法G6G6为为:N D|ND D 0|1|2|3|4|5|6|7|8|9 N D|ND D 0|1|2|3|4|5|6|7|8|9n(1)G6(1)G6的语言的语言L(G6)L(G6)是什么是什么?n注意注意：集合的写法不正确：集合的写法不正确n解：解：L(G

7、6)=0,1,2,3,4,5,6,7,8,9L(G6)=0,1,2,3,4,5,6,7,8,9+=0=0 9 9数字构成的所有数字串，可以数字构成的所有数字串，可以0 0开头开头 n(2)(2)给出句子给出句子01270127、3434和和568568的最左和最右推导。的最左和最右推导。n注意注意：1)1)步骤，步骤，和和 的区别的区别；2)2)不能写为不能写为n解：解：01270127的最左推导：的最左推导：N NNDNDNDDNDDNDDDNDDDDDDDDDDD 0DDD0DDD01DD01DD012D012D01270127 0127 0127的最右推导：的最右推导：N NNDNDN7

8、N7ND7ND7N27N27ND27ND27 N127N127D127D12701270127+13CH.2.CH.2.练习题练习题8(P36.)8(P36.)n8.8.令文法为令文法为 E T|E+T|E-T E T|E+T|E-T T F|T*F|T/F T F|T*F|T/F F (E)|i F (E)|i (1)给出给出 i+i*i、i*(i+i)的最左推导的最左推导和最右推导。和最右推导。解解：此处仅以：此处仅以 i*(i+i)为例给出答案为例给出答案最左推导最左推导E E T T T*F T*F F*F F*F i*F i*F i*(E)i*(E)i*(E+T)i*(E+T)i*(

9、T+T)i*(T+T)i*(F+T)i*(F+T)i*(i+T)i*(i+T)i*(i+F i*(i+F)i*(i+i)i*(i+i)最右推导最右推导E E T T T*F T*F T*(E)T*(E)T*(E+T)T*(E+T)T*(E+F)T*(E+F)T*(E+i)T*(E+i)T*(T+i)T*(T+i)T*(F+i)T*(F+i)T*(i+i)T*(i+i)F*(i+i)F*(i+i)i*(i+i)i*(i+i)14CH.2.CH.2.练习题练习题8(P36.)8(P36.)n8.8.令文法为令文法为 E T|E+T|E-T E T|E+T|E-T T F|T*F|T/FT F|T*

10、F|T/F F (E)|i F (E)|iEE -TE -TTF F iF iii-i-i i-i-i 的语法树的语法树(2)给出给出 i+i+i、i+i*i和和i-i-i的语法树。的语法树。EE +TE +TTF F iF iii+i+i i+i+i 的语法树的语法树i+i*i i+i*i 的语法树的语法树EE +TTTF F iF ii*n注意注意：树枝和符号均不可随意增减！：树枝和符号均不可随意增减！15CH.2.CH.2.练习题练习题9(P36.)9(P36.)n9.9.证明下面的文法是二义的：证明下面的文法是二义的：S iSeS|iS|i S iSeS|iS|in证明证明:因为存在句

11、子因为存在句子 iiiei iiiei，它对应两棵不同的语法树，它对应两棵不同的语法树,如右图如右图:所以该文法是二义文法。所以该文法是二义文法。n说明说明：按定义只要能给出一：按定义只要能给出一个反例即可，个反例即可，iiieiiiiei不是唯一不是唯一的反例。的反例。S i S i S e SiiiSi S e S i Si2022/12/15程程 序序 设设 计计 语语 言言 Chapter 5.Chapter 5.自下而上自下而上语法分析语法分析2022/12/1517CH.5.CH.5.练习题练习题1(P133.)1(P133.)n1.1.令文法令文法G1G1为：为：EE+T|T T

12、T*F|F F(E)|i EE+T|T TT*F|F F(E)|i 证证明明E+T*FE+T*F是是它它的的一一个个句句型型,指指出出这这个个句句型型的的所所有有短短语、直接短语和句柄。语、直接短语和句柄。n证证明明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*FEE +

13、TT *F语法树语法树2022/12/1518CH.5.CH.5.练习题练习题1(P133.)1(P133.)n1.1.令文法令文法G1G1为：为：EE+T|T TT*F|F F(E)|i EE+T|T TT*F|F F(E)|i 证证明明E+T*FE+T*F是是它它的的一一个个句句型型,指指出出这这个个句句型型的的所所有有短短语、直接短语和句柄。语、直接短语和句柄。n证证明明2:可可构构造造出出E+T*F的的语语法法树树，如如右右图所示图所示，E+T*F是是G1的一个句型。的一个句型。n证明证明3:(也可用归约来证明也可用归约来证明)（概概念念熟熟悉悉后后，短短语语、直直接接短短语语和和句句

14、柄柄可可直直接接列列出出而不用说明）而不用说明）短语短语:E+T*F，T*F 直接短语直接短语:T*F 句柄句柄:T*FEE +TT *F语法树语法树2022/12/1519CH.5.CH.5.练习题练习题2(P133.)2(P133.)n2.2.考虑下面的表格结构文法考虑下面的表格结构文法G2G2：Sa|Sa|(T)TT,S|S|(T)TT,S|S (1)(1)给出给出(a,(a,a)(a,(a,a)的最左和最右推导。的最左和最右推导。n(1)解解:(a,(a,a)的的最左推导：最左推导：S(T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)(a,(S,S)(a,(a,S)(a,

15、(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)2022/12/1520CH.5.CH.5.练习题练习题2(P133.)2(P133.)n2.(2)2.(2)指指出出(a,(a,a)(a,(a,a)的的规规范范归归约约及及每每一一步步的的句句柄柄。根根据据这这个个规规范范归归约约，给给出出“移移进进-归归约约”的的过过程程，并并给给出它的语法树自下而上的构造过程。出它的语法树自下而上的构造过程。n(2)解解:(a,(a,a)的规范归约及每一步的句柄的规范归约及每一步的句柄:(a,(a,a

16、)(S,(a,a)(T,(a,a)(T,(S,a)(T,(T,a)(T,(T,S)(T,(T)(T,S)(T)S.2022/12/1521CH.5.CH.5.练习题练习题2(P133.)2(P133.)n2.(2).2.(2).给出给出(a,(a,a)“(a,(a,a)“移进移进-归约归约”的过程。的过程。n(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)#归

17、约归约 T S a 6#(T,(a,a)#移进移进,7#(T,(a,a)#移进移进(8#(T,(a ,a)#移进移进 a2022/12/1522CH.5.CH.5.练习题练习题2(P133.)2(P133.)n2.(2).2.(2).给出给出(a,(a,a)“(a,(a,a)“移进移进-归约归约”的过程。的过程。n(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 )#移进移进

18、 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,S2022/12/1523CH.5.CH.5.练习题练习题2(P133.)2(P133.)n2.(2).2.(2).给出给出(a,(a,a)“(a,(a,a)“移进移进-归约归约”的过程。的过程。n(2)解解:(a,(a,a)的的“移进移进-归约归约”过程过程:步骤步骤 符号栈符号栈 输入串输入串 动作动作 句柄句柄 17#(T )#归约归约 T T,S (T)18#(T)#移进移进)19#S#归约归约 S (T)

19、20 成功成功,分析结束分析结束,接受输入串接受输入串2022/12/1524CH.5.CH.5.练习题练习题2(P133.)2(P133.)n2.(2).2.(2).给出给出(a,(a,a)(a,(a,a)的语法树自下而上构造过程。的语法树自下而上构造过程。n(2)解解:(a,(a,a)的的语语法法树树自自下下而而上上构构造造过过程程:用序号表示用序号表示S(T )T ,S (T )T ,SSaSaa2022/12/1525CH.5.CH.5.练习题练习题3(P133.)3(P133.)n3.(1)3.(1)计算练习计算练习2 2文法文法G2G2的的FIRSTVTFIRSTVT和和LASTV

20、TLASTVT。Sa|Sa|(T)TT,S|S|(T)TT,S|Sn(1)解解:（执行相应的算法可求得）（执行相应的算法可求得）FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,),2022/12/1526CH.5.CH.5.练习题练习题3(P133.)3(P133.)n3.(2)3.(2)计计算算文文法法G2G2的的优优先先关关系系,G2,G2是是一一个个算算符符优优先先文文法吗法吗?Sa|?Sa|(T)TT,S|S|(T)TT,S|Sn(2)解解:FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)

21、LASTVT(T)=,a,)n逐逐一一考考察察 S(T)和和 TT,S 两两两两相相邻邻的的符符号号，得得到到算算符符优优先先关关系系,如如右右图；图；G2是算符优先文法是算符优先文法。a (),#a (=,#=.2022/12/15273.(4)3.(4)给出输入串给出输入串(a,(a,a)(a,(a,a)的的算符优先分析过程。算符优先分析过程。nSa|Sa|(T)TT,S|S|(T)TT,S|S序号序号符号栈符号栈输入串输入串优先关系优先关系下一步的动作下一步的动作0#(a,(a,a)#(移进移进(1#(a,(a,a)#(a移进移进 a2#(a ,(a,a)#(,归约归约 Sa3#(S ,

22、(a,a)#(,移进移进,4#(S,(a,a)#,(移进移进(5#(S,(a,a)#(a移进移进 a6#(S,(a ,a)#(,归约归约 Sa7#(S,(S ,a)#(,移进移进,8#(S,(S,a)#,(=,#=最左素短语最左素短语.2022/12/1528序号序号符号栈符号栈输入串输入串优先关系优先关系下一步的动作下一步的动作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)#*#归约归

23、约 S(T)16#S#=#接受接受17#S#停停.3.(4)3.(4)给出输入串给出输入串(a,(a,a)(a,(a,a)的的算符优先分析过程。算符优先分析过程。nSa|Sa|(T)TT,S|S|(T)TT,S|S a (),#a (=,#=最左素短语最左素短语.2022/12/1529n5.(1)5.(1)考虑文法考虑文法 SAS|b ASA|a SAS|b ASA|a 列出这个文法的所有列出这个文法的所有LR(0)LR(0)项目。项目。CH.5.CH.5.练习题练习题5(P134.)5(P134.)n解解(1):(1):拓广文法，加入拓广文法，加入 SSSS 拓广文法的拓广文法的LR(0)

24、LR(0)项目有项目有:S.S SS.S.S SS.S.AS SA.SS.AS SA.S SAS.S.b Sb.A.SA SAS.S.b Sb.A.SA AS.A ASA.A.a Aa.AS.A ASA.A.a Aa.2022/12/1530n5.(2)5.(2)构造文法构造文法 SAS|b ASA|a SAS|b ASA|a 的的LR(0)LR(0)项目集规范族及识别活前缀项目集规范族及识别活前缀的的DFADFA。1）拓广文法，加入）拓广文法，加入 SS2）画出）画出 DFA2022/12/15n5.(2)5.(2)构造文法构造文法 SAS|b ASA|a SAS|b ASA|a 的的LR(

25、0)LR(0)项目集规范族及识别活前缀的项目集规范族及识别活前缀的DFADFA。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 S.AS S.b SbaAASbaASabSabASAbaSabA2022/12/1532n5.(3)5.(3)文法文法 SAS|b ASA|a SAS|b ASA|a 是是LR(0)LR(0)文法吗？文法吗

26、？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 S.AS S.b SbaAASbaASabSabASAbaSabA不是不是LR(0)文法文法！因为存在冲突，例因为存在冲突，例如状态如状态1、状态、状态52022/12/15程程 序序 设设 计计 语语 言言 Chapter 4.Chapter 4.自上而下自上而下语法分析语法分析20

27、22/12/1534CH.4.CH.4.练习题练习题1(P81.)1(P81.)n1.考虑下面文法考虑下面文法G1:Sa|(T)TT，S|Sn(1)消去消去G1的左递归。然后对每个非终结符的左递归。然后对每个非终结符,写出写出不带回溯的递归子程序。不带回溯的递归子程序。n解解(1)消左后的文法消左后的文法G1:Sa|(T)TST T,ST|2022/12/1535CH.4.CH.4.练习题练习题1(P81.)1(P81.)n解解(1)不带回溯的递归子程序不带回溯的递归子程序:Sa|(T)Procedure S;Begin if sym=a or sym=then advance else if

28、 sym=(then begin advance;T;if sym=)then advance else error end else error End;36CH.4.CH.4.练习题练习题1(P81.)1(P81.)n解解(1)不带回溯的递归不带回溯的递归子程序子程序:nTST Procedure T;Begin S;T end;n解解(1)不带回溯的递归不带回溯的递归子程序子程序:nT,ST|procedure T;begin if sym=,then begin advance;S;T end End;37CH.4.CH.4.练习题练习题1(P81.)1(P81.)(2)经改写后的文法

29、是否是经改写后的文法是否是LL(1)的的?给出它的预测分析表。给出它的预测分析表。消左后的文法消左后的文法G1:Sa|(T)TST T,ST|(2)因为因为G1:文法不含左递归文法不含左递归;对对 Sa|(T)FIRST(a)=a,FIRST()=,FIRST(T)=(,集合互不相交且不含集合互不相交且不含;对对 T,ST|FIRST(,ST)=,FIRST()=,其交集为空。其交集为空。但但FIRST(T)=FIRST(,ST)FIRST()=，,然而，然而，FOLLOW(T)=)FIRST(T)=，,，两者，两者 不不相交。相交。所以，所以，G1是是LL(1)文法。文法。38CH.4.CH

30、.4.练习题练习题1(P81.)1(P81.)(2)构造构造G1的的预测分析表预测分析表:对对Sa|(T)对对TST FIRST(a)=a FIRST(ST)=a,(FIRST()=对对 T,ST|FIRST(T)=(FIRST(,ST)=,预测分析表预测分析表:FOLLOW(T)=)a (),#SSaSS(T)TTSTTSTTST TTT,ST2022/12/1539CH4.CH4.1.(3)给出对符号串给出对符号串(a，)的分析过的分析过程程步骤步骤 符号栈符号栈 输入串输入串 动作动作,所用产生式所用产生式 .0#S (a,)#初始；初始；用用 S,(查表查表 1#)T(a,)#S(T)

31、,展开展开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#分析成功分析成功,结束分析结束分析40CH.4.CH.4.练习题练习题3(P82.)3(P82.)n3.下面文法中下面文法中,哪些是哪些是LL(1)的的,说明理由。说明理

32、由。n(1)SABc A a|B b|。n解，解，因为因为 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)文法。文法。41CH.4.CH.4.练习题练习题3(P82.)3(P82.)n3.下面文法中下面文法中,

33、哪些是哪些是LL(1)的的,说明理由。说明理由。n(2)SAb A a|B|B b|。n解解(1)因为因为 FOLLOW(S)=#对对 Aa|B|;FIRST(S)=a,b FIRST(B)=b,与与FIRST()=相交相交;所以文法不是所以文法不是LL(1)文法。文法。n解解(2)对对 Aa|因为因为 FIRST(A)=a,b,，FOLLOW(A)=b,FOLLOW和和FIRST两者相交。两者相交。所以文法不是所以文法不是LL(1)文法。文法。42CH.4.CH.4.练习题练习题3(P82.)3(P82.)n3.下面文法中下面文法中,哪些是哪些是LL(1)的的,说明理由。说明理由。n(3)S

34、ABBA A a|B b|。n解，解，虽然虽然 FOLLOW(S)=#文法不含左递归文法不含左递归;FIRST(S)=a,b,对对 Aa|，其候选式的，其候选式的FIRST集合不相交集合不相交;对对 Bb|，其候选式的，其候选式的FIRST集合也不相交集合也不相交;但但 对对 Aa|（由 Bb|出发证明也可）FOLLOW(A)=a,b,#,FIRST(A)=a,两者相交。两者相交。所以，文法不是所以，文法不是LL(1)文法。文法。43CH.4.CH.4.练习题练习题3(P82.)3(P82.)n3.下面文法中下面文法中,哪些是哪些是LL(1)的的,说明理由。说明理由。n(4)SaSe|B Bb

35、Be|C CcCe|d。n解，解，因为因为 文法不含左递归文法不含左递归;对对 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.Chapter 7.语义分析和中语义分析和中间代码产生间代码产生2

36、022/12/1545P217-1na*（-b+c）后缀式：后缀式：ab-c+*na+b*（c+d/e）后缀式：后缀式：abcde/+*+n-a+b*（-c+d）后缀式：后缀式：a-bc-d+*+nnot A or not（C or not D）后缀式：后缀式：A not C D not or not orn（A and B）or（not C or D）后缀式：后缀式：A B and C not D or or2022/12/1546P217-3n-（a+b）*（c+d）-（a+b+c）的四元式序列：的四元式序列：（1）(+，a，b，T1)（2）(-，T1，-，T2)（3）(+，c，d，T3)

37、（4）(*，T2，T3，T4)（5）(+，a，b，T5)（6）(+，T5，c，T6)（7）(-，T4，T6，T7)2022/12/1547P218-4n自下而上分析过程中把赋值语句自下而上分析过程中把赋值语句 A:=B*（-C+D）翻翻译译成成三三地地址址码码的步骤：的步骤：（参看（参看p179的语义子程序）的语义子程序）2022/12/15n语法分析语法分析翻译过程：翻译过程：nA:=B*(-C+D)A:=E1*(-C+D)E1.place=k2 A:=E1*(-E2+D)E2.place=k3 A:=E1*(E3+D)A:=E1*(E3+E4)A:=E1*(E5)A:=E1*E6 A:=E

38、7 S.产生一个新的中间变量产生一个新的中间变量T1E3.place=k5产生代码产生代码 k5:=uminus k3名字名字属性属性地址地址ABCDT1T2T3k1K2k3k4k5k6k7符号表符号表2022/12/1549A:=B*(-C+D)的三地址码的三地址码k5:=uminus k3k6:=k5+k4k7:=k2*k6k1:=k7名字名字属性属性地址地址ABCDT1T2T3k1K2k3k4k5k6k7符号表符号表（参看（参看p179的语义的语义子程序）子程序）2022/12/1550P218-6：用用7.4.2节的办法，把节的办法，把A or（B and not（C or D）翻译成

39、四元式序列翻译成四元式序列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，-，-，.）TCFC2022/12/1551P218-7100：（：（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

40、，-，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;2022/12/15程程 序序 设设 计计 语语 言言 Chapter 8.Chapter 11.2022/12/1553

41、CH8.CH8.CH11.CH11.n1.什么是符号表？符号表有哪些重要作用？什么是符号表？符号表有哪些重要作用？n2.符符号号表表的的表表项项常常包包括括哪哪些些部部分分？各各描描述述什什么？么？n3.有有哪哪些些存存储储分分配配策策略略？并并叙叙述述何何时时用用何何种种存储分配策略？存储分配策略？n4.代码优化的常用措施和优化的三个层次。代码优化的常用措施和优化的三个层次。2022/12/15程程 序序 设设 计计 语语 言言 补充题补充题2022/12/1555补充题补充题n1.画画出出编编译译程程序序的的总总体体逻逻辑辑结结构构图图，简简述述各各部分的主要功能。部分的主要功能。2022

42、/12/1556补充题补充题n2.已知文法已知文法GZ:Z0U|1V U1Z|1 V0Z|0n请写出此文法描述的只含有个符号的全部句子。请写出此文法描述的只含有个符号的全部句子。nGZ产生的语言是什么？产生的语言是什么？n该文法在该文法在Chomsky文法分类中属于几型文法？文法分类中属于几型文法？2022/12/1557【解】【解】n（1）0101，0110，1010，1001n（2）分分析析GZ所所推推导导出出的的句句子子的的特特点点：由由Z开开始始的的推导不外乎图推导不外乎图1所示的四种情形。所示的四种情形。由由Z推推导导出出10或或01后后就就终终止止或或进进入入递递归归，而而Z的的每

43、每次次递递归归将将推推导导出出相相同同的的符符号号串串：10或或01。所所以以GZ产产生的语言生的语言L(GZ)=x|x(10|01)+n(3)该文法属于该文法属于3型文法。型文法。Z0U|1V U1Z|1V0Z|02022/12/1558补充题补充题n3.已已知知文文法法和和它它的的LR分分析析表表如如下下，给给出出串串dbdb#的的LR分析过程。分析过程。GS：(1)SAdB (2)Aa (3)A (4)Bb (5)BBdb (6)BACTIONACTIONGOTOGOTOa ad db b#S SA AB B0 0s3s3r3r31 12 21 1accacc2 2s4s43 3r2r2

44、4 4r6r6s5s5r6r66 65 5r4r4r4r46 6s7s7r1r17 7s8s88 8r5r5r5r5LR分析表分析表 2022/12/1559【解】【解】n串串dbdb#的的LR分析过程如下：分析过程如下：步步骤骤状状态态符号符号输输入串入串下一步下一步的动作的动作0 0 0 0#dbdb#dbdb#r3 归约归约1 10202#A#Adbdb#dbdb#s4 移进移进2 2024024#Ad#Adbdb#bdb#s5 移进移进3 302450245#Adb#Adbdb#db#r4 归约归约4 402460246#AdB#AdBdb#db#s7 移进移进5 5024670246

45、7#AdBd#AdBdb#b#s8 移进移进6 6024678024678#AdBdb#AdBdb#r5 归约归约9 902460246#AdB#AdB#r1 归约归约10100101#S#S#acc1111 停停2022/12/1560补充题补充题n n4.给定文法和语义动作如下：给定文法和语义动作如下：A A aB print“0”aB print“0”A A c print“1”c print“1”B B Ab print“2”Ab print“2”问：按照以上的语义子程序，问：按照以上的语义子程序，aacbb aacbb 经经翻译后的输出结果是什么？请给出翻译翻译后的输出结果是什么？请

46、给出翻译过程。过程。61aacbbaacbb翻翻 译译 后后的的输输出出结结果果是是打打印印出出下下面面的的字符串：字符串：12020bBcAAaBAabA A aB print“0”aB print“0”A A c print“1”c print“1”B B Ab print“2”Ab print“2”62翻译过程和翻译结果翻译过程和翻译结果n语法分析语法分析：naacbbaacbb aaAbb(1)aaAbb(1)aaBb (2)aaBb (2)aAb (3)aAb (3)aB (4)aB (4)A (5)A (5).n翻译过程翻译过程：(1)(1)print“1”(2)(2)print“

47、2”(3)(3)print“0”(4)(4)print“2”(5)(5)print“0”A A A A aB print aB print“0”“0”A A A A c print c print“1”“1”B B Ab print Ab print“2”“2”翻译结果：翻译结果：打印出字符串打印出字符串打印出字符串打印出字符串12020120202022/12/1563补充题补充题n5.课课堂堂上上讲讲过过的的以以及及课课件件中中给给出出的的有有代代表表性性的的例例题题都都要要亲亲自自动动手手独独力力做做一一遍遍。n6.参参阅阅“编编译译原原理理_(V_jx_Summary_精简精简=完全完全)”2022/12/1564此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢