编译原理题库——综合题.doc

编译原理A卷已知文法 A-aAd|aAb| 判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。解：增加一个非终结符S/后，产生原文法的增广文法有： S-A A-aAd|aAb| 下面构造它的LR(0)项目集规范族为： 从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOLLOW(A)a=b,d,#a=，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。 其SLR(1)分析表为： 对输入串ab#给出分析过程为： 编译原理B卷构造下述文法 GS 的自动机： S-A0 A-A0|S1|0 该自动机是确定的吗？若不确定，则对它确定化。解：由于该文法的产生式S-A0，A-A0|S1中没有字符集VT的输入，所以不是确定的自动机。 要将其他确定化，必须先用代入法得到它对应的正规式。把S?A0代入产生式A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入S-A0有该文法的正规式：0(0|01)*0，所以，改写该文法为确定的自动机为： 由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化： 下表由子集法将NFA转换为DFA: 由上表可知DFA为：编译原理C卷6(20分)已知上下文无关文法：S L=R | RL *R | idR L(1) 请构造非终结符的FIRST和FOLLOW集合。（5分）(2) 构造该文法的LL(1)分析表。该文法是LL(1)文法吗？（15分7. （20分）考虑以下文法：S AA BA | B aB| b证明该文法是LR（1）的。(1)证明它是LR(1)文法；(2)构造它的LR(1)分析表。7（20分）阅读下面的LEX程序，并回答：（1）该程序完成了什么功能？（2）修改该程序，使之能够计算输入的标识符个数。（直接改在试题上）LEX程序如下：%# include int num_int = 0;int num_float = 0;int num_line = 0;int num_id = 0;%digit 0-9integer +-?digit+flt +-?digit+.digit+lettera-zA-zidletter(letter|digit)*%integer num_int+ ;flt num_float+ ;n num_line+ ;. ;idnum_id+;%main()yylex() ;printf(“n%d integers, %d floating point numbers, %d lines, %d identifiers.n”,num_int, num_float, num_line, num_id) ;C卷答案6解：(1)根据L *R | id，可得到FIRST(L)=*, id；根据R L，可得到FIRST(R)= FIRST(L)=*, id；根据S L=R | R，可得到FIRST(S)= FIRST(L) FIRST(R)=*, id；S是开始符号，所以有$FOLLOW(S)；又根据S L=R，可得到=FOLLOW(L)；又根据S L=R | R，可得到FOLLOW(S)FOLLOW(L)；又根据L *R，可得到FOLLOW(L)FOLLOW(R)；又根据R L，可得到FOLLOW(R)FOLLOW(L)；所以有FOLLOW(S)=$，FOLLOWL= FOLLOWR=$, =。(2) 构造LL(1)分析表如下：*=id$SS L=RS RS L=RS RLL *RL idRR LR L由于分析的表目中存在冲突，该文法不是LL(1)文法。7. （20分）考虑以下文法：S AA BA | B aB| b证明该文法是LR（1）的。(1)证明它是LR(1)文法；(2)构造它的LR(1)分析表；7答：该程序完成的功能：计算整数、浮点数的个数，统计行数，并分别输出。修改见程序。编译原理D卷7、证明下面文法是SLR(1)但不是LR(0)的。SAAAbbBaBaAcaaAb8、证明下面的文法是LL(1)的但不是SLR(1)的。SAaAbBbBaAB1.构造表达式（4*7+1）*2的附注语法树。四、（20分）设文法GS为SaAcB 问：1、该文法是否为算符文法，为什么？AAb|b 2、构造算符优先关系表。Bd 3、该文法是否可改造为LL（1）文法，为什么？五、（本题20分）设文法G为： EeAf|eBg AaA|a BBb|a对于输入串eaaaf，采用LR（0）、LL（1）、SLR（1）等方法中合适的一种进行分析。六、（25分）有作控制用的布尔表达式文法GE及其语义动作如下：1、 构造SLR（1）分析表（若不是SLR(1)）的，则说明理由）2、 分析布尔式abc的四元式生成过程，并画出最后的真假链表。3、 给出语句IF abc THEN I:=m*n ELSE I:=m+n的完整四元式序列。文法GE：(1)Eii E.TC:=NXQ; E.FC=NXQ+1;GEN(J,ENTRY(i),ENTRY(i),O);GEN(J, , ,0)(2)EAE E.FC:=E.FC; E.FC:=MERGE(A.TC ,E.TC)(3)AB BACKPATCH(B.FC ,NXQ); A.TC:=B.TC(4)Bi B.TC:=NXQ; B.FC:=NXQ+1;GEN(Jnz, ENTRY(i), ,0); GEN(J, , ,0)答案：7证明：求该文法的LR(0)项目集规范族如下：I0=S，AbBaGO(I0，A)=SA，AAb =I1GO(I0，b)=AbBa，BaAc，Ba，BaAb=I2GO(I1，b)=AAb=I3GO(I2，B)=AbBa=I4GO(I2，a)=BaAc，Ba，BaA b，AAb，Ab Ba=I5GO(I4，a)= AbBa= I6GO(I5，A)= BaAc，BaAb，AAb= I7GO(I5，b)= AbBa，BaAc，Ba，BaAb = I2GO(I7，c)= BaAc= I8GO(I2，b)= BaAb，AAb= I9考虑I1，I5都存在“移进归约”冲突，所以该文法不是LR(0)的。由于FOLLOW(S)=#，不包含b，所以I1的冲突可以消解；由于FOLLOW(B)=a，不包含b，所以I5的冲突可以消解；由于FOLLOW(B)=a，FOLLOW(A)=c，b，#，二者不相交，所以I9的冲突也可以消解。综上所述，该文法是SLR(1)的。8证明：因为FIRST(AaAb)=a，FIRST(BbBa)=bFIRST(AaAb)FIRST(BbBa)=所以该文法是LL(1)的。求该文法的LR(0)项目集规范族如下：I0=SS，SAaAb，SBbBa，A，BI1=SSI2=SAaAbI3=SBbBaI4=SAaAb，AI5=SBbBa，BI6=SAaAbI7=SBbBaI8=SAaAbI9=SBbBa考虑I0：FOLLOW(A)=FOLLOW(B)=a，bA和B的冲突无法消解，所以该文法不是SLR(1)的。1解：LE.val = 58nT.val = 58T.val = 29F.val = 2*digit.lexval= 2F.val = 29 (E.val = 29 )E.val = 28T.val = 1 +E.val = 1digit.lexval=1 11111= 1T.val = 28F.val = 7 *digit.lexval = 7digit.lexval=4四 答：1、该文法是算符文法。因为其任一产生式的右部都不含相继（并列）的非终结符，即不含如下形式QR的产生式右部。 （4分）2、FIRST(S)=a, LAST(S)=c,FIRST(A)=b, LAST(A)=b,FIRST(B)=d, LAST(B)=d。 （3分）构造算符优先关系表如下： （5分）abcd#abcd#=3、该文法可以改造为LL（1）文法。 （8分）原因： 消除左递归：SaAcB AbA AbA| Bd； FIRST(A)=a, FOLLOW(A)=c,FIRST(A)=b, , FOLLOW(A)=c,FIRST(B)=d, FOLLOW(B)=#,FIRST(S)=a, FOLLOW(S)=#,对于每个非终结符的各个产生式的FIRST集两两不相交； 对于A，FIRST（A）FOLLOW（A）=。 综上所述，原文法可以改造成LL（1）文法。五、（20分）原文法不是LL（1）文法，故不能直接使用LL（1）分析法进行分析。步骤如下：1、拓广文法：EE EeAfEeBg AaA Aa BBb Ba （2分）2、项目集规范族：（6分）由此项目集规范族可判断，原文法非LR（0）文法，故不能直接使用LR（0）分析法进行分析。因此，使用SLR（1）分析法分析原文法。3、构造SLR（1）分析表如下： FOLLOW(A)=f；FOLLOW(B)=b,g；FOLLOW(E)=#。ACTIONGOTO状态abefg#ABE0S211acc2S4353S64S8r7r5r775S10S96r27r48S8r579r310r6r6 （6分）4、分析输入串eaaaf如下：步骤状态符号输入串动作10#eaaaf#预备202#eaaaf#移进3024#eaaaf#移进40248#eaaaf#移进502488#eaaaf#移进602487#eaaAf#归约70247#eaAf#归约8023#aAf#归约90236#aAf#移进1001#E#归约11acc接受（6分）六、（25分）1、步骤：（1）拓广文法：EE Ei(1)i(2)EAE(1) AB Bi （2分）（2）项目集规范族：（6分）（3）SLR（1）分析表如下：FOLLOW(E)=#；FOLLOW(A)=i；FOLLOW(B)= 。ACTIONGOTO状态i#EAB0S21341acc2S6r43S27344S55r36S87r28r1（6分）2、分析输入串abc如下：步骤状态栈符号输入串动作四元式10#abc#预备202#ibc#移进304#Bbc#归约B.TC=1,B.FC=2;Gen(Jnz,a,_,0);Gen(J,_,_,3);4045#Bbc#移进503#Abc#归约A.TC=B.TC=1;BackPatch(2,3);6032#Aic#移进70326#AiC#移进803268#Aii#移进9037#AE#归约E.TC=3,E.FC=4;Gen(J,b,c,0);Gen(J,_,_,0);1001#E#归约E.FC=4;E.TC=MERG(1,3);11acc接受（6分）1、 Gen(Jnz,a,_,0)2、 Gen(J,_,_,3)3、 Gen(J,b,c,1)4、 Gen(J,_,_,0)整理： 真出口为3； 假出口为4。 （2分）3、四元式： 1、（Jnz,a,_,5）2、(J,_,_,3)3、(J,b,c,5)4、(J,_,_,8)5、(*,m,n,T1)6、(:=,T1,_,I)7、(J,_,_,10)8、(+,m,n,T2)9、(:=,T2,_,I)10、 （3分） 编译原理E卷三、应用题（共50分）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分)2、将下列条件语句翻译成四元式的中间代码形式：(6分)if ab or cf then s1 else s23、有正规文法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分)4、对表达式文法GE： (16分)E E - TTT T FFF ( E )a(1)判断GE是否为LL(1)文法。若不是，改造为LL(1)文法。(8分)(2)构造预测分析表，并对输入串w=a-aa#进行预测分析。(8分)三、应用题参考答案（共50分）1、（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分)2、if ab or cf then s1 else s2生成的三地址代码/四元式序列如下：(6分)(1) if a b goto (7)(2) goto (3)(3) if c f goto (7)(6) goto (p+1)(7) s1对应的四元式序列 (p) goto (q)(p+1) s2对应的四元式序列 (q)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分)4、(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分)二、设S=0，1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)三、写一个文法使其语言为L(G)= anbmambn | m,n1。(6分)四、对于文法G(E): (8分)ET|E+TTF|T*FF(E)|iETF(E)E+TFiTT*F1. 写出句型(T*F+i)的最右推导并画出语法树。2. 写出上述句型的短语，直接短语、句柄和素短语。五、设文法G(S)：(12分)1 构造各非终结符的FIRSTVT和LASTVT集合；2 构造优先关系表和优先函数。(12分)六、设某语言的do-while语句的语法形式为 (9分) S do S(1) While E其语义解释为：真假S(1)的代码E的代码针对自下而上的语法分析器，按如下要求构造该语句的翻译模式：(1) 写出适合语法制导翻译的产生式；(2) 写出每个产生式对应的语义动作.七、(8分)将语句if (A0) then while C0 do C:=C+D翻译成四元式。(8分)八、(10分) 设有基本块如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)画出DAG图；(2)设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。九、(9分) 设已构造出文法G(S)：(1) S BB(2) B aB(3) B b的LR分析表如下ACTIONGOTO状态ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。E卷答案：2答：构造相应的正规式：(0|1)*1(0|1) (3分)NFA: (2分) 1 110432 e e e e 1 0 0确定化：(3分)I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4 0 143210 0 1 0 0 0 1 1 13答：文法G(S):S aSb | BB bBa | ba4答：1. (4分)ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i) 2. (4分)短语：(T*F+i), T*F+i, T*F, i直接短语：T*F, i句柄：T*F素短语：T*F, i5答：(6分)FIRSTVT(S)= i，+，)，( FIRSTVT(A)= +，)，( FIRSTVT(B)= )，( LASTVT(S)= i，+，*，( LASTVT(A)= +，*，( LASTVT(B)= *，( 优先关系表: (3分)i+()*i()优先函数: (3分)i+()*f26616g14661。6答：(1). 适合语法制导翻译的文法(3分) G(S): R do UR S(1) While SU E (2). (6分) R do R.QUAD:=NXQ UR S(1) While U.QUAD:=R.QUAD; BACKPATCH(S.CHAIN, NXQ) SU E BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC 答案二：(1) S do M1 S(1) While M2 E M (3分)(2) M M.QUAD := NXQ (6分)S do M1 S(1) While M2 EBACKPATCH(S(1).CHAIN, M2.QUAD);BACKPATCH(E.TC, M1.QUAD); S.CHAIN:=E. FC7答：100 (j， B， 0， 104)103 (j， -， -， 109)104 (j， C， 0， 106)105 (j， -， -， 109)106 (+， C， D， T1)107 (:=， T1， -， C)108 (j， -， -， 104)109 (控制结构3分，其他5分)T1,T5, B3T24SR+/*_T3T4AT6,Bn4n5n1n2n3n6n8n78答：(1) DAG如右图：(6分)(2) 四元式序列：(4分)T1:=S+RT4:=S/RA:=T1-T4B:=T1*49答：步骤状态符号输入串00#abab#103#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab#70269#BaB#8025#BB#901#S#acc编译原理F卷四、问答题：22、设有语言 L= | 0,1 + ，且不以 0 开头，但以 00 结尾 。试写出描述 L 的正规表达式；构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的 NDFA 、 DFA 的状态转换图，以及 DFA 的形式化描述 ) 。23、给定文法 GS ：S SaA|aA AbS|b请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。请构造该文法的 LR(0) 分析表。什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？ 24、对下面的文法G：S-aBc|bABA-aAb|bB-b| (1)计算这个文法的每个非终结符的FIRST和FOLLOW集合； （2）证明这个文法是LL（1）的；（3）构造它的预测分析表。25、设字母表= a，b，对于以aa或ab结尾的字的正规集。（1）请写出描述该语言的正规式。（2）构造该正规式所对应的NFA（画出转换图）；（3）将所求的NFA确定化（画出DFA的转换图）；（4）将所求出的DFA最小化（画出极小化后的转换图）； 26、设文法G为 S E E TE | T eT | t (1)证明它是LR(1)文法； (2)构造它的LR(1)分析表； (3)给出输入符号串etet的分析过程。 27、对文法G(S)：S S a T | a T | a TT a T | a(1) 消除该文法的左递归和提取左公因子；(2) 构造各非终结符的FIRST和FOLLOW集合；(3) 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。F答案：22答：（ 1 ）正规表达式： 1(0|1) * 00 （ 2 ）第一步：将正规表达式转换为 NDFA 第二步：将 NDFA 确定化为 DFA ：造表法确定化（ 3 分） 确定化后 DFA M 的状态转换表 状态 输入I 0I 1t01SA,D,Bq 0q 1A,D,BD,B,CD,B重新命名q 1q 2q 3D,B,CD,B,C,ZD,Bq 2q 4q 3D,BD,B,CD,Bq 3q 2q 3D,B,C,ZD,B,C,ZD,Bq 4q 4q 3DFA 的状态转换图第三步：给出 DFA 的形式化描述 DFA M = （ q 0 , q 1 , q 2 , q 3 , q 4 , 0,1, t, q 0 , q 4 ）t 的定义见 M 的状态转换表。2323答： （1）拓广文法： GS: S S S SaA S a A AbS A b 该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA ： 该文法的 LR(0) 分析表： 状态ACTIONGOTOab#SA0S 211S 3acc2r 3r 3r 33S 544r 2r 2 /S 6r 25r 5r 5r 56S 277r 4 /S 3r 4r 4 LR(0) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中没有冲突状态。该文法不是 LR(0) 文法，因为存在冲突状态： I 4 和 I 7。 SLR(1) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中有冲突状态，冲突可用 FOLLOW 集解决。该文法不是 SLR(1) 文法。因为 FOLLOW(S)=a,b,# ，所以无法解决冲突。24答：（1）first(B)=b, ,first(A)=a,b,first(S)=a,bFollow(S)=#,follow(A)=b,#,follow(B)=c,# (2)因为只有FIRST(B)含有e , 所以只考虑： FOLLOW(B)=FIRST(c) FOLLOW(S)=c, # 该文法的LL(1)表 (3)该文法的LL(1)分析表如下： abc#SaBcbABAaAbbBbee25答： （1）正则式为：（a|b）*a(a|b）。 （1分）（2）由正则式得到的转换系统如下图： （1分） （3）由子集法构造的DFA如下图： （4）DFA最小化如下图： 26答：(1)拓广文法G：（1分）(0) S S (1) S E (2) E TE (3) E (4) T eT (5) T t FIRST(A) = , e,t FIRST(B) = e, t 构造的DFA如下:由项目集规范族看出，不存在冲突动作。该文法是LR(1)文法。 (2) LR(1)分析表 状态 ActionGoto e t # S E T 0 S4 S5 r3 1 2 3 1 acc 2 r1 3 S4 S5 r3 6 3 4 S4 S5 7 5 r5 r5 r5 6 r2 7 r4 r4 r4 (3)输入串abab的分析过程为： 步骤状态栈符号栈当前字符剩余字符串动作(1)0#etet#移进(2)04#etet#移进(3)045#etet#归约 Tt(4)047#eTet#归约 Tet(5)03#Tet#移进(6)034#Tet#移进(7)0345#TeT#归约 Tt(8)0347#TeT#归约 Tet(9)033#TT#归约 E(10)0336#TTE#归约 ETE(11)036#TE#归约 ETE(12)02# E#归约 SE(13)01#S#acc27答：（1）消除左递归S a T S | a T SS a T S | T T a T | a提取左公因子S a T S | a T SS a T S | T a TT T | (2) 各非终结符的FIRST和FOLLOW集合： FIRST(S)=a， FIRST(S)= ， FIRST(T)= FIRST(T)= ， FOLLOW(S)=# FOLLOW(S)=#FOLLOW(T)=，# FOLLOW(T)=，# (3) LL(1)分析表如下(3分) ，该文法是LL(1)文法。（1分）a#SSaTSSaTSSSaTSSTTaTTTTTT编译原理G卷六、问答题1、给出上下文无关文法的定义2、文法GS： SaSPQ|abQ QPPQ bPbb bQbc cQcc（1）它是Chomsky哪一型文法？（2）它生成的语言是什么？3、按指定类型，给出语言的文法。L=aibj|ji1的上下文无关文法。4、有文法G：SaAcB|BdAAaB|cBbScA|b（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄；（2）写出句子acabcbbdcc的最左推导过程。 S（L）|aS|a LL, S|S5、对于文法GS：（1）画出句型（S,（a）的语法树。（2）写出上述句型的所有短语、直接短语、句柄和素短语。6、考虑文法GT：TT*F|FFFP|PP（T）|iTT * FF PP （ T ）T * F图2-8-4 句型T*P（T*F）的语法树证明T*P（T*F）是该文法的一个句型，并指出直接短语和句柄。G卷答案：1解答一个上下文无关文法G是一个四元式（VT,VN,S, P），其中：VT是一个非空有限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VTVN=；S是一个非终结符号，称为开始符号；P是一个产生式集合（有限），每个产生式的形式是P，其中，PVN，(VTVN)*。开始符号S至少必须在某个产生式的左部出现一次。 2解答 （1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法GS是Chomsky1型文法，即上下文有关文法。（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到： SabQabc SaSPQaabQPQaabPQQaabbQQaabbcQaabbcc SaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc 于是得到文法GS生成的语言L=anbncn|n13【解答】（1）由L=aibj|ji1知，所求该语言对应的上下文无关文法首先应有SaSb型产生式，以保证b的个数不少于a的个数；其次，还需有SSb或S