編譯原理-第5章-習題與答案2上課講義

1、編譯原理-第 5 章-習題與答案 2精品文檔第五章 習題5-1 設有文法GS：A/aA/(1) 找出部分符號序偶間的簡單優(yōu)先關系。(2) 驗證GS不是簡單優(yōu)先文法。5-2 對于算符文法GS：SETT*FFPP(E)i(1) 找出部分終結符號序偶間的算符優(yōu)先關系。(2) 驗證GS不是算符優(yōu)先文法。5-3 設有文法：EEEE+T|TTT1TT*F|FF(E)|i11111其相應的簡單優(yōu)先矩陣如題圖5-3所示，試給出對符號串（）進行簡單優(yōu)先分析的過程。EETTF+*()i1111 )i題圖 5-3文法 GE的簡單優(yōu)先矩陣收集于網絡，如有侵權請聯系管理員刪除精品文檔5-4 設有文法GE：EE+T|TT

2、T*F|FF(E)|i其相應的算符優(yōu)先矩陣如題圖5-4所示。試給出對符號串（）進行算符優(yōu)先分析的過程。+)#(i*+)# 題圖 5-4 文法 GE的算符優(yōu)先矩陣5-5 對于下列的文法，試分別構造識別其全部可歸前綴的DFA和LR(0)分析表，并判斷哪些是LR(0)文法。(1) SaScab(2) SaSSbaSSSc(3) SAa5-6 下列文法是否是文法？若是，構造相應的SLR(1)分析表，若不是，則闡明其理由。(1) SbRSa(2) SaSABBA(3) SbBaABcAdbcBdd收集于網絡，如有侵權請聯系管理員刪除精品文檔5-7 對如下的文法分別構造LR(0)及 SLR(1)分析表，并

3、比較兩者的異同。cAdba5-8 對于文法GS:SABAaBb(1) 構造LR(1)分析表；(2) 給出用LR(1)分析表對輸入符號串abab的分析過程。5-9 對于如下的文法，構造LR(1)項目集族，并判斷它們是否為LR(1)文法。(1) AABaBb(2) a第 5章 習題答案25-1 解：(1) 由文法的產生式和如答案圖5-1(a)所示的句型A的語法樹，可得G 中的部分優(yōu)先關系如答案圖5-1(b)所示。收集于網絡，如有侵權請聯系管理員刪除精品文檔S/AaAS/AaAA/AA/aa/(a) 句型A/a/的語法樹(b)部分符號序偶間的優(yōu)先關系答案圖5-1(2) 由答案圖5-1(b)可知，在符

4、號A和之間，即存在等于關系，又存在低于關系，故文法GS不是簡單優(yōu)先文法。5-2 解：(1) 由文法GS的產生式可直接看出：（ = ）此外，再考察句型P(E)和 i*(T*F)的語法樹 (見答案圖5-2(a)(b)。由答案圖5-2(a)可得： , , (由答案圖5-2(b)可得：i * ,* ( , ( * , * ）收集于網絡，如有侵權請聯系管理員刪除精品文檔ETT-*FF(E)F-T-P()T* F(a)句型 -P-(E)的語法樹(b)句型i*(T*F)的語法樹(2)由答案圖5-2(a)可知，在終結符號和之間，存在兩種算符優(yōu)先關系： , 故文法 GS不是算符優(yōu)先文法。5-3 解：對符號串進行

5、簡單優(yōu)先分析的過程如答案表5-3所示。因為分析成功，所以符號串(i+i)是文法的合法句子。答案表5-3 (i+i)的簡單優(yōu)先分析過程當前符號（余留輸入串i+i)#+i)#i)#所用步驟分析棧關系低于句柄產生式低于 i優(yōu)于 +優(yōu)于 +優(yōu)于 +優(yōu)于 +2 #(i3 #(F4 #(T5 #(Ti Fii)#i)#1i)#T ET1111收集于網絡，如有侵權請聯系管理員刪除精品文檔#(E等于低于優(yōu)于優(yōu)于優(yōu)于優(yōu)于優(yōu)于等于優(yōu)于優(yōu)于優(yōu)于優(yōu)于優(yōu)于i)#)#1#(E+#(E+iiFT#(E+F#10#(E+T#11 #(E+T#111#EEE11#TT11EEE11分析成功優(yōu)于5-4 解：對符號串進行算符優(yōu)先分

6、析的過程如答案表5-4所示。因為分析成功，所以符號串(i+i)是文法GE的合法句子。句子(i+i)及其分析過程中所得句型的語法樹如答案圖5-4所示。答案表5-4 i+i)的算符優(yōu)先分析過程當前棧頂終結符號優(yōu)先當前輸余留最左步驟分析棧關系入符號 輸入串素短語0123 # ( i+i# (F(+i)#收集于網絡，如有侵權請聯系管理員刪除精品文檔 i#分析成功#ETF(E+)()(E)ETFi答案圖5-4 句子(i+i)及其分析過程中所得句型的語法樹5-5 解：(1) 在文法GS中引入一個新的開始符號，且將SS作為第0個產生式添加到文法G中，從而得到G的拓廣文法GS：0.SSaScab1.SaSb收

7、集于網絡，如有侵權請聯系管理員刪除精品文檔識別文法GS全部可歸前綴的DFA如答案圖5-5-(1)所示。10abc23a答案圖5-5-(1) 識別GS全部可歸前綴的DFA因為文法GS的每個項目集中都不含沖突項目，所以文法GS是 文法，故可構造出不含沖突動作的LR(0)分析表如答案表5-5-(1)所示。答案表5-5-(1) 文法GS的LR(0)分析表狀態(tài)#01234563245312srrr6312rrrrrrr3123r1r2(2) 在文法GS中引入一個新的開始符號，且將SS 作為第0 個產生式添加到文法G 中，從而得到G 的拓廣文法GS：收集于網絡，如有侵權請聯系管理員刪除精品文檔0.SSaS

8、SSc1.SaSSb識別文法GS全部可歸前綴的DFA如答案圖5-5-(2)所示。S10cacccbSSaaaS因為文法GS的每個項目集中都不含沖突項目，所以文法GS是 文法，故可構造出不含沖突動作的LR(0)分析表如答案表5-5-(2)所示。答案表5-5-(2) 文法GS的LR(0)分析表狀態(tài)#0123453srss423333rr33ss5722收集于網絡，如有侵權請聯系管理員刪除精品文檔67rrrrrr12121212r(3) 在文法GS中引入一個新的開始符號，且將SS作為第0個產生式添加到文法G中，從而得到G的拓廣文法GS：0.SSAba1.SA識別文法GS全部可歸前綴的DFA如答案圖5

9、-5-(3)所示。SI : SS 10a2Ab34答案圖5-5-(3) 識別GS全部可歸前綴的DFA因為在 LR(0)項目集I中含有移進歸約沖突項目，所以文法GS不是 文2法，故構造出的LR(0)分析表中含有沖突動作。文法GS的LR(0)分析表如答案表5-5-(3)所示。答案表5-5-(3) 文法GS的LR(0)分析表狀態(tài)01234accr11rrr323r2r2收集于網絡，如有侵權請聯系管理員刪除精品文檔5-6 解：(1) 在文法GS中引入一個新的開始符號，且將SS作為第0個產生式添加到文法G中，從而得到G的拓廣文法GS：0.SS1.SSab2. SbRSa識別文法GS全部可歸前綴的DFA如

10、答案圖5-6-(1)所示。a01I : Sa bSS ab6bb32aba答案圖5-6-(1)識別GS全部可歸前綴的DFA由答案圖5-6-(1)可知，在項目集I 和 I中都存在“移進-歸約”沖突。在項目集I144= RS, SSab 中, 由于FOLLOR(R)=a，FOLLOR(R)a=a ，所以其項目集的“移進歸約沖突不可能通過 SLR(1)規(guī)則得到解決，從而該文法不是 SLR(1)文法。(2) 在文法GS中引入一個新的開始符號，且將SS作為第0個產生式添加到文法G中，從而得到G的拓廣文法GS：收集于網絡，如有侵權請聯系管理員刪除精品文檔0.SS1.SaSAB2.SBAaABb識別文法GS

11、全部可歸前綴的DFA如答案圖5-6-(2)所示。S10SaI : a SABBB2aS aSABS BA baAbI44Bbb893BBAAabI4答案圖 5-6-(2) 識別 全部可歸前綴的DFA因為文法GS的每個項目集中都不含沖突項目，所以文法GS是 文法，故也是SLR(1)文法。因為 FOLLOW(S)=a,b,#, FOLLOW(A)=a,b,#, FOLLOW(B)=a,b,#,所以文法GS的 SLR(1)分析表如答案表5-6-(2)所示。答案表5-6-(2) 文法GS的SLR(1)分析表狀態(tài)a#S1B30ss42收集于網絡，如有侵權請聯系管理員刪除精品文檔accssrsrsrsrr

12、52445424441369751011rr13r3(3) 在文法GS中引入一個新的開始符號，且將SS作為第0個產生式添加到文法G中，從而得到G的拓廣文法GS：0.SS1.SaAcBdd2.SbB3. AcAd識別文法GS全部可歸前綴的DFA如答案圖5-6-(3)所示。收集于網絡，如有侵權請聯系管理員刪除精品文檔S109ccbBaBd2Adc5cdA 由答案圖5-6-(3)可知，在項目集I ,I ,I 和 I 中都存在“移進歸約”沖突。2359因為在項目集I 和 I 中, 由于 FOLLOR(A)=d,#，FOLLOR(A)c=，所以其項25目集的移進-”沖突能通過SLR(1)規(guī)則得到解決；又

13、因為在項目集I 和 I 中, 由于FOLLOR(B)=d,#，FOLLOR(B)c=，所以其39項目集的“移進歸約沖突也能通過SLR(1)規(guī)則得到解決；所以文法GS是 SLR(1)文法。因為 FOLLOR(S)=#，FOLLOR(A)=d,#FOLLOR(B)=d,#，所以文法的SLR(1)分析表如答案表5-6-(3)所示。答案表5-6-(3) 文法GS的SLR(1)分析表狀態(tài)as#B01223accsrr4454收集于網絡，如有侵權請聯系管理員刪除精品文檔rrr866146477rrrr332696101112rr555-7 解：在文法中引入一個新的開始符號S，且將SS作為第0個產生式添加到

14、文法G中，從而得到G的拓廣文法GS：0.SS1.ScAd2.SbASca識別文法GS全部可歸前綴的DFA如答案圖5-7所示。S10bcAS2cc8ad4 收集于網絡，如有侵權請聯系管理員刪除精品文檔因為文法GS的每個項目集中都不含沖突項目，所以文法GS是 文文法 GS的 LR(0)分析表如答案表5-7-(a)所示。法。答案表5-7-(a) 文法GS的LR(0)分析表狀態(tài)a#01234567832srr224472rr118rrrr33333因為 FOLLOR(S)=#,cFOLLOR(A)=b,c,d，所以文法GS的 SLR(1)分析表如答案表 5-7-(b)所示。答案表5-7-(b) 文法G

15、S的SLR(1)分析表狀態(tài)as#01234563242rr44ss726rr11收集于網絡，如有侵權請聯系管理員刪除精品文檔78sr83rr33兩個表的相同之處為：(1) 兩個表的GOTO表部分完全相同。(2) 在兩個表的ACTION表中，不含歸約項目的項目集對應的行的元素完全相同，即第 0,2,5,7行完全相同。兩個表的不同之處為：在兩個表的ACTION表中，含有歸約項目的項目集對應的行的元素不同，即第3,4,6,8行的元素不同。以第3行為例，答案表5-7-(a)中的所有元素都為r ；而在答2案表 5-7-(b)中 ,因為FOLLOR(S)=#,c，故僅在“#”和“c”列對應的元素為r 。2

16、5-8 解：(1) 在文法GS中引入一個新的開始符號，且將SS作為第0個產生式添加到文法G中，從而得到G的拓廣文法GS：0.SS1.SAaBb2.ABA文法 GS的 LR(1)項目集及DFA如答案圖5-8所示。收集于網絡，如有侵權請聯系管理員刪除精品文檔S1 A ,# ,# ,#AaI :BA ,#3bb ,b ,I :b5baa ,Bb , 文法 GS的 LR(1)分析表如答案表5-8-(1)所示。答案表5-8-(1) 文法GS的LR(1)分析表狀態(tài)012345674acc6rr4r44(2) 用 LR(1)分析表對輸入符號串abab的分析過程如答案表5-8-(2)所示。因為分析成功，所以符

17、號串abab是文法GS的合法句子。收集于網絡，如有侵權請聯系管理員刪除精品文檔答案表5-8-(2) 符號串abab的 LR分析過程步驟1狀態(tài)棧符號棧余留輸入串分析動作下一狀態(tài)I0452II0#a#ab#aB#BGOTOI ,B=704GOTOI ,B=300II0#Ba#Bab#BaB#BB#BBA#BA#A04GOTOI ,B=7044GOTOI ,B=3043GOTOI ,A=603310111213GOTOI ,A=60363GOTOI ,A=2032160IIGOTOI ,S=100II0#S#acc5-9 解：(1) 在文法GS中引入一個新的開始符號，且將SS作為第0個產生式添加到文

18、法G中，從而得到G的拓廣文法GS：0.SS1.SAaBb2.AAB文法 GS的 LR(1)項目集及DFA如答案圖5-9-(1)所示。收集于網絡，如有侵權請聯系管理員刪除精品文檔S10AA AB , a/b/#A , a/b/#I : A , #2AA B , a/b/# aB , a/b/# b , a/b/#aa aB , a/b/# b , a/b/#Bb答案圖5-9-(1) 文法GS的LR(1)項目集及DFA文法 GS的 LR(1)分析表如答案表5-9-(1)所示。因為分析表中不含多重定義的元素，所以文法GS是LR(1)文法。答案表5-9-(1) 文法GS的LR(1)分析表狀態(tài)01234563accsrrsr525546r4r4(2) 在文法GS中引入一個新的開始符號，且將SS 作為第0 個產生式添加到文法G 中，從而得到G 的拓廣文法GS：收集于網絡，如有侵權請聯系管理員刪除精品文檔0.SS1.SaSa2.Sa文法 GS的 LR(1)項目集及DFA如答案圖5-9