编译原理―应用题

1、题型一四、现有文法GE:(共10分)E E+T|E-T|TT T*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)，即有 E-F*(i)成立，所以，E-F*(i)是文 法的一个句型。2、语法树(2分):EF（ E ）TIi3、句型分析(5分)句型E-F*(i)相对于E的短语有：E-F*(i), i 。句型E-F*(

2、i)相对于T的短语有：F*(i), F ，i。句型E-F*(i)相对于F的短语有：(i), i 。(3分) 句型E-F*(i)相对于T F的直接短语有：F句型E-F*(i)相对于F-i的直接短语有：i 。(2分)句型E-F*(i)的句柄为：F。( 1分)三、现有文法 GE:(共12分)E E+T|E-T|TT T*F|T/F|FF i|(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

3、 =F+T*(E)，即有E= F+T*(E)成立，所以，F+T*(E)是文法的一个句型2、语法树(3分)TF3、句型分析(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)相对于T F的直接短语有：F 。句型F+T*(E)相对于F (E)的直接短语有：(E)0 (2分)句型F+T*（E）的句柄为：F（1 分）1、有文法GS : （12分）S aAS|aA SbA|SS|ba（1）证明aabbaa是文法的一个句子。（3分）（2）构造句子aabbaa的语法

4、树。（3分）（3）指出该句子的所有短语、直接短语和句柄。（6分）答：（1）证明（3 分）：因为存在推导序列 S=aAS=aSbAS=aabAS=aabbaS=aabbaa，即有 S=*aabbaa成立，所以，是文法的一个句子。（2）语法树（3分）：/、a.1 A S/ S bl A1 、aS（3）句型分析（6分）：将句型改写为 a1a2b1b2a3a4,贝该句型相对于 S的短语： a1a2b1b2a3a4和a4;相对于 A的短语： a2b1b2a3和b2a3;对于S a的直接短语：a2, a4；相对于 A ba的直接短语：b2a3;句柄：a2。1有文法GE : （16分）E T + E| T

5、T T * F | F F （ 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的短语有

6、i。相对于T T*F的直接短语：T*F,相对于Fi的直 接短语：i。句柄：T*F。（4）该句型的所有素短语：T*F和I; T*F为最左素短语。（3分）、现有文法GS:（共10分）S SS*S SS+S a6证明aa+a*是文法的一个句子。（2分）7、构造句型aa+a*的语法推导树。（2分）8、 指出该句型所有短语、直接短语和句柄。（6分）第二题：（10分）3、证明（3 分）：因为存在推导序列 S=SS*=SS+S*=aS+S*aa+S*=aa+a*,*即有S= aa+a*成立，且aa+a*全部由终结符构成，所以aa+a*是文法的 一个句子。2、语法树（2分）：S3、句型分析（5分）句型aa+a

7、*相对于S的短语有：a +&*, a +, a i,a 2,a3。（ 2分）句型aa+a*相对于S a的直接短语有：a或ai,a2,a3。 （2分）句型aa+a*的句柄为：a 1。（1分）三、现有文法 GE:（共12分）E EE+E EE*E FF i9、 证明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+ ，即有E ii*i+ 成立（2分），且ii*i+

8、所含符号全部为终 结符（1分），所以，ii*i+是文法的一个句子。2、语法树（3分）F F i 3i 1 i 23、句型分析（6分）句型ii*i+ 相对于E的短语有：i心引3+, i花*, i 1,i 2,i 3（3分）句型ii*i+相对于F的短语有：i订2,i 3（ 1分）句型ii*i+相对于Fi的直接短语有:i或i 1,i 2,i 3（1分）句型ii*i+的句柄为：i 1（1分）说明：（1）短语、直接短语的说明可不具体指明所相对的非终结符或规则。（2）没用下标区分i 1,i 2,i 3的扣1分。（3）短语每错两个扣1分题型二三、给定正规式 R=（01|10） （01|10） *，要求：（1

9、0 分）2、构造对应的正规文法 G使得L（G）=L（R）。（4分）3、 构造对应的NFA M状态图，使得L（M）=L（R）。（3 分）3、将所得NFA M确定化为DFA （3 分）第三题：（10分）1、正规文法GS（ 4分）：S 0A|1BA 1S|1B 0S|02、NFA （3 分） ：3、DFA（ 3 分）：步骤如下表所示（可省）：标记新状态I011T0SAB 丁T1AS,ZT2BpS,ZT3S,ZAB将集合T0至T3各用一个状态表示，确定化后所得 DFA M如下:四、给定正规式R=d（a|bc） *d，要求：（12 分）4、构造对应的NFA M状态图，使得L（M）=L（R）。（4 分）5

10、、 将所得NFA M确定化和最小化。（8 分）第四题：（12分）1、NFA M（4 分）2、（1）确定化（4分）步骤如下表所示（可省）：标记新状态laIbIcIdTO1f 2,4 dT12,42,435T23:2,4T35将集合TO至T3各用一个状态表示，确定化后所得 DFA M如下:（2）最小化 （4分）步骤如下表所示（可省）：步 骤分割根据分割结果1是否终态P 1=1, 2, 3 ; P2=42P1根据d弧映射P11=1 : P12=2 : P13=3最后还有4个不可再分割的子集，每个子集中只包含一个状态，即原DFA M已经是最小化DFA。3说明：此大题答案只供参考，可以是其他答案，只要功

11、能等价即可。3、有正规文法GS:(12分)St aA|bBAt bS|baS|a构造对应的正规式 R，使得L(R)=L(G)。 (3分)(2)构造对应的 NFA状态图，使得 L(M)=L(R)。(3分)将所得NFA确定化为DFA。(3分)将所得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分)将所得NFA确定化为DFA状态图如上右图所示：(3分)(4)将所得 DFA最小化：首先

12、根据是否终态划分为非终态集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分)：标记新状态I011T0AB,C,ET1B,C,ED,GF,GT2:D,GGHT3F,GGHT4:GG:町:T5H将集合TO至T5各用一个状态表示，确定化后所得 DFA M如下:3、最小化 （4分）步骤如

13、下表所示（可省）：步骤分割根据分割结果1是否终态P仁A,B,C,D,E ; P2=F2P1根据1弧映射P11=A; P12=B; P13=C,D,E最后有四个不可再分割的子集，每个子集对应一个状态，即有最小化DFA如下：说明：此大题答案只供参考，可以是其他答案，只要功能等价即可。四、将正规式R=bb（a|bb）a*b转换为相应的NFA Ml状态图，使得L（M）=L（R），并将所得NFA M确定化和最小化。（12分）第四题：（12分）1、NFA M （3 分）2、确定化（3分）步骤如下表所示（可省）：标记新状态lalbTOf2:T123,4,6T23,4,65,97T3:5,99:10:T478

14、,9T599 10T6:10:T78,9910将集合TO至T7各用一个状态表示，确定化后所得 DFA M如下:3、最小化 （3分）步骤如下表所示（可省）：步骤分割根据分割结果1是否终态:P仁1, 2, 3, 4, 5, 6, 8 ; P2=72P1根据a弧映射P11=3, 4, 6, 8; P12=1, 2, 53P11根据b弧映射:P11 仁:P112=4, 6, 84P12根据b弧映射P121=1 : 2 : P122 =5最后有六个不可再分割的子集，每个子集对应一个状态，得最小化DFA如下:说明：此大题答案只供参考，可以是其他答案，只要功能等价即可。题型三五、任意给定一个文法 GS:（1

15、0分）1、 给出判断GS是否为LL 文法的步骤。（4分）2、 如果GS是LL文法，怎样构造它的预测分析表？（3分）3、 怎样根据预测分析表对给定的某个输入串进行预测分析？（3分）第五题：（10分）对任意给定的一个文法 GS:1 、判断是否为LL（1）文法的步骤：（4分）1）画出各非终结符能否推导出的情况表。2）用定义法或关系图法计算FIRST、FOLLOWS3）计算各规则的SELECT!。4）检查所有左部相同的规则的SELECT集是否相交，如果不相交，贝U GS 为LL（1）文法。否则，说明GS不是LL（1）文法。2、构造GS预测分析表：（3分）预测分析表为一个二维矩阵,其形式为MA,a,其中

16、A VN ,a VT或#。对 文法中的规则A- a ,若有终结符a SELECT（A a ）,则将A- a填入MA,a中。 （书写时，通常省略规则左部，只填- a ）。对所有没有值的MA,a标记为出错。3、 根据预测分析表M对给定的某个输入串进行预测分析的过程，可用下述算 法表示：（3分）#,S进栈；II初始化工作，S为开始符doX= 当前栈顶符号 ；a= 当前输入符号；if (X V TU #)if (X=a)if (X ! =#) 将X弹出,且前移输入指针else error() else if (MX,a=Y1Y2Yk )将X弹出；依次YkY2Y1将压入栈;else error()；wh

17、ile( X ! =#)；说明： 此答案只供参考，可以是其他答案，只要意思相近即可。六、已知 GS ：(18分)S (A)|a|bA A,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)=(

18、a,(b,S) =(a,(b,b)2、(1) 判断： (3 分)计算各条规则的SELECTS及左部相同规则的SELECTS的交集如下：规则SELECT!左部相同规则的SELEC集的交集S aaS bbS (A)(A A,Sa,b,(a,b,(A Sa,b,(显然，GS不是LL 文法。(2)将GS改写如下：(4分)GS:S a|b|(A)A ,SA | &A SA规则SELEC集左部相同规则的SELEC集的交集S aaS bbS (A)(A ,S A，A )A SAa,b,(显然，改写后的GS是LL(1)文法(2)预测分析表：(3分)ab(J)#Sab(A)A ,SAASASASA4、( 1)输

19、入串(b,b)#的分析过程：(4分)步骤分析栈剩余输入串所用规则步骤分析栈剩余输入串所用规则1#S(b,b)#S (A)7#)A S,b)#,匹配2#)A(b,b)#(匹配8#)A Sb)#St b3#)Ab,b)#At SA9#)A bb)#b匹配4#) ASb,b)#St b10#)A)#At 5#)A bb,b)#b匹配11#)#)匹配6#)A,b)#At ,s A12#接受(2)输入串(b,b)是GS的句子。(1分)4、对表达式文法 GE:(16分)E t E- T | TT A F| F( E )| a(1) 判断GE是否为LL(1)文法。若不是，改造为 LL(1)文法。(8分)(2

20、) 构造预测分析表，并对输入串w=a-aAa#进行预测分析。(8分),a a(2分)Ft ( E ) | a答:(1)计算GE的SELECT集如下：(2分)SELECT(Et E -T )=( , aSELECT(Et t )=(SELECT(Tt t a F)=( , aSELECT (T t F)=(,SELECT( F t ( e )=( SELECT( F t a=a由于 SELECT(Et E -T ) n SELECT(E t T )=( a MR SELECT(T T a F) n SELECT(T F)=( , a MR select (F t ( E ) n select (

21、F t a) = ( n a= 故GE不是LL(1)文法。(1分)对GE的E t E T和T t T a F两条规则消除左递归后变为： Et T E Et-t E | Tt f T Tta f T |计算消除左递归后 GE的SELECT集如下：(2分)SELECT(Et T E )=( a SELECT(Et)=#)select(tt a f t )=A SELECT(Ft ( E )=(由于 select(et -t e ) n select (ESELECT(Et TE )= - SELECT(Tt F T )=( a SELECT(Tt)= ,-#, )SELECT(F t a)=at

22、) = Rselect (T t a f t) n select (T t)= r select (F t ( E ) n select (F t a) = = 0 故消除左递归后的 GE是LL(1)文法。(1分)(2)根据消除左递归后的GE的SELECT集构造预测分析表如下:(3分)E二JF-*ef tI4T-FT*rpi-* e-nf tf tFr-(E)iH输入串T1豪EIE2#E*T3#ETTdFa-a Aa#F Hl4ET-aa-a Aa#(Hi Kua5*ETAa#r eB*七去宜#E-*-TE7-a Ae#匹配-8#ETa Aa#T -Pf9*Aa#F 一 ti10洋ETa匹配a

23、11#EbTr 一*12L慎配亠13#S T F-a#卩f si14a#匹配0IS*T g16#r e*17*对输入串w=a-aAa#的分析过程如下表所示(注意：规则右部以逆序入栈)：(5分)四、已知GE :(15分)E- a|*|(T)T- T,E|E4、 给出(*,(a,*)的最右推导。(3分)5、 将GE改写为LL 文法，再给出它的预测分析表；(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,*)=(

24、*,(a,*)2、( 1)将GE改写如下：(3分)GE:E- a|*|(T)T- ,E T | &T E T规则SELECTS左部相同规则的SELECTS的交集E- aaE *E- (T)(T ,E T，T &)T ETa,*,(显然，改写后的GE是LL 文法。(2)预测分析表：(4分)a*(J)#Ea*(T)T ,ETTETETET4、输入串(a,*)#的分析过程：(5分)步骤分析栈剩余输入串所用规则步骤分析栈剩余输入串所用规则1#E(a,*)#E (T)7#) T E,*)#,匹配2#)T(a,*)#(匹配8#) T E*)#E *3#)Ta,*)#T ET9#) T *)#*匹配4#)

25、T Ea,*)#E a10#) T )#T 5#) T aa,*)#a匹配11#)#)匹配6#) T ,*)#T ,S T12#接受五、已知GS :(18分)S- b|+|(T)T T,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分)

26、计算各条规则的SELECT及左部相同规则的SELECT!的交集如下:规则SELECTS左部相同规则的SELECTS的交集S bbS+S (T)(T T,Sb,+,(b,+,(T Sb,+,(显然，GS不是LL(1)文法。3、( 1)将GS改写如下：(4分)GS:S- b|+|(T)Tt ,S T | T S T规则SELECTS左部相同规则的SELECTS的交集S bbS+S (T)(T ,S T，T &)T S Tb,+,(显然，改写后的GS是LL(1)文法(2)预测分析表：(4分)b+(J)#Sb+(T)T ,S T TS TS TS T4、输入串(b,+)#的分析过程：(5分)步骤分析栈

27、剩余输入串所用规则步骤分析栈剩余输入串所用规则1#S(b,+)#S (T)7#) T S,+)#,匹配2#)T(b,+)#(匹配8#) T S+)#S+3#)Tb,+)#T S T9#) T +)#+匹配4#) TSb,+)#S b10#) T )#T &5#) T bb,+)#b匹配11#)#)匹配6#) T ,+)#T ,S T12#接受题型四七、现有文法GS:(共18分)0)SS1) SL = R2) SR3) L* R4) Li5) RL1、构造GS的LR(O)项目集规范族DFA并据此判断GS是否为LR(O)文 法或SLR(1)文法。(6分)2、构造GS的LR(1)项目集规范族DFA并

28、据此判断GS是否为LR(1)文 法或LALR(1)文法。(6分)3、 给出相应的LALR分析表。(3分)4、 简述LR分析算法。(3分)第七题：(18分)1、( 1)GS的LR(O)项目集规范族DFA(3分)：(2) 检查发现12 =S- L.=R, R - L. 中存在移进一归约冲突，所以，GS不是LR(O)文法。(1分)(3) 在I2 =S - L.=R, R - L. 中，由于根据归约项目 R - L.所得的 FOLLOW(R)=,#中含有移进项目S - L.=R中的“二”，当面临输入符号为“=” 时，出现了移进归约冲突：S L .=R 12 且 go(l2,=)=l6actio n 2

29、,= = S6R L . 12 且 “=” 在 FOLLOW(R)=,# 中，actio n 2,= = r5说明GS不是SLR (1)文法。(2分)2、(1) GS的LR(1)项目集规范族DFA(3分)：Ia:SR.LR, =/#Rf. U 二/#.机=/.i,二/#打： sl 二出 aR7,#S. S,ff .L二R, # SrL. *R, =/U L. i, =/URf丄#SL= R,ffRf I nL-*.*R,L- i, ftIll:L*. R, #R. U #L. *R?# L. i, UI 证 Rf L., #* Rf L-,二/#J片：L *R., =/#R(2) 在上面LR项

30、目集规范族的12中，当输入#号时才用项目R-L.归约; 当输入=号时用项目S-L.=R作移进。所以，SLR 不能解决的移进-归约冲突 可由LR(1)方法解决。故该文法是LR(1)文法。(2分)(3) 进一步合并LR(1)项目集规范族中同心集14和111、15和112、17和 113、18和110，得合并结果为：I4、15、I7 、和18。显然，它们依然不 含归约-归约冲突。故该文法是LALR(1)文法。(1分)3、LALR( 1)分析表：(3 分)状态ACTIONGOTO=*i#SLR0S4S51231acc2S6r53r24S4S5875r4r46S4S5897r3r38r5r2r59r14

31、、LR算法如下：(3分)设s是栈顶状态，a是输入指针ip所指向的当前符号；1) 令ip指向输入串的第一个符号；将#压入符号栈，将开始状态0压入状 态栈；2) 重复执行如下过程：if( actio n s,a=sj) 把符号a入符号栈，把状态j入状态栈；使ip指向下一个输入符号。else if( acti on s,a=rj) 从栈顶弹出第j条规则右部串长| B |个符号；把归约得到的非终结符A压入符号栈；将gotos,A的值j压入状态栈；并输出规则A B。else if(acti on s,a=acc )return ； /* 分析成功*/elseerror()； /* 报错 */说明：此答案

32、只供参考，可以是其他答案，只要意思相近即可。七、对给定文法GS:( 共18分)0) S S1) S A2) S B3) A aAc4) A a5) B bBd6) B b5、 构造GS的LR(O)项目集规范族DFA并据此判断GS是否为LR(O)文 法。(6分)6、进一步判断GS是否为SLR文法，并给出对应的SLR分析表。(6分) 3、 给出输入串bbd#的SLR(1)分析过程。(4分)4、判断GS是否为LR(1)文法和LALR(1)文法。(2分)第七题：(18分)1、( 1)GS的LR(0)项目集规范族DFA(4分):I-: B *bB.d爲：bBd.A.ilAc(2)检查发现 I4 =A a

33、., 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 中

34、，由于 FOLLOW(B)=d,# 中 不含 “b”。在构造LR分析表时，遇到移进项目B .bBd, B .b时，在“ b” 列置移进标记S5;遇到归约项目B b.时，只在“ d”，“#”两列置归约标记 r5。所以，15中的移进一归约冲突通过引入 FOLLOWS也得到了解决故GS是SLR (1)文法。(3分)(2) SLR(1)分析表如下：(3分)状态ACTIONGOTOabcd#SAB0S4S51231acc2r13r24S4r4r465S5r6r676S87S98r3r39r5r53、输入串bbd#分析如下：(4分)步骤状态栈符号栈剩余输入串ACTIONGOTO10#bbd#S5205#b

35、bd#S53055#bbd#r674057#bBd#S950579#bBd#r53603#B#r21701#S#acc4、根据各种LR分析方法的能力由强到弱的排列次序：LR(1)文法LALR(1) SLR(1) LR(0) 知：一个 LR(O)文法肯定是 SLR(1)文法；一个SLR(1)文法肯定是LALR(1)文法；而一个LALR(1)文法肯定是LR(1)文法。既然GS是SLR( 1)文法，那么，它肯定也是 LR文法和LALR(1)文法。(2分)六、对给定文法GS:( 共18分)0) S S1) S A2) S B3) A aAc4) A a5) B bBd6) B b7、 构造其LR(0)

36、项目集规范族DFA并据此判断它是否为LR(0)文法。(7分)8、进一步判断它是否为SLR(1)文法，并给出对应的SLR(1)分析表。(6分)3、给出输入串aac#的SLR(1)分析过程。(5分)第六题：(18分)1、( 1) GS的LR(0)项目集规范族DFA(5分)：(2)检查发现 14 =A a., A .aAc, A .a 和 15 =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 .

37、a中的“ a”。在 构造LR分析表时，遇到移进项目 A f.aAc,或A f.a时，在“ a”列置移进标 记S4;遇到归约项目A - a.时，只在“ c”，“ # ”两列置归约标记r4。所以， 14中的移进一归约冲突通过引入 FOLLOW集得到了解决。、同样，在 15 =B b., B .bBd, B .b 中，由于 FOLLOW(B)=d,# 中 不含 “b”。在构造LR分析表时，遇到移进项目B -.bBd, B -.b时，在“ b” 列置移进标记S5;遇到归约项目B -b.时，只在“ d”，“#”两列置归约标记 r5。所以，15中的移进一归约冲突通过引入 FOLLOWS也得到了解决。故GS

38、是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（O）文法。（4分）10、如何判断GS是否为SLR（1）文法。（4分）11、如何

39、判断GS是否为LR（1）文法。（4分）12、如何判断GS是否为LALR文法。（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）文法。否则