編譯原理試題及答案(二)ppt課件

1、編譯原理參考答案,程 序 設(shè) 計(jì) 語(yǔ) 言,Chapter 4. 自上而下語(yǔ)法分析,1,CH.4.練習(xí)題1(P81.),1.考慮下面文法G1: Sa|(T) TT，S|S (1) 消去G1的左遞歸。然后對(duì)每個(gè)非終結(jié)符,寫出不帶回溯的遞歸子程序。,解(1) 消左后的文法G1: Sa|(T) TST T ,ST|,2,CH.4.練習(xí)題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 adv

2、ance else error end else error End;,3,CH.4.練習(xí)題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;,4,CH.4.練習(xí)題1(P81.),(2) 經(jīng)改寫后的文法是否是LL(1)的? 給出它的預(yù)測(cè)分析表。 消左后的文法G1 : Sa|(T) TST T ,ST|,(2) 因?yàn)镚1 : 文法不含左遞歸; 對(duì) Sa|(T) FI

3、RST(a)=a, FIRST()=, FIRST( (T) )= ( , 集合互不相交且不含; 對(duì) T,ST| FIRST( ,ST )= , , FIRST()=, 其交集為空。 但FIRST(T)=FIRST( ,ST )FIRST()=，, 然而，F(xiàn)OLLOW(T)= ) FIRST(T)=，, ，兩者 不相交。 所以，G1是LL(1)文法。,5,CH.4.練習(xí)題1(P81.),(2)構(gòu)造G1的預(yù)測(cè)分析表: 對(duì)Sa|(T) 對(duì)TST FIRST(a)=a FIRST(ST)=a,( FIRST()= 對(duì) T,ST| FIRST(T)=( FIRST(,ST)=, 預(yù)測(cè)分析表: FOLL

4、OW(T)=),6,CH4.1.(3) 給出對(duì)符號(hào)串(a，) 的分析過(guò)程,步驟 符號(hào)棧 輸入串 動(dòng)作, 所用產(chǎn)生式 . 0 #S (a,)# 初始；用 S , ( 查表 1 #)T( (a,)# S(T), 展開(kāi)S 2 #)T a,)# 匹配(；用 T , a 查表 3 #)TS a,)# TST , 展開(kāi)T; 用 S ,a 查表 4 #)Ta a,)# S a, 展開(kāi)S 5 #)T ,)# 匹配a; 用T , , 查表 6 #)TS, ,)# T ,ST, 展開(kāi)T 7 #)TS )# 匹配, ；用 S , 查表 8 #)T )# S , 展開(kāi)S 9 #)T )# 匹配 ；用 T , )查表

5、10 #) )# T,展 開(kāi)T 11 # # 匹配 ) 12 # # 分析成功, 結(jié)束分析,7,CH.4.練習(xí)題3(P82.),3.下面文法中, 哪些是LL(1)的, 說(shuō)明理由。 (1) SABc A a| B b|。,解，因?yàn)?FOLLOW(S)=# 文法不含左遞歸; FIRST(S)=a,b,c 對(duì) Aa| 候選式的FIRST集合互不相交; FIRST(A) 但, FOLLOW(A)=b,c FIRST(A)=a, 兩者不相交。 Bb| 其候選式的FIRST集合互不相交; FIRST(B) 但， FOLLOW(B)=c FIRST(B)=b, 兩者也不相交。 所以，文法是LL(1)文法。,

6、8,CH.4.練習(xí)題3(P82.),3.下面文法中, 哪些是LL(1)的, 說(shuō)明理由。 (2) SAb A a|B| B b|。,解(1) 因?yàn)?FOLLOW(S)=# 對(duì) Aa|B| ; FIRST(S)=a,b FIRST(B)=b,與FIRST()=相交; 所以文法不是LL(1)文法。 解(2) 對(duì) Aa| 因?yàn)镕IRST(A)= a,b, ，F(xiàn)OLLOW(A)=b, FOLLOW和FIRST兩者相交。 所以文法不是LL(1)文法。,9,CH.4.練習(xí)題3(P82.),3.下面文法中, 哪些是LL(1)的, 說(shuō)明理由。 (3) SABBA A a| B b|。,解，雖然 FOLLOW(S

7、)=# 文法不含左遞歸; FIRST(S)=a, b, 對(duì) Aa|，其候選式的FIRST集合不相交; 對(duì) Bb|，其候選式的FIRST集合也不相交; 但 對(duì) Aa| （由 Bb|出發(fā)證明也可） FOLLOW(A)= a, b, # , FIRST(A)= a, 兩者相交。 所以，文法不是LL(1)文法。,10,CH.4.練習(xí)題3(P82.),3.下面文法中, 哪些是LL(1)的, 說(shuō)明理由。 (4) SaSe|B BbBe|C CcCe|d。,解， 因?yàn)?文法不含左遞歸; 對(duì) SaSe|B、BbBe|C 和 CcCe|d 各產(chǎn)生式的候選式的FIRST集合均不相交; 即 FIRST(aSe) F

8、IRST(B)= ； FIRST(bBe) FIRST(C)= ； FIRST(cCe) FIRST(d)= ； FIRST(S)= a,b,c,d ，F(xiàn)IRST(B)= b,c,d FIRST(C)= c,d 均不含。 所以，文法是LL(1)文法。,11,編譯原理參考答案,程 序 設(shè) 計(jì) 語(yǔ) 言,Chapter 7. 語(yǔ)義分析和中間代碼產(chǎn)生,12,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

9、 not or （A and B）or（not C or D） 后綴式：A B and C not D or or,13,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),14,P218-4,自下而上分析過(guò)程中把賦值語(yǔ)句 A := B * （-C + D）翻譯成三地址碼的步驟： （參看p179的語(yǔ)義子程序）,15,語(yǔ)法分析翻譯過(guò)程： A := B * (-C + D)

10、 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,產(chǎn)生一個(gè)新的中間變量T1 E3.place=k5 產(chǎn)生代碼 k5:=uminus k3,k1 K2 k3 k4 k5 k6 k7,符號(hào)表,16,A := B * (-C + D)的三地址碼,k5:=uminus k3 k6:= k5+ k4 k7:= k2* k6 k1:= k7,k1 K2 k3 k4 k5 k6

11、k7,符號(hào)表,（參看p179的語(yǔ)義子程序）,17,P218-6：用7.4.2節(jié)的辦法，把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，-，-，.）,18,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，

12、-，-，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節(jié)的辦法，把下面的語(yǔ)句翻譯成四元式序列： while A C and B D do if A=1 then C:=C+1 else while A D do A:=A+2;,19,編譯原理參考答案,程 序 設(shè) 計(jì) 語(yǔ) 言,Chapter 8. Chapter 11.,20,C

13、H8. CH11.,1. 什么是符號(hào)表？符號(hào)表有哪些重要作用？ 2. 符號(hào)表的表項(xiàng)常包括哪些部分？各描述什么？ 3. 有哪些存儲(chǔ)分配策略？并敘述何時(shí)用何種存儲(chǔ)分配策略？ 4. 代碼優(yōu)化的常用措施和優(yōu)化的三個(gè)層次。,21,編譯原理參考答案,程 序 設(shè) 計(jì) 語(yǔ) 言,補(bǔ)充題,22,補(bǔ)充題,1. 畫出編譯程序的總體邏輯結(jié)構(gòu)圖，簡(jiǎn)述各部分的主要功能。,23,補(bǔ)充題,2. 已知文法GZ: Z0U|1V U1Z|1 V0Z|0 請(qǐng)寫出此文法描述的只含有個(gè)符號(hào)的全部句子。 GZ產(chǎn)生的語(yǔ)言是什么？ 該文法在Chomsky文法分類中屬于幾型文法？,24,【解】,（1）0101，0110，1010， 1001 （2

14、）分析GZ所推導(dǎo)出的句子的特點(diǎn)：由Z開(kāi)始的推導(dǎo)不外乎圖1所示的四種情形。 由Z推導(dǎo)出10或01后就終止或進(jìn)入遞歸，而Z的每次遞歸將推導(dǎo)出相同的符號(hào)串：10或01。所以GZ產(chǎn)生的語(yǔ)言L(GZ)=x|x(10|01)+ (3) 該文法屬于3型文法。,Z0U|1V U1Z|1 V0Z|0,25,補(bǔ)充題,3. 已知文法和它的LR分析表如下，給出串dbdb# 的LR分析過(guò)程。 GS：(1) SAdB (2)Aa (3) A (4) Bb (5)BBdb (6)B,LR分析表,26,【解】,串dbdb# 的LR分析過(guò)程如下：,27,補(bǔ)充題,4 . 給定文法和語(yǔ)義動(dòng)作如下： A aB print “0” A c print “1” B Ab print “2”問(wèn)：按照以上的語(yǔ)義子程序，aacbb 經(jīng)翻譯后的輸出結(jié)果是什么？請(qǐng)給出翻譯過(guò)程。,28,aacbb翻譯后的輸出結(jié)果是打印出下面的字符串： 12020,b,B,c,A,A,a,B,A,a,b,A aB print “0”A c print “1”B Ab print “2”,29,翻譯過(guò)程和翻譯結(jié)果,語(yǔ)法分析： aacbb aaAbb (1) aaBb (2) aAb (