编译原理试题及答案(二).ppt

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

1、程程 序序 设设 计计 语语 言言 Chapter 4.Chapter 4.自上而下自上而下语法分析语法分析2022/12/222CH.4.CH.4.练习题练习题1(1(P81.)P81.)n1.考虑下面文法考虑下面文法G1:Sa|(T)TT，S|Sn(1)消去消去G1的左递归。然后对每个非终结符的左递归。然后对每个非终结符,写出写出不带回溯的递归子程序不带回溯的递归子程序。n解解(1)消左后的文法消左后的文法G1:Sa|(T)TST T,ST|2022/12/223CH.4.CH.4.练习题练习题1 1(P81.)(P81.)n解解(1)不带回溯的递归子程序不带回溯的递归子程序:Sa|(T)

2、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;4CH.4.CH.4.练习题练习题1 1(P81.)(P81.)n解解(1)不带回溯的递归不带回溯的递归子程序子程序:nTST Procedure T;Begin S;T end;n解解(1)不带回溯的递归不带回溯的递归子程序子程序:nT,ST|procedure T;begin if sym=,then begin advance;

3、S;T end End;5CH.4.CH.4.练习题练习题1(1(P81.)P81.)(2)经改写后的文法是否是经改写后的文法是否是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)=)FIR

4、ST(T)=，,，两者，两者 不不相交。相交。所以，所以，G1是是LL(1)文法。文法。6CH.4.CH.4.练习题练习题1(1(P81.)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/227CH4.CH4.1.(3)给出对符号串给出对符号串(a，)的分析过的分析过程程步骤步骤 符号栈符号栈 输入串输入串 动作动作,

5、所用产生式所用产生式 .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#分析成功分析成功,结束分析结束分析8CH.4.CH.4.练习题练习题

6、3(3(P82.)P82.)n3.下面文法中下面文法中,哪些是哪些是LL(1)的的,说明理由。说明理由。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)文法

7、。文法。9CH.4.CH.4.练习题练习题3(3(P82.)P82.)n3.下面文法中下面文法中,哪些是哪些是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)文法。文法。10CH.4.CH.4.练习题练习题3(3(P82.

8、)P82.)n3.下面文法中下面文法中,哪些是哪些是LL(1)的的,说明理由。说明理由。n(3)SABBA 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)文法。文法。11CH.4.CH.4.练习题练习题3(3(P82.)P82.)n3

9、.下面文法中下面文法中,哪些是哪些是LL(1)的的,说明理由。说明理由。n(4)SaSe|B BbBe|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)文法。文法。程程 序序 设设 计计

10、语语 言言 Chapter 7.Chapter 7.语义分析和中语义分析和中间代码产生间代码产生2022/12/2213P217-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/2214P217-3n-（a+b）*（c+d）-（a+b+c）的四元式序

11、列：的四元式序列：（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)2022/12/2215P218-4n自下而上分析过程中把赋值语句自下而上分析过程中把赋值语句 A:=B*（-C+D）翻翻译译成成三三地地址址码码的步骤：的步骤：（参看（参看p179的语义子程序）的语义子程序）2022/12/22n语法分析语法分析翻译过程：翻译过程：nA:=B*(-C+D)A:=E1*(-C+D)E1.place=k2 A:=E1*(-E2+D)E2.place=k3

12、 A:=E1*(E3+D)A:=E1*(E3+E4)A:=E1*(E5)A:=E1*E6 A:=E7 S.产生一个新的中间变量产生一个新的中间变量T1E3.place=k5产生代码产生代码 k5:=uminus k3名字名字属性属性地址地址ABCDT1T2T3k1K2k3k4k5k6k7符号表符号表2022/12/2217A:=B*(-C+D)的三地址码的三地址码k5:=uminus k3k6:=k5+k4k7:=k2*k6k1:=k7名字名字属性属性地址地址ABCDT1T2T3k1K2k3k4k5k6k7符号表符号表（参看（参看p179的语义的语义子程序）子程序）2022/12/2218P2

13、18-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，-，-，.）TCFC2022/12/2219P218-7100：（：（j，A，C，102）101：（：（j，-，-，115）102：（：（j，B，D，104）103：（：（j，-，-，115）104：（：（j=，A，1，

14、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;2022/12/22程程

15、 序序 设设 计计 语语 言言 Chapter 8.Chapter 11.2022/12/2221CH8.CH8.CH11.CH11.n1.什么是符号表？符号表有哪些重要作用？什么是符号表？符号表有哪些重要作用？n2.符符号号表表的的表表项项常常包包括括哪哪些些部部分分？各各描描述述什什么？么？n3.有有哪哪些些存存储储分分配配策策略略？并并叙叙述述何何时时用用何何种种存储分配策略？存储分配策略？n4.代码优化的常用措施和优化的三个层次。代码优化的常用措施和优化的三个层次。2022/12/22程程 序序 设设 计计 语语 言言 补充题补充题2022/12/2223补充题补充题n1.画画出出编编

16、译译程程序序的的总总体体逻逻辑辑结结构构图图，简简述述各各部分的主要功能。部分的主要功能。2022/12/2224补充题补充题n2.已知文法已知文法GZ:Z0U|1V U1Z|1 V0Z|0n请写出此文法描述的只含有个符号的全部句子。请写出此文法描述的只含有个符号的全部句子。nGZ产生的语言是什么？产生的语言是什么？n该文法在该文法在Chomsky文法分类中属于几型文法？文法分类中属于几型文法？2022/12/2225【解解】n（1）0101，0110，1010，1001n（2）分分析析GZ所所推推导导出出的的句句子子的的特特点点：由由Z开开始始的的推导不外乎图推导不外乎图1所示的四种情形。所

17、示的四种情形。由由Z推推导导出出10或或01后后就就终终止止或或进进入入递递归归，而而Z的的每每次次递递归归将将推推导导出出相相同同的的符符号号串串：10或或01。所所以以GZ产产生的语言生的语言L(GZ)=x|x(10|01)+n(3)该文法属于该文法属于3型文法。型文法。Z0U|1V U1Z|1V0Z|02022/12/2226补充题补充题n3.已已知知文文法法和和它它的的LR分分析析表表如如下下，给给出出串串dbdb#的的LR分析过程。分析过程。GS：(1)SAdB (2)Aa (3)A (4)Bb (5)BBdb (6)BACTIONACTIONGOTOGOTOa ad db b#S

18、SA AB B0 0s3s3r3r31 12 21 1accacc2 2s4s43 3r2r24 4r6r6s5s5r6r66 65 5r4r4r4r46 6s7s7r1r17 7s8s88 8r5r5r5r5LR分析表分析表 2022/12/2227【解解】n串串dbdb#的的LR分析过程如下：分析过程如下：步步骤骤状状态态符号符号输输入串入串下一步下一步的动作的动作0 0 0 0#dbdbdbdb#r3 归约归约1 10202#A#Adbdbdbdb#s4 移进移进2 2024024#Ad#Adbdbbdb#s5 移进移进3 302450245#AdbAdbdb#db#r4 归约归约4 4

19、02460246#AdBAdBdb#db#s7 移进移进5 50246702467#AdBdAdBdb#b#s8 移进移进6 6024678024678#AdBdbAdBdb#r5 归约归约9 902460246#AdBAdB#r1 归约归约10100101#S#S#acc1111 停停2022/12/2228补充题补充题n n4.给定文法和语义动作如下：给定文法和语义动作如下：A A aBaB print“0”print“0”A A c print“1”c print“1”B B AbAb print“2”print“2”问：按照以上的语义子程序，问：按照以上的语义子程序，aacbbaacb

20、b 经经翻译后的输出结果是什么？请给出翻译翻译后的输出结果是什么？请给出翻译过程。过程。29aacbbaacbb翻翻 译译 后后的的输输出出结结果果是是打打印印出出下下面面的的字符串：字符串：12020bBcAAaBAabA A aBaB print“0”print“0”A A c print“1”c print“1”B B AbAb print“2”print“2”30翻译过程和翻译结果翻译过程和翻译结果n语法分析语法分析：naacbbaacbb aaAbbaaAbb(1)(1)aaBbaaBb (2)(2)aAbaAb (3)(3)aBaB (4)(4)A (5)A (5).n翻译过程翻译

21、过程：(1)(1)print“1”(2)(2)print“2”(3)(3)print“0”(4)(4)print“2”(5)(5)print“0”A A A A aBaB print print“0”“0”A A A A c print c print“1”“1”B B AbAb print print“2”“2”翻译结果：翻译结果：打印出字符串打印出字符串打印出字符串打印出字符串12020120202022/12/2231补充题补充题n5.课课堂堂上上讲讲过过的的以以及及课课件件中中给给出出的的有有代代表表性性的的例例题题都都要要亲亲自自动动手手独独力力做做一一遍遍。n6.参参阅阅“编编译译原原理理_(V_jx_Summary_精简精简=完全完全)”2022/12/22