編譯原理—應(yīng)用題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上題型一四、現(xiàn)有文法GE： (共10分)EE+T|E-T|TTT*F|T/F|FFi|(E) 1、 證明：E-F*(i)是文法的一個句型。(3分)2、 構(gòu)造句型E-F*(i)的語法推導(dǎo)樹。(2分)1、 指出該句型所有短語、直接短語和句柄。(5分)第四題：（10分）1、 證明（3分）：因為存在推導(dǎo)序列E=>E-T=>E-T*F=>E-F*F=>E- F*(E) =>E- F*(T)=>E-F*(F)=>E-F*(i)，即有EE-F*(i)成立，所以，E-F*(i)是文法的一個句型。2、語法樹（2分）：EE - T T * F F

2、（ E ）TFi3、句型分析（5分） 句型E-F*(i)相對于E的短語有: E-F*(i), i。句型E-F*(i)相對于T的短語有: F*(i), F，i。句型E-F*(i)相對于F的短語有: (i), i。 （3分） 句型E-F*(i)相對于TF的直接短語有: F 。句型E-F*(i)相對于Fi的直接短語有: i 。（2分）句型E-F*(i)的句柄為: F。 （1分）三、現(xiàn)有文法GE： (共12分)EE+T|E-T|TTT*F|T/F|FFi|(E) 3、 證明：F+T*(E)是文法的一個句型。(3分)4、 構(gòu)造句型F+T*(E)的語法推導(dǎo)樹。(3分)5、 指出該句型所有短語、直接短語和句

3、柄。(6分)第三題：（12分）2、 證明（3分）：因為存在推導(dǎo)序列E => E+T => T+T =>F+T =>F+T*F => F+T*(E)，即有 EF+T*(E)成立，所以，F(xiàn)+T*(E)是文法的一個句型。2、語法樹（3分）EE + T T T * F F （ E ）3、句型分析（6分） 句型F+T*(E)相對于E的短語有: F+T*(E), F。句型F+T*(E)相對于T的短語有: F, T*(E)。句型F+T*(E)相對于F的短語有: (E)。 （3分） 句型F+T*(E)相對于TF的直接短語有: F 。句型F+T*(E)相對于F(E)的直接短語有:

4、(E) 。（2分）句型F+T*(E)的句柄為: F。 （1分）1、有文法GS：(12分)SaAS|aASbA|SS|ba(1)證明aabbaa是文法的一個句子。(3分)(2)構(gòu)造句子aabbaa的語法樹。(3分)(3)指出該句子的所有短語、直接短語和句柄。(6分)答：（1）證明(3分)：因為存在推導(dǎo)序列S=>aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa，即有S=*>aabbaa成立，所以，是文法的一個句子。（2）語法樹（3分）：（3）句型分析（6分）：將句型改寫為a1a2b1b2a3a4，則：該句型相對于S的短語：a1a2b1b2a3a

5、4和 a4；相對于A的短語： a2b1b2a3和b2a3；對于Sa的直接短語：a2，a4；相對于Aba的直接短語：b2a3；句柄：a2。1、有文法GE：(16分)E T + ETT T * FFF ( E )i(1)證明T+T*F+i是文法的一個句型。(3分)(2)構(gòu)造型T+T*F+i的語法樹。(3分)(3)指出該句型的所有短語、直接短語和句柄。(7分)(4)指出該句型的所有素短語和最左素短語。(3分)答：1）證明(3分)：因為存在推導(dǎo)序列：E=>T+E=>T+T+E=>T+T*F+E=>T+T*F+T=>T+T*F+F=>T+T*F+i，即有E=*>

6、T+T*F+i成立，所以，T+T*F+i是文法的一個句型。（2）語法樹（3分）：（3）句型分析（7分）：該句型相對于E的短語：T+T*F+i、T*F+i和i ；相對于T的短語有：T*F和i，相對于F的短語有i。相對于TT*F的直接短語：T*F,相對于Fi的直接短語：i。句柄：T*F。(4) 該句型的所有素短語：T*F和 I；T*F為最左素短語。(3分)二、現(xiàn)有文法GS： (共10分)SSS*SSS+Sa6、 證明aa+a*是文法的一個句子。(2分)7、 構(gòu)造句型aa+a*的語法推導(dǎo)樹。(2分)8、 指出該句型所有短語、直接短語和句柄。(6分)第二題：（10分）3、 證明（3分）：因為存在推導(dǎo)序

7、列S=>SS*=>SS+S*=>aS+S* =>aa+S*=>aa+a*，即有 Saa+a*成立，且aa+a*全部由終結(jié)符構(gòu)成，所以aa+a*是文法的一個句子。2、語法樹（2分）： S S S * S S + a3 a1 a2 3、句型分析（5分） 句型aa+a*相對于S的短語有: a1a2+a3*, a1a2+, a1,a2,a3。（2分） 句型aa+a*相對于Sa的直接短語有: a或 a1,a2,a3。（2分）句型aa+a*的句柄為: a1。 （1分）三、現(xiàn)有文法GE： (共12分)EEE+EEE*EFFi9、 證明ii*i+是文法的一個句子。(3分)10、

8、構(gòu)造句型ii*i+的語法推導(dǎo)樹。(3分)11、 指出該句型所有短語、直接短語和句柄。(6分)第三題：（12分）1、證明（3分）：因為存在推導(dǎo)序列E=>EE+=>EE*E+=>FE*E+=>iE*E+=>iF*E+=> ii*E+=>ii*F+=>ii*i+，即有Eii*i+成立（2分），且ii*i+所含符號全部為終結(jié)符（1分），所以，ii*i+是文法的一個句子。2、語法樹（3分）EE E +E E * FF F i3 i1 i23、句型分析（6分） 句型ii*i+相對于E的短語有: i1i2*i3+, i1i2*, i1,i2,i3 （3分）句型

9、ii*i+相對于F的短語有: i1,i2,i3 （1分）句型ii*i+相對于Fi的直接短語有:i或i1,i2,i3 （1分）句型ii*i+的句柄為: i1 （1分）說明：（1）短語、直接短語的說明可不具體指明所相對的非終結(jié)符或規(guī)則。（2）沒用下標(biāo)區(qū)分i1,i2,i3 的扣1分。（3）短語每錯兩個扣1分。題型二三、給定正規(guī)式R=(01|10) (01|10)* ，要求： (10分)2、 構(gòu)造對應(yīng)的正規(guī)文法G，使得L(G)=L(R)。 (4分)3、 構(gòu)造對應(yīng)的NFA M狀態(tài)圖，使得L(M)=L(R)。 (3分)3、將所得NFA M確定化為DFA。 (3分)第三題：（10分）1、正規(guī)文法GS（4分）

10、：S0A|1BA1S|1B0S|02、NFA （3分） ：3、DFA（3分） ：步驟如下表所示（可?。簶?biāo)記新狀態(tài)I0I1T0SABT1AS,ZT2BS,ZT3S,ZAB將集合T0至T3各用一個狀態(tài)表示，確定化后所得DFA M如下：四、給定正規(guī)式R=d(a|bc)*d，要求： (12分)4、 構(gòu)造對應(yīng)的NFA M狀態(tài)圖，使得L(M)=L(R)。 (4分)5、 將所得NFA M確定化和最小化。 (8分)第四題：（12分）1、NFA M （4分）2、(1)確定化（4分） 步驟如下表所示（可省）：標(biāo)記新狀態(tài)IaIbIcIdT012,4T12,42,435T232,4T35將集合T0至T3各用一個狀態(tài)

11、表示，確定化后所得DFA M如下：(2)最小化 （4分）步驟如下表所示（可?。翰襟E分割根據(jù)分割結(jié)果1是否終態(tài)P1=1，2，3；P2=42P1根據(jù)d弧映射P11=1；P12=2；P13=3最后還有4個不可再分割的子集，每個子集中只包含一個狀態(tài)，即原DFA M已經(jīng)是最小化DFA 。說明：此大題答案只供參考，可以是其他答案，只要功能等價即可。3、有正規(guī)文法GS： (12分)SaA|bB AbS|b BaS|a (1)構(gòu)造對應(yīng)的正規(guī)式R，使得L(R)=L(G)。 (3分)(2)構(gòu)造對應(yīng)的NFA狀態(tài)圖，使得L(M)=L(R)。 (3分)(3)將所得NFA確定化為DFA。 (3分)(4)將所得DFA最小

12、化。 (3分) 答：(1)代入后有S的規(guī)則右部=a（bS|b）|b(aS|a)=ab（S|）|ba（S|）=（ab|ba）（S|）,故對應(yīng)的正規(guī)式R=(ab|ba)(ab|ba)* 。 (3分)(2)對應(yīng)的NFA狀態(tài)圖如下左圖所示： (3分) (3)將所得NFA確定化為DFA狀態(tài)圖如上右圖所示： (3分)(4)將所得DFA最小化：首先根據(jù)是否終態(tài)劃分為非終態(tài)集P1=S,A,B和終態(tài)集P2=Z；然后對P1根據(jù)a弧劃分為P11=S,P12=A，P13=B?？梢娫璂FA已是最小化的DFA。 (3分)三、給定正規(guī)式R=0(0|1)0*1，要求： (12分)1、構(gòu)造對應(yīng)的NFA M狀態(tài)圖，使得L(M)=

13、L(R)。 (4分)2、將所得NFA M確定化和最小化。 (8分)第三題：（12分）1、NFA （4分）：2、確定化（4分）：標(biāo)記新狀態(tài)I0I1T0AB,C,ET1B,C,ED,GF,GT2D,GGHT3F,GGHT4GGHT5H將集合T0至T5各用一個狀態(tài)表示，確定化后所得DFA M如下：3、最小化 （4分） ：步驟如下表所示（可省）：步驟分割根據(jù)分割結(jié)果1是否終態(tài)P1=A,B,C,D,E；P2=F2P1根據(jù)1弧映射P11=A；P12=B；P13=C,D,E最后有四個不可再分割的子集，每個子集對應(yīng)一個狀態(tài)，即有最小化DFA如下： 說明：此大題答案只供參考，可以是其他答案，只要功能等價即可。四

14、、將正規(guī)式R=bb(a|bb)a*b轉(zhuǎn)換為相應(yīng)的NFA M狀態(tài)圖，使得L(M)=L(R)，并將所得NFA M確定化和最小化。(12分)第四題：（12分）1、NFA M （3分） 2、確定化（3分） 步驟如下表所示（可?。簶?biāo)記新狀態(tài)IaIbT012T123,4,6T23,4,65,97T35,9910T478,9T599 10T610T78,9910將集合T0至T7各用一個狀態(tài)表示，確定化后所得DFA M如下：3、最小化 （3分）步驟如下表所示（可?。翰襟E分割根據(jù)分割結(jié)果1是否終態(tài)P1=1，2，3，4，5，6，8；P2=72P1根據(jù)a弧映射P11=3，4，6，8；P12=1，2，53P11根

15、據(jù)b弧映射P111=3；P112=4，6，84P12根據(jù)b弧映射P121=1；2； P122 =5最后有六個不可再分割的子集，每個子集對應(yīng)一個狀態(tài)，得最小化DFA如下：說明：此大題答案只供參考，可以是其他答案，只要功能等價即可。題型三五、任意給定一個文法GS： (10分)1、 給出判斷GS是否為LL(1)文法的步驟。(4分)2、 如果GS是LL(1)文法，怎樣構(gòu)造它的預(yù)測分析表？(3分)3、 怎樣根據(jù)預(yù)測分析表對給定的某個輸入串進(jìn)行預(yù)測分析？(3分)第五題： (10分)對任意給定的一個文法GS： 1、判斷是否為LL(1)文法的步驟：(4分)1）畫出各非終結(jié)符能否推導(dǎo)出的情況表。2）用定義法或關(guān)

16、系圖法計算FIRST、FOLLOW集。3）計算各規(guī)則的SELECT集。4） 檢查所有左部相同的規(guī)則的SELECT集是否相交，如果不相交，則GS為LL(1)文法。否則，說明GS不是LL(1)文法。2、構(gòu)造GS預(yù)測分析表：(3分)預(yù)測分析表為一個二維矩陣,其形式為MA,a,其中AVN ,aVT或#。對文法中的規(guī)則A,若有終結(jié)符aSELECT(A),則將A填入MA,a中。(書寫時，通常省略規(guī)則左部，只填)。對所有沒有值的MA,a標(biāo)記為出錯。3、根據(jù)預(yù)測分析表M對給定的某個輸入串進(jìn)行預(yù)測分析的過程，可用下述算法表示：(3分)#,S進(jìn)棧 ; /初始化工作，S為開始符do X=當(dāng)前棧頂符號;a=當(dāng)前輸入符

17、號；if (XT#) if (X=a) if (X ! =#) 將X彈出,且前移輸入指針else error() else if (MX,a=Y1Y2Yk )將X彈出;依次YkY2Y1將壓入棧;else error();while( X ! =#);說明：此答案只供參考，可以是其他答案，只要意思相近即可。六、已知GS： (18分)S(A)|a|bAA,S|S1、給出(a,(b,b)的最左推導(dǎo)。(3分)2、判斷該文法是否為LL(1)文法。若是，直接給出它的預(yù)測分析表；若不是，先將其改寫為LL(1)文法，再給出它的預(yù)測分析表；(10分)3、給出輸入串(b,b)#的分析過程，并說明該串是否為GS的句

18、子。(5分)第六題： (18分)1、給出(a,(b,b)的最左推導(dǎo)：(3分)S=>(A)=>(A,S)=>(S,S)=>(a,S)=>(a,(A)=>(a,(A,S)=>(a,(S,S)=>(a,(b,S) =>(a,(b,b)2、(1)判斷：(3分)計算各條規(guī)則的SELECT集及左部相同規(guī)則的SELECT集的交集如下：規(guī)則SELECT集左部相同規(guī)則的SELECT集的交集SaaSbbS(A)(AA,Sa,b,(a,b,(ASa,b,(顯然，GS不是 LL(1) 文法。（2）將GS改寫如下：(4分)GS：Sa|b|(A)A,SA|ASA規(guī)則S

19、ELECT集左部相同規(guī)則的SELECT集的交集SaaSbbS(A)(A,S A,A)ASAa,b,(顯然，改寫后的GS是 LL(1) 文法。（2）預(yù)測分析表：(3分)ab(,)#Sab(A)A ,SAASASASA4、（1）輸入串(b,b)#的分析過程：(4分)步驟分析棧剩余輸入串所用規(guī)則步驟分析棧剩余輸入串所用規(guī)則1#S(b,b)#S(A)7#)AS,b)#,匹配2#)A(b,b)#(匹配8#)ASb)#Sb3#)Ab,b)#ASA9#)Abb)#b匹配4#) A Sb,b)#Sb10#)A)#A5#)Abb,b)#b匹配11#)#)匹配6#)A,b)#A,S A12#接受（2）輸入串(b,

20、b)是GS的句子。(1分)4、對表達(dá)式文法GE： (16分)E E - TTT T FFF ( E )a(1)判斷GE是否為LL(1)文法。若不是，改造為LL(1)文法。(8分)(2)構(gòu)造預(yù)測分析表，并對輸入串w=a-aa#進(jìn)行預(yù)測分析。(8分)答：(1)計算GE的SELECT集如下：(2分)SELECT(E E T )=(，aSELECT(E T )=(，aSELECT(T T F)=(，a SELECT(T F)=(，aSELECT(F ( E )=( SELECT(F a)=a 由于SELECT(E E T ) SELECT(E T )=(，a；SELECT(T T F) SELECT(

21、T F)=(，a；SELECT (F ( E )SELECT (F a) = (a =故 GE不是LL(1) 文法。(1分)對GE的E E T和T T F兩條規(guī)則消除左遞歸后變?yōu)椋?2分)ET EE T E|T F TT F TF ( E )a計算消除左遞歸后GE的SELECT集如下：(2分)SELECT(E T E)=(，aSELECT(E T E)= SELECT(E)=#，)SELECT(T F T)=(，aSELECT(T F T)= SELECT(T)= ，#，)SELECT(F( E )=(SELECT(Fa)=a由于SELECT(E T E)SELECT (E') =SE

22、LECT (T' F T') SELECT (T') =SELECT (F ( E )SELECT (F a) = =故消除左遞歸后的GE是LL(1) 文法。(1分)（2）根據(jù)消除左遞歸后的GE的SELECT集構(gòu)造預(yù)測分析表如下：(3分) 對輸入串w=a-aa#的分析過程如下表所示（注意：規(guī)則右部以逆序入棧）：(5分)四、已知GE： (15分)Ea|*|(T)TT,E|E4、 給出(*,(a,*)的最右推導(dǎo)。(3分)5、 將GE改寫為LL(1)文法，再給出它的預(yù)測分析表；(7分)6、 給出輸入串(a,*)#的分析過程。(5分)第四題： (15分)1、給出(*,(a,*)

23、的最右推導(dǎo)：(3分)E=>(T)=>(T,E)=>(T,(T)=>(T,(T,E)=>(T,(T,*)=>(T,(E,*)=>(T,(a,*) =>(E,(a,*)=>(*,(a,*)2、（1）將GE改寫如下：(3分)GE：Ea|*|(T)T,E T|TE T規(guī)則SELECT集左部相同規(guī)則的SELECT集的交集EaaE*E(T)(T,E T,T)TETa,*,(顯然，改寫后的GE是 LL(1) 文法。（2）預(yù)測分析表：(4分)a*(,)#Ea*(T)T ,ETTETETET4、輸入串(a,*)#的分析過程：(5分)步驟分析棧剩余輸入串所用規(guī)

24、則步驟分析棧剩余輸入串所用規(guī)則1#E(a,*)#E(T)7#) TE, *)#,匹配2#)T(a,*)#(匹配8#) TE*)#E*3#)Ta,*)#TET9#) T*)#*匹配4#) TEa,*)#Ea10#) T)#T5#) Taa,*)#a匹配11#)#)匹配6#) T,*)#T,S T12#接受五、已知GS： (18分)Sb|+|(T)TT,S|S7、 給出(+,(b,+)的最左推導(dǎo)。(2分)8、 證明GS不是LL(1)文法。(3分)9、 將GS改寫為LL(1)文法，再給出它的預(yù)測分析表；(8分)4、給出輸入串(b,+)#的分析過程。(5分)第五題： (18分)1、給出(+,(b,+)

25、的最左推導(dǎo)：(2分)S=>(T)=>(T,S)=>(S,S)=>(+,S)=>(+,(T)=>(+,(T,S) =>(+,(S,S)=>(+,(b,S) =>(+,(b,+)2、證明：(3分)計算各條規(guī)則的SELECT集及左部相同規(guī)則的SELECT集的交集如下：規(guī)則SELECT集左部相同規(guī)則的SELECT集的交集SbbS+S(T)(TT,Sb,+,(b,+,(TSb,+,(顯然，GS不是 LL(1) 文法。3、（1）將GS改寫如下：(4分)GS：Sb|+|(T)T,S T|TS T規(guī)則SELECT集左部相同規(guī)則的SELECT集的交集SbbS

26、+S(T)(T,S T,T)TS Tb,+,(顯然，改寫后的GS是 LL(1) 文法。（2）預(yù)測分析表：(4分)b+(,)#Sb+(T)T ,S TTS TS TS T4、輸入串(b,+)#的分析過程：(5分)步驟分析棧剩余輸入串所用規(guī)則步驟分析棧剩余輸入串所用規(guī)則1#S(b,+)#S(T)7#) T S,+)#,匹配2#)T(b,+)#(匹配8#) T S+)#S+3#)Tb,+)#TS T9#) T+)#+匹配4#) T Sb,+)#Sb10#) T)#T5#) Tbb,+)#b匹配11#)#)匹配6#) T,+)#T,S T12#接受題型四七、現(xiàn)有文法GS： (共18分)0) S'

27、; S1) S L = R2) S R3) L * R4) L i5) R L1、 構(gòu)造GS的LR(0)項目集規(guī)范族DFA，并據(jù)此判斷GS是否為LR(0) 文法或SLR(1)文法。(6分)2、 構(gòu)造GS的LR(1)項目集規(guī)范族DFA，并據(jù)此判斷GS是否為LR(1)文法或LALR(1)文法。(6分)3、 給出相應(yīng)的LALR(1)分析表。(3分)4、 簡述LR分析算法。(3分)第七題： (18分) 1、（1）GS的LR(0)項目集規(guī)范族DFA（3分）：（2）檢查發(fā)現(xiàn)I2 =S L.=R, R L. 中存在移進(jìn)歸約沖突，所以，GS不是LR(0)文法。（1分）（3）在I2 =S L.=R, R L.

28、中，由于根據(jù)歸約項目R L.所得的FOLLOW(R)=,# 中含有移進(jìn)項目S L.=R中的“=”，當(dāng)面臨輸入符號為“ =” 時，出現(xiàn)了移進(jìn)歸約沖突： S L .=R I2 且 go(I2,=)=I6 Þ action2,= = S6 R L . I2 且 “=” 在FOLLOW(R)=,# 中， Þ action2,= = r5說明GS不是 SLR（1）文法。（2分）2、（1）GS的LR(1)項目集規(guī)范族DFA（3分）：（2）在上面LR(1)項目集規(guī)范族的I2中，當(dāng)輸入#號時才用項目RL.歸約；當(dāng)輸入=號時用項目SL.=R作移進(jìn)。所以， SLR(1)不能解決的移進(jìn)-歸約沖突

29、可由LR(1)方法解決。故該文法是LR(1)文法。（2分）（3）進(jìn)一步合并LR(1)項目集規(guī)范族中同心集I4和I11、I5和I12、I7和I13、I8和I10 ，得合并結(jié)果為：I4、I5 、 I7 、和I8 。顯然，它們依然不含歸約-歸約沖突。故該文法是LALR(1)文法。（1分）3、LALR（1）分析表：（3分）狀態(tài)ACTIONGOTO=*i#SLR0S4S51231acc2S6r53r24S4S5875r4r46S4S5897r3r38r5r2r59r14、LR算法如下：(3分)設(shè)s是棧頂狀態(tài)，a是輸入指針ip所指向的當(dāng)前符號；1）令ip指向輸入串的第一個符號；將#壓入符號棧，將開始狀態(tài)0

30、壓入狀態(tài)棧；2）重復(fù)執(zhí)行如下過程： if（actions,a=sj） 把符號a入符號棧，把狀態(tài)j入狀態(tài)棧； 使 ip 指向下一個輸入符號。 else if （actions,a=rj） 從棧頂彈出第j條規(guī)則右部串長|個符號； 把歸約得到的非終結(jié)符A壓入符號棧；將gotos,A的值j壓入狀態(tài)棧； 并輸出規(guī)則 A。 else if （actions,a=acc） return； /* 分析成功 */ else error()；/* 報錯 */ 說明：此答案只供參考，可以是其他答案，只要意思相近即可。七、對給定文法GS: (共18分)0) S S 1) S A2）S B3) A aAc4) A a5

31、) B bBd6) B b5、 構(gòu)造GS的LR(0)項目集規(guī)范族DFA，并據(jù)此判斷GS是否為LR(0)文法。 (6分)6、 進(jìn)一步判斷GS是否為SLR(1)文法，并給出對應(yīng)的SLR(1)分析表。(6分)3、給出輸入串bbd#的SLR(1)分析過程。(4分)4、判斷GS是否為LR(1)文法和LALR(1)文法。 (2分)第七題： (18分) 1、（1）GS的LR(0)項目集規(guī)范族DFA（4分）：（2）檢查發(fā)現(xiàn)I4 =A a., A .aAc, A .a 和I5 =B b., B .bBd, B .b 中存在移進(jìn)歸約沖突，所以，GS不是LR(0)文法。（2分）2、（1）在I4 =A a., A .

32、aAc, A .a 中，由于根據(jù)歸約項目A a.所得的FOLLOW(A)=c,# 中不含移進(jìn)項目A .aAc,或 A .a中的“a”。在構(gòu)造LR分析表時，遇到移進(jìn)項目A .aAc,或 A .a時，在“a”列置移進(jìn)標(biāo)記S4；遇到歸約項目A a.時，只在“c”,“#”兩列置歸約標(biāo)記r4。所以，I4中的移進(jìn)歸約沖突通過引入FOLLOW集得到了解決。、同樣，在I5 =B b., B .bBd, B .b 中，由于FOLLOW(B)=d,# 中不含 “b”。在構(gòu)造LR分析表時，遇到移進(jìn)項目B .bBd, B .b時，在“b”列置移進(jìn)標(biāo)記S5；遇到歸約項目B b.時，只在“d”,“#”兩列置歸約標(biāo)記r5。

33、所以，I5中的移進(jìn)歸約沖突通過引入FOLLOW集也得到了解決。故GS是 SLR（1）文法。（3分）（2）SLR(1)分析表如下：（3分）狀態(tài)ACTIONGOTOabcd#SAB0S4S51231acc 2r1 3r2 4S4r4r46 5S5r6r676S8 7S9 8r3r3 9r5r5 3、輸入串bbd#分析如下: （4分）步驟狀態(tài)棧符號棧剩余輸入串ACTIONGOTO10#bbd#S5205#bbd#S53055#bbd#r674057#bBd#S950579#bBd#r53603#B#r21701#S#ac

34、c4、根據(jù)各種LR分析方法的能力由強(qiáng)到弱的排列次序：LR(1)文法 > LALR(1) > SLR(1) > LR(0) 知：一個LR(0)文法肯定是SLR(1) 文法；一個SLR(1)文法肯定是LALR(1)文法；而一個LALR(1)文法肯定是LR(1)文法。既然GS 是SLR（1）文法，那么，它肯定也是LR(1)文法和LALR(1)文法。（2分）六、對給定文法GS: (共18分)0) S S 1) S A2）S B3) A aAc4) A a5) B bBd6) B b7、 構(gòu)造其LR(0)項目集規(guī)范族DFA，并據(jù)此判斷它是否為LR(0)文法。 (7分)8、 進(jìn)一步判斷它

35、是否為SLR(1)文法，并給出對應(yīng)的SLR(1)分析表。(6分)3、給出輸入串a(chǎn)ac#的SLR(1)分析過程。(5分)第六題： (18分) 1、（1）GS的LR(0)項目集規(guī)范族DFA（5分）：（2）檢查發(fā)現(xiàn)I4 =A a., A .aAc, A .a 和I5 =B b., B .bBd, B .b 中存在移進(jìn)歸約沖突，所以，GS不是LR(0)文法。（2分）2、（1）在I4 =A a., A .aAc, A .a 中，由于根據(jù)歸約項目A a.所得的FOLLOW(A)=c,# 中不含移進(jìn)項目A .aAc,或 A .a中的“a”。在構(gòu)造LR分析表時，遇到移進(jìn)項目A .aAc,或 A .a時，在“a

36、”列置移進(jìn)標(biāo)記S4；遇到歸約項目A a.時，只在“c”,“#”兩列置歸約標(biāo)記r4。所以，I4中的移進(jìn)歸約沖突通過引入FOLLOW集得到了解決。、同樣，在I5 =B b., B .bBd, B .b 中，由于FOLLOW(B)=d,# 中不含 “b”。在構(gòu)造LR分析表時，遇到移進(jìn)項目B .bBd, B .b時，在“b”列置移進(jìn)標(biāo)記S5；遇到歸約項目B b.時，只在“d”,“#”兩列置歸約標(biāo)記r5。所以，I5中的移進(jìn)歸約沖突通過引入FOLLOW集也得到了解決。故GS是 SLR（1）文法。（3分）（2）SLR(1)分析表如下：（3分）狀態(tài)ACTIONGOTOabcd#SAB0S4S51231acc&

37、#160;2r1 3r2 4S4r4r46 5S5r6r676S8 7S9 8r3r3 9r5r5 3、輸入串a(chǎn)ac#分析如下: （5分）步驟狀態(tài)棧符號棧剩余輸入串ACTIONGOTO10#aac#S4204#aac#S43044#aac#r464046#aAc#S850468#aAc#r32602#A#r11701#S#acc七、對任意給定的一個上下文無關(guān)文法GS: (共20分)9、 如何判斷GS是否為LR(0)文法。(4分)10、 如何判斷GS是否為SLR(1)文法。(4分)11、 如何判斷GS是否為LR(1)文法。(4分)12、 如何判斷GS是否為LALR(1)文法。(4分)5、說明LR(0)、SLR(1)、LR(1)和LALR(1)四類文法的相互關(guān)系。 (4分)第七題 (20分)對任意給定的一個上下文無關(guān)文法GS： 1、判斷是否為LR(0)文法的步驟：(4分)（1）構(gòu)造GS的LR(0)項目集規(guī)范族。（2）檢查各項目集中是否存在移進(jìn)歸約沖突或歸約歸約沖突。如果有某一個項目集中同時存在移進(jìn)項目和歸約項目，或者同時存在兩個或兩個以上的歸約項目，則該項目集存在移進(jìn)歸約沖突或歸約歸約沖突。（3）如果所有狀態(tài)中都不存在移進(jìn)歸約沖突或歸