編譯原理考試習(xí)題及答案實(shí)用教案

1、2021-12-15CH.3.CH.3.練習(xí)題8(8(P64.)P64.) 8. 給出下面的正規(guī)表達(dá)式。 (1) 以01結(jié)尾的二進(jìn)制數(shù)串; 正規(guī)式 (0|1)*01 (2) 能被5整除的十進(jìn)制整數(shù)(zhngsh); 允許任意0開(kāi)頭： (0|1|2|3|4|5|6|7|8|9)*(0|5) 不允許0開(kāi)頭（0本身除外）：(0|5)|(1|2|3|9)(0|1|2|3|9)*(0|5)第1頁(yè)/共64頁(yè)第一頁(yè)，共65頁(yè)。2021-12-15CH.3.CH.3.練習(xí)題7(7(P64.)P64.) 7. (1) 1(0|1)*101 構(gòu)造DFA。 解1: 正規(guī)(zhnggu)式對(duì)應(yīng)的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頁(yè)/共64頁(yè)第二頁(yè)，共65頁(yè)。 (1) 正規(guī)(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頁(yè)/共64頁(yè)第三頁(yè)，共65頁(yè)。 (1) 正規(guī)(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頁(yè)/共64頁(yè)第四頁(yè)，共65

4、頁(yè)。2021-12-15CH.3.CH.3.練習(xí)題7(7(P64.)P64.) 7. 構(gòu)造下列(xili)正規(guī)式相應(yīng)的DFA。 (1) 1(0|1)*101 解2: 正規(guī)式對(duì)應(yīng)的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頁(yè)/共64頁(yè)第五頁(yè)，共65頁(yè)。2021-12-15 7. 構(gòu)造(guzo)下列正規(guī)式相應(yīng)的NFA。(P64.) (2) 1(1010*|1 (010)*1)*0XY201131010*1 (010)*

5、1XY201136451100*7811(010)*第6頁(yè)/共64頁(yè)第六頁(yè)，共65頁(yè)。2021-12-15 7. 構(gòu)造下列(xili)正規(guī)式相應(yīng)的NFA。(P64.) (2) 1(1010*|1 (010)*1)*0XY201136451100*7811(010)*XY2011364511007811910010第7頁(yè)/共64頁(yè)第七頁(yè)，共65頁(yè)。XY2011364511007811910010XY201136451100781191001211017. (2) 1(1010*|1 (010)*1)*0的NFA。第8頁(yè)/共64頁(yè)第八頁(yè)，共65頁(yè)。2021-12-15CH.3.CH.3.練習(xí)題14

6、(14(P64.)P64.) (1) 正規(guī)(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頁(yè)/共64頁(yè)第九頁(yè)，共65頁(yè)。2021-12-15CH.3.CH.3.練習(xí)題14(14(P64.)P64.) (1) 正規(guī)(zhnggu)式: (10|0)* (2) NFA:YX1001201001012DFA:構(gòu)造一個(gè)DFA，它接受(jishu) S0,1上所有滿(mǎn)足如下條件的字符串：每個(gè)1都有0直接跟在右邊。10010DF

7、A:(最簡(jiǎn))第10頁(yè)/共64頁(yè)第十頁(yè)，共65頁(yè)。程 序 設(shè) 計(jì) 語(yǔ) 言 Chapter 2.高級(jí)語(yǔ)言及其語(yǔ)法(yf)描述第11頁(yè)/共64頁(yè)第十一頁(yè)，共65頁(yè)。CH.2.CH.2.練習(xí)題6(6(P36.)P36.) 6.令文法G6為: N D|ND D 0|1|2|3|4|5|6|7|8|9 (1) G6的語(yǔ)言L(G6)是什么? 注意：集合(jh)的寫(xiě)法不正確 解：L(G6)=0,1,2,3,4,5,6,7,8,9+ =09數(shù)字構(gòu)成的所有數(shù)字串，可以0開(kāi)頭 (2) 給出句子0127、34和568的最左和最右推導(dǎo)。 注意：1)步驟，和 的區(qū)別；2) 不能寫(xiě)為 解：0127的最左推導(dǎo)：NNDNDDN

8、DDDDDDD 0DDD01DD012D0127 0127的最右推導(dǎo)：NNDN7ND7N27ND27 N127D1270127+第12頁(yè)/共64頁(yè)第十二頁(yè)，共65頁(yè)。CH.2.CH.2.練習(xí)題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)的最左推導(dǎo)(tudo)和最右推導(dǎo)(tudo)。解：此處僅以 i*(i+i) 為例給出答案(d n)最左推導(dǎo)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) 最右推導(dǎo)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頁(yè)/共64頁(yè)第十三頁(yè)，共65頁(yè)。CH.2.CH.2.練習(xí)題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 的語(yǔ)法(yf)(yf)樹(shù)(2) 給出 i+i+i、i+i*i和i-i-i的語(yǔ)法(yf)樹(shù)。EE + TE + TTF F iF iii+i+i i+i+i 的語(yǔ)法樹(shù)i+ii+i* *i i 的語(yǔ)法樹(shù)EE + TTTF F iF ii*n注意：樹(shù)枝和符號(hào)均不可隨意增減！第14頁(yè)/共64頁(yè)第十四頁(yè)，共65頁(yè)。2021-12-15CH.2.CH.2.練習(xí)題9(9(P36.)P36.) 9. 證明下面的文法是二義的： S iSeS|iS

11、|i 證明: 因?yàn)榇嬖诰渥?iiiei，它對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù),如右圖: 所以該文法是二義文法。 說(shuō)明：按定義只要(zhyo)能給出一個(gè)反例即可，iiiei不是唯一的反例。S i S i S e SiiiSi S e S i Si第15頁(yè)/共64頁(yè)第十五頁(yè)，共65頁(yè)。程 序 設(shè) 計(jì) 語(yǔ) 言 Chapter 5.自下而上(z xi r shn)語(yǔ)法分析第16頁(yè)/共64頁(yè)第十六頁(yè)，共65頁(yè)。2021-12-15CH.5.CH.5.練習(xí)題1(1(P133.)P133.) 1.令文法G1為：EE+T|T TT*F|F F(E)|i 證明E+T*F是它的一個(gè)句型,指出這個(gè)(zh ge)句型的所有短語(yǔ)、直

12、接短語(yǔ)和句柄。n證明證明1: 存在從開(kāi)始符號(hào)存在從開(kāi)始符號(hào)E出發(fā)到出發(fā)到E+T*F的的推導(dǎo)：推導(dǎo)： E E+T E+T*F n E+T*F是是G1的一個(gè)句型。的一個(gè)句型。n短語(yǔ)短語(yǔ)(duny): E+T*F是句型相對(duì)于非終結(jié)符是句型相對(duì)于非終結(jié)符E的短語(yǔ)的短語(yǔ)(duny); T*F是句型相對(duì)于非終結(jié)是句型相對(duì)于非終結(jié)符符T的短語(yǔ)的短語(yǔ)(duny)。n直接短語(yǔ)直接短語(yǔ)(duny): T*F是句型相對(duì)于規(guī)則是句型相對(duì)于規(guī)則TT*F的直接短語(yǔ)的直接短語(yǔ)(duny)n句柄句柄: T*FEE + TT * F語(yǔ)法樹(shù)第17頁(yè)/共64頁(yè)第十七頁(yè)，共65頁(yè)。2021-12-15CH.5.CH.5.練習(xí)題1(1

13、(P133.)P133.) 1.令文法G1為：EE+T|T TT*F|F F(E)|i 證明E+T*F是它的一個(gè)句型,指出這個(gè)句型的所有(suyu)短語(yǔ)、直接短語(yǔ)和句柄。n證明證明2: 可構(gòu)造可構(gòu)造(guzo)出出E+T*F的語(yǔ)法樹(shù)，的語(yǔ)法樹(shù)，如右圖所示，如右圖所示， E+T*F是是G1的一個(gè)句型。的一個(gè)句型。n證明證明3: (也可用歸約來(lái)證明也可用歸約來(lái)證明)n（概念熟悉后，短語(yǔ)、直接短語(yǔ)和句柄可直（概念熟悉后，短語(yǔ)、直接短語(yǔ)和句柄可直接列出而不用說(shuō)明）接列出而不用說(shuō)明）n 短語(yǔ)短語(yǔ): E+T*F，T*Fn 直接短語(yǔ)直接短語(yǔ): T*Fn 句柄句柄: T*FEE + TT * F語(yǔ)法樹(shù)第18頁(yè)

14、/共64頁(yè)第十八頁(yè)，共65頁(yè)。2021-12-15CH.5.CH.5.練習(xí)題2(2(P133.)P133.) 2.考慮下面的表格結(jié)構(gòu)文法(wnf)G2： Sa|(T) TT,S|S (1)給出(a,(a,a)的最左和最右推導(dǎo)。 n(1) 解解: (a,(a,a)的的n最左推導(dǎo)最左推導(dǎo)(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最右推導(dǎo)最右推導(dǎo)(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頁(yè)/共64頁(yè)第十九頁(yè)，共65頁(yè)。2021-12-15CH.5.CH.5.練習(xí)題2(2(P133.)P133.) 2.(2)指出(a,(a,a)的規(guī)范歸約及每一步的句柄。根據(jù)這個(gè)規(guī)范歸約，給出“移進(jìn)-歸約”的過(guò)程(guchng)，并給出它的語(yǔ)法樹(shù)自下而上的構(gòu)造過(guò)程(guchng)。n(2) 解解: (a,(a,a)的規(guī)范歸約及每一步的句柄的規(guī)范歸約及每一步的句柄: ( 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頁(yè)/共64頁(yè)第二十頁(yè)，共65

16、頁(yè)。2021-12-15CH.5.CH.5.練習(xí)題2(2(P133.)P133.) 2.(2).給出(a,(a,a)“移進(jìn)-歸約”的過(guò)程(guchng)。n(2) 解解: (a,(a,a)的的“移進(jìn)移進(jìn)-歸約歸約”過(guò)程過(guò)程(guchng):n步驟步驟 符號(hào)棧符號(hào)棧 輸入串輸入串 動(dòng)作動(dòng)作 句柄句柄n 1 # ( a ,(a,a)# an 2 #( a ,(a,a)# 移進(jìn)移進(jìn) (n 3 #( a ,(a,a)# 移進(jìn)移進(jìn) an 4 #( S ,(a,a)# 歸約歸約 S a Sn 5 #( T ,( a ,a)# 歸約歸約 T S an 6 #( T , ( a ,a)# 移進(jìn)移進(jìn) ,n 7

17、#(T,( a ,a)# 移進(jìn)移進(jìn) (n 8 #(T,( a ,a)# 移進(jìn)移進(jìn) a第21頁(yè)/共64頁(yè)第二十一頁(yè)，共65頁(yè)。2021-12-15CH.5.CH.5.練習(xí)題2(2(P133.)P133.) 2.(2).給出(a,(a,a)“移進(jìn)-歸約”的過(guò)程(guchng)。n(2) 解解: (a,(a,a)的的“移進(jìn)移進(jìn)-歸約歸約”過(guò)程過(guò)程:n步驟步驟 符號(hào)符號(hào)(fho)棧棧 輸入串輸入串 動(dòng)作動(dòng)作 句柄句柄n 9 #(T,( S ,a)# 歸約歸約 S a Sn 10 #(T,(T , a )# 歸約歸約 T S an 11 #(T,(T, a )# 移進(jìn)移進(jìn) ,n 12 #(T,(T, a

18、 )# 移進(jìn)移進(jìn) an 13 #(T,( T,S )# 歸約歸約 S a T,Sn 14 #(T, (T ) )# 歸約歸約 T T,S (T)n 15 #(T, (T) )# 移進(jìn)移進(jìn) )n 16 #( T, S )# 歸約歸約 S (T) T,S第22頁(yè)/共64頁(yè)第二十二頁(yè)，共65頁(yè)。2021-12-15CH.5.CH.5.練習(xí)題2(2(P133.)P133.) 2.(2).給出(a,(a,a)“移進(jìn)-歸約”的過(guò)程(guchng)。n(2) 解解: (a,(a,a)的的“移進(jìn)移進(jìn)-歸約歸約”過(guò)程過(guò)程:n步驟步驟 符號(hào)棧符號(hào)棧 輸入輸入(shr)串串 動(dòng)作動(dòng)作 句柄句柄 n 17 # (T

19、) # 歸約歸約 T T,S (T)n 18 # (T) # 移進(jìn)移進(jìn) )n 19 # S # 歸約歸約 S (T)n 20 成功成功,分析結(jié)束分析結(jié)束,接受輸入接受輸入(shr)串串第23頁(yè)/共64頁(yè)第二十三頁(yè)，共65頁(yè)。2021-12-15CH.5.CH.5.練習(xí)題2(2(P133.)P133.) 2.(2).給出(a,(a,a)的語(yǔ)法(yf)樹(shù)自下而上構(gòu)造過(guò)程。n(2) 解解:n (a,(a,a)的語(yǔ)法的語(yǔ)法樹(shù)自下而上構(gòu)造樹(shù)自下而上構(gòu)造(guzo)過(guò)程過(guò)程: 用用序號(hào)表示序號(hào)表示S( T ) T , S ( T ) T , SSaSaa第24頁(yè)/共64頁(yè)第二十四頁(yè)，共65頁(yè)。2021-1

20、2-15CH.5.CH.5.練習(xí)題3(3(P133.)P133.) 3.(1) 計(jì)算(j sun)練習(xí)2文法G2的FIRSTVT和LASTVT。 Sa|(T) TT,S|Sn(1) 解解: （執(zhí)行相應(yīng)（執(zhí)行相應(yīng)(xingyng)的算的算法可求得）法可求得）n FIRSTVT(S)= a, , ( n FIRSTVT(T)= , a, , ( n LASTVT(S)= a, , ) n LASTVT(T)= , , a, , ) ,第25頁(yè)/共64頁(yè)第二十五頁(yè)，共65頁(yè)。2021-12-15CH.5.CH.5.練習(xí)題3(3(P133.)P133.) 3.(2)計(jì)算(j sun)文法G2的優(yōu)先關(guān)系

21、,G2是一個(gè)算符優(yōu)先文法嗎? 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)的符號(hào)，得到算符優(yōu)先關(guān)系, 如右圖；nG2是算符優(yōu)先文法 。 a ( ) ,# a ( = , #=.第26頁(yè)/共64頁(yè)第二十六頁(yè)，共65頁(yè)。2021-12-153.(4)3.(4)給出輸入串給出輸入串(a,(a,a)(a,(a,a)的算符優(yōu)先分析的算符優(yōu)先分析(fnx)(

22、fnx)過(guò)過(guò)程。程。 Sa|(T) TT,S|S序號(hào)序號(hào)符號(hào)棧符號(hào)棧輸入串輸入串優(yōu)先關(guān)系優(yōu)先關(guān)系下一步的動(dòng)作下一步的動(dòng)作0#(a,(a,a)#(移進(jìn)移進(jìn) (1#( a,(a,a)#(a移進(jìn)移進(jìn) a2#(a ,(a,a)#(,歸約歸約 Sa3#(S ,(a,a)#(,移進(jìn)移進(jìn) ,4#(S, (a,a)#,(移進(jìn)移進(jìn) (5#(S,( a,a)#(a移進(jìn)移進(jìn) a6#(S,(a ,a)#(,歸約歸約 Sa7#(S,(S ,a)#(,移進(jìn)移進(jìn) ,8#(S,(S, a)#, ( = , #=最左素短語(yǔ)(duny).第27頁(yè)/共64頁(yè)第二十七頁(yè)，共65頁(yè)。2021-12-15序號(hào)序號(hào)符號(hào)棧符號(hào)棧輸入串輸入串

23、優(yōu)先關(guān)系優(yōu)先關(guān)系下一步的動(dòng)作下一步的動(dòng)作9#(S,(S,a )#,)歸約歸約 Sa10#(S,(S,S )#()歸約歸約 TS,S11#(S,(T )#(=)移進(jìn)移進(jìn) )12#(S,(T) )#,)歸約歸約 S(T)13#(S,S )#()歸約歸約 TS,S14#(T )#(=)移進(jìn)移進(jìn) )15#(T) #*#歸約歸約 S(T)16#S #=#接受接受17#S #停停.3.(4)3.(4)給出輸入串給出輸入串(a,(a,a)(a,(a,a)的算符優(yōu)先的算符優(yōu)先(yuxin)(yuxin)分析過(guò)分析過(guò)程。程。 Sa|(T) TT,S|S a ( ) ,# a ( = , #=最左素短語(yǔ)(duny

24、).第28頁(yè)/共64頁(yè)第二十八頁(yè)，共65頁(yè)。2021-12-15 5.(1) 考慮文法 SAS|b ASA|a 列出這個(gè)(zh ge)文法的所有LR(0)項(xiàng)目。 CH.5.CH.5.練習(xí)題5(5(P134.)P134.)n解(1): (1): 拓廣文法，加入(jir) S(jir) SSSn 拓廣文法的LR(0)LR(0)項(xiàng)目有: :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頁(yè)/共64頁(yè)第二十九頁(yè)，共65頁(yè)。

25、2021-12-155.(2) 構(gòu)造文法 SAS|b ASA|a 的LR(0)項(xiàng)目集規(guī)范族及識(shí)別(shbi)活前綴的DFA。 1）拓廣文法(wnf)，加入 SS2）畫(huà)出 DFA第30頁(yè)/共64頁(yè)第三十頁(yè)，共65頁(yè)。 5.(2) 構(gòu)造文法 SAS|b ASA|a 的LR(0)項(xiàng)目集規(guī)范(gufn)族及識(shí)別活前綴的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頁(yè)/共64頁(yè)第三十一頁(yè)，共65頁(yè)。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)文法！因?yàn)榇嬖?cnzi)沖突，例如狀態(tài)1、狀態(tài)5第32頁(yè)/共64頁(yè)第三十二頁(yè)，共65頁(yè)。程 序 設(shè) 計(jì) 語(yǔ) 言 Chapter 4. 自上而下(z shn r xi)語(yǔ)法分析第33頁(yè)/共64頁(yè)第三十三頁(yè)，共65頁(yè)。2021-12-15CH.4.CH.4.練習(xí)題1(1(P81.)P81.) 1.考慮下面文法G1: Sa|(T) TT，S|S (1) 消去G1的左遞歸。然后(rnhu)對(duì)每個(gè)非終結(jié)符,寫(xiě)出不帶回溯的遞歸子程序。n解解(1) 消左后的文法消左后的文法(wnf)G1: n Sa|(T)n TSTn T

28、,ST|第34頁(yè)/共64頁(yè)第三十四頁(yè)，共65頁(yè)。CH.4.CH.4.練習(xí)題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頁(yè)/共64頁(yè)第三十五頁(yè)，共65頁(yè)。CH.4.CH.4.練習(xí)題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頁(yè)/共64頁(yè)第三十六頁(yè)，共65頁(yè)。CH.4.CH.4.練習(xí)題1(1(P81.)P81.)(2) 經(jīng)改寫(xiě)(gixi)后的文法是否是LL(1)的? 給出它的預(yù)測(cè)分析表。消左后的文法G1 : Sa|(T) TST T ,ST|(2) 因?yàn)镚1 : 文法不含左遞歸; 對(duì) Sa|(T) FIRST(a)=

30、a, FIRST()=, FIRST( (T) )= ( , 集合(jh)互不相交且不含; 對(duì) T,ST| FIRST( ,ST )= , , FIRST()=, 其交集為空。 但FIRST(T)=FIRST( ,ST )FIRST()=，, 然而，F(xiàn)OLLOW(T)= ) FIRST(T)=，, ，兩者 不相交。 所以，G1是LL(1)文法。 第37頁(yè)/共64頁(yè)第三十七頁(yè)，共65頁(yè)。2021-12-15CH.4.CH.4.練習(xí)題1(1(P81.)P81.)(2)構(gòu)造G1的預(yù)測(cè)(yc)分析表: 對(duì)Sa|(T) 對(duì)TST FIRST(a)=a FIRST(ST)=a,( FIRST()= 對(duì) T

31、,ST| FIRST(T)=( FIRST(,ST)=,預(yù)測(cè)(yc)分析表: FOLLOW(T)=) a ( ) , # SSaSS(T) TTSTTSTTST TTT ,ST第38頁(yè)/共64頁(yè)第三十八頁(yè)，共65頁(yè)。CH4.1.(3) CH4.1.(3) 給出對(duì)符號(hào)串(a(a，) ) 的分析(fnx)(fnx)過(guò)程步驟 符號(hào)棧 輸入串 動(dòng)作, 所用產(chǎn)生式 . 0 #S (a,)# 初始(ch sh)；用 S , ( 查表 1 #)T( (a,)# S(T), 展開(kāi)S 2 #)T a,)# 匹配(；用 T , a 查表 3 #)TS a,)# TST , 展開(kāi)T; 用 S ,a 查表 4 #)T

32、a 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 , )查表 10 #) )# T,展 開(kāi)T 11 # # 匹配 ) 12 # # 分析成功, 結(jié)束分析第39頁(yè)/共64頁(yè)第三十九頁(yè)，共65頁(yè)。CH.4.CH.4.練習(xí)題3(3(P82.)P82.) 3.下面文法(wnf)中, 哪些是LL(1)的, 說(shuō)明理由。 (1) SABc A a| B b|。n解，因?yàn)?yn wi) FOLLOW(S)=#n 文法不

33、含左遞歸; FIRST(S)=a,b,c n 對(duì) 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頁(yè)/共64頁(yè)第四十頁(yè)，共65頁(yè)。CH.4.CH.4.練習(xí)題3(3(P82.)P82.) 3.下面文法(wnf)中, 哪些是LL(1)的, 說(shuō)明理由。 (2) SAb A a|B| B b|。n解(1) 因?yàn)?FOLLOW(S)=#n 對(duì)

34、 Aa|B| ; FIRST(S)=a,b n FIRST(B)=b,與FIRST()=相交;n所以文法(wnf)不是LL(1)文法(wnf)。n解(2) 對(duì) Aa|n 因?yàn)镕IRST(A)= a,b, ，F(xiàn)OLLOW(A)=b, n FOLLOW和FIRST兩者相交。n 所以文法(wnf)不是LL(1)文法(wnf)。第41頁(yè)/共64頁(yè)第四十一頁(yè)，共65頁(yè)。CH.4.CH.4.練習(xí)題3(3(P82.)P82.) 3.下面(xi mian)文法中, 哪些是LL(1)的, 說(shuō)明理由。 (3) SABBA A a| B b|。n解，雖然 FOLLOW(S)=#n 文法不含左遞歸; FIRST(S)

35、=a, b, n 對(duì) Aa|，其候選(hu xun)式的FIRST集合不相交;n 對(duì) Bb|，其候選(hu xun)式的FIRST集合也不相交;n 但 對(duì) Aa| （由 Bb|出發(fā)證明也可）n FOLLOW(A)= a, b, # , FIRST(A)= a, n 兩者相交。n 所以，文法不是LL(1)文法。第42頁(yè)/共64頁(yè)第四十二頁(yè)，共65頁(yè)。CH.4.CH.4.練習(xí)題3(3(P82.)P82.) 3.下面文法(wnf)中, 哪些是LL(1)的, 說(shuō)明理由。 (4) SaSe|B BbBe|C CcCe|d。n解， 因?yàn)?文法不含左遞歸; n 對(duì) SaSe|B、BbBe|C 和 CcCe|

36、dn 各產(chǎn)生式的候選(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 ，F(xiàn)IRST(B)= b,c,d n FIRST(C)= c,d 均不含。n 所以，文法是LL(1)文法。第43頁(yè)/共64頁(yè)第四十三頁(yè)，共65頁(yè)。程 序 設(shè) 計(jì) 語(yǔ) 言 Chapter 7. 語(yǔ)義分析(fnx)和中間代碼產(chǎn)生第44頁(yè)/共64頁(yè)第四十四頁(yè)，共65頁(yè)。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頁(yè)/共64頁(yè)第四十五頁(yè)，共65頁(yè)。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頁(yè)/共64頁(yè)第四十六頁(yè)，共65頁(yè)。2021-12-15P218-4自下而上分析過(guò)程中把賦值語(yǔ)句(yj) A := B * （-C + D）翻譯成三地址碼的步驟： （參看p179的語(yǔ)義子程序）第47頁(yè)/共64頁(yè)第四十七頁(yè)，共65頁(yè)。 語(yǔ)法分析翻譯(fny)過(guò)程： 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.產(chǎn)生一個(gè)新的中間產(chǎn)生一個(gè)新的中間(zhngjin)變量變量T1E3.place=k5產(chǎn)生代碼產(chǎn)生代碼 k5:=uminus k3名字名字屬性屬性地址地址ABCDT1T2T3k1K2k3k4k5k6k7符號(hào)表第48頁(yè)/共64頁(yè)第四十八頁(yè)，共65頁(yè)。2021-12-15A := B * (-C + D)的三地址碼k5:=uminus k3k6:= k5+ k4k7:= k2* k6k1:= k7名字名字屬性屬性地址地址ABCDT1T2T3k1K2k3k4k5k6k7符號(hào)表（參看(cnkn)p17

40、9的語(yǔ)義子程序）第49頁(yè)/共64頁(yè)第四十九頁(yè)，共65頁(yè)。2021-12-15P218-6：用7.4.2節(jié)的辦法(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頁(yè)/共64頁(yè)第五十頁(yè)，共65頁(yè)。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節(jié)的辦法，把下面的語(yǔ)句翻譯成四元(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頁(yè)/共64頁(yè)第五十一頁(yè)，共65頁(yè)。程 序

42、設(shè) 計(jì) 語(yǔ) 言 Chapter 8. Chapter 11.第52頁(yè)/共64頁(yè)第五十二頁(yè)，共65頁(yè)。2021-12-15CH8.CH8. CH11. CH11. 1. 什么(shn me)是符號(hào)表？符號(hào)表有哪些重要作用？ 2. 符號(hào)表的表項(xiàng)常包括哪些部分？各描述什么(shn me)？ 3. 有哪些存儲(chǔ)分配策略？并敘述何時(shí)用何種存儲(chǔ)分配策略？ 4. 代碼優(yōu)化的常用措施和優(yōu)化的三個(gè)層次。第53頁(yè)/共64頁(yè)第五十三頁(yè)，共65頁(yè)。程 序 設(shè) 計(jì) 語(yǔ) 言 補(bǔ)充(bchng)題第54頁(yè)/共64頁(yè)第五十四頁(yè)，共65頁(yè)。2021-12-15補(bǔ)充(bchng)題 1. 畫(huà)出編譯程序(bin y chn x)的總

43、體邏輯結(jié)構(gòu)圖，簡(jiǎn)述各部分的主要功能。第55頁(yè)/共64頁(yè)第五十五頁(yè)，共65頁(yè)。2021-12-15補(bǔ)充(bchng)題 2. 已知文法GZ: Z0U|1V U1Z|1 V0Z|0 請(qǐng)寫(xiě)出此文法描述的只含有個(gè)符號(hào)的全部句子。 GZ產(chǎn)生的語(yǔ)言是什么？ 該文法在Chomsky文法分類(lèi)(fn li)中屬于幾型文法？第56頁(yè)/共64頁(yè)第五十六頁(yè)，共65頁(yè)。2021-12-15【解】 （1）0101，0110，1010， 1001 （2）分析GZ所推導(dǎo)出的句子的特點(diǎn)：由Z開(kāi)始(kish)的推導(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型文法。 圖 1 文法GZ可能的幾種推導(dǎo) Z 0 1 U Z U 0 Z 1 Z 1 V 0 Z Z 1 0 V Z0U|1V U1Z|1V0Z|0第57頁(yè)/共64頁(yè)第五十七頁(yè)，共65頁(yè)。2021-12-15補(bǔ)充(bchng)題 3. 已知文法和它的LR分析表如下(rxi)，給出串dbdb# 的LR分析過(guò)程。 GS：(1) SAdB (2)Aa (3) A (4) Bb (5)BBdb (6)BACTIONACTIONGOTOGOTOa