編譯原理_第1~5章習題課答案

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

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

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

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

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

6、形式，這種內(nèi)部表示形式叫做中間序變成一種內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間 語言或稱中間代碼，它是一種結構簡單、含義明確的記語言或稱中間代碼，它是一種結構簡單、含義明確的記 號系統(tǒng)。號系統(tǒng)。 編編 譯譯 原原 理理 chapter15習習 題題 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的最左和最右推導。的最左和最右推導。 編編 譯譯 原原 理理 chapter15習習 題題 7、 寫一文法，使其語言是寫一文法，使其語言是奇數(shù)集奇數(shù)集。 要求：不以要求：不以0打頭。打頭。 復雜的情況復雜的情況: :分三部分分三部分 末尾：以末尾：以1|3|5|7|9結尾結尾 ( (一位一位):):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習習 題題 9、證明文法、證明文法: S iSeS | iS | i 是二義的。是二義的。 二義性的含義二義性的含義: :如果文法存在如果文法存在某個句子某個句子對應兩棵以上對應兩棵以上 不同的語法樹，或者兩種以上不同的最不同的語法樹，或者兩種以上不同的最 左左/ /右推導，則稱這個文法是二義

9、的。右推導，則稱這個文法是二義的。 首先：找到此文法對應的一個首先：找到此文法對應的一個句子句子 iiiei 其次：構造與之對應的其次：構造與之對應的兩棵兩棵語法樹語法樹 S i S e S i S i i S i S i S e S i i 結論：因為該文法存在句子結論：因為該文法存在句子iiieiiiiei對應兩棵對應兩棵 不同的語法樹，因而該文法是二義的。不同的語法樹，因而該文法是二義的。 編編 譯譯 原原 理理 chapter15習習 題題 11、給出下面語言的相應文法、給出下面語言的相應文法 L1=anbnci| n1,i0 G1(S): SAB AaAb|ab BcB| 從從n，i

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

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

12、據(jù)重命名后的狀態(tài)轉換矩陣得出最后的DFA. . 問題：將狀態(tài)轉換圖與問題：將狀態(tài)轉換圖與DFA混淆?；煜?。 編編 譯譯 原原 理理 chapter15習習 題題 1(0|1)*101 .狀態(tài)轉換圖狀態(tài)轉換圖 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習習 題題 .狀態(tài)轉換矩陣狀態(tài)轉換矩陣 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習習 題題 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)轉換矩陣重命名后的狀態(tài)轉換矩陣 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習習 題題 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)轉換圖狀態(tài)轉換圖 編編 譯譯 原原 理理 chapter15習習 題題 .狀態(tài)轉換矩陣狀態(tài)轉換矩陣 編編 譯譯 原原 理理 chapter15習習 題題 . .重命名后的狀態(tài)轉換矩陣重命名后的狀態(tài)轉換矩陣.DFA 編編 譯譯 原原 理理 chapter15習習 題題 8、給出下面正規(guī)表達式、給出下面正規(guī)表達式 （1）以）以01結尾的二進制數(shù)串。結尾的二進制數(shù)串。 (0 | 1)*01 （2）能被）能被5整除的十進制數(shù)。整除的十進制數(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）英文字母組成的所有符號串，要求符號串中的）英文字母組成的所有符號串，要求符號串中的 字母按字典序排列。字母按字典序排列。 (A | a)* (B | b)* (C | c)* (Z | z)* （3）包含奇）包含奇數(shù)個數(shù)個1或奇或奇數(shù)個數(shù)個0的二的二進進制串制串 0*1(0|10*1)*|1*0(0|10*1)* 編編 譯譯 原原 理理 chapter15習習 題題 （5）沒沒有重有重複複出出現(xiàn)現(xiàn)的的數(shù)數(shù)字的字的數(shù)數(shù)字符字符號號串的全串的全體體 令令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ī)表達式、給出下面正規(guī)表達式 （6）最多有一）最多有一個個重重複複出出現(xiàn)現(xiàn)的的數(shù)數(shù)字的字的數(shù)數(shù)字符字符號號串的全串的全體體 i ri0ri1.ri9 i (0,1,2.,9) ri0ri1.ri9 P(0,1,2.,9) （7）不包含字串）不包含字串a(chǎn)bb的由的由a和和b組組成的符成的符號號串的全串的全體體 b*(a*|(ba)*)* 編編 譯譯 原原 理理 chapter15習習 題題 9、對下面情況給出、對下面情況給出DFA及正規(guī)表達式：及正規(guī)表

17、達式： （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習習 題題 12、將圖、將圖3.18的的(a)和和(b)分別確定化和最少化。分別確定化和最少化。 (a) a a a,b 1 0 .狀態(tài)轉換矩陣狀態(tài)轉換矩陣 00,11 1 0,10,11 0 . .重命名后的狀態(tài)轉

18、換矩陣重命名后的狀態(tài)轉換矩陣 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習習 題題 023 145 a a a a b b b b b b a a (b) 這道題實質上已經(jīng)是確定化了的，所以我們只需最小化這道題實質上已經(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等價等價

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

20、)* 01 1 0 yx (0|10)* x y 1 2 1 0 0 編編 譯譯 原原 理理 chapter15習習 題題 x y 1 2 1 0 0 確定化：確定化： 給狀態(tài)編號：給狀態(tài)編號： 編編 譯譯 原原 理理 chapter15習習 題題 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習習 題題 15、給定右線性文法、給定右線性文法G：求一個與：求一個與G等價的左線性文法。等價的左線性文

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習習 題題 補充：構造一右線性文法，使它與如下文法等價：補充：構造一右線性文法，使它與如下文法等價： SAB AUT Ua|aU Tb|bT Bc|cB 并根據(jù)所得右線性文法，構造出相應的狀態(tài)轉換圖。并根據(jù)所

22、得右線性文法，構造出相應的狀態(tài)轉換圖。 思路：思路： 先寫出原文法所描述的語言先寫出原文法所描述的語言 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習習 題題 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)文法，給出預測分析表。文法，給出預測分析表。 經(jīng)改寫后的

23、文法滿足經(jīng)改寫后的文法滿足3個條件，所以是個條件，所以是LL(1)的的 編編 譯譯 原原 理理 chapter15習習 題題 預測分析表構造算法預測分析表構造算法: 1.對文法中的每個產(chǎn)生式對文法中的每個產(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習習 題題 預測分析表構造算法預測分析表構造算

24、法: 1.對文法中的每個產(chǎn)生式對文法中的每個產(chǎn)生式A 執(zhí)行第二步和第三步執(zhí)行第二步和第三步; 2.對每個終結符對每個終結符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( ),則對于任何則對于任何b FOLLOW(A)把把A 加至加至MA,b中中 FOLLOW(T)=FOLLOW(T)

25、=) T 編編 譯譯 原原 理理 chapter15習習 題題 遞歸子程序：遞歸子程序： 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習習 題題 procedure T;procedure T; beginbegin S;TS;T EndEnd procedure T;procedure T; beginbegin if

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

27、法？ （2）若是構造）若是構造LL（1）分析表？）分析表？ （3）簡述）簡述LL（1）分析器的工作原理。）分析器的工作原理。 編編 譯譯 原原 理理 chapter15習習 題題 4.2：有文法：有文法： E TE E +E | T FT T T | F PF F *F | P (E) |a|b| （1）求）求First、Follow集，判斷是否是集，判斷是否是LL（1）文法？）文法？ （2）若是構造）若是構造LL（1）分析表？）分析表？ （3）簡述）簡述LL（1）分析器的工作原理。）分析器的工作原理。 編編 譯譯 原原 理理 chapter15習習 題題 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 TT

29、 FT T FT T T-T T MFTT MFT T T FF i F （E） A A +A - M M *M / i+-*/（）# 編編 譯譯 原原 理理 chapter15習習 題題P81.2.對文法對文法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)= #,) FOLL

30、OW(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習習 題題 2)考慮下列產(chǎn)生式: FIRST(+E)FIRST()=+= FIRST(+E)FOLLOW(E)=+#,)= FIRST(T)FIRST()=(,a,b,= FI

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

32、e 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習習 題題 procedure T; begin if sym=( or sym=a or sym=b or sym= then T else if sym=* then error end procedure F

33、; 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習習 題題 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習習 題題 n4.3下面文法中，那些是下面文法中，那些是LL(1)文法的，說明理由文法的，說明理由 n構造不帶回溯的自上而下分析的文法條件構造不帶回溯的自上而下分析的文法條件 1. 文法不含左遞歸，文法不含左遞歸， 2. 對于文法中每一個非終結符對于文法中每一個非終結符A的各個產(chǎn)生式的候選的各個產(chǎn)生式的候選 首符集兩兩不相交。即，若首符集兩兩不相交。即，若A 1| 2| n 則則 FIRST( i)FIRST( j) (i j) 3. 對文法中的每個非終結符對文法中的每個非終結符A，若它存在某個候選首，若它存在某個候選首 符集包含

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

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

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

38、d VarTail VarTail(Expr)| (1)構造LL(1)分析表 (2)給出對句子id- - id(id)分析過程 編編 譯譯 原原 理理 chapter15習習 題題 (2)給出對句子id- - id(id)分析過程 編編 譯譯 原原 理理 chapter15習習 題題 (2)給出對句子id- - id(id)分析過程 編編 譯譯 原原 理理 chapter15習習 題題 (2)給出對句子id- - id(id)分析過程 編編 譯譯 原原 理理 chapter15習習 題題 (2)給出對句子id- - id(id)分析過程 編編 譯譯 原原 理理 chapter15習習 題題 c

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

40、| S （1）給出）給出(a,(a,a)和和(a,a),(a),a)的最左和最右推導。的最左和最右推導。 (a,(a,a)的最的最左左推導：推導： 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)的最的最左左推導：推導： 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),S

41、) (a,a),a),a) 編編 譯譯 原原 理理 chapter15習習 題題 (a,a),(a),a)的最右推導：的最右推導： 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)的最右推導：的最右推導： 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習習 題題 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習習 題題 根據(jù)這個規(guī)范規(guī)約，給出根據(jù)這個規(guī)范規(guī)約，

43、給出“移進移進歸約歸約”的過程，的過程， 并給出它的語法樹的自下而上的構造過程。并給出它的語法樹的自下而上的構造過程。 符號棧符號棧 輸入串：輸入串： ( ( ( 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 編編 譯譯 原原 理理 chapter15

44、習習 題題 3、(1)計算練習計算練習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）LA

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