编译原理—应用题

题型一四、现有文法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 （ 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、 指出该句型所有短语、直接短语和句柄。(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)的直接短语有: (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的短语：a1a2b1b2a3a4和 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=*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分）：因为存在推导序列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、 构造句型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分）句型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分）：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各用一个状态表示，确定化后所得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最小化。 (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)=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如下： 说明：此大题答案只供参考，可以是其他答案，只要功能等价即可。四、将正规式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根据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）用定义法或关系图法计算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=当前输入符号；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的句子。(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规则SELECT集左部相同规则的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,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(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) =SELECT (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,*)的最右推导：(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分)步骤分析栈剩余输入串所用规则步骤分析栈剩余输入串所用规则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,+)的最左推导：(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+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 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. 中，由于根据归约项目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)不能解决的移进-归约冲突可由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压入状态栈；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) 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 .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。所以，I5中的移进归约冲突通过引入FOLLOW集也得到了解决。故GS是 SLR（1）文法。（3分）（2）SLR(1)分析表如下：（3分）状态ACTIONGOTOabcd#SAB0S4S51231acc2r13r24S4r4r465S5r6r676S87S98r3r39r5r53、输入串bbd#分析如下: （4分）步骤状态栈符号栈剩余输入串ACTIONGOTO10#bbd#S5205#bbd#S53055#bbd#r674057#bBd#S950579#bBd#r53603#B#r21701#S#acc4、根据各种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、 进一步判断它是否为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”列置移进标记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#SAB0S4S51231acc2r13r24S4r4r465S5r6r676S87S98r3r39r5r53、输入串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）如果所有状态中都不存在移进归约冲突或归约归约冲突，说明GS是LR(0)文法。否则，说明GS不是LR(0)文法。2、判断是否为SLR(1)文法的步骤：(4分)（1）构造GS的LR(0)项目集规范族。（2）检查各项目集中是否存在移进归约冲突或归约归约冲突。如果有某一个项目集中同时存在移进项目和归约项目，或者同时存在两个或两个以上的归约项目，则该项目集存在移进归约冲突或归约归约冲突。（3）如果对各个项目集I中存在的移进归约冲突或归约归约冲突都可通过如下引入FOLLOW集的方法解决，即对I=X.b，A . ，B. ，若所有含有A和B的句型中，满足：FOLLOW(A)FOLLOW(B)=且FOLLOW (A)b=FOLLOW(B)b = ，则在状态I中面临输入符a的动作可由下面规定决策：若a=b，则移进；若aFOLLOW(A)，则用A . 归约，若aFOLLOW(B)，则用B. 归约；此外报错。也即在根据LR(0)项目集规范族构造LR分析表时，遇到归约项目时，只在该项目左边非终结符的FOLLOW集元素列置归约标记rj。如果这样构造出来的LR分析表不存在冲突，则 GS为SLR（1）文法。否则，GS不是SLR(1)文法。3、判断是否为LR(1)文法的步骤：(4分)（1）构造GS的LR(1)项目集规范族（注意各个项目都带有向前搜索符号集）。（2）检查各项目集中是否存在移进归约冲突或归约归约冲突。如果有某一个项目集中同时存在移进项目和归约项目，或者同时存在两个或两个以上的归约项目，则该项目集存在移进归约冲突或归约归约冲突。（3）如果对各个项目集I中存在的移进归约冲突或归约归约冲突都可通过考虑项目所带的向前搜索符号集来解决，即根据LR(1)项目集规范族构造LR分析表时，遇到归约项目时，只在该项目所带的向前搜索符号集元素列置归约标记rj。如果这样构造出来的LR分析表不存在冲突，则 GS为LR（1）文法。否则，GS不是LR(1)文法。4、判断是否为LALR(1)文法的步骤：(4分)（1）构造GS的LR(1)项目集规范族，并进一步合并LR(1)项目集规范簇中的所有同心集。（2）检查合并同心集后各项目集中是否存在移进归约冲突或归约归约冲突。如果有某一个项目集中同时存在移进项目和归约项目，或者同时存在两个或两个以上的归约项目，则该项目集存在移进归约冲突或归约归约冲突。（3）如果对各个项目集I中存在的移进归约冲突或归约归约冲突都可通过考虑项目所带的向前搜索符号集来解决，即根据合并同心集后的LR(1)项目集规范族构造LR分析表时，遇到归约项目时，只在该项目所带的向前搜索符号集元素列置归约标记rj。如果这样构造出来的LR分析表不存在冲突，则 GS为LALR（1）文法。否则，GS不是LALR(1)文法。5、四类文法的相互关系： (4分)一个LR(0)文法肯定是SLR(1)文法；一个SLR(1)文法肯定是LALR(1)文法；而一个LALR(1)文法肯定是LR(1)文法。反之，不成立。说明：此答案只供参考，可以是其他答案，只要意思相近即可。