1、精選優質文檔-傾情為你奉上題型一四、現有文法GE： (共10分)EE+T|E-T|TTT*F|T/F|FFi|(E) 1、 證明：E-F*(i)是文法的一個句型。(3分)2、 構造句型E-F*(i)的語法推導樹。(2分)1、 指出該句型所有短語、直接短語和句柄。(5分)第四題：（10分）1、 證明（3分）：因為存在推導序列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分）三、現有文法GE： (共12分)EE+T|E-T|TTT*F|T/F|FFi|(E) 3、 證明：F+T*(E)是文法的一個句型。(3分)4、 構造句型F+T*(E)的語法推導樹。(3分)5、 指出該句型所有短語、直接短語和句

3、柄。(6分)第三題：（12分）2、 證明（3分）：因為存在推導序列E => E+T => T+T =>F+T =>F+T*F => F+T*(E)，即有 EF+T*(E)成立，所以，F+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)構造句子aabbaa的語法樹。(3分)(3)指出該句子的所有短語、直接短語和句柄。(6分)答：（1）證明(3分)：因為存在推導序列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)構造型T+T*F+i的語法樹。(3分)(3)指出該句型的所有短語、直接短語和句柄。(7分)(4)指出該句型的所有素短語和最左素短語。(3分)答：1）證明(3分)：因為存在推導序列：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分)二、現有文法GS： (共10分)SSS*SSS+Sa6、 證明aa+a*是文法的一個句子。(2分)7、 構造句型aa+a*的語法推導樹。(2分)8、 指出該句型所有短語、直接短語和句柄。(6分)第二題：（10分）3、 證明（3分）：因為存在推導序

7、列S=>SS*=>SS+S*=>aS+S* =>aa+S*=>aa+a*，即有 Saa+a*成立，且aa+a*全部由終結符構成，所以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分）三、現有文法GE： (共12分)EEE+EEE*EFFi9、 證明ii*i+是文法的一個句子。(3分)10、

8、構造句型ii*i+的語法推導樹。(3分)11、 指出該句型所有短語、直接短語和句柄。(6分)第三題：（12分）1、證明（3分）：因為存在推導序列E=>EE+=>EE*E+=>FE*E+=>iE*E+=>iF*E+=> ii*E+=>ii*F+=>ii*i+，即有Eii*i+成立（2分），且ii*i+所含符號全部為終結符（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）短語、直接短語的說明可不具體指明所相對的非終結符或規則。（2）沒用下標區分i1,i2,i3 的扣1分。（3）短語每錯兩個扣1分。題型二三、給定正規式R=(01|10) (01|10)* ，要求： (10分)2、 構造對應的正規文法G，使得L(G)=L(R)。 (4分)3、 構造對應的NFA M狀態圖，使得L(M)=L(R)。 (3分)3、將所得NFA M確定化為DFA。 (3分)第三題：（10分）1、正規文法GS（4分）

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

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

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

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

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

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

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

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)的最左推導。(3分)2、判斷該文法是否為LL(1)文法。若是，直接給出它的預測分析表；若不是，先將其改寫為LL(1)文法，再給出它的預測分析表；(10分)3、給出輸入串(b,b)#的分析過程，并說明該串是否為GS的句

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

19、ELECT集左部相同規則的SELECT集的交集SaaSbbS(A)(A,S A,A)ASAa,b,(顯然，改寫后的GS是 LL(1) 文法。（2）預測分析表：(3分)ab(,)#Sab(A)A ,SAASASASA4、（1）輸入串(b,b)#的分析過程：(4分)步驟分析棧剩余輸入串所用規則步驟分析棧剩余輸入串所用規則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、對表達式文法GE： (16分)E E - TTT T FFF ( E )a(1)判斷GE是否為LL(1)文法。若不是，改造為LL(1)文法。(8分)(2)構造預測分析表，并對輸入串w=a-aa#進行預測分析。(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兩條規則消除左遞歸后變為：(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）根據消除左遞歸后的GE的SELECT集構造預測分析表如下：(3分) 對輸入串w=a-aa#的分析過程如下表所示（注意：規則右部以逆序入棧）：(5分)四、已知GE： (15分)Ea|*|(T)TT,E|E4、 給出(*,(a,*)的最右推導。(3分)5、 將GE改寫為LL(1)文法，再給出它的預測分析表；(7分)6、 給出輸入串(a,*)#的分析過程。(5分)第四題： (15分)1、給出(*,(a,*)

23、的最右推導：(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規則SELECT集左部相同規則的SELECT集的交集EaaE*E(T)(T,E T,T)TETa,*,(顯然，改寫后的GE是 LL(1) 文法。（2）預測分析表：(4分)a*(,)#Ea*(T)T ,ETTETETET4、輸入串(a,*)#的分析過程：(5分)步驟分析棧剩余輸入串所用規

24、則步驟分析棧剩余輸入串所用規則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,+)的最左推導。(2分)8、 證明GS不是LL(1)文法。(3分)9、 將GS改寫為LL(1)文法，再給出它的預測分析表；(8分)4、給出輸入串(b,+)#的分析過程。(5分)第五題： (18分)1、給出(+,(b,+)

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

26、+S(T)(T,S T,T)TS Tb,+,(顯然，改寫后的GS是 LL(1) 文法。（2）預測分析表：(4分)b+(,)#Sb+(T)T ,S TTS TS TS T4、輸入串(b,+)#的分析過程：(5分)步驟分析棧剩余輸入串所用規則步驟分析棧剩余輸入串所用規則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#接受題型四七、現有文法GS： (共18分)0) S'

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

28、中，由于根據歸約項目R L.所得的FOLLOW(R)=,# 中含有移進項目S L.=R中的“=”，當面臨輸入符號為“ =” 時，出現了移進歸約沖突： 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)項目集規范族DFA（3分）：（2）在上面LR(1)項目集規范族的I2中，當輸入#號時才用項目RL.歸約；當輸入=號時用項目SL.=R作移進。所以， SLR(1)不能解決的移進-歸約沖突

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

30、壓入狀態棧；2）重復執行如下過程： if（actions,a=sj） 把符號a入符號棧，把狀態j入狀態棧； 使 ip 指向下一個輸入符號。 else if （actions,a=rj） 從棧頂彈出第j條規則右部串長|個符號； 把歸約得到的非終結符A壓入符號棧；將gotos,A的值j壓入狀態棧； 并輸出規則 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、 構造GS的LR(0)項目集規范族DFA，并據此判斷GS是否為LR(0)文法。 (6分)6、 進一步判斷GS是否為SLR(1)文法，并給出對應的SLR(1)分析表。(6分)3、給出輸入串bbd#的SLR(1)分析過程。(4分)4、判斷GS是否為LR(1)文法和LALR(1)文法。 (2分)第七題： (18分) 1、（1）GS的LR(0)項目集規范族DFA（4分）：（2）檢查發現I4 =A a., A .aAc, A .a 和I5 =B b., B .bBd, B .b 中存在移進歸約沖突，所以，GS不是LR(0)文法。（2分）2、（1）在I4 =A a., A .

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

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

34、c4、根據各種LR分析方法的能力由強到弱的排列次序：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、 構造其LR(0)項目集規范族DFA，并據此判斷它是否為LR(0)文法。 (7分)8、 進一步判斷它

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

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

37、#160;2r1 3r2 4S4r4r46 5S5r6r676S8 7S9 8r3r3 9r5r5 3、輸入串aac#分析如下: （5分）步驟狀態棧符號棧剩余輸入串ACTIONGOTO10#aac#S4204#aac#S43044#aac#r464046#aAc#S850468#aAc#r32602#A#r11701#S#acc七、對任意給定的一個上下文無關文法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)四類文法的相互關系。 (4分)第七題 (20分)對任意給定的一個上下文無關文法GS： 1、判斷是否為LR(0)文法的步驟：(4分)（1）構造GS的LR(0)項目集規范族。（2）檢查各項目集中是否存在移進歸約沖突或歸約歸約沖突。如果有某一個項目集中同時存在移進項目和歸約項目，或者同時存在兩個或兩個以上的歸約項目，則該項目集存在移進歸約沖突或歸約歸約沖突。（3）如果所有狀態中都不存在移進歸約沖突或歸