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

1、2021-11-30CH.4.CH.4.练习题1(1(P81.)P81.) 1.考虑下面(xi mian)文法G1: Sa|(T) TT，S|S (1) 消去G1的左递归。然后对每个非终结符,写出不带回溯的递归子程序。n解解(1) 消左后的文法消左后的文法(wnf)G1: n Sa|(T)n TSTn T ,ST|第1页/共31页第一页，共32页。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=

2、( thenn begin advance;n T;n if sym=) then advancen else errorn endn else errorn End;第2页/共31页第二页，共32页。CH.4.CH.4.练习题1 1(P81.)(P81.)n解(1) 不带回溯(hu s)的递归子程序: 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;第3页

3、/共31页第三页，共32页。CH.4.CH.4.练习题1(1(P81.)P81.)(2) 经改写(gixi)后的文法是否是LL(1)的? 给出它的预测分析表。消左后的文法G1 : Sa|(T) TST T ,ST|(2) 因为G1 : 文法不含左递归; 对 Sa|(T) FIRST(a)=a, FIRST()=, FIRST( (T) )= ( , 集合互不相交(xingjio)且不含; 对 T,ST| FIRST( ,ST )= , , FIRST()=, 其交集为空。 但FIRST(T)=FIRST( ,ST )FIRST()=，, 然而，FOLLOW(T)= ) FIRST(T)=，,

4、，两者 不相交(xingjio)。 所以，G1是LL(1)文法。 第4页/共31页第四页，共32页。2021-11-30CH.4.CH.4.练习题1(1(P81.)P81.)(2)构造G1的预测(yc)分析表: 对Sa|(T) 对TST FIRST(a)=a FIRST(ST)=a,( FIRST()= 对 T,ST| FIRST(T)=( FIRST(,ST)=,预测(yc)分析表: FOLLOW(T)=) a ( ) , # SSaSS(T) TTSTTSTTST TTT ,ST第5页/共31页第五页，共32页。CH4.1.(3) CH4.1.(3) 给出对符号串(a(a，) ) 的分析(

5、fnx)(fnx)过程步骤 符号栈 输入串 动作, 所用(su yn)产生式 . 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

6、# # 匹配 ) 12 # # 分析成功, 结束分析第6页/共31页第六页，共32页。CH.4.CH.4.练习题3(3(P82.)P82.) 3.下面文法中, 哪些(nxi)是LL(1)的, 说明理由。 (1) SABc A a| B b|。n解，因为 FOLLOW(S)=#n 文法不含左递归; FIRST(S)=a,b,c n 对 Aa|n 候选式的FIRST集合互不相交(xingjio); FIRST(A) n 但, FOLLOW(A)=b,c FIRST(A)=a, 两者不相交(xingjio)。n Bb|n 其候选式的FIRST集合互不相交(xingjio); FIRST(B)n 但，

7、 FOLLOW(B)=c FIRST(B)=b, 两者也不相交(xingjio)。n n所以，文法是LL(1)文法。第7页/共31页第七页，共32页。CH.4.CH.4.练习题3(3(P82.)P82.) 3.下面文法中, 哪些(nxi)是LL(1)的, 说明理由。 (2) SAb A a|B| B b|。n解(1) 因为 FOLLOW(S)=#n 对 Aa|B| ; FIRST(S)=a,b n FIRST(B)=b,与FIRST()=相交;n所以(suy)文法不是LL(1)文法。n解(2) 对 Aa|n 因为FIRST(A)= a,b, ，FOLLOW(A)=b, n FOLLOW和FIR

8、ST两者相交。n 所以(suy)文法不是LL(1)文法。第8页/共31页第八页，共32页。CH.4.CH.4.练习题3(3(P82.)P82.) 3.下面文法中, 哪些是LL(1)的, 说明(shumng)理由。 (3) SABBA A a| B b|。n解，虽然 FOLLOW(S)=#n 文法(wnf)不含左递归; FIRST(S)=a, b, n 对 Aa|，其候选式的FIRST集合不相交;n 对 Bb|，其候选式的FIRST集合也不相交;n 但 对 Aa| （由 Bb|出发证明也可）n FOLLOW(A)= a, b, # , FIRST(A)= a, n 两者相交。n 所以，文法(wn

9、f)不是LL(1)文法(wnf)。第9页/共31页第九页，共32页。CH.4.CH.4.练习题3(3(P82.)P82.) 3.下面文法中, 哪些(nxi)是LL(1)的, 说明理由。 (4) SaSe|B BbBe|C CcCe|d。n解， 因为(yn wi) 文法不含左递归; n 对 SaSe|B、BbBe|C 和 CcCe|dn 各产生式的候选式的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

10、 n FIRST(C)= c,d 均不含。n 所以，文法是LL(1)文法。第10页/共31页第十页，共32页。程 序 设 计 语 言 Chapter 7. Chapter 7. 语义分析语义分析(fnx)(fnx)和中间代码产生和中间代码产生第11页/共31页第十一页，共32页。2021-11-30P217-1 a*（-b+c） 后缀(huzhu)式：ab-c+* 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

11、or not or （A and B）or（not C or D） 后缀(huzhu)式：A B and C not D or or第12页/共31页第十二页，共32页。2021-11-30P217-3 -（a+b）*（c+d）-（a+b+c） 的四元(s yun)式序列： （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)第13页/共31页第十三页，共32页。2021-11-30P218-4自下而上分析(fnx)过程中把赋值语句 A :=

12、 B * （-C + D）翻译成三地址码的步骤： （参看p179的语义子程序）第14页/共31页第十四页，共32页。 语法分析翻译(fny)过程： A := 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 := E7 S.产生一个新的中间产生一个新的中间(zhngjin)变量变量T1E3.place=k5产生代码产生代码 k5:=uminus k3名字名字

13、属性属性地址地址ABCDT1T2T3k1K2k3k4k5k6k7符号表第15页/共31页第十五页，共32页。2021-11-30A := B * (-C + D)的三地址码k5:=uminus k3k6:= k5+ k4k7:= k2* k6k1:= k7名字名字属性属性地址地址ABCDT1T2T3k1K2k3k4k5k6k7符号表（参看(cnkn)p179的语义子程序）第16页/共31页第十六页，共32页。2021-11-30P218-6：用节的办法，把A or （B and not（C or D）翻译成四元(s yun)式序列100：（jnz，A，-，0）101：（j，-，-，102）10

14、2：（jnz，B，-，104）103：（j，-，-，0）104：（jnz，C，-，.）105：（j，-，-，106）106：（jnz，D，-，.）107：（j，-，-，.）TCFC第17页/共31页第十七页，共32页。2021-11-30P218-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，-，C）108：（j，-，-，100）109：（j，A，D，111）110：（j，-，-，100）111：（+，A，2

15、，T2）112：（:=，T2，-，A）113：（j，-，-，109）114：（j，-，-，100）115：用节的办法(bnf)，把下面的语句翻译成四元式序列：while A C and B D do if A=1 then C:=C+1 else while A D do A:=A+2;第18页/共31页第十八页，共32页。程 序 设 计 语 言 Chapter 8. Chapter 11.第19页/共31页第十九页，共32页。2021-11-30CH8.CH8. CH11. CH11. 1. 什么是符号表？符号表有哪些重要作用？ 2. 符号表的表项常包括哪些部分？各描述什么？ 3. 有哪些存

16、储分配(fnpi)策略？并叙述何时用何种存储分配(fnpi)策略？ 4. 代码优化的常用措施和优化的三个层次。第20页/共31页第二十页，共32页。程 序 设 计 语 言 补充补充(bchng)(bchng)题题第21页/共31页第二十一页，共32页。2021-11-30补充(bchng)题 1. 画出编译程序的总体(zngt)逻辑结构图，简述各部分的主要功能。第22页/共31页第二十二页，共32页。2021-11-30补充(bchng)题 2. 已知文法GZ: Z0U|1V U1Z|1 V0Z|0 请写出此文法描述的只含有个符号的全部句子。 GZ产生(chnshng)的语言是什么？ 该文法在

17、Chomsky文法分类中属于几型文法？第23页/共31页第二十三页，共32页。2021-11-30【解】 （1）0101，0110，1010， 1001 （2）分析GZ所推导出的句子的特点：由Z开始的推导不外乎图1所示的四种情形。 由Z推导出10或01后就终止或进入递归，而Z的每次递归将推导出相同的符号串：10或01。所以(suy)GZ产生的语言L(GZ)=x|x(10|01)+ (3) 该文法属于3型文法。 图 1文 法G Z 可 能 的 几 种 推 导 Z 0 1 U Z U 0 Z 1 Z 1 V 0 Z Z 1 0 V Z0U|1V U1Z|1V0Z|0第24页/共31页第二十四页，共

18、32页。2021-11-30补充(bchng)题 3. 已知文法(wnf)和它的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 3r2r24 4r6r6s5s5r6r66 65 5r4r4r4r46 6s7s7r1r17 7s8s88 8r5r5r5r5LR分析(fnx)表 第25页/共31页第二十五页，共32页。2021-11-30【解】 串dbdb#

19、的LR分析(fnx)过程如下： 步骤步骤状态状态符号符号输入串输入串下一步下一步的动作的动作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 50246702467#AdBd#AdBdb#b# s8 移进移进6 6024678024678#AdBdb#AdBdb# # r5 归约归约9 902460246#AdB#AdB# # r1 归约归约10100101#S#S# # acc1111 停停第26页/共31页第二十六页，共32页。补充补充(bchng)题题第27页/共31页第二十七页，共32页。aacbb翻译后的输出(shch)结果是打印出下面的字符串：12020 aB print “0” aB print “0” c print “1” c print “1”B B Ab print “2” Ab print “2”第28页/共31页第二十八页，共32页。2021-11-30翻译过程翻译过程(guchng)(guchng)和翻译结果和翻译结果语法分析：aacbb aaA