1、第一章 編譯程序概述1.1 什么是編譯程序編譯程序是現代計算機系統的基本組成部分之一，而且多數計算機系統都含有不止一個高級語言的編譯程序。對有些高級語言甚至配置了幾個不同性能的編譯程序。1.2編譯過程概述和編譯程序的結構編譯程序完成從源程序到目標程序的翻譯工作，是一個復雜的整體的過程。從概念上來講，一個編譯程序的整個工作過程是劃分成階段進行的，每個階段將源程序的一種表示形式轉換成另一種表示形式，各個階段進行的操作在邏輯上是緊密連接在一起的。一般一個編譯過程劃分成詞法分析、語法分析、語義分析、中間代碼生成，代碼優化和目標代碼生成六個階段,這是一種典型的劃分方法。事實上，某些階段可能組合在一起，這

2、些階段間的源程序的中間表示形式就沒必要構造出來了。我們將分別介紹各階段的任務。另外兩個重要的工作：表格管理和出錯處理與上述六個階段都有聯系。編譯過程中源程序的各種信息被保留在種種不同的表格里，編譯各階段的工作都涉及到構造、查找或更新有關的表格，因此需要有表格管理的工作；如果編譯過程中發現源程序有錯誤，編譯程序應報告錯誤的性質和錯誤發生的地點，并且將錯誤所造成的影響限制在盡可能小的范圍內，使得源程序的其余部分能繼續被編譯下去，有些編譯程序還能自動校正錯誤，這些工作稱之為出錯處理。圖1.3表示了編譯的各個階段。圖1.3 編譯的各個階段1.3 高級語言解釋系統為了實現在一個計算機上運行高級語言的程序

3、,主要有兩個途徑：第一個途徑是把該程序翻譯為這個計算機的指令代碼序列，這就是我們已經描述的編譯過程。第二個途徑是編寫一個程序，它解釋所遇到的高級語言程序中的語句并且完成這些語句的動作，這樣的程序就叫解釋程序。從功能上說，一個解釋程序能讓計算機執行高級語言。它與編譯程序的主要不同是它不生成目標代碼，它每遇到一個語句，就要對這個語句進行分析以決定語句的含義，執行相應的動作。右面的圖示意了它的工作機理第二章：PL/0編譯程序問答第1題PL/0語言允許過程嵌套定義和遞歸調用，試問它的編譯程序如何解決運行時的存儲管理。答:PL/0語言允許過程嵌套定義和遞歸調用，它的編譯程序在運行時采用了棧式動態存儲管理

4、。（數組CODE存放的只讀目標程序，它在運行時不改變。）運行時的數據區S是由解釋程序定義的一維整型數組，解釋執行時對數據空間S的管理遵循后進先出規則，當每個過程(包括主程序)被調用時，才分配數據空間，退出過程時，則所分配的數據空間被釋放。應用動態鏈和靜態鏈的方式分別解決遞歸調用和非局部變量的引用問題。問答第2題 若PL/0編譯程序運行時的存儲分配策略采用棧式動態分配，并用動態鏈和靜態鏈的方式分別解決遞歸調用和非局部變量的引用問題，試寫出下列程序執行到賦值語句b=10時運行棧的布局示意圖。 var x,y; procedure p; var a; procedure q;var b; begin

5、 (q) b=10; end (q); procedure s; var c,d;procedure r; var e,f; begin (r) call q; end (r); begin (s) call r; end (s);begin (p)call s; end (p); begin (main)call p; end (main).答：程序執行到賦值語句b=10時運行棧的布局示意圖為：問答第3題寫出題2中當程序編譯到r的過程體時的名字表table的內容。namekindlevel/valadrsize     答題2中當程序編譯到r

6、的過程體時的名字表table的內容為：namekindlevel/valadrsizexvariable0dx yvariable0dx+1 pprocedure0過程p的入口（待填）5avariable1dx qprocedure1過程q的入口4sprocedure1過程s的入口（待填）5cvariable2dx dvariable2dx rprocedure2過程r的入口5evariable3dx fvariable3dx+1 注意：q和s是并列的過程，所以q定義的變量b被覆蓋。問答第4題指出棧頂指針T，最新活動記錄基地

7、址指針B，動態鏈指針DL，靜態鏈指針SL與返回地址RA的用途。答：棧頂指針T，最新活動記錄基地址指針B，動態鏈指針DL，靜態鏈指針SL與返回地址RA的用途說明如下： T： 棧頂寄存器T指出了當前棧中最新分配的單元(T也是數組S的下標)。B：基址寄存器，指向每個過程被調用時，在數據區S中給它分配的數據段起 始 地址，也稱基地址。SL： 靜態鏈，指向定義該過程的直接外過程（或主程序）運行時最新數據段的基地址，用以引用非局部（包圍它的過程）變量時，尋找該變量的地址。DL： 動態鏈，指向調用該過程前正在運行過程的數據段基地址，用以過程執行結束釋放數據空間時，恢復調用該過程前運行棧的狀態。 RA： 返回

8、地址，記錄調用該過程時目標程序的斷點，即調用過程指令的下一條指令的地址，用以過程執行結束后返回調用過程時的下一條指令繼續執行。在每個過程被調用時在棧頂分配3個聯系單元，用以存放SL，DL， RA。問答第5題PL/0編譯程序所產生的目標代碼是一種假想棧式計算機的匯編語言，請說明該匯編語言中下列指令各自的功能和所完成的操作。· INT 0 A · OPR 0 0 · CAL L A答：PL/0編譯程序所產生的目標代碼中有3條非常重要的特殊指令，這3條指令在code中的位置和功能以及所完成的操作說明如下：INT 0 A在過程目標程序的入口處，開辟A個單元的數據段。A為局

9、部變量的個數+3。 OPR 0 0在過程目標程序的出口處，釋放數據段（退棧），恢復調用該過程前正在運行的過程的數據段基址寄存器B和棧頂寄存器T的值，并將返回地址送到指令地址寄存器P中，以使調用前的程序從斷點開始繼續執行。CAL L A調用過程，完成填寫靜態鏈、動態鏈、返回地址，給出被調用過程的基地址值，送入基址寄存器B中，目標程序的入口地址A的值送指令地址寄存器P中，使指令從A開始執行。問答第6題給出對PL/0語言作如下功能擴充時的語法圖和EBNF的語法描述。(1) 擴充條件語句的功能使其為： if條件then語句else語句(2) 擴充repeat語句為：repeat語句；語句until條件

10、答：對PL/0語言作如下功能擴充時的語法圖和EBNF的語法描述如下： (1) 擴充條件語句的語法圖為：EBNF的語法描述為： 條件語句:= if條件then語句else語句 (2) 擴充repeat語句的語法圖為： EBNF的語法描述為： 重復語句:= repeat語句；語句until條件 第三章：詞法分析程序問答第1題構造正規式1(0|1)*101相應的DFA.答：先構造NFA：用子集法將NFA確定化 .01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他狀態，令AB為B、AC為C、ABY為D，因為D含有Y（NFA的終態），所以D為終態。.01X.AAABBCBC

11、ADDCBDFA的狀態圖：:問答第2題將下圖確定化：解：用子集法將NFA確定化： .01SVQQUVQVZQUQUVQUZVZZZVZ.QUZVZQUZZZZ重新命名狀態子集，令VQ為A、QU為B、VZ為C、V為D、QUZ為E、Z為F。.01SABACBBDECFFDF.ECEFFFDFA的狀態圖：問答第3題將下圖的（a）和（b）分別確定化和最小化：解： 初始分劃得0：終態組0，非終態組1,2,3,4,5 對非終態組進行審查： 1,2,3,4,5a 0,1,3,5而0,1,3,5既不屬于0，也不屬于1,2,3,4,5 4 a 0，所以得到新分劃 1：0，4，1,2,3,5 對1,2,3,5進行

12、審查：1,5 b 42,3 b 1,2,3,5，故得到新分劃 2：0，4，1, 5，2,31, 5 a 1, 5 2,3 a 1,3，故狀態2和狀態3不等價，得到新分劃3：0，2，3，4，1, 5 這是最后分劃了最小DFA：問答第4題構造一個DFA，它接收=0,1上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。并給出該語言的正規式。解：按題意相應的正規表達式是(0*10)*0*，或0*(0 | 10)*0* 構造相應的DFA，首先構造NFA為用子集法確定化：II0I1X,0,1,3,Y0,1,3,Y21,3,Y0,1,3,Y0,1,3,Y1,3,Y1,3,Y222重新命名狀態集：S011

13、2342244333 DFA的狀態圖：可將該DFA最小化：終態組為1,2,4，非終態組為3，1,2,40 1,2,4，1,2,41 3，所以1,2,4為等價狀態，可合并。 第四章 文法和語言問答第1題寫一文法，使其語言是偶正整數的集合。 要求：(1) 允許0打頭； (2)不允許0打頭。答 ：(1)允許0開頭的偶正整數集合的文法ENT|DTNT|DND|1|3|5|7|9D0|2|4|6|8(2)不允許0開頭的偶正整數集合的文法ENT|D TFT|G ND|1|3|5|7|9D2|4|6|8FN|0GD|0問答第2題證明下述文法G表達式是二義的。 表達式=a|(表達式)|表達式運算符表達式 運算

14、符=+|-|*|/答：可為句子a+a*a構造兩個不同的最右推導:最右推導1 表達式表達式運算符表達式表達式運算符a 表達式* a 表達式運算符表達式* a 表達式運算符a * a 表達式+ a * a a + a * a最右推導2 表達式表達式運算符表達式表達式運算符表達式運算符表達式表達式運算符表達式運算符 a 表達式運算符表達式 * a 表達式運算符a * a 表達式+ a * a a + a * a問答第3題令文法GE為： ET|E+T|E-TTF|T*F|T/FF(E)|i 證明E+T*F是它的一個句型，指出這個句型的所有短語、直接短語和句柄。答：因為存在推導序列: E E+T E +

15、 * F 所以 E+T*F是文法GE的一個句型句型 E+T*F的短語有:E+T*F,T*F 直接短語有:T*F 句柄為:T*F問答第4題給出生成下述語言的上下文無關文法：（1） anbnambm| n，m>=0 （2） 1n0m 1m0n| n，m>=0答： (1)SAA AaAb| (2) S1S0|A A0A1|問答第5題給出生成下述語言的三型文法： (1) anbm|n,m>=1 (2)anbmck|n,m,k>=0 答： (1)SaA AaA|B BbB|b (2)AaA|B BbB|C CcC|問答第6題給出下述文法所對應的正規式： S0A|1BA1S|1 B

16、0S|0答：R = (01 | 10) ( 01 | 10 )*第五章 自頂向下語法分析方法問答第1題對文法GS Sa|(T)TT,S|S (1) 給出(a,(a,a)和(a,a),(a),a)的最左推導。(2) 對文法G，進行改寫，然后對每個非終結符寫出不帶回溯的遞歸子程序。 (3) 經改寫后的文法是否是LL(1)的?給出它的預測分析表。(4) 給出輸入串(a,a)#的分析過程，并說明該串是否為G的句子。答：文法Sa|(T) TT,S|S (1) 對(a,(a,a)的最左推導為：S(T) (T,S) (S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S) (a,(a,S)

17、(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) (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),(T),S) (a,a),(S),S) (a,a),(a),S) (a,a),(a),a)(2) 改寫文法為： 0) Sa 1) S 2) S( T ) 3) TS N4) N, S N5) N 非終結符FIRST集FOLLOW集Sa,(#,)Ta,().N

18、,.).對左部為N的產生式可知：FIRST （, S N）=，FIRST （）=FOLLOW （N）=) 由于SELECT(N , S N)SELECT(N ) =， )=所以文法是LL(1)的。 預測分析表（Predicting Analysis Table） a(),#Sa(T)   TS NS NS N   N   , S N 也可由預測分析表中無多重入口判定文法是LL(1)的。(3) 對輸入串（a,a）#的分析過程為：棧（STACK）當前輸入符（CUR_CHAR）剩余輸入符（I

19、NOUT_STRING）所用產生式（OPERATION）#S #)T(#)T #)NS #)Na#)N#)NS,#)NS #)Na#)N#)#(aaa,aa)#a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.a)#.)#.)#.#.#.S(T).TSNSa.N,SN.Sa.N可見輸入串（a,a）#是文法的句子。問答第2題已知文法GS：SMH|a HLSo|KdML|LeHfMK|bLM判斷G是否是LL(1)文法，如果是，構造LL(1)分析表。答：文法：SMH|aHLSo| KdML|LeHfMK|bLM 展開為：0） SM H1） Sa2） HL S o 3） H 4） Kd M

20、 L 5） K6） Le H f 7） MK 8） Mb L M 非終結符FIRST集FOLLOW集Sa,d,b,e#,o.Md,b.e,#,o.H,e.#,f,o.Le.a,d,b,e,o,#Kd,.e,#,o.對相同左部的產生式可知： SELECT(SM H)SELECT(Sa) = d,b ,e，#,o a =SELECT(HL S o)SELECT(H) = e #,f,o =SELECT(Kd M L)SELECT(K) = d e,#,o =SELECT(MK)SELECT(Mb L M) = d，e,#,o b =所以文法是LL(1)的。預測分析表（Predicting Anal

21、ysis Table） aodefb#SaMHMHMH MHMHM KKK bLMKH  LSo L   eHf   K dML  由預測分析表中無多重入口也可判定文法是LL(1)的。問答第3題對于一個文法若消除了左遞歸，提取了左公共因子后是否一定為LL(1)文法?試對下面文法進行改寫，并對改寫后的文法進行判斷。(1) AaABe|aBBb|d (3) SAa|bASB Bab答：（1） 文法： AaABe|a BBb|d 提取左公共因

22、子和消除左遞歸后文法變為：0) Aa N1) NA B e 2) N 3) Bd N14) N1b N15) N1非終結符FIRST集FOLLOW集Aa.#,dBd.e.Na,#,dN1b,e.對相同左部的產生式可知： SELECT(NA B e)SELECT(N) = a #,d =SELECT(N1b N1)SELECT(N1) = b e =所以文法是LL(1)的。預測分析表（Predicting Analysis Table） aebd#Aa N    B   d N1 N1 b N1&

23、#160; NABe  也可由預測分析表中無多重入口判定文法是LL(1)的。 （2）文法：SAa|b ASBBab第1種改寫：用A的產生式右部代替S的產生式右部的A得： SSBa|bBab消除左遞歸后文法變為： 0) Sb N1) NB a N2) N3) Ba b 非終結符FIRST集FOLLOW集Sb.#Ba.aN,a#對相同左部的產生式可知： SELECT(NB a N)SELECT(N) = a # =所以文法是LL(1)的。預測分析表（Predicting Analysis Table） ab#S b N Ba b 

24、; NB a N 也可由預測分析表中無多重入口判定文法是LL(1)的。 第2種改寫：用S的產生式右部代替A的產生式右部的S得： SAa|bAAaB|bBBab 消除左遞歸后文法變為： 0) SA a 1) Sb 2) Ab B N3) Na B N4) N 5) Ba b非終結符FIRST集FOLLOW集Sb.#Ab.aBa.aNa,a對相同左部的產生式可知：SELECT(SA a)SELECT(Sb) = b b = b SELECT(Na B N)SELECT(N) = a a = a 所以文法不是LL(1)的。預測分析表（Predicting Analysis Tab

25、le） ab#S A a.   b. A b B N Ba b.  Na B N   .  也可由預測分析表中含有多重入口判定文法不是LL(1)的。第六章 算符優先分析法問答第1題已知文法GS為：Sa|(T) TT,S|S (1) 計算GS的FIRSTVT和LASTVT。(2) 構造GS的算符優先關系表并說明GS是否為算符優先文法。(3) 給出輸入串(a,a)#和(a,(a,a)#的算符優先分析過程。答：文法：Sa|(T)TT,S|S 展開為：

26、Sa SS(T) TT,STS (1) FIRSTVT - LASTVT表 非終結符FIRSTVT集LASTVT集S a ( . a ) .T a ( , a ) , (2) 算符優先關系表（OPERATER PRIORITY RELATION TABLE） a(),#a(),#.表中無多重人口所以是算符優先（OPG）文法。（3）對輸入串（a,a）#的算符優先分析過程為棧（STACK）當前輸入字符（CHAR）剩余輸入串（INPUT_STRING）動作（ACTION）#(#(a#(N#(N,#(N,a#(N,N#(N#(N)#N(a,a)#a,a)#.,a)#.a)#.a)#.)#.#

27、.#.#.Move inMove inReduce: SaMove inMove inReduce: SaReduce: TT,SMove inReduce: S(T)Success! 對輸入串（a,(a,a)）# 的算符優先分析過程為：棧（STACK）當前字符（CHAR）剩余輸入串（INPUT_STRING）動作（ACTION）#(#(a#(N#(N,#(N,(#(N,(a#(N,(N#(N,(N#(N,(N,a#(N,(N,N#(N,(N#(N,(N)#(N,N#(N#(N)#N(a,(a,a)#a,(a,a)#.,(a,a)#.(a,a)#.(a,a)#.a,a)#.,a)#.a)#.a

28、)#.)#.)#.)#.)#.#.#.#.Move inMove inReduce: SaMove inMove inMove inReduce: SaMove inMove inReduce: SaReduce: TT,SMove inReduce: S(T)Reduce: TT,SMove inReduce: S(T) Success!問答第2題對題1的GS (1) 給出(a,(a,a)和(a,a)的最右推導，和規范歸約過程。(2) 將(1)和題1中的(3)進行比較給出算符優先歸約和規范歸約的區別。答：文法：Sa|(T) TT,S|S 對(a,a）和（a,(a,a)）的最右推導：(a,a）

29、的最右推導過程為：S(T) (T,S) (T,a) (S,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,(a,a) 對輸入串(a,a）# 的規范歸約過程為： 棧（stack）剩余輸入串（input left）動作（action）#( #( a#( S#( T#( T,#( T,a#( T,S#( T#(T)#S(a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.)#.)#.)#.#.#.ShiftShiftReduce by :S aReduc

30、e by :TSShiftShiftReduce by :S aReduce by :T T,SShiftReduce by :S (T)Success!(4) 對輸入串（a,(a,a)）# 的規范歸約過程為：棧（stack）剩余輸入串（input left）動作（action）#( #( a#( S#( T#( T,#( T,(#( T,(a#( T,(S#( T,(T#( T,(T,#( T,(T,a#( T,(T,S#( T,(T#( T,(T)#( T,(S#( T#( T)#S(a,(a,a)#.a,(a,a)#.,(a,a)#.,(a,a)#.,(a,a)#.(a,a)#.a,a)

31、#.,a)#.,a)#.,a)#.a)#.)#.)#.)#.)#.)#.)#.#.#.ShiftShiftReduce by :S aReduce by :TSShiftShiftShiftReduce by :S aReduce by :T SShiftShiftReduce by :S aReduce by :T TSShiftReduce by :S (T)Reduce by :T T,SShiftReduce by :S (T)Success!第七章 LR分析法問答第1題已知文法AaAd|aAb| 判斷該文法是否是SLR(1)文法，若是構造相應分析表，并對輸入串ab#給出分析過程。答：

32、文法： AaAd|aAb| 拓廣文法為G，增加產生式SA若產生式排序為：0 S' A 1 A aAd2 A aAb3 A 由產生式知： First (S' ) = ,aFirst (A ) = ,aFollow(S' ) = # Follow(A ) = d,b,#G的LR(0)項目集族及識別活前綴的DFA如下圖所示： 在I0中：A .aAd和A .aAb為移進項目，A .為歸約項目，存在移進-歸約沖突，因此所給文法不是LR(0)文法。在I0、I2中：Follow(A) a= d，b，# a=所以在I0、I2中的移進-歸約沖突可以由Follow集解決，所以G是SLR(1

33、)文法。 構造的SLR(1)分析表如下： 題目1的SLR(1)分析表 狀態（State）ActionGoto ad b #A012345S2r3r3r3 accS2r3r3r3S4S5r1r1r1 r2r2r21.3題目1對輸入串ab#的分析過程狀態棧（state stack） 文法符號棧 剩余輸入串（input left）動作（action）00 20 2 30 2 30 1#a#aA#aAb#Aab#.b#.b#.#.#.ShiftReduce by :A ShiftReduce by :A aAb分析成功，說明輸入串ab是題目1文法的句子問答第2題若有定義二進制數的文法如下：S

34、L.L|L LLB|BB0|1 (1) 試為該文法構造LR分析表，并說明屬哪類LR分析表。(2) 給出輸入串101.110的分析過程。答：文法： SL.L|L LLB|BB0|1 拓廣文法為G，增加產生式SS若產生式排序為：0 S' S 1 S L.L 2 S L 3 L LB 4 L B5 B 06 B 1 由產生式知： First (S' ) = 0,1First (S ) = 0,1 First (L ) = 0,1First (B ) = 0,1Follow(S' ) = # Follow(S ) = #Follow(L ) = .,0,1,#Follow(B

35、) = .,0,1,#G的LR(0)項目集族及識別活前綴的DFA如下圖所示： 在I2中：B .0和 B .1為移進項目，S L.為歸約項目，存在移進-歸約沖突，因此所給文法不是LR(0)文法。在I2、I8中：Follow(s) 0，1= # 0，1=所以在I2 、I8中的移進-歸約沖突可以由Follow集解決，所以G是SLR(1)文法。 構造的SLR(1)分析表如下：題目2的SLR(1)分析表 狀態（State）ActionGoto · 01 #SLB012345678S4S5 accS6S4S5r2r4r4r4r4r5r5r5r5r6r6r6r6S4S5r3r3r3r3S

36、4S5r1123.7.83. 7題目2對輸入串101.110#的分析過程狀態棧（state stack） 文法符號棧剩余輸入串（input left）動作（action）00 50 30 20 2 40 2 70 2 0 2 50 2 70 2 0 2 60 2 6 5 0 2 6 3 0 2 6 8 0 2 6 8 50 2 6 8 70 2 6 80 2 6 8 40 2 6 8 70 1#1#B#L#L0#LB#L#L1#LB#L#L.#L.1#L.B#L.L#L.L1#L.LB#L.L#L.L0#L.LB#S101.110#.01.110#.01.110#.01.110#.1.110#

37、.1.110#.1.110#.110#.110#.110#.110#.10#.10#.10#.0#.0#.0#.#.#.#.ShiftReduce by :B 1Reduce by :S LBShiftReduce by :B 0Reduce by :S LBShiftReduce by :B 1Reduce by :S LBShiftShiftReduce by :B 1Reduce by :S BShiftReduce by :B 1Reduce by :S LBShiftReduce by :B 0Reduce by :S L.L分析成功，說明輸入串101.110是題目2文法的句子。問答

38、第3題文法G=(U,T,S,a,b,c,d,e,P,S) 其中P為：SUTa|TbTS|Sc|d UUS|e (1) 判斷G是LR(0)，SLR(1)，LALR(1)還是LR(1)，說明理由。 (2) 構造相應的分析表。答：文法：SUTa|Tb TS|Sc|dUUS|e 拓廣文法為G'，增加產生式S'S若產生式排序為：0 S' S1 S UTa 2 S Tb 3 T S 4 T Sc5 T d 6 U US 7 U e 由產生式知： First (S' ) = d,eFirst (S ) = d,eFirst (U ) = e First (T ) = d,eF

39、ollow(S' ) = # Follow(S ) = a,b,c,d,e,#Follow(U ) = d,e Follow(T ) = a,b G的LR(0)項目集族及識別活前綴的DFA如下圖所示： 在I1中：S' S.為接受項目，T S. 為歸約項目，T S.c為移進項目，存在接受-歸約和移進-歸約沖突，因此所給文法不是LR(0)文法。 在I1中： Follow(S') Follow(T)= # a ，b=Follow(T) c= a ，b c=在I8中：Follow(U) Follow(T) c=d,e a ，b c=所以在I1中的接受-歸約和移進-歸約沖突與I8

40、中的移進-歸約和歸約-歸約沖突可以由Follow集解決，所以G是SLR(1)文法。 構造的SLR(1)分析表如下：題目3的SLR(1)分析表 狀態（State）ActionGoto a b c d e#SUT012345678910 S5S4r3r3S6AccS5S4S9.r7r7r5r5. r4r4.S10S9.r3r3.S6r6r6. r2r2.r2r2r2r2r1r1.r1r1r1r1123.827 問答第4題證明文法：SA$ ABaBb|DbDaBD是LR(1)但不是SLR(1)。(其中'$'相當于'#')答：文法： ABaBb|DbDa BD

41、拓廣文法為G，增加產生式SA若產生式排序為：0 S'A1 A BaBb 2 A DbDa 3 B 4 D 由產生式知： First (S' ) = a,b First (A ) = a,bFirst (B ) = First (D ) = Follow(S' ) = #Follow(A ) = # Follow(B ) = a,bFollow(D ) = a,bG的LR(1)項目集族及識別活前綴的DFA如下圖所示： 在I0中：B .,a和T .，b為歸約項目，但它們的搜索符不同，若當前輸入符為a時用產生式B 歸約，為b時用產生式D 歸約，所以該文法是LR(1)文法。若不

42、看搜索符，在I0中項目B .和T .為歸約-歸約沖突，而Follow(B ) Follow(D ) = a,b a,b，沖突不能用Follow集解決，所以該文法不是SLR(1)文法。構造的LR(1)分析表如下：題目4的LR(1)分析表 StateActionGoto a.b.#ABD0123456789r3r4. AccS4.S5r3r4.S8S9.r1r2123.67 問答第5題給定文法： Sdo S or S|do S|S;S|act (1) 構造識別該文法活前綴的DFA。 (2) 該文法是LR(0)嗎?是SLR(1)嗎?說明理由。 (3) 若對一些終結符的優先級以及算符的結合規則規定如下：a) or 優先性大于 do;b) ;服從左結合； c) ;優先性大于 do ； d) ;優先性大于 or ；請構造該文法的LR分析表,并說明LR(0)項目集中是否存在沖突和沖突如何解決的。答：首先化簡文法,用d代替do;用o代替 or;用a代替 act;文法可寫成：SdSoS|dS|S;S|a拓廣文法為G'，增加產生式SS若產生式排序為：0 S' S 1 S dSoS2 S dS 3 S S;S4 S a 由產生式知：First (S' ) = d,aFirst (S ) = d,a Follow(S' ) = # Follo