編譯原理(第2版)陳意云張昱編著課后答案-學(xué)習(xí)資料

1、編譯(biny)原理習(xí)題2003.4第一頁，共106頁。目錄(ml) chap 1 基本知識 chap 3 詞法分析 chap 4 語法分析 chap 5 語法制導(dǎo)翻譯 chap 6 運行時刻(shk)環(huán)境 chap 7 中間代碼生成 chap 8 代碼生成第二頁，共106頁。第一章 練習(xí)(linx)1.1 文法 S ( L ) | a L L , S | S(a) 指出(zh ch)文法的終結(jié)符號, 非終結(jié)符號, 開始符號.文法的四個組成部分: 終結(jié)符號 VT : 語言不可再分的基本符號 非終結(jié)符號VN : 語法范疇(語法概念) 開始符號 S : 最終(zu zhn)感興趣的語法范疇 產(chǎn)生式

2、 P : 定義語法范疇的一種書寫形式終結(jié)符號: ( , ) a 非終結(jié)符號: S L開始符號: S元語言符號: 表示“定義為” | 表示“或”第三頁，共106頁。(b) 給出句子(j zi)的分析樹分析樹: (推導(dǎo)(tudo)樹) 表示一個句型的推導(dǎo)(tudo) (a, (a,a) S ( L ) L , S S ( L ) a S a第四頁，共106頁。(c) 給出句子(j zi)的最左推導(dǎo) 給出每次推導(dǎo)后得到的句型的短語, 直接短語最左推導(dǎo) : 推導(dǎo)中任何一步 都是對中的最左非終結(jié) lm 符號進行替換的推導(dǎo).短語 是文法的句型(S * ) S * A且A + 則是關(guān)于A的句型的短語. 直接

3、(zhji)短語 是文法的句型(S * ) S * A且A 則是關(guān)于A的句型的直接(zhji)短語. 句柄: 一個句型的最左直接(zhji)短語稱為句柄.第五頁，共106頁。 S ( L ) ( L, S ) ( S, S ) ( a, S ) ( a, ( L )短語(duny) ( L ) L, S S a a ( L, S ) S,S a, S a, ( L ) ( S, S ) (a, S) ( a, ( L ) ( L )直接 ( L ) L, S S a a 短語(duny) ( L ) ( a, ( L, S ) ( a, ( S, S) ( a, (a, S) ( a, (a,

4、 a)短語(duny) a a a a a, ( L, S ) a, ( S, S) a, (a, S) a, (a, a) ( a, ( L, S ) ( a, ( S, S) ( a, (a, S) ( a, (a, a) L, S S a a (L, S) S, S a, S a, a ( S, S) ( a, S) ( a, a)直接 a a a a短語(duny) L, S S a a a 第六頁，共106頁。(d) 構(gòu)造(guzo)各個句子的最右推導(dǎo). 最右推導(dǎo)(規(guī)范推導(dǎo))(e) 這個文法產(chǎn)生的語言是什么? a (a) (a,a) (a,a),a) . a和數(shù)據(jù)元素為a的廣義表全體

5、第七頁，共106頁。1.2 考慮文法 S aSbS | bSaS |(a) 試說明此文法是二義性的.(定義1.5) 如果一文法的句子存在兩棵分析樹, 則該句子是二義性的 . 如果一文法包含二義性的句子,則這個文法是二義性的. 可以(ky)從句子abab有兩個不同的最左推導(dǎo)來說明. S aSbS abS abaSbS ababS abab lm lm lm lm lm S aSbS abSaSbS abaSbS ababS abab lm lm lm lm lm 句子abab有兩個不同的最左推導(dǎo), 該句子是二義性的 . 所以此文法是二義性的.第八頁，共106頁。(b) 對于句子abab構(gòu)造兩個相

6、應(yīng)的最右推導(dǎo). S aSbS aSb abSaSb abSab abab rm rm rm rm rm S aSbS aSbaSbS aSbaSb aSbab abab rm rm rm rm rm (c)對于句子abab構(gòu)造兩個相應(yīng)的分析樹. S S a S b S a S b S b S aS a S b S (d) 此文法產(chǎn)生的語言是什么? 由相同(xin tn)個數(shù)的a和b組成的字符串.第九頁，共106頁。1.3 考慮文法 bexpr bexpr or bterm | bterm bterm bterm and bfactor | bfactor bfactor not bfactor

7、 | ( bfactor ) | true | false(a) 請指出此文法的終結(jié)(zhngji)符號, 非終結(jié)(zhngji)符號和開始符號. 終結(jié)(zhngji)符號: or, and, not, (, ), true, false 非終結(jié)(zhngji)符號: bexpr, bterm, bfactor 開始符號: bexpr第十頁，共106頁。(b) 試對于(duy)句子 not ( true or false) 構(gòu)造一棵分析樹. bexpr bterm bfactor not bfactor ( bexpr ) bexpr or bterm bterm bfactor bfacto

8、r false true第十一頁，共106頁。(c) 試說明(shumng)此文法產(chǎn)生的語言是全體布爾表達式.第十二頁，共106頁。練習(xí):長度為n的字符串, 分別(fnbi)有多少個前綴, 后綴, 子串, 真前綴, 子序列 ?前綴: n+1后綴(huzhu): n+1子串: 1+ n+(n-1)+.+1 = 1+n(n+1)/2真前綴: n子序列: 1+Cn1+Cn2+Cn3+.+Cnn = 2n第十三頁，共106頁。 E E + T T * F i給出句型(j xn)E+T*i的短語, 直接短語和句柄 E E + T F T * F 給出句型F+T*F的短語(duny), 直接短語(duny

9、)和句柄短語(duny): i, T*i, E+T*i直接短語(duny): i句柄: i短語: F, T*F, F+T*F直接短語: F, T*F句柄: F第十四頁，共106頁。第三章 練習(xí)(linx)3.3 試描述下列(xili)正規(guī)表達式所表示的語言:(a) 0 ( 0 | 1)* 0(b) ( ( | 0 ) 1* ) *由0和1組成且以0開始和結(jié)束(jish)的符號串全體.(c) ( 0 | 1 )* 0 ( 0 | 1) ( 0 | 1)由0和1組成的符號串全體.由0和1組成且以000,001,010或011結(jié)束的符號串全體.長度大于等于3且倒數(shù)第3個字符為0的01符號串全體.第十

10、五頁，共106頁。(d) 0*10*10*10*(e) ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )*有且只有(zhyu)3個1的0、1字符串全體.帶有偶數(shù)(u sh)個0和偶數(shù)(u sh)個1的由0和1組成的符號串全體.帶有偶數(shù)(u sh)個a和偶數(shù)(u sh)個b的符號串全體.( (aa|bb) | (ab|ba) (aa|bb)* (ab|ba) )*第十六頁，共106頁。3.4 對于下列語言分別寫出它們的正規(guī)(zhnggu)表達式:(a) 英文字母組成的所有符號串, 要求符號串中順序包含 五個元音字母.

11、令letter=非元音(yunyn)的英文字母 letter* (a|A) letter* (e|E) letter* (i|I) letter* (o|O) letter* (u|U) letter* (b) 英文字母組成的所有符號串, 要求符號串中的字母依 照字典(zdin)序排列. ( a | A)* ( b | B)* ( c | C)*. ( z | Z)*第十七頁，共106頁。 (c)沒有重復(fù)(chngf)出現(xiàn)的數(shù)字的數(shù)字符號串全體.(d) 最多有一個(y )重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號串全體令 ri = i | , i=0,1,2,.,9 R0|R1|R2|.|R9記為 Ri i(0

12、,1,2.,9)P(0,1,2.,9)表示(biosh)0,1,2.,9的全排列 ri0ri1.ri9 i0i1. i9P(0,1,2.,9) i ri0ri1.ri9i(0,1,2.,9) i0i1. i9P(0,1,2.,9)第十八頁，共106頁。(e) 帶有偶數(shù)(u sh)個0和奇數(shù)個1的由0和1組成的符號串全體. E為帶有偶數(shù)(u sh)個0和1的由0和1組成的符號串全體.即 ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )* E 1 E | E 0 E 1 E 0 E(f) 不包含子串011的由0和1組成(

13、z chn)的符號串全體. (g) 不包含子序列011的由0和1組成的符號串全體1*0*10* |1*( 0* | (10)* )*第十九頁，共106頁。練習(xí):1. 令A(yù),B和C是任意正規(guī)(zhnggu)式,證明以下關(guān)系成立: A|A=A (A*)*=A* A*=|AA* (AB)* A =A(BA)* (A|B)*=(A*B*)*=(A*|B*)* A=b|aA當(dāng)且僅當(dāng)A=a*b第二十頁，共106頁。3.6 給出接受下列在字母表0，1上的DFA。（a）所有以00結(jié)束(jish)的符號串的集合；AstartB0C010NFA等價于A1startBC00011DFA(1|0)*00第二十一頁，共

14、106頁。（b）所有具有(jyu)三個0的符號串的集合。1*01*01*01*AstartB0C01DFA11B01第二十二頁，共106頁。3.7 構(gòu)造等價(dngji)于下列正規(guī)表達式的有限自動機.(a) 10|(0|11)0*100011AstartD1BEC1NFA 0 1A D BCD D EBC E DE / / 1010AstartBC0DEDFA1第二十三頁，共106頁。(b) (0|1)* |(11)*0|111AstartCBEDNFA 0 1ABDE ABDE ABCDEABCDE ABDE ABCDE11Astart0BDFA01Astart最小化DFA0第二十四頁，共1

15、06頁。3.8 給定(i dn)右線性文法G: S 0S | 1S | 1A | 0B A 1C | B 0C | 1 C 0C | 1C | 0 | 1 試求一個等價的左線性文法G. 000,11SstartB1ACf狀態(tài)轉(zhuǎn)移圖100,10,1左線性文法G: f A1 | B0 | C1 | C0 A S1 B S0 C A1 | B0 | C1 | C0 S S0 | S1 | 圖中狀態(tài)C和f可合并, 得到左線性文法G: C A1 | B0 | C1 | C0 A S1 B S0 S S0 | S1 | 第二十五頁，共106頁。3.9-3.11(d) (a|b)*abb(a|b)* 1st

16、art2a4ba3bbba由正規(guī)表達式構(gòu)造NFA1start12a14b13bbaaba124a134bba由NFA得到DFAABCDEFB C D E F A B C D E ABaDbCbabaab最小化DFA第二十六頁，共106頁。3.13 對于下列正規(guī)(zhnggu)表達式構(gòu)造最小狀態(tài)的DFA.(b) (a|b)*a(a|b)(a|b)a1start2a43babNFAbaAstartBabHGaCDaaaEFabaaabbbb最小化DFA第二十七頁，共106頁。4.4 考慮文法 R R | R | RR | R* | (R) | a | b(a)試說明此文法生成在符號a和b之上的所有

17、正規(guī)表達式.(b)試說明此文法是二義性的.(c)試構(gòu)造一個(y )等價的無二義性文法.(b) 句子(j zi)a|aa的兩種最左推導(dǎo). 句子(j zi)aa*的兩種最左推導(dǎo). RR Ra R * a R R * R R a a(c)消除二義性 R R | S | S S ST | T T U* | U U (R) | a | b第二十八頁，共106頁。4.5 dangling-else文法(wnf): stmt if expr then stmt | matched-stmt matched-stmt if expr then matched-stmt else stmt | other 試說

18、明此文法(wnf)是二義性的。句子(j zi) if e1 then if e2 then s1 else if e3 then s2 else s3 if e1 then if e2 then s1 else if e3 then s2 else s3 S MSif E then MS else S e1 if E then MS else S MS e2 other if E then S other s1 e3 MS s3 other s2 Sif E then S e1 MSif E then MS else S e2 other MS s1 if E then MS else S e

19、3 other MS s2 other s3第二十九頁，共106頁。4.3 對于(duy)下面的每一個語言設(shè)計一個文法。試問其中哪些語言是正規(guī)的？(a) 使得在每一個0后至少立即跟隨一個1的由0和1組成的符號串的全體。(b) 具有相同(xin tn)數(shù)目的0和1的由0和1組成的符號串的全體。(c) 具有不同(b tn)數(shù)目的0和1的由0和1組成的符號串的全體。S 1S | 01S | (1|01)*S 0S1S | 1S0S | 非正規(guī)語言S SAS S 0S1S | 1S0S | A B | C 非正規(guī)語言B 1B | 1C 0C | 0S A | BA 0 | 0A | A0 | 10A

20、| 01A| A10 | A01| 1A0 | 0A1B 0 | 0B | B0 | 10B | 01B| B10 | B01| 1B0| 0B1第三十頁，共106頁。(d) 所有(suyu)形如xy而xy的由0和1組成的符號串。S 0E | 1E | LBRE 00E | 01E | 10E | 11E | B I I1B | OO1B | IO1C | OI1CC IO1C | OI1C | I1 O OI1O1I IO1I1I I I1O1O OO1L I 1LLO 0LI1R R1O1R R0LR 所有(suyu)形如xy而x=y的由0和1組成的符號串。S 0S0| 1S1| 第三十一

21、頁，共106頁。4.5 (a) 給出一個上下文無關(guān)產(chǎn)生式的集合， 使它與A B*a (C|D) 生成(shn chn)同樣的 符號串集合。 A B a E B B B | E C | D (b) 是否可以把E T | E+T寫為： E T +T 是否可以把E T | E+T | E-T寫為： E T (+|-T) E T +T 等價于 E T T T +TT |第三十二頁，共106頁。4.7對于文法S aSbS | bSaS | 構(gòu)造(guzo)一個帶有回溯的遞歸下降分析器. 問能否構(gòu)造(guzo)一個預(yù)測分析器.procedure match(t:token);begin ifkahead

22、= t thenend;procedure S;begin if match第三十三頁，共106頁。4.9 對于文法 bexpr bexpr or bterm | bterm bterm bterm and bfactor | bfactor bfactor not bfactor | (bexpr) | true | false 構(gòu)造(guzo)一個預(yù)測分析器。1. 消除左遞歸bexpr bterm bexpr bexpr or bterm bexpr | bterm bfactor btermbterm and bfactor bterm | bfactor not bfactor | (

23、bexpr) | true | false2. First(bexpr) = First(bterm) = First(bfactor) =not, (, true, false First(bexpr) = or, First(bterm) = and, Follow(bexpr) = $, ) Follow(bexpr) = $, ) Follow(bterm) = or, $, ) Follow(bterm) = or, $, ) Follow(bfactor) = or, and, $, )第三十四頁，共106頁。(1) bexpr bterm bexpr (2) bexpr or b

24、term bexpr (3) bexpr (4) bterm bfactor bterm(5) bterm and bfactor bterm (6) bterm (7) bfactor not bfactor(8) bfactor (bexpr) (9) bfactor true (10) bfactor falseFirst(bexpr) = First(bterm) = First(bfactor) =not, (, true, falseFirst(bexpr) = or, First(bterm) = and, Follow(bexpr) = $, )Follow(bexpr) =

25、$, )Follow(bterm) = or, $, ) Follow(bterm) = or, $, )Follow(bfactor) = or, and, $, ) or and not true false ( ) $bexpr (1) (1) (1) (1) synch synch bexpr (2) (3) (3) bterm synch (4) (4) (4) (4) synch synch bterm (6) (5) (6) (6)bfactor synch synch (7) (9) (10) (8) synch synch 第三十五頁，共106頁。4.11試說明沒有一個左遞歸

26、文法可以是LL(1)的。 (1) 直接左遞歸文法中存在(cnzi)產(chǎn)生式: A A1 | A2 |.| Am | 1 | 2 |.| n, 其中 1 2 . n均不以A開頭 First(Ai) First( j) = First( j) 若 j *, First(A i) Follow(A) = First( i) , 不是LL(1)文法. (2) 間接左遞歸文法中存在(cnzi)產(chǎn)生式集合: A B1 1 | 1 | 2 |.| n B1 B2 2 . Bm A First(B1 1) = First(A m . 1) First( j) First(B1 1) , j=1,.,n Firs

27、t( j) First(B1 1) , j=1,.,n 若 j *, First(B1 1) Follow(A) = First( m . 1) , 不是LL(1)文法.第三十六頁，共106頁。4.12試說明(shumng)沒有一個LL(1)文法可以是二義性的。 若有一個LL(1)文法是二義性的, 則存在句子w 有兩種不同的最左推導(dǎo): S * A 1 * w S * A 2 * w 對于文法中的產(chǎn)生式 A 1 | 2 , 其中1 , 2 First(1) First(2) = First(w) 與LL(1)文法矛盾.第三十七頁，共106頁。4.15 文法(wnf) S (L) | a L L,

28、 S | S的算符優(yōu)先關(guān)系由表4.20給出。建立與表相應(yīng)的算符優(yōu)先函數(shù)并用算符優(yōu)先分析法分析句子(a, (a, a)及(a, (a,a), (a,a)。算符優(yōu)先(yuxin)關(guān)系表 a ( ) , $a ( = ) , $ 算符優(yōu)先函數(shù) a ( ) , $f 2 0 2 2 0g 3 3 0 1 0句子(a, (a, a)的分析過程棧 輸入(shr) 動作$ (a,(a,a)$ $( shift$( a,(a,a)$ (a shift $(a ,(a,a)$ a, reduce$(S ,(a,a)$ (, shift $(S, (a,a)$ ,( shift $(S,( a,a)$ (a sh

29、ift $(S,(a ,a)$ a, reduce$(S,(S ,a)$ (, shift$(S,(S, a)$ ,a shift$(S,(S,a )$ a) reduce$(S,(S,S )$ ,) reduce$(S,(L )$ (=) shift$(S,(L) )$ ) reduce$(S,S )$ ,) reduce$(L )$ (=) shift$(L) $ )$ reduce$S $ accept 第三十八頁，共106頁。4.16 試為下列(xili)各文法建立算符優(yōu)先關(guān)系表。(a) S a S b S | b S a S | a b $a = b = $ acc設(shè)G是一個運算符文

30、法, R和S是G中任何兩個終結(jié)符, 定義:(1) R=S當(dāng)且僅當(dāng)G中存在(cnzi)產(chǎn)生式 .RS. 或 .RS.(2) RS當(dāng)且僅當(dāng)G中存在(cnzi)產(chǎn)生式 .R., 其中 + S. 或 + S.(3) RS當(dāng)且僅當(dāng)G中存在(cnzi)產(chǎn)生式 . S., 其中 + .R 或 + .R最左終結(jié)符: S.或 S., S是的最左終結(jié)符 ., 則的最左終結(jié)符是的最左終結(jié)符對于文法(wnf)中 R.的產(chǎn)生式, R 的最左終結(jié)符.第三十九頁，共106頁。(b) bexpr bexpr or bterm | bterm bterm bterm and bfactor | bfactor bfactor

31、not bfactor | (bexpr) | true | false or and not ( ) true false $or ( = true false $ acc 最左終結(jié)符 最右終結(jié)符bexpr or, and, not, (, true, false or, and, not, ), true, falsebterm and, not, (, true, false and, not, ), true, falsebfactor not, (, true, false not, ), true, false第四十頁，共106頁。4.18 給出文法LR(0)項目集族及相應(yīng)的識別活

32、前綴(qinzhu)的自動機的狀態(tài)轉(zhuǎn)移圖. S S C cC S CC C d I0: S .S S .CC C . cC C .dI1: S S.I2: S C.C C .cC C .dI3: C c.C C .cC C .dI4: C d.I5: S CC.I6: C cC.I0I1SCI2cI3CI5dI4cdCI6cdstart第四十一頁，共106頁。4.19 利用圖4.31畫出文法(wnf)4.27的識別活前綴的自動機的狀態(tài)轉(zhuǎn)移圖. (P.200)I0: S .S S .iSeS S .iS S .aI1: S S.I2: S i.Ses S i.S S .iSeS S .iS S

33、.a0I3: S a.I4: S iS.eS S iS.I5: S iSe.S S .iSeS S .iS S .aI6: S iSeS.iI0I1SaI3iI2SI4istarteI5SI6aa第四十二頁，共106頁。4.21 考慮文法 S A S | b A S A | a(1) 構(gòu)造文法的LR(0)項目集規(guī)范族及相應(yīng)的DFA.(2) 如果把每一個LR(0)項目看成一個狀態(tài), 并從每個形如B.X的狀態(tài)出發(fā)畫一條標(biāo)記為X的弧到狀態(tài)BX., 且從從每個形如B.A的狀態(tài)出發(fā)畫一條標(biāo)記為的弧到所有形如A.的狀態(tài).這樣(zhyng)就得到了一個NFA. 說明這個NFA和(1)的DFA是等價的.(3)

34、 構(gòu)造文法的SLR分析表.(4) 對于輸入串bab, 給出SLR分析器的動作.(5) 構(gòu)造文法的LR(1)分析表和LALR分析表.第四十三頁，共106頁。I0: S .S S .AS S .b A .SA A .aI1:(I0,S) S S. A S.A A .SA A .a S .AS S .bI2: (I0,A) (I2,A) (I6,A) S A.S S .AS S .b A .SA A .aI3: (I0,b) (I1,b) (I2,b) (I5,b) (I6,b) (I7,b) S b.I4: (I0,a) (I1,a) (I2,a) (I5,a) (I6,a) (I7,a) A a

35、.I5: (I1,S) (I5,S) (I7,S) A S.A A .SA A .a S .AS S .bI6: (I1,A) (I5,A) (I7,A) A SA. S A.S S .AS S .b A .SA A .aI7 : (I2,S) (I6,S) S AS. A S.A A .SA A .a S .AS S .b第四十四頁，共106頁。First(S) = First(S) = First(A) = b, aFollow(S) = $Follow(S) = a, b, $Follow(A) = a, bSLR分析(fnx)表STATE ACTION GOTO a b $ S A0

36、s4 s3 1 21 s4 s3 acc 5 62 s4 s3 7 2 3 r3 r3 r34 r5 r5 5 s4 s3 5 66 s4/r4 s3/r4 7 27 s4/r2 s3/r2 r2 5 6SLR分析表存在(cnzi)移入-歸約沖突.為消除二義性，假設(shè)a的優(yōu)先級高于b，則遇到a時移入，遇到b時歸約。輸入(shr)串bab, SLR分析器的動作:棧 輸入(shr) 動作0 bab$ shift30b3 ab$ reduce S b0S1 ab$ shift40S1a4 b$ reduce A a0S1A6 b$ shift-reduce collision 輸入串bab, SLR分

37、析器的動作:棧 輸入 動作0 bab$ shift30b3 ab$ reduce S b0S1 ab$ shift40S1a4 b$ reduce A a0S1A6 b$ reduce A SA0A2 b$ shift30A2b3 $ reduce S b0A2S7 $ reduce S AS0S1 $ accept第四十五頁，共106頁。LR(1)項目(xingm)集規(guī)范族I0: S .S, $ S .AS, $/a/b S .b, $/a/b A .SA, a/b A .a, a/bI1:(I0,S) S S., $ A S.A, a/b A .SA, a/b A .a, a/b S .A

38、S, a/b S .b, a/bI2: (I0,A) (I2,A) S A.S, $/a/b S .AS, $/a/b S .b, $/a/b A .SA, a/b A .a, a/bI3: (I0,b) (I2,b) S b., $/a/bI4: (I0,a) (I1,a) (I2,a) (I5,a) (I6,a) (I8,a) (I9,a) (I10,a) A a., a/bI5: (I1,S) (I5,S) (I8,S) (I10,S) A S.A, a/b A .SA, a/b A .a, a/b S .AS, a/b S .b, a/bI6: (I1,A) (I5,A) (I8,A)

39、 (I10,A) A SA., a/b S A.S, a/b S .AS, a/b S .b, a/b A .SA, a/b A .a, a/bI7 : (I1,b) (I5,b) (I6,b) (I8,b) (I9,b) (I10,b) S b., a/bI8 : (I2,S) S AS., $/a/b A S.A, a/b A .SA, a/b A .a, a/b S .AS, a/b S .b, a/bI9: (I6,A) (I9,A) S A.S, a/b S .AS, a/b S .b, a/b A .SA, a/b A .a, a/bI10: (I6,S) (I9,S) S AS.

40、, a/b A S.A, a/b A .SA, a/b A .a, a/b S .AS, a/b S .b, a/b第四十六頁，共106頁。STATE ACTION GOTO a b $ S A0 s4 s3 1 21 s4 s7 acc 5 62 s4 s3 8 2 3 r3 r3 r34 r5 r5 5 s4 s7 5 66 s4/r4 s7/r4 10 97 r3 r38 s4/r2 s7/r2 r2 5 69 s4 s7 10 910 s4/r2 s7/r2 5 6 LR(1)分析(fnx)表該文法的LR(1)分析表中存在移入-歸約沖突，文法具有二義性。為消除(xioch)二義性，假設(shè)

41、a的優(yōu)先級高于b，則遇到a時移入，遇到b時歸約。s4r4r2第四十七頁，共106頁。該文法不是LR(1)文法.具有二義性.對于(duy)句子abab,存在兩顆不同的分析樹.SASaASSAbbaSASaSAbbaAS第四十八頁，共106頁。4.22 構(gòu)造文法 S a S S b | a S S S | c 的LR(0)項目集規(guī)范族及識別(shbi)活前綴的自動機.I0: S .S S .aSSb S .aSSS S .cI1: S S.I2: S a.SSb S a.SSS S .aSSb S .aSSS S .cI3: S c.I4: S aS.Sb S aS.SS S .aSSb S .a

42、SSS S .cI5: S aSS.b S aSS.S S .aSSb S .aSSS S .cI6: S aSSb.I7: S aSSS.I0I1ScI3aI2SI4startSI5bI6acaaccSI7第四十九頁，共106頁。4.25 證明(zhngmng)下面文法是SLR(1)文法, 并構(gòu)造其SLR分析表. E E + T (1) F F* (5) E T (2) F a (6) T T F (3) F b (7) T F (4)I0: E .E E .E+T E .T T .TF T .F F .F* F .a F .bI1: E E. E E.+TI2: E T. T T.F F

43、.F* F .a F .bI3: T F. F F.*I4: F a.I5: F b.I6: E E+.T T .TF T .F F .F* F .a F .bI7: T TF. F F.*I8: F F*.I9: E E+T. T T.F F .F* F .a F .b action goto + * a b $ E T F0 s4 s5 1 2 31 s6 acc2 r2 s4 s5 r2 73 r4 s8 r4 r4 r4 4 r6 r6 r6 r6 r6 5 r7 r7 r7 r7 r7 6 s4 s5 9 37 r3 s8 r3 r3 r3 8 r5 r5 r5 r5 r5 9 r1

44、 s4 s5 r1 7 Follow(E) = +, $Follow(T) = +, $, a, bFollow(E) = +, $, *, a, b第五十頁，共106頁。4.26 證明每一個(y )LL(1)文法都是LR(1)文法.第五十一頁，共106頁。4.27 證明下面(xi mian)文法是LL(1)的但不是SLR(1)文法. S A a A b | B b B a A B First(AaAb)=aFirst(BbBa)=bFirst(AaAb) First(BbBa) = 文法(wnf)是LL(1)的.構(gòu)造SLR(1)項目集:I0: S .S S .AaAb S .BbBa A .

45、 B .Follow(A) = Follow(B) = a, b存在歸約-歸約沖突,該文法(wnf)不是SLR(1)文法(wnf).第五十二頁，共106頁。4.28 證明任何(rnh)一個LR(1)文法都是無二義文法.第五十三頁，共106頁。4.29 證明任何(rnh)SLR(1)文法都是LR(1)文法.假設(shè)文法G是SLR(1)文法, 則對于文法的狀態(tài)i:對于A.X, XVT, , XFollow(B), i中沒有項目B.對于A.和B ., Follow(A) Follow(B) = 構(gòu)造G的LR(1)項目集, 若G是LR(1)文法, 則項目集i必須滿足條件:(1)對于A.X, a, XVT,

46、 , XFollow(B), i中沒有項目B., X. (顯然(xinrn)成立)(2)沒有A., a和B .,a的兩個項目.由closure(I)的構(gòu)造A.B,a, B., First(a)可得知, 項目A.的向前搜索符號Follow(A)對于一個項目集中的不同歸約項目A2.搜索符A, B3.,搜索符A搜索符A 搜索符A = 不存在歸約-歸約沖突, 所以條件(2)成立.第五十四頁，共106頁。4.31 為下面的文法(wnf)構(gòu)造它的LR(1)項目集規(guī)范族,并判斷它是否為LR(1)文法(wnf)? 若是,構(gòu)造它的分析表. S E S S S E (1) E E + T | T E E + T

47、(2) E T (3) T ( E ) | a T ( E ) (4) T a (5)I0: S .S $ S .E $ E .E+T $/+ E .T $/+ T .(E) $/+ T .a $/+I1: S S. $ I2: S E. $ E E.+T $/+I3: E T. $/+I4: T (.E) $/+ E .E+T )/+ E .T )/+ T .(E) )/+ T .a )/+I5: T a. $/+I6: E E+.T $/+ T .(E) $/+ T .a $/+I7: T (E.) $/+ E E.+T )/+I8: E T. )/+I9: T (.E) )/+ E .E

48、+T )/+ E .T )/+ T .(E) )/+ T .a )/+I10:T a. )/+I11:E E+T. $/+I12: T (E). $/+ I13:E E+.T )/+ T .(E) )/+ T .a )/+I14: T (E.) )/+ E E.+T )/+I15: E E+T. )/+I16: T (E). )/+LR(1)項目(xingm)集規(guī)范族:第五十五頁，共106頁。 action goto + ( ) a $ S E T0 s4 s5 1 2 31 acc2 s6 r13 r3 r3 4 s9 s10 7 85 r5 r56 s4 s5 117 s13 s12 8

49、r3 r39 s9 s5 14 8 10 r5 r511 r2 r2 12 r4 r413 s9 s10 1514s13 s16 15r2 r216r4 r4LR(1) 分析(fnx)表:第五十六頁，共106頁。LALR(1)分析(fnx)表: action goto + ( ) a $ S E T 0 s4 9 s5 10 1 2 3 8 1 acc 2 s6 13 r1 3 8 r3 r3 r3 4 9 s4 9 s5 10 7 14 3 8 5 10 r5 r5 r5 6 13 s4 9 s5 10 11 15 7 14 s6 13 s12 1611 15 r2 r2 r212 16 r

50、4 r4 r4LALR(1)分析表不存在沖突, 所以(suy)該文法是LALR(1)文法.第五十七頁，共106頁。證明文法(wnf)G: ad bd ae be c c是LR(1)文法(wnf), 但不是LALR(1)文法(wnf).第五十八頁，共106頁。5.1 對于輸入(shr)的表達式(4*7+1)*2, 根據(jù)表5.1的語法制導(dǎo)定義建立一棵帶注釋的分析樹. L E.val=58 n T.val=58 T.val=29 * F.val=2 F.val=29 digit.lexval=2 ( E.val=29 ) E.val=28 + T.val=1 T.val=28 F.val=1T.va

51、l=4 * F.val=7 digit.lexval=1F.val=4 digit.lexval=7digit.lexval=4（lex表示是從詞法分析來的）第五十九頁，共106頁。5.2 試根據(jù) (a) 表5.3中的語法制導(dǎo)定義(dngy)， 和 (b) 圖5.17的翻譯模式來建立表達式(a)+(b)的分析樹和語法樹.(a) E T ( E nptr ) E + T T ( E ) ( E ) T nptr T nptr id ididentry to aidentry to a+第六十頁，共106頁。(b) E T R ( E nptr ) T R ( E ) + T i R s T np

52、tr R ( E ) id Tnptr R id identry to aidentry to a+第六十一頁，共106頁。5.4 E E+T | T T num.num | num(a) 給出一個語法制導(dǎo)(zhdo)定義以確定每個子表達式的類型. 5.7(b) 擴充(a)中的語法制導(dǎo)(zhdo)定義把表達式翻譯成前綴形式, 并且決定 類型.(a) E E1+T if ( E1.type=real or T.type=real ) then E.type=real else E.type=integer E T E.type = T.type; T num.num T.type = real;

53、 T num T.type = integer;第六十二頁，共106頁。(b) S E S.type = E.type; S.code = E.code; E E1+T if ( E1.t ype = real and T.type = integer ) then begin E.type = real; E.code = + | E1 .code | inttoreal(T.code) end else if ( E1.t ype = integer and T.type = real ) then begin E.type = real; E.code = + | inttoreal(E

54、1 .code) | T.code end else begin E.type = E1.t ype; E.code = + | E1 .code | T.code end E T E.type = T.type ; E.code = T.code T num.num T.type = real; T.code = (num.num).lexval T num T.type = integer; T.code = num.lexval第六十三頁，共106頁。 E T E.type = T.type ; E.code = T.code T num.num T.type = real; T.cod

55、e = (num.num).lexval T num T.type = integer; T.code = num.lexval第六十四頁，共106頁。 S t c E t c E t c + T t c E t c + T t c num.num T t c num num 第六十五頁，共106頁。5.5 S L.L | L L L B | B B 0 | 1 (a) 試用各有關(guān)綜合(zngh)屬性決定S.val.引入L的屬性(shxng)b記錄2的L的位數(shù)次冪值S L1.L2 S.val = L1.val +L2.val / L2.b;S L S.val = L.val;L L1 B L.

56、val = L1.val *2 + B.val; L.b = L.b*2;L B L.val = B.val; L.b = 2;B 0 B.val = 0;B 1 B.val = 1;第六十六頁，共106頁。 S val L v . L b v L v B v L b v B v B v 0 L b v B v 1 1 B v 0 1第六十七頁，共106頁。(b) 試用一個(y )語法制導(dǎo)定義來決定S.val, 在這個定義中B僅有綜合 屬性c,給出由B生成的位對于最后的數(shù)值的分擔(dān)額.引入B的繼承屬性(shxng)i, 綜合屬性(shxng)cS L1.L2 L1.i = 20; L2 .i =

57、 2-1; S.val = L1.val +L2.valS L L.i = 20; S.val = L.val;L L1 B if L.i = 20 then begin L1.i = L.i *2 ; B.i = L.i end else begin L1.i = L.i ; L.s = L1.s/2; B.i = L1.s end L.val = L1.val +B.c L B B.i = L.i ; L.s= L.i/2; L.val = B.cB 0 B.c = B.i*0B 1 B.c = B.i*1第六十八頁，共106頁。 S val i L v . i L s vi L v i

58、B c i L s v i B ci B c 0 i L s v i B c 1 1 i B c 0 1第六十九頁，共106頁。5.6 重寫例5.3中語法制導(dǎo)定義的基礎(chǔ)文法(wnf), 使類型信息只需用綜合屬性來傳遞. D T LL L1 , id | idT intT real改寫(gixi)為:D L id addtype(id.entry, L.type)L L1 id, L.type = L1 .type; addtype(id.entry, L1.type)L T L.type = T.typeT int T.type = intT real T.type = real D L id

59、 L id ,T int第七十頁，共106頁。5.7 試從5.4(a)和 (b)中的語法制導(dǎo)定義(dngy)中消除左遞歸.(a) E T F F.it = T.t; E.t = F.t F +TF1 F1.t = F.it and T.t; F.t = F1 .t F F.t = F.it T num.num T.t = false; T num T.t = true; E tTt it F tnum + Tt it F t num.num 第七十一頁，共106頁。(b) E T F F.it = T.t; E.t = F.t; F.ic = T.c; E.c = F.c F +TF1 if

60、F.it = real and T.t = integer then begin F1.it = real; F1.ic = + | F.ic | inttoreal(T.c); end else if F.it = integer and T.t = real then begin F1.it = real; F1.ic = + | inttoreal(F.ic) | T.c; end else begin F1.it = F.it; F1.ic = + | F.ic | T.c; end F.t = F1.it;F.c = F1.ic; F F.t = F.it; F.c = F.ic;