編譯原理_第1-5章習(xí)題課答案

1、編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 chapter1 1、何謂源程序、目標(biāo)程序、翻譯程序、編譯程序、何謂源程序、目標(biāo)程序、翻譯程序、編譯程序 和解釋程序？它們之間可能有何種關(guān)系？和解釋程序？它們之間可能有何種關(guān)系？ 源程序：用源語言編寫的程序。源程序：用源語言編寫的程序。 目標(biāo)程序：源程序經(jīng)翻譯程序過加工處理后生成的程序。目標(biāo)程序：源程序經(jīng)翻譯程序過加工處理后生成的程序。 翻譯程序：將源程序轉(zhuǎn)換為與其邏輯上等價(jià)的目標(biāo)程序。翻譯程序：將源程序轉(zhuǎn)換為與其邏輯上等價(jià)的目標(biāo)程序。 編譯程序：編譯程序： 源語言為高級(jí)語言，目標(biāo)語言為匯編語言或機(jī)源語言為高級(jí)語言，目標(biāo)語言為匯編語言或機(jī)

2、器語言的翻譯程序。器語言的翻譯程序。 解釋程序：解釋程序： 源語言程序作為輸入，但不產(chǎn)生目標(biāo)程序，而源語言程序作為輸入，但不產(chǎn)生目標(biāo)程序，而 是邊解釋邊執(zhí)行源程序本身。是邊解釋邊執(zhí)行源程序本身。 先翻譯后執(zhí)行先翻譯后執(zhí)行 邊解釋邊執(zhí)行邊解釋邊執(zhí)行 執(zhí)行速度快執(zhí)行速度快 有利于程序的調(diào)試有利于程序的調(diào)試 多次運(yùn)算多次運(yùn)算 1次運(yùn)算次運(yùn)算 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 2、一個(gè)典型的編譯系統(tǒng)通常由有哪些部分組成？、一個(gè)典型的編譯系統(tǒng)通常由有哪些部分組成？ 各部分的主要功能是什么？各部分的主要功能是什么？ chapter1 編譯系統(tǒng)編譯系統(tǒng) 編譯程序編譯程序 語法分析語法分析

3、 語義分析與中間代碼生成語義分析與中間代碼生成 優(yōu)化優(yōu)化 目標(biāo)代碼生成目標(biāo)代碼生成 運(yùn)行系統(tǒng)運(yùn)行系統(tǒng) 詞法分析詞法分析 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 語法分析語法分析(Syntax Analysis)： 在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法 短語，如短語，如“程序程序”，“語句語句”，“表達(dá)式表達(dá)式”等等。等等。 語義分析語義分析(Syntactic Analysis)： 語義分析是在語法分析程序確定出語法短語后，審語義分析是在語法分析程序確定出語法短語后，審 查有無語義錯(cuò)誤，并為代碼生成階段收集類型信息。查有無語義錯(cuò)誤，

4、并為代碼生成階段收集類型信息。 chapter1 詞法分析詞法分析(Lexical Analysis)： 從左到右從左到右一個(gè)字符一個(gè)字符的讀入源程序，對(duì)一個(gè)字符一個(gè)字符的讀入源程序，對(duì) 構(gòu)成源程序的字符串進(jìn)行掃描和分解，從而構(gòu)成源程序的字符串進(jìn)行掃描和分解，從而識(shí)別出識(shí)別出 一個(gè)個(gè)單詞一個(gè)個(gè)單詞（也稱單詞符號(hào)或簡(jiǎn)稱符號(hào)）。（也稱單詞符號(hào)或簡(jiǎn)稱符號(hào)）。 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 chapter1 代碼優(yōu)化代碼優(yōu)化(Optimization of code)： 為了使生成的目標(biāo)代碼更為高效，可以對(duì)產(chǎn)生的中為了使生成的目標(biāo)代碼更為高效，可以對(duì)產(chǎn)生的中 間代碼進(jìn)行變換或進(jìn)

5、行改造，這就是代碼的優(yōu)化。間代碼進(jìn)行變換或進(jìn)行改造，這就是代碼的優(yōu)化。 代碼生成代碼生成(Generation of code)： 目標(biāo)代碼生成是編譯器的最后一個(gè)階段。在生成目目標(biāo)代碼生成是編譯器的最后一個(gè)階段。在生成目 標(biāo)代碼時(shí)要考慮以下幾個(gè)問題：標(biāo)代碼時(shí)要考慮以下幾個(gè)問題：計(jì)算機(jī)的系統(tǒng)結(jié)構(gòu)、指計(jì)算機(jī)的系統(tǒng)結(jié)構(gòu)、指 令系統(tǒng)、寄存器的分配以及內(nèi)存的組織令系統(tǒng)、寄存器的分配以及內(nèi)存的組織等。等。 中間代碼生成中間代碼生成(Generation of intermediate code)： 完成語法分析和語義處理工作后，編譯程序?qū)⒃闯掏瓿烧Z法分析和語義處理工作后，編譯程序?qū)⒃闯?序變成一種內(nèi)部表示

6、形式，這種內(nèi)部表示形式叫做中間序變成一種內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間 語言或稱中間代碼，它是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記語言或稱中間代碼，它是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記 號(hào)系統(tǒng)。號(hào)系統(tǒng)。 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 chapter2 1.寫出寫出C語言和語言和Java語言的輸入字母表。語言的輸入字母表。 C語言：語言：09數(shù)字，大小寫英文字母，鍵盤上可見的字符數(shù)字，大小寫英文字母，鍵盤上可見的字符 Java語言：語言：Unicode可以包括的所有字符。可以包括的所有字符。 6.文法文法G6為為: N D|ND D 0|1|2|3|4|5|6|7|8|9 （1）

7、 G6的語言是什么的語言是什么? G6的語言是：的語言是： 09的數(shù)字組成的任意的數(shù)字組成的任意非空非空串串 L(G6)=x|x0,1,2,3,4,5,6,7,8,9+ （2）給出句子）給出句子0127、34和和568的最左和最右推導(dǎo)。的最左和最右推導(dǎo)。 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 7、 寫一文法，使其語言是寫一文法，使其語言是奇數(shù)集奇數(shù)集。 要求：不以要求：不以0打頭。打頭。 復(fù)雜的情況復(fù)雜的情況: :分三部分分三部分 末尾：以末尾：以1|3|5|7|9結(jié)尾結(jié)尾 ( (一位一位):):D 1|3|5|7|9 開頭：除了開頭：除了0的任意數(shù)字的任意數(shù)字 中間部分：空或

8、者任意數(shù)字串中間部分：空或者任意數(shù)字串 D1|3|5|7|9 CCA| A0|B 所以題目要求的文法所以題目要求的文法GNGN可以寫成：可以寫成： N BCD|D D 1|3|5|7|9 B 2|4|6|8|D C CA | A 0 | B B2|4|6|8|D 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 9、證明文法、證明文法: S iSeS | iS | i 是二義的。是二義的。 二義性的含義二義性的含義: :如果文法存在如果文法存在某個(gè)句子某個(gè)句子對(duì)應(yīng)兩棵以上對(duì)應(yīng)兩棵以上 不同的語法樹，或者兩種以上不同的最不同的語法樹，或者兩種以上不同的最 左左/ /右推導(dǎo)，則稱這個(gè)文法是二義

9、的。右推導(dǎo)，則稱這個(gè)文法是二義的。 首先：找到此文法對(duì)應(yīng)的一個(gè)首先：找到此文法對(duì)應(yīng)的一個(gè)句子句子 iiiei 其次：構(gòu)造與之對(duì)應(yīng)的其次：構(gòu)造與之對(duì)應(yīng)的兩棵兩棵語法樹語法樹 S i S e S i S i i S i S i S e S i i 結(jié)論：因?yàn)樵撐姆ù嬖诰渥咏Y(jié)論：因?yàn)樵撐姆ù嬖诰渥觟iieiiiiei對(duì)應(yīng)兩棵對(duì)應(yīng)兩棵 不同的語法樹，因而該文法是二義的。不同的語法樹，因而該文法是二義的。 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 11、給出下面語言的相應(yīng)文法、給出下面語言的相應(yīng)文法 L1=anbnci| n1,i0 G1(S): SAB AaAb|ab BcB| 從從n，i

10、的不同取值來把的不同取值來把L1分成兩部分：分成兩部分： A aAb | ab 前半部分是前半部分是 an bn ： 后半部分是后半部分是 c i ：B Bc | 所以整個(gè)文法所以整個(gè)文法G1S可以寫為：可以寫為： 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 L2=aibncn| n1,i0 G2(S): SAB AaA| BbBc|bc L3=anbnambm| m,n0 G3(S): SAB AaAb| BaBb| 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 L4=1n 0m 1m 0n| n,m0 可以看成是兩部分：可以看成是兩部分： 剩下兩邊的部分就是：剩下兩邊的部

11、分就是： S 1S0 中間部分是中間部分是 0m 1m ： A 0A1 | 所以所以G4S可以寫為：可以寫為： S 1S0 | A A 0A1 | | A 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 chapter3 7.構(gòu)造下列正規(guī)式相應(yīng)的構(gòu)造下列正規(guī)式相應(yīng)的DFA。 步驟步驟: : . .根據(jù)正規(guī)式根據(jù)正規(guī)式畫出畫出對(duì)應(yīng)的對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖; ; . .根據(jù)狀態(tài)轉(zhuǎn)換圖畫出對(duì)應(yīng)的根據(jù)狀態(tài)轉(zhuǎn)換圖畫出對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣; ; . .根據(jù)狀態(tài)轉(zhuǎn)換矩陣得到根據(jù)狀態(tài)轉(zhuǎn)換矩陣得到重命名后的狀態(tài)轉(zhuǎn)換矩陣重命名后的狀態(tài)轉(zhuǎn)換矩陣; ; . .根據(jù)重命名后的狀態(tài)轉(zhuǎn)換矩陣得出最后的根

12、據(jù)重命名后的狀態(tài)轉(zhuǎn)換矩陣得出最后的DFA. . 問題：將狀態(tài)轉(zhuǎn)換圖與問題：將狀態(tài)轉(zhuǎn)換圖與DFA混淆?；煜?。 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 1(0|1)*101 .狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖 a b a d b 1(0|1)*101 a 1 (0|1)* 101 d c ef 1 0 1 1 01 g g g 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 .狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣 II0 I1 ab,c,d b,c,dc,dc,d,e c,dc,dc,d,e c,d,ec,d,fc,d,e c,d,fc,dc,d,e,g c,d,e,gc,d,fc,d,e 1 ab

13、d c ef 1 0 101 g 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 I I0I1 a b,c,d b,c,d c,d c,d,e c,dc,dc,d,e c,d,ec,d,fc,d,e c,d,fc,dc,d,e,g c,d,e,gc,d,fc,d,e . .重命名后的狀態(tài)轉(zhuǎn)換矩陣重命名后的狀態(tài)轉(zhuǎn)換矩陣 S01 A(始態(tài)始態(tài))B BCD C C D D E D E C F(終態(tài)終態(tài)) F(終態(tài)終態(tài))ED AB 1 0C 1D 0 1 0 E 1 0 1 01 F .DFA 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 1(1010*|1(010)*1)*0 ab d

14、 c 1 0 e 0 1 0 1 f gh i 0 1 11 0 j k lm n .狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 .狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 . .重命名后的狀態(tài)轉(zhuǎn)換矩陣重命名后的狀態(tài)轉(zhuǎn)換矩陣.DFA 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 8、給出下面正規(guī)表達(dá)式、給出下面正規(guī)表達(dá)式 （1）以）以01結(jié)尾的二進(jìn)制數(shù)串。結(jié)尾的二進(jìn)制數(shù)串。 (0 | 1)*01 （2）能被）能被5整除的十進(jìn)制數(shù)。整除的十進(jìn)制數(shù)。 0 | 5(0 |5)| (1|2|3|4|5|6|7|8|9)(0|

15、1|2|3|4|5|6|7|8|9)* （4）英文字母組成的所有符號(hào)串，要求符號(hào)串中的）英文字母組成的所有符號(hào)串，要求符號(hào)串中的 字母按字典序排列。字母按字典序排列。 (A | a)* (B | b)* (C | c)* (Z | z)* （3）包含奇數(shù)個(gè)）包含奇數(shù)個(gè)1或奇數(shù)個(gè)或奇數(shù)個(gè)0的二進(jìn)制串的二進(jìn)制串 0*1(0|10*1)*|1*0(0|10*1)* 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 （5）沒有重複出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體）沒有重複出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體 令令ri=i| ,i=0,1,2.9 R0|R1|R2|.|R9記為記為Ri i (0,1,2.,9)

16、 P（0,1,2.,9)表示表示0,1,2.,9的全排列的全排列 ri0ri1.ri9 ri0ri1.ri9 P(0,1,2.,9) 8、給出下面正規(guī)表達(dá)式、給出下面正規(guī)表達(dá)式 （6）最多有一個(gè)重複出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體）最多有一個(gè)重複出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體 i ri0ri1.ri9 i (0,1,2.,9) ri0ri1.ri9 P(0,1,2.,9) （7）不包含字串）不包含字串a(chǎn)bb的由的由a和和b組成的符號(hào)串的全體組成的符號(hào)串的全體 b*(a*|(ba)*)* 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 9、對(duì)下面情況給出、對(duì)下面情況給出DFA及正規(guī)表達(dá)式：及正規(guī)

17、表達(dá)式： （1）0,1上的含有子串上的含有子串010的所有串。的所有串。 正規(guī)式：正規(guī)式：(0 | 1)* 010 (0 | 1)* DFA做法同第做法同第7題。題。 （2） 0,1上不含子串上不含子串010的所有串。的所有串。 正規(guī)式：正規(guī)式：1*(0|11*1)* 1*0*1*(0 | 11)*(0 | 1)1*( 0 | 11)*1* 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 12、將圖、將圖3.18的的(a)和和(b)分別確定化和最少化。分別確定化和最少化。 (a) a a a,b 1 0 .狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣 00,11 1 0,10,11 0 . .重命名后的狀態(tài)

18、轉(zhuǎn)換矩陣重命名后的狀態(tài)轉(zhuǎn)換矩陣 012 2 112 0 0 a 2b a b a .DFA .最小化最小化 0=(0,1,2) 1 0,1a=1 0,1b=2 因此，不能再分因此，不能再分 0 2 b a a 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 023 145 a a a a b b b b b b a a (b) 這道題實(shí)質(zhì)上已經(jīng)是確定化了的，所以我們只需最小化這道題實(shí)質(zhì)上已經(jīng)是確定化了的，所以我們只需最小化 ：2，3，4，5 0，1 2，3，4，5a=0，1，3，5 分屬兩區(qū)，所以分為分屬兩區(qū)，所以分為2，4 3，5 0，1a=1 0，1b=2，4 所以所以 0，1等價(jià)等

19、價(jià) 2，4a=0，1 2，4b=3，5 所以所以2，4等價(jià)等價(jià) 3，5a=3，5 3，5b=2，4 所以所以3，5等價(jià)等價(jià) 所以分為所以分為 0，1 2，4 3，5 023 a a bb b a 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 14、構(gòu)造一個(gè)、構(gòu)造一個(gè)DFA，它接受，它接受=0,1上所有滿足如下上所有滿足如下 條件的字符串：每個(gè)條件的字符串：每個(gè)1都有都有0直接跟在右邊。直接跟在右邊。 思路：先寫出滿足條件的正規(guī)式，由正規(guī)式構(gòu)造思路：先寫出滿足條件的正規(guī)式，由正規(guī)式構(gòu)造 NFA，再把，再把NFA確定化和最小化。確定化和最小化。 滿足條件的正規(guī)式：滿足條件的正規(guī)式：(0|1

20、0)* 01 1 0 yx (0|10)* x y 1 2 1 0 0 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 x y 1 2 1 0 0 確定化：確定化： 給狀態(tài)編號(hào)：給狀態(tài)編號(hào)： 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 0 2 1 0 1 1 0 0 最小化：最小化： 0,1，2 0,10=1 0,11=2 20=0，21= 2或或0,1 所以所以0,1不可分，用狀態(tài)不可分，用狀態(tài)0代表它們代表它們 0 2 1 0 0 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 15、給定右線性文法、給定右線性文法G：求一個(gè)與：求一個(gè)與G等價(jià)的左線性文法。等價(jià)的左線性

21、文法。 S 0S | 1S | 1A | 0B A 1C | 1 B 0C | 0 C 0C | 1C | 0 | 1 S A B CZ 0 0 11 1 0 0 0 1 1 0 1 GZ: Z Z0|Z1|B0|A1 B A0 | 0 A B1 | 1 確定化、最小化后的確定化、最小化后的DFA為：為： S B 0 A 1 10Z 0 1 0,1 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 補(bǔ)充：構(gòu)造一右線性文法，使它與如下文法等價(jià)：補(bǔ)充：構(gòu)造一右線性文法，使它與如下文法等價(jià)： SAB AUT Ua|aU Tb|bT Bc|cB 并根據(jù)所得右線性文法，構(gòu)造出相應(yīng)的狀態(tài)轉(zhuǎn)換圖。并根據(jù)

22、所得右線性文法，構(gòu)造出相應(yīng)的狀態(tài)轉(zhuǎn)換圖。 思路：思路： 先寫出原文法所描述的語言先寫出原文法所描述的語言 L(G)=ambnck|m,n,k1 GS: S aS|aB B bB|bC C cC|c a S a C b c B b c T 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 chapter4 4.1、考慮下面文法、考慮下面文法G1：S a | | （T） T T，S | S （1）消去）消去G1的左遞歸；的左遞歸； S a | | （T） T ST T ，S T | （2）經(jīng)改寫后的文法是否是）經(jīng)改寫后的文法是否是LL(1)文法，給出預(yù)測(cè)分析表。文法，給出預(yù)測(cè)分析表。 經(jīng)改寫后

23、的文法滿足經(jīng)改寫后的文法滿足3個(gè)條件，所以是個(gè)條件，所以是LL(1)的的 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 預(yù)測(cè)分析表構(gòu)造算法預(yù)測(cè)分析表構(gòu)造算法: 1.對(duì)文法中的每個(gè)產(chǎn)生式對(duì)文法中的每個(gè)產(chǎn)生式A 執(zhí)行第二步和第三步執(zhí)行第二步和第三步; FIRST(S)=a,( FIRST(T)=a,( FIRST(T)= , , FOLLOW(S) = ), ,# FOLLOW(T) = ) FOLLOW(T) = ) a（，）# S T T S aS S (T) T STT STT ST T ,STT 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 預(yù)測(cè)分析表構(gòu)造算法預(yù)測(cè)分析表構(gòu)造

24、算法: 1.對(duì)文法中的每個(gè)產(chǎn)生式對(duì)文法中的每個(gè)產(chǎn)生式A 執(zhí)行第二步和第三步執(zhí)行第二步和第三步; 2.對(duì)每個(gè)終結(jié)符對(duì)每個(gè)終結(jié)符a FIRST( ),把把A a加到加到MA,a中中; S a; S ; S (T); T ST; T ,ST T FTRST（a）=a FIRST（）= FIRST（T）=（ FIRST（ST）=a，（，（ FIRST（，（，ST）=，F(xiàn)IRST（）= a（，）# S T T S aS S (T) T STT STT ST T ,ST 3.若若 FIRST( ),則對(duì)于任何則對(duì)于任何b FOLLOW(A)把把A 加至加至MA,b中中 FOLLOW(T)=FOLLOW(T

25、)=) T 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 遞歸子程序：遞歸子程序： procedure S; begin if sym=a or sym= then abvance else if sym=( then begin advance;T; if sym=) then advance; else error; end else error end; 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 procedure T;procedure T; beginbegin S;TS;T EndEnd procedure T;procedure T; beginbegin i

26、f sym=,if sym=, then bengin then bengin advance; advance; S;T S;T end end EndEnd sym:是輸入串指針是輸入串指針I(yè)P所指的符號(hào)所指的符號(hào) advance:是把是把IP調(diào)至下一個(gè)輸入符號(hào)調(diào)至下一個(gè)輸入符號(hào) error:是出錯(cuò)診察程序是出錯(cuò)診察程序 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 補(bǔ)充題：有文法：補(bǔ)充題：有文法： E TE E ATE | T FT T MFT | F （E）| i A + | - M * | / （1）求）求First、Follow集，判斷是否是集，判斷是否是LL（1）文法？）

27、文法？ （2）若是構(gòu)造）若是構(gòu)造LL（1）分析表？）分析表？ （3）簡(jiǎn)述）簡(jiǎn)述LL（1）分析器的工作原理。）分析器的工作原理。 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 4.2：有文法：有文法： E TE E +E | T FT T T | F PF F *F | P (E) |a|b| （1）求）求First、Follow集，判斷是否是集，判斷是否是LL（1）文法？）文法？ （2）若是構(gòu)造）若是構(gòu)造LL（1）分析表？）分析表？ （3）簡(jiǎn)述）簡(jiǎn)述LL（1）分析器的工作原理。）分析器的工作原理。 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 E TE E ATE | T FT

28、 T MFT | F （E）| i A + | - M * | / FIRST(M)=* ， / FIRST(A)=+，- FIRST(F)=(， i FIRST(T)=* ，/ ， FIRST(T)=(， i) FIRST(E)=+ ，- ， FIRST(E)=(， iFOLLOW(E)=# ，) FOLLOW(E)=# ，) FOLLOW(T)= + ，- ，# ，) FOLLOW(T)= + ，- ，# ，) FOLLOW(F)=* ，/ ， + ，- ，# ，) FOLLOW(A)= (， i FOLLOW(M)= (， i E E TE E TE E E ATEE ATE E E T

29、T FT T FT T T-T T MFTT MFT T T FF i F （E） A A +A - M M *M / i+-*/（）# 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題P81.2.對(duì)文法對(duì)文法G: E TE E +E| T FT T T| F PF F *F| P (E)|a|b| 1)FIRST(E)=FIRST(T) =FIRST(F) =FIRST(P) =(,a,b, FIRST(E) =+, FIRST(T) =FIRST(T) = (,a,b, , FIRST(F) =*, FOLLOW(E) =#,)FOLLOW(E) =FOLLOW(E)= #,) FOL

30、LOW(T) =FIRST(E) FOLLOW(E)= +,#,) FOLLOW(T) =FOLLOW(T)= +,#,) FOLLOW(F) =FIRST(T) FOLLOW(T)=(,a,b, , +,#,) FOLLOWF) =FOLLOW(F) =(,a,b, , +,#,) FOLLOW(P) =FIRST(F) FOLLOW(F)= *, (,a,b, , +,#,) 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 2)考慮下列產(chǎn)生式: FIRST(+E)FIRST()=+= FIRST(+E)FOLLOW(E)=+#,)= FIRST(T)FIRST()=(,a,b,= F

31、IRST(T)FOLLOW(T)=(,a,b,+,),#= FIRST(*F)FIRST()=*= FIRST(*F)FOLLOW(F)=*(,a,b,+,),#= FIRST(E)FIRST(a) FIRST(b) FIRST()= 所以,該文法式LL(1)文法. 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 3)預(yù)測(cè)分析表： 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 4)程序程序 procedure E; begin if sym=( or sym=a or sym=b or sym= then begin T; E end else error end procedu

32、re E; begin if sym=+ then begin advance; E end else if sym) and sym# then error end procedure T; begin if sym=( or sym=a or sym=b or sym= then begin F; T end else error end 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 procedure T; begin if sym=( or sym=a or sym=b or sym= then T else if sym=* then error end procedure

33、F; begin if sym=( or sym=a or sym=b or sym= then begin P; F end else error end procedure F; begin if sym=* then begin advance; F end end 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 procedure P; begin if sym=a or sym=b or sym= then advance else if sym=( then begin advance; E; if sym=) then advance else error end else

34、 error end; 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 n4.3下面文法中，那些是下面文法中，那些是LL(1)文法的，說明理由文法的，說明理由 n構(gòu)造不帶回溯的自上而下分析的文法條件構(gòu)造不帶回溯的自上而下分析的文法條件 1. 文法不含左遞歸，文法不含左遞歸， 2. 對(duì)于文法中每一個(gè)非終結(jié)符對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選的各個(gè)產(chǎn)生式的候選 首符集兩兩不相交。即，若首符集兩兩不相交。即，若A 1| 2| n 則則 FIRST( i)FIRST( j) (i j) 3. 對(duì)文法中的每個(gè)非終結(jié)符對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首，若它存在某個(gè)候選首 符集包

35、含符集包含 ，則，則FIRST(A)FOLLOW(A)= 如果一個(gè)文法如果一個(gè)文法G滿足以上條件，則稱該文法滿足以上條件，則稱該文法G為為 LL(1)LL(1)文法文法。 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 4.3.1 SAbc Aa| Bb| 是，滿足三個(gè)條件 4.3.2 SAb Aa|B| Bb| 對(duì)于A不滿足條件3 4.3.3 SABBA Aa| Bb| A、B都不滿足條件3 4.3.4 SaSe|B BbBe| CcCe| d 滿足條件3 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 解題思路：構(gòu)造文法的預(yù)測(cè)分析表，通常應(yīng)當(dāng)按下列步驟進(jìn)行： 1.消除文法的左遞

36、歸（包括所有直接左遞歸和間接左遞歸） 2.對(duì)消除左遞歸后的文法，提取公因子 3.對(duì)經(jīng)過上述改造后的文法，計(jì)算它的每個(gè)非終結(jié)符的FIRST集合和 FOLLOW集合； 4.根據(jù)FIRST集合和FOLLOW集合構(gòu)造預(yù)測(cè)分析表： 第1步對(duì)文法G的每個(gè)產(chǎn)生式A執(zhí)行第1步和第3步； 第2步對(duì)每個(gè)終結(jié)符aFIRST(),把A加至MA,a中； 第3步若 FIRST(),則對(duì)任何b FIRST(A),把A加至MA,b中； 第4步把所有無定義的MA,a標(biāo)上“出錯(cuò)標(biāo)誌” 4.4對(duì)下面的文法： Expr-Expr Expr(Expr)|Var ExprTail ExprTail-Expr| Varid VarTail

37、 VarTail(Expr)| (1)構(gòu)造LL(1)分析表 (2)給出對(duì)句子id- - id(id)分析過程 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 4.4對(duì)下面的文法： Expr-Expr Expr(Expr)|Var ExprTail ExprTail-Expr| Varid VarTail VarTail(Expr)| (1)構(gòu)造LL(1)分析表 (2)給出對(duì)句子id- - id(id)分析過程 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 4.4對(duì)下面的文法： Expr-Expr Expr(Expr)|Var ExprTail ExprTail-Expr| Var

38、id VarTail VarTail(Expr)| (1)構(gòu)造LL(1)分析表 (2)給出對(duì)句子id- - id(id)分析過程 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 (2)給出對(duì)句子id- - id(id)分析過程 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 (2)給出對(duì)句子id- - id(id)分析過程 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 (2)給出對(duì)句子id- - id(id)分析過程 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 (2)給出對(duì)句子id- - id(id)分析過程 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題

39、chapter5 1、令文法、令文法G1為：為： EE+T | T TT*F | F F(E) | i 證明證明E+T*F是它的一個(gè)句型，指出這個(gè)句型的所有是它的一個(gè)句型，指出這個(gè)句型的所有 短語、直接短語和句柄。短語、直接短語和句柄。 E E +T T*F T*F是句型是句型E+T*F相對(duì)于相對(duì)于T的短語的短語 E+T*F句型句型E+T*F相對(duì)于相對(duì)于E的短語的短語 T*F是句型是句型E+T*F相對(duì)于相對(duì)于T的直接短語的直接短語 T*F是句柄是句柄 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 2、考慮下面的表格結(jié)構(gòu)文法、考慮下面的表格結(jié)構(gòu)文法G2： Sa | | (T) T T,S

40、 | S （1）給出）給出(a,(a,a)和和(a,a),(a),a)的最左和最右推導(dǎo)。的最左和最右推導(dǎo)。 (a,(a,a)的最的最左左推導(dǎo)：推導(dǎo)： S (T) (T,S) (S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S) (a,(a,S) (a,(a,a) (a,a),(a),a)的最的最左左推導(dǎo)：推導(dǎo)： S (T) (T,S) (S,S) (T),S) (T,S),S) (T,S,S),S) (S,S,S),S) (T,S),S,S),S) (S,S),S,S),S) (a,S),S,S),S) (a,a),S,S),S) (a,a),S),S) (a,a),a),

41、S) (a,a),a),a) 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 (a,a),(a),a)的最右推導(dǎo)：的最右推導(dǎo)： S (T) (T,S) (S,S) (S,a) (T),a) (T,S,S),S) (S,S,S),S) (T,S),S,S),S) (S,S),S,S),S) (a,S),S,S),S) (a,a),S,S),S) (a,a),S),S) (a,a),a),S) (a,a),a),a) (a,(a,a)的最右推導(dǎo)：的最右推導(dǎo)： S (T) (T,S) (T,(T) (T,(T,S) (T,(T,a) (T,(S,a) (T,(a,a) (S,(a,a) (a,

42、(a,a) 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 2）指出）指出(a,a),(a),a)的規(guī)范歸約及每一步的句柄。的規(guī)范歸約及每一步的句柄。 S (T) T,S a (T) S T,S T,S(T) S a (T) S T,S a S a aSa (S,a),(a),a) STS (T,a),(a),a)aSa (T,S),(a),a) T,STT , S (T),(a),a)(T)S(T) (S,(a),a)S TS (T,(a),a) S (T,S,(a),a) T,STT , S 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 根據(jù)這個(gè)規(guī)范規(guī)約，給出根據(jù)這個(gè)規(guī)范規(guī)約

43、，給出“移進(jìn)移進(jìn)歸約歸約”的過程，的過程， 并給出它的語法樹的自下而上的構(gòu)造過程。并給出它的語法樹的自下而上的構(gòu)造過程。 符號(hào)棧符號(hào)棧 輸入串：輸入串： ( ( ( a , a ) , , ( a ) ) , a ) # S (T) T,S a (T) S T,S T,S(T) S a (T) S T,S a S a ( ( ( a S , T a S S ) T , S T ( a S T ) S ) S T , a S T ) S 歸約規(guī)則歸約規(guī)則句柄句柄 aSa STS aSa T,STT , S (T)S(T) S TS S T,STT , S 編編 譯譯 原原 理理 chapter1

44、5習(xí)習(xí) 題題 3、(1)計(jì)算練習(xí)計(jì)算練習(xí)2文法文法G2的的FIRSTVT和和LASTVT。 G2： Sa | | (T) T T,S | S FIRSTVT(S)= a， ，( FIRSTVT(T)=， ， a， ，( LASTVT(S)=a， ，) LASTVT(T)=， ， a， ，) S （T） （ ） . T T，S ， FIRSTVT(S) . ， a , ， , ， ( . . . T T，S LASTVT(T) ， ， . a ，, ，, ） ，, ， ， . . . . S （T） ( FIRSTVT(T) . ( a, ( , ( ( , ( ， . . . . S （T）L

45、ASTVT(T) ) . a ) , ) , ) ) , ， ) . . . . 對(duì)待特殊地對(duì)待特殊地#,把它看作句型的開始和結(jié)束符把它看作句型的開始和結(jié)束符.根據(jù)根據(jù)#S#同理可得同理可得 # a , # , # ( , . . . # # . a # , # , ） # , . . . # , ) ( a #,)(a = . . . . . . . . . . . . . . . . . . . . . . = . 1 1、文法是算術(shù)文法，且不含、文法是算術(shù)文法，且不含 產(chǎn)生式。產(chǎn)生式。 2 2、由優(yōu)先關(guān)系矩陣可知，任何、由優(yōu)先關(guān)系矩陣可知，任何 兩個(gè)終結(jié)符之間的優(yōu)先關(guān)系不多兩個(gè)終結(jié)符之間的優(yōu)先關(guān)系不多 于一種。于一種。 綜上，該文法是算術(shù)優(yōu)先文法。綜上，該文法是算術(shù)優(yōu)先文法。 編編 譯譯 原原 理理 chapter15習(xí)習(xí) 題題 . ，a（）# ， a ( ) # . . . . . . . . . . . . . . . . . . . . . . 輸入串輸入串(a,(a,a)的算符優(yōu)先過程。的算符優(yōu)先過程。 .( .a ., .( .a ., .a . ) . ) . #aS #(S,(a,a)# . . . . ., . . . .(, (aa)# aS #(S,(S,a)# . . . . . . , (,(a) #