编译原理—应用题

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）如果所有状态中都不存在移进归约冲突或归