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

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

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)： 在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法短語，如短語，如“程序程序”，“語句語句”，“表達式表達式”等等。等等。 語義分析語義分析(Syntactic Analysis)： 語義分析是在語法分析程序確定出語法短語后，審語義分析是在語法分析程序確定出語法短語后，審查有無語義錯誤，并為代碼生成階段收集類型信息。查有無語義錯誤，并為代碼生成階段收集類型信息。 chapter1 詞法分

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

5、化。 代碼生成代碼生成(Generation of code)： 目標代碼生成是編譯器的最后一個階段。在生成目目標代碼生成是編譯器的最后一個階段。在生成目標代碼時要考慮以下幾個問題：標代碼時要考慮以下幾個問題：計算機的系統(tǒng)結(jié)構(gòu)、指計算機的系統(tǒng)結(jié)構(gòu)、指令系統(tǒng)、寄存器的分配以及內(nèi)存的組織令系統(tǒng)、寄存器的分配以及內(nèi)存的組織等。等。 中間代碼生成中間代碼生成(Generation of intermediate code)： 完成語法分析和語義處理工作后，編譯程序?qū)⒃闯掏瓿烧Z法分析和語義處理工作后，編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間序變成一種內(nèi)部表示形式，這種內(nèi)部表示形式叫

6、做中間語言或稱中間代碼，它是一種結(jié)構(gòu)簡單、含義明確的記語言或稱中間代碼，它是一種結(jié)構(gòu)簡單、含義明確的記號系統(tǒng)。號系統(tǒng)。編編 譯譯 原原 理理 chapter15習習題題chapter21.寫出寫出C語言和語言和Java語言的輸入字母表。語言的輸入字母表。C語言：語言：09數(shù)字，大小寫英文字母，鍵盤上可見的字符數(shù)字，大小寫英文字母，鍵盤上可見的字符Java語言：語言：Unicode可以包括的所有字符?？梢园ǖ乃凶址?.文法文法G6為為: N D|ND D 0|1|2|3|4|5|6|7|8|9 （1） G6的語言是什么的語言是什么? G6的語言是：的語言是： 09的數(shù)字組成的任意的數(shù)字組成

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

8、的文法GNGN可以寫成：可以寫成：N BCD|DD 1|3|5|7|9B 2|4|6|8|DC CA |A 0 | BB2|4|6|8|D編編 譯譯 原原 理理 chapter15習習題題9、證明文法、證明文法: S iSeS | iS | i 是二義的。是二義的。二義性的含義二義性的含義: :如果文法存在如果文法存在某個句子某個句子對應(yīng)兩棵以上對應(yīng)兩棵以上不同的語法樹，或者兩種以上不同的最不同的語法樹，或者兩種以上不同的最左左/ /右推導(dǎo)，則稱這個文法是二義的。右推導(dǎo)，則稱這個文法是二義的。首先：找到此文法對應(yīng)的一個首先：找到此文法對應(yīng)的一個句子句子 iiiei其次：構(gòu)造與之對應(yīng)的其次：構(gòu)造

9、與之對應(yīng)的兩棵兩棵語法樹語法樹S i S e S i S i i S i S i S e S i i結(jié)論：因為該文法存在句子結(jié)論：因為該文法存在句子iiieiiiiei對應(yīng)兩棵對應(yīng)兩棵 不同的語法樹，因而該文法是二義的。不同的語法樹，因而該文法是二義的。編編 譯譯 原原 理理 chapter15習習題題11、給出下面語言的相應(yīng)文法、給出下面語言的相應(yīng)文法L1=anbnci| n1,i0 G1(S): SAB AaAb|ab BcB|從從n，i的不同取值來把的不同取值來把L1分成兩部分：分成兩部分：A aAb | ab 前半部分是前半部分是 an bn ： 后半部分是后半部分是 c i ：B B

10、c | 所以整個文法所以整個文法G1S可以寫為：可以寫為：編編 譯譯 原原 理理 chapter15習習題題L2=aibncn| n1,i0G2(S): SAB AaA| BbBc|bcL3=anbnambm| m,n0G3(S): SAB AaAb| BaBb|編編 譯譯 原原 理理 chapter15習習題題L4=1n 0m 1m 0n| n,m0可以看成是兩部分：可以看成是兩部分：剩下兩邊的部分就是：剩下兩邊的部分就是：S 1S0中間部分是中間部分是 0m 1m ：A 0A1 | 所以所以G4S可以寫為：可以寫為： S 1S0 | A A 0A1 | A編編 譯譯 原原 理理 chapt

11、er15習習題題chapter37.構(gòu)造下列正規(guī)式相應(yīng)的構(gòu)造下列正規(guī)式相應(yīng)的DFA。步驟步驟: :. .根據(jù)正規(guī)式根據(jù)正規(guī)式畫出畫出對應(yīng)的對應(yīng)的狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖; ;. .根據(jù)狀態(tài)轉(zhuǎn)換圖畫出對應(yīng)的根據(jù)狀態(tài)轉(zhuǎn)換圖畫出對應(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)換矩陣得出最后的根據(jù)重命名后的狀態(tài)轉(zhuǎn)換矩陣得出最后的DFA. .問題：將狀態(tài)轉(zhuǎn)換圖與問題：將狀態(tài)轉(zhuǎn)換圖與DFA混淆?；煜?。編編 譯譯 原原 理理 chapter15習習題題1(0|1)*101.狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖 abad

12、b1(0|1)*101a1(0|1)*101dcef101101ggg編編 譯譯 原原 理理 chapter15習習題題.狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣II0I1ab,c,db,c,dc,dc,d,ec,dc,dc,d,ec,d,ec,d,fc,d,ec,d,fc,dc,d,e,gc,d,e,gc,d,fc,d,e1abdcef10101g編編 譯譯 原原 理理 chapter15習習題題II0I1ab,c,db,c,dc,dc,d,ec,dc,dc,d,ec,d,ec,d,fc,d,ec,d,fc,dc,d,e,gc,d,e,gc,d,fc,d,e. .重命名后的狀態(tài)轉(zhuǎn)換矩陣重命名后的狀態(tài)轉(zhuǎn)換矩陣

13、S01A(始態(tài)始態(tài))BBCDCCDDEDECF(終態(tài)終態(tài))F(終態(tài)終態(tài))EDAB10C1D010E10101F.DFA編編 譯譯 原原 理理 chapter15習習題題1(1010*|1(010)*1)*0abdc10e0101fghi01110jklmn.狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖 編編 譯譯 原原 理理 chapter15習習題題.狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣II 0I 101,2,31,2,345,9,10,115,9,10,116,122,36,122,3,7,8,132,345,9,10,112,3,7,8,132,3,4,8,10,115,9,10,112,3,4,8,10,112,3,4,

14、8,122,3,5,9,10,112,3,4,8,122,3,4,85,9,10,11,132,3,5,9,10,114,6,122,3,5,9,10,112,3,4,82,3,4,85,9,10,115,9,10,11,136,10,11,122,34,6,122,3,7,8,136,10,11,12122,3,7,8,1312131310,1110,11122,3編編 譯譯 原原 理理 chapter15習習題題. .重命名后的狀態(tài)轉(zhuǎn)換矩陣重命名后的狀態(tài)轉(zhuǎn)換矩陣II 0I 11223445657634784891091112101310111141214613714157151616171

15、7156.DFA編編 譯譯 原原 理理 chapter15習習題題8、給出下面正規(guī)表達式、給出下面正規(guī)表達式（1）以）以01結(jié)尾的二進制數(shù)串。結(jié)尾的二進制數(shù)串。(0 | 1)*01（2）能被）能被5整除的十進制數(shù)。整除的十進制數(shù)。0 | 5(0 |5)| (1|2|3|4|5|6|7|8|9)(0|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的二進制串的二進制

16、串0*1(0|10*1)*|1*0(0|10*1)*編編 譯譯 原原 理理 chapter15習習題題（5）沒有重複出現(xiàn)的數(shù)字的數(shù)字符號串的全體）沒有重複出現(xiàn)的數(shù)字的數(shù)字符號串的全體令令ri=i| ,i=0,1,2.9R0|R1|R2|.|R9記為記為Ri i (0,1,2.,9) P（0,1,2.,9)表示表示0,1,2.,9的全排列的全排列ri0ri1.ri9ri0ri1.ri9 P(0,1,2.,9)8、給出下面正規(guī)表達式、給出下面正規(guī)表達式（6）最多有一個重複出現(xiàn)的數(shù)字的數(shù)字符號串的全體）最多有一個重複出現(xiàn)的數(shù)字的數(shù)字符號串的全體i ri0ri1.ri9 i (0,1,2.,9) ri

17、0ri1.ri9 P(0,1,2.,9)（7）不包含字串）不包含字串a(chǎn)bb的由的由a和和b組成的符號串的全體組成的符號串的全體b*(a*|(ba)*)*編編 譯譯 原原 理理 chapter15習習題題9、對下面情況給出、對下面情況給出DFA及正規(guī)表達式：及正規(guī)表達式：（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*編編

18、譯譯 原原 理理 chapter15習習題題12、將圖、將圖3.18的的(a)和和(b)分別確定化和最少化。分別確定化和最少化。(a)aaa,b10.狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣 I Ia Ib 00,1110,10,110. .重命名后的狀態(tài)轉(zhuǎn)換矩陣重命名后的狀態(tài)轉(zhuǎn)換矩陣 I Ia Ib 012211200a2baba.DFA.最小化最小化0=(0,1,2)10,1a=10,1b=2因此，不能再分因此，不能再分02baa編編 譯譯 原原 理理 chapter15習習題題023145aaaabbbbbbaa(b)這道題實質(zhì)上已經(jīng)是確定化了的，所以我們只需最小化這道題實質(zhì)上已經(jīng)是確定化了的，所以我們

19、只需最小化 ：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等價等價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 023aabbba編編 譯譯 原原 理理 chapter15習習題題14、構(gòu)造一個、構(gòu)造一個DFA，它接受，它接受=0,1上所有滿足如下上所有滿足如下 條件的字符串：每個條件的字符串：每個1都有都有0直接跟在右邊。直接跟在右邊。思路：先寫出滿足條件的正規(guī)式，由

20、正規(guī)式構(gòu)造思路：先寫出滿足條件的正規(guī)式，由正規(guī)式構(gòu)造 NFA，再把，再把NFA確定化和最小化。確定化和最小化。滿足條件的正規(guī)式：滿足條件的正規(guī)式：(0|10)*0110yx(0|10)*xy12100編編 譯譯 原原 理理 chapter15習習題題xy12100確定化：確定化：0 01 1X,1,YX,1,Y1,Y1,Y221,Y1,Y1,Y1,Y22221,Y1,Y給狀態(tài)編號：給狀態(tài)編號：0 01 10 01 12 21 11 12 22 21 1編編 譯譯 原原 理理 chapter15習習題題02101100最小化：最小化：0,1，20,10=1 0,11=220=0，21= 2或或0

21、,1所以所以0,1不可分，用狀態(tài)不可分，用狀態(tài)0代表它們代表它們02100編編 譯譯 原原 理理 chapter15習習題題15、給定右線性文法、給定右線性文法G：求一個與：求一個與G等價的左線性文法。等價的左線性文法。S 0S | 1S | 1A | 0BA 1C | 1B 0C | 0C 0C | 1C | 0 | 1SABCZ001110001101GZ:Z Z0|Z1|B0|A1B A0 | 0A B1 | 1確定化、最小化后的確定化、最小化后的DFA為：為：SB0A110Z010,1編編 譯譯 原原 理理 chapter15習習題題補充：構(gòu)造一右線性文法，使它與如下文法等價：補充：構(gòu)

22、造一右線性文法，使它與如下文法等價： SAB AUT Ua|aU Tb|bT Bc|cB 并根據(jù)所得右線性文法，構(gòu)造出相應(yīng)的狀態(tài)轉(zhuǎn)換圖。并根據(jù)所得右線性文法，構(gòu)造出相應(yīng)的狀態(tài)轉(zhuǎn)換圖。思路：思路： 先寫出原文法所描述的語言先寫出原文法所描述的語言 L(G)=ambnck|m,n,k1GS: S aS|aB B bB|bC C cC|caSaCbcBbcT編編 譯譯 原原 理理 chapter15習習題題chapter44.1、考慮下面文法、考慮下面文法G1：S a | | （T） T T，S | S（1）消去）消去G1的左遞歸；的左遞歸；S a | | （T）T STT ，S T |（2）經(jīng)改寫

23、后的文法是否是）經(jīng)改寫后的文法是否是LL(1)文法，給出預(yù)測分析表。文法，給出預(yù)測分析表。經(jīng)改寫后的文法滿足經(jīng)改寫后的文法滿足3個條件，所以是個條件，所以是LL(1)的的編編 譯譯 原原 理理 chapter15習習題題預(yù)測分析表構(gòu)造算法預(yù)測分析表構(gòu)造算法: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 STT ,STT 編編

24、 譯譯 原原 理理 chapter15習習題題預(yù)測分析表構(gòu)造算法預(yù)測分析表構(gòu)造算法:1.對文法中的每個產(chǎn)生式對文法中的每個產(chǎn)生式A 執(zhí)行第二步和第三步執(zhí)行第二步和第三步;2.對每個終結(jié)符對每個終結(jié)符a FIRST( ),把把A a加到加到MA,a中中;S a; S ; S (T); T ST; T ,ST T FTRST（a）=aFIRST（）=FIRST（T）=（ FIRST（ST）=a，（，（FIRST（，（，ST）=，F(xiàn)IRST（）= a（，）#S T T S aS S (T)T STT STT STT ,ST3.若若 FIRST( ),則對于任何則對于任何b FOLLOW(A)把把A

25、加至加至MA,b中中FOLLOW(T)=FOLLOW(T)=)T 編編 譯譯 原原 理理 chapter15習習題題遞歸子程序：遞歸子程序：procedure S;beginif sym=a or sym= then abvance else if sym=( then beginadvance;T;if sym=) then advance; else error; endelse errorend;編編 譯譯 原原 理理 chapter15習習題題procedure T;procedure T;beginbeginS;TS;TEndEndprocedure T;procedure T;be

26、ginbeginif sym=,if sym=, then bengin then bengin advance; advance; S;T S;T end endEndEndsym:是輸入串指針是輸入串指針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）若是構(gòu)造）若是構(gòu)造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）若是構(gòu)造）若是構(gòu)造LL（1）分析表？）分析表？（3）簡述）簡述LL（1）分析器的工作原理。）分析器的工作原理。編編 譯譯 原原 理理 chapter15習習題題E TEE ATE |T FTT MFT |F （E

28、）| iA + | -M * | /FIRST(M)=* ， /FIRST(A)=+，- FIRST(F)=(， iFIRST(T)=* ，/ ， FIRST(T)=(， i)FIRST(E)=+ ，- ， FIRST(E)=(， iFOLLOW(E)=# ，)FOLLOW(E)=# ，)FOLLOW(T)= + ，- ，# ，)FOLLOW(T)= + ，- ，# ，)FOLLOW(F)=* ，/ ， + ，- ，# ，) FOLLOW(A)= (， iFOLLOW(M)= (， iEE TE E TE E E ATEE ATE E E TT FT T FT T T-T T MFTT MFT

29、 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)= #,)FOLLOW(T) =FIRST(E) FOLLOW(E)= +,#

30、,)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, , +,#,) (ab+*)#EE TEE TEETEETEEE+EE E TTFTTFTTFTTFTTTTTTTTTTT T T FFPFFPFFPFFPFFF F F F F FFF F PP(E)PaPbP編編 譯譯 原原 理理 chapter15習習題題 2)考慮下列產(chǎn)生式: FIRST(+E

31、)FIRST()=+= FIRST(+E)FOLLOW(E)=+#,)= FIRST(T)FIRST()=(,a,b,= FIRST(T)FOLLOW(T)=(,a,b,+,),#= FIRST(*F)FIRST()=*= FIRST(*F)FOLLOW(F)=*(,a,b,+,),#= FIRST(E)FIRST(a) FIRST(b) FIRST()= 所以,該文法式LL(1)文法.編編 譯譯 原原 理理 chapter15習習題題(ab+*)#EETEE TEETEETEEE+EE E TTFTTFTTFTTFTTTTTTTTTTT T T FFPFFPFFPFFPFFF F F F F

32、 FFF F PP(E)PaPbP3)預(yù)測分析表：編編 譯譯 原原 理理 chapter15習習題題4)程序程序procedure E;beginif sym=( or sym=a or sym=b or sym= then begin T; E end else errorendprocedure E;beginif sym=+ then begin advance; E end else if sym) and sym# then errorendprocedure T;beginif sym=( or sym=a or sym=b or sym= then begin F; T end

33、else errorend編編 譯譯 原原 理理 chapter15習習題題procedure T;beginif sym=( or sym=a or sym=b or sym= then T else if sym=* then errorendprocedure F;beginif sym=( or sym=a or sym=b or sym= then begin P; F end else errorendprocedure F;beginif sym=* then begin advance; F endend 編編 譯譯 原原 理理 chapter15習習題題procedure P

34、;beginif sym=a or sym=b or sym= then advance else if sym=( thenbeginadvance; E;if sym=) then advance else errorendelse errorend;編編 譯譯 原原 理理 chapter15習習題題n4.3下面文法中，那些是下面文法中，那些是LL(1)文法的，說明理由文法的，說明理由n構(gòu)造不帶回溯的自上而下分析的文法條件構(gòu)造不帶回溯的自上而下分析的文法條件 1. 文法不含左遞歸，文法不含左遞歸， 2. 對于文法中每一個非終結(jié)符對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選的各個產(chǎn)生式的候選

35、首符集兩兩不相交。即，若首符集兩兩不相交。即，若A 1| 2| n 則則 FIRST( i)FIRST( j) (i j) 3. 對文法中的每個非終結(jié)符對文法中的每個非終結(jié)符A，若它存在某個候選首，若它存在某個候選首符集包含符集包含 ，則，則FIRST(A)FOLLOW(A)= 如果一個文法如果一個文法G滿足以上條件，則稱該文法滿足以上條件，則稱該文法G為為LL(1)LL(1)文法文法。編編 譯譯 原原 理理 chapter15習習題題4.3.1SAbcAa| Bb| 是，滿足三個條件4.3.2SAbAa|B| Bb| 對于A不滿足條件34.3.3SABBAAa| Bb| A、B都不滿足條件3

36、4.3.4SaSe|BBbBe| CcCe| d滿足條件3編編 譯譯 原原 理理 chapter15習習題題解題思路：構(gòu)造文法的預(yù)測分析表，通常應(yīng)當按下列步驟進行： 1.消除文法的左遞歸（包括所有直接左遞歸和間接左遞歸） 2.對消除左遞歸后的文法，提取公因子 3.對經(jīng)過上述改造后的文法，計算它的每個非終結(jié)符的FIRST集合和FOLLOW集合； 4.根據(jù)FIRST集合和FOLLOW集合構(gòu)造預(yù)測分析表： 第1步對文法G的每個產(chǎn)生式A執(zhí)行第1步和第3步； 第2步對每個終結(jié)符aFIRST(),把A加至MA,a中； 第3步若 FIRST(),則對任何b FIRST(A),把A加至MA,b中； 第4步把所

37、有無定義的MA,a標上“出錯標誌” 4.4對下面的文法：Expr-ExprExpr(Expr)|Var ExprTailExprTail-Expr| Varid VarTailVarTail(Expr)| (1)構(gòu)造LL(1)分析表(2)給出對句子id- - id(id)分析過程編編 譯譯 原原 理理 chapter15習習題題 4.4對下面的文法：Expr-ExprExpr(Expr)|Var ExprTailExprTail-Expr| Varid VarTailVarTail(Expr)| (1)構(gòu)造LL(1)分析表(2)給出對句子id- - id(id)分析過程解答：FIRST(Exp

38、r)=-,(,id FOLLOW(Expr)=),# FIRST(ExprTail)=-, FOLLOW(ExprTail)=),# FIRST(Var)=idFOLLOW(Var)=-,),# FIRST(VarTail)=(,FOLLOW(VarTail)=-,),# 編編 譯譯 原原 理理 chapter15習習題題 4.4對下面的文法：Expr-ExprExpr(Expr)|Var ExprTailExprTail-Expr| Varid VarTailVarTail(Expr)| (1)構(gòu)造LL(1)分析表(2)給出對句子id- - id(id)分析過程-id()#ExprExpr-

39、ExprExprVar ExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVarid VarTailVarTailVarTail VarTail(Expr)VarTail VarTail 編編 譯譯 原原 理理 chapter15習習題題-id()#ExprExpr-ExprExprVar ExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVarid VarTailVarTailVarTail VarTail(Expr)VarTail VarTail 步驟符號

40、棧輸入串所用產(chǎn)生式0#Exprid- -id(id)#開始1#ExprTail varid- -id(id)#ExprVar ExprTail2#ExprTail varTail idid- -id(id)#Varid VarTail3#ExprTail varTail- -id(id)#出棧，輸入串後移4#ExprTail - -id(id)#VarTail 5#Expr - - -id(id)#ExprTail-Expr(2)給出對句子id- - id(id)分析過程編編 譯譯 原原 理理 chapter15習習題題-id()#ExprExpr-ExprExprVar ExprTailEx

41、pr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVarid VarTailVarTailVarTail VarTail(Expr)VarTail VarTail 步驟符號棧輸入串所用產(chǎn)生式5#Expr - - -id(id)#ExprTail-Expr6#Expr-id(id)#出棧，輸入串後移7#Expr - -id(id)#Expr-Expr8#Exprid(id)#出棧，輸入串後移9#ExprTail Var id(id)#ExprVar ExprTail10#ExprTail VarTail id id(id)#Varid VarTai

42、l11#ExprTail VarTail(id)#出棧，輸入串後移(2)給出對句子id- - id(id)分析過程編編 譯譯 原原 理理 chapter15習習題題-id()#ExprExpr-ExprExprVar ExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVarid VarTailVarTailVarTail VarTail(Expr)VarTail VarTail 步驟符號棧輸入串所用產(chǎn)生式11#ExprTail VarTail(id)#出棧，輸入串後移12#ExprTail )Expr(id)#VarTail(

43、Expr)13#ExprTail )Expr(id)#出棧，輸入串後移14#ExprTail ) )Expr(id)#Expr(Expr)15#ExprTail ) )Exprid)#出棧，輸入串後移16#ExprTail ) ) ExprTail Varid)#ExprVar ExprTail17#ExprTail ) ) ExprTail VarTail idid)#Varid VarTail(2)給出對句子id- - id(id)分析過程編編 譯譯 原原 理理 chapter15習習題題-id()#ExprExpr-ExprExprVar ExprTailExpr(Expr)ExprTa

44、iExprTail-ExprExprTail ExprTail VarVarid VarTailVarTailVarTail VarTail(Expr)VarTail VarTail 步驟符號棧輸入串所用產(chǎn)生式17#ExprTail ) ) ExprTail VarTail idid)#Varid VarTail18#ExprTail ) ) ExprTail VarTail)#出棧，輸入串後移19#ExprTail ) ) ExprTail)#VarTail 20#ExprTail ) )#ExprTail 21#ExprTail )#出棧，輸入串後移22# ExprTail#出棧，輸入串後

45、移23#ExprTail 成功(2)給出對句子id- - id(id)分析過程編編 譯譯 原原 理理 chapter15習習題題chapter51、令文法、令文法G1為：為： EE+T | T TT*F | F F(E) | i 證明證明E+T*F是它的一個句型，指出這個句型的所有是它的一個句型，指出這個句型的所有短語、直接短語和句柄。短語、直接短語和句柄。EE+TT*FT*F是句型是句型E+T*F相對于相對于T的短語的短語E+T*F句型句型E+T*F相對于相對于E的短語的短語T*F是句型是句型E+T*F相對于相對于T的直接短語的直接短語T*F是句柄是句柄編編 譯譯 原原 理理 chapter

46、15習習題題2、考慮下面的表格結(jié)構(gòu)文法、考慮下面的表格結(jié)構(gòu)文法G2： Sa | | (T) T T,S | 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,

47、S),S,S),S) (a,a),S,S),S) (a,a),S),S) (a,a),a),S) (a,a),a),a)編編 譯譯 原原 理理 chapter15習習題題(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)

48、 (T,(T,a) (T,(S,a) (T,(a,a) (S,(a,a) (a,(a,a)編編 譯譯 原原 理理 chapter15習習題題2）指出）指出(a,a),(a),a)的規(guī)范歸約及每一步的句柄。的規(guī)范歸約及每一步的句柄。S(T)T,Sa(T)ST,ST,S(T)Sa(T)ST,SaSa句型句型句柄句柄歸約規(guī)則歸約規(guī)則(a,a),(a),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)STS(T,(a),a)S(T,S,(a),a)T,STT , S(T,(a),a)aS

49、a(T,(S),a)STS(T,(T),a)(T)S(T)(T, S),a)T,STT , S(T),a)TS(T )(S,a)STS(T,a)aSa(T,S) T,STT , S(T)(T)S(T)S編編 譯譯 原原 理理 chapter15習習題題根據(jù)這個規(guī)范規(guī)約，給出根據(jù)這個規(guī)范規(guī)約，給出“移進移進歸約歸約”的過程，的過程，并給出它的語法樹的自下而上的構(gòu)造過程。并給出它的語法樹的自下而上的構(gòu)造過程。 #符號棧符號棧輸入串：輸入串：( ( ( a , a ) , , ( a ) ) , a ) # S(T)T,Sa(T)ST,ST,S(T)Sa(T)ST,SaSa(aS,TaSS)T, S

50、T(a S T)S)S T,a ST)S歸約規(guī)則歸約規(guī)則句柄句柄aSaSTSaSaT,STT , S(T)S(T)STSST,STT , S編編 譯譯 原原 理理 chapter15習習題題3、(1)計算練習計算練習2文法文法G2的的FIRSTVT和和LASTVT。 G2： Sa | | (T) T T,S | SFIRSTVT(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 ，, ，

51、, ） ，, ， ，.S （T） ( FIRSTVT(T). ( a, ( , ( ( , ( ，.S （T）LASTVT(T) ). a ) , ) , ) ) , ， ) .對待特殊地對待特殊地#,把它看作句型的開始和結(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)系矩陣可知，任何兩個終結(jié)符之間的優(yōu)先關(guān)系不多兩個終結(jié)符之間的優(yōu)先關(guān)系不多于一種。于一種。綜上，該

52、文法是算術(shù)優(yōu)先文法。綜上，該文法是算術(shù)優(yōu)先文法。編編 譯譯 原原 理理 chapter15習習題題. ，a（）#， a ( ) # .輸入串輸入串(a,(a,a)的算符優(yōu)先過程。的算符優(yōu)先過程。步驟步驟句型句型優(yōu)先關(guān)系優(yōu)先關(guān)系最左素最左素短語短語規(guī)約規(guī)約符號符號1#(a,(a,a)#2345678.(.a.,.(.a.,.a.).).#aS#(S,(a,a)#.,.(,(aa)#aS#(S,(S,a)#.,(,(a)#.aS#(S,(S,S)#.,(,(.)#.(,(#.)#S,ST#(S,(T)#.(T)S#(S,S)#.(,.)#.S,ST#(T)#.(.)#.(T)S#S#確認！確認！問題：沒有依據(jù)最左素短語進行規(guī)約問題：沒有依據(jù)最左素短語進行規(guī)約編編 譯譯 原原 理理 chapter15習習題題P134-5考慮文法SAS|b ASA|a1、列出這個文法的所有