編譯Bottom-Up習(xí)題解答

1、1、已知文法G(S)：Sf aS|bS|a(1)構(gòu)造該文法的LR(0)項(xiàng)目集規(guī)范族(2) 構(gòu)造識(shí)別該文法所產(chǎn)生的活前綴的DFA。(3)構(gòu)造其SLR分析表，并判斷該文法是否是 SLR(1)文法。解題思路構(gòu)造 LR(0) 項(xiàng)目集規(guī)范族，有兩種方法：一種是利用有限自動(dòng)機(jī)來構(gòu)造，另一種是利用函數(shù) CLOSURE 和 GO 來構(gòu)造。 本題采取第2 種方法， 通過計(jì)算函數(shù)CLOSURE 和 GO 得到文法的 LR(0) 項(xiàng)目集規(guī)范族，而GO 函數(shù)則把LR(0) 項(xiàng)目集規(guī)范族連成一個(gè)識(shí)別該文法所產(chǎn)生的活前綴的DFA。解答(1)將文法G(S)拓廣為G(S'):(0)S' -S(i)SfaS(2

2、)S-bS(3)S-a構(gòu)造該文法的LR(0) 項(xiàng)目集規(guī)范族：Io=CLOSURE(S 7 S戶S3 S, S aS, S bS,腔 aIi=GO( Io , a尸CLOSURE(S-a S , S-a )=S-a S , S-a -,腔 aS,S bS, S aI2=GO( I。, b尸CLOSURE(S-b S )= S-b S, * aS=r bS, S 7 a a13=GO( I。, S)=CLOSURE( S' S= S' 7 S GO(11, a戶CLOSURE(S -aS , Sa )=11GO(12, b)=CLOSURE( S-b S)=I2I4=GO(I i,

3、 S)=CLOSURE( * aS )=SaS GO(12, a)= CLOSURE(S -a S , Sa )=11GO(12, b)= CLOSURE( S-b S)=I2I5=GO(I 2, S)=CLOSURE(S -bS )= S-bS 所以，項(xiàng)目集Io, Il, I2, I3, I4和I5構(gòu)成了該文法的LR(0)項(xiàng)目集規(guī)范族。(2)我們用GO 函數(shù)把 LR(0) 項(xiàng)目集規(guī)范族連成一個(gè)識(shí)別該文法所產(chǎn)生的活前綴的DFA 如圖4.1 所示。圖4識(shí)別活前綴的D卜A(3)構(gòu)造其SLR分析表。表4.1 SLR分析表ACTIONGOTO狀態(tài)ab#S0S1S231S1S2r342S1S253acc

4、4r15r2注意到狀態(tài)Ii存在“移進(jìn)-歸納”沖突，計(jì)算 S的FOLLOW 集合：FOLLOW(S)=#可以采用SLR沖突消解法，得到表 4.1所列的SLR分析表。從分析表可以看出，表中沒有沖突項(xiàng)，所以該文法是SLR(1)文法。2、證明AdBd是文法G(S)的活前綴。說明活前綴在 LR分析中的作用。給出串 dbdb#的 LR分析過程。G(S)： (1) S-AdB (2)A-a (3) A - e(4) B -b (5)B -Bdb (6)B 一解題思路所謂活前綴是指規(guī)范句型的一個(gè)前綴，這種前綴不句柄之后的任何符號(hào)。根 據(jù)此定義，直接證明AdBd是文法G(S)的活前綴。解答存在下面的規(guī)范推導(dǎo)：S

5、 > AdB <> AdBdb可見AdBdb是文法G的規(guī)范句型，AdBd是該規(guī)范句型的前綴。 另外，在該規(guī)范句型中 Bdb 是句柄，前綴是 AdBd不含句柄Bdb之后的任何符號(hào)，所以 AdBd是文法G(S)的活前綴。在LR分析工作過程中的任何時(shí)候， 棧里的方法符號(hào)(自棧底而上)XiX2jXm應(yīng)該構(gòu)成活 前綴，把輸入串的剩余部分配上之后即應(yīng)成為規(guī)范句型(如果整個(gè)輸入串確實(shí)構(gòu)成一個(gè)句子)。因此，只要輸入串的已掃描部分保持可歸約成一個(gè)活前綴，那就意味著所掃描過的部 分沒有錯(cuò)誤。構(gòu)造文法G的LR分析表4.2所列。表4.2 LR分析表ACTIONGOTOadb#SAB0s3r3121a

6、cc2s43r24r6s5r665r4r46s7r17s88r5r5串dbdb#的LR分析過程如下:步驟狀態(tài)符號(hào)輸入串00#dbdb#102#Adbdb#2024#Adbdb#30245#Adbdb#40246#AdBdb#502467#AdBdb#6024678#AdBdb#90246#AdB#1001#S#acc3、根據(jù)程序設(shè)計(jì)語言的一遮要求，為定義條件語句的二義文法G(S)構(gòu)造SLR(1)分析表,要求 寫出步驟和必要的說明。G(S)： S - iSeS|iS|a解答將文法G(S)拓廣為G(S'):(0) S' -S(1) S-iSeS(2) S- iS(3)S一 a構(gòu)造此

7、文法的LR(0)項(xiàng)目集規(guī)范族，識(shí)別該文法所產(chǎn)生的活前綴的DFA如圖4.2所示。圖4.2識(shí)別活前綴的DFA注意到狀態(tài)I4存在“移進(jìn)歸約”沖突，計(jì)算 FOLLOW集合：FOLLOW (S) = e, #當(dāng)LR分析器處于狀態(tài) 4時(shí)，如果下一輸入符號(hào)是“ #" ，則按S-iS歸約；如果下一 輸入符號(hào)是“ e”，則既可以按S-iS歸約，也可以執(zhí)行移入。根據(jù)程序設(shè)計(jì)語言的 要求，條件語句的else子句應(yīng)當(dāng)和最近的沒有else子句的if語句匹配，根據(jù) 這一要求，我們規(guī)定：當(dāng)LR分析器處于狀態(tài)4時(shí)，如果下一輸入符號(hào)是， 則按S-iS歸約；如果下一輸入符號(hào)是“ e”，則執(zhí)行移入。構(gòu)造SLR (1)分析

8、 表如表4.3所列。表4.3 SLR (1)分析表ACTIONGOTOiea#S0s2s311acc2s2s343r3r34s5r25s2s366r1r14、設(shè)下列文法生成變量的類型說明:D - id LL 一 , id L | : TT 一 integer | real構(gòu)造一個(gè)翻譯模式，把每個(gè)標(biāo)識(shí)符的類型存入符號(hào)表。解題思路這是一個(gè)對說明語句進(jìn)行語義分析的題目，不需要產(chǎn)生代碼，但要求把每個(gè) 標(biāo)識(shí)符的類型填入符號(hào)表中。解答對D, L, T設(shè)置綜合屬性type。過程addtype(id,type) 用來把標(biāo)識(shí)符id及 其類型 type 填入到符號(hào)表中。翻譯模式如下：D f id L addtyp

9、e(id.entry,L.type) L f ,id L1 addtype(id.entry,L1.type);L.type:=L1.type;L : T L.type:=T.typeT f integer T.type:=intergerT f real T.type:=real5、文法G的產(chǎn)生式如下：S - (L) | aL - L , S | S(1) 試寫出一個(gè)語法制導(dǎo)定義，它輸出配對括號(hào)個(gè)數(shù);(2) 寫一個(gè)翻譯方案，打印每個(gè)a 的嵌套深度。如(a),a), 打印 2,1 。解題思路本題包括兩部分，第 1 部分要求寫語法制導(dǎo)定義，第 2 部分要求寫翻譯方案。語法制導(dǎo)定義(或?qū)傩晕姆?可

10、以看作是關(guān)于語言翻譯的高級(jí)規(guī)范說明，其中隱去實(shí)現(xiàn)細(xì)節(jié)，使用戶從明確說明翻譯順序的工作中解脫出來。翻譯方案 (也稱翻譯模式) 給出了使用語義規(guī)則進(jìn)行計(jì)算的次序，把某些實(shí)現(xiàn)細(xì)節(jié)表示出來。讀者從下面解答中可體會(huì)兩者的區(qū)別。解答( 1) 為S、 L 引入屬性h, 代表配對括號(hào)個(gè)數(shù)。語法制導(dǎo)定義如下：產(chǎn)生式語義規(guī)則5 -(L)S.h:=L.h+16 -aS.h:=0L -L1 , SL.h:=L1.h+S.hL SL.h:=S.hS' -Sprint(S.h)(2)為S、L引入d,代表a的嵌套深度。翻譯方案如下：S' - S.d:=0; SS - '(' L.d:=S.d

11、+1; L )S faprint(S.d);L L1.d:=L.d;L1S.d:=L.d; SL S.d:=L.dS6、下列文法對整型常數(shù)和實(shí)型常數(shù)施用加法運(yùn)算符“+”生成表達(dá)式; 當(dāng)兩個(gè)整型數(shù)相加時(shí)，結(jié)果仍為整型數(shù)，否則，結(jié)果為實(shí)型數(shù)：E - E+T | TT f num.num | num(1) 試給出確定每個(gè)子表達(dá)式結(jié)果類型的屬性文法。(2) 擴(kuò)充 (1) 的屬性文法，使之把表達(dá)式翻譯成后綴形式，同時(shí)也能確定結(jié)果的類型。應(yīng)該注意使用一元運(yùn)算符inttoreal 把整型數(shù)轉(zhuǎn)換成實(shí)型數(shù)，以便使后綴形如加法運(yùn)算符的兩個(gè)操作數(shù)具有相同的類型。解題思路確定每個(gè)子表達(dá)式結(jié)果類型的屬性文法是比較容易定

12、義的。關(guān)鍵是如何擴(kuò)充此屬性文法，使之把表達(dá)式翻譯成后綴形式。我們將不在name或num.num向T歸約的時(shí)候輸出該運(yùn)算對象，而是把運(yùn)算對象的輸出放在T 或E T 向 E 歸約的時(shí)候。這是因?yàn)榭紤]輸出類型轉(zhuǎn)換算符inttoreal的動(dòng)作可能在E+ T歸約的時(shí)候進(jìn)行，如果這時(shí)兩個(gè)運(yùn)算對象都在前面 name或num.num向T歸約的時(shí)候已輸 出，需要為第1 個(gè)運(yùn)算對象輸出類型轉(zhuǎn)換算符時(shí)就已經(jīng)為時(shí)太晚。還要注意的是，在E T 向 E 歸約時(shí)，該加法運(yùn)算的第1 個(gè)運(yùn)算對象已經(jīng)輸出。所以E-E+ T的語義規(guī)則不需要有輸出E運(yùn)算對象的動(dòng)作。解答( 1)為文法符號(hào)E 和 T 配以綜合屬性type, 用來表示它

13、們的類型。類型值分別用 int 和 real 來表示。確定每個(gè)子表達(dá)式結(jié)果類型的屬性文法如下：產(chǎn)生式語義規(guī)則E- E1 + TT.type:=if E1.type=int and T.type=int then int else realE- TE.type:=T.typeTf num.num T.type:=realTf num T.type:=int(2) 下面屬性文法將表達(dá)式的后綴表示打印輸出，其中 lexeme 屬性表示單詞的拼 寫。產(chǎn)生式語義規(guī)則E- E1 + Tif E1.type=real and T.type=int thenbeginE.type:=real;print(T.lexeme);print( inttoreal ); endelse if E1.type=int and T.type=real then beginE.type:=real;print( inttoreal );