文法和语言习题讲解.ppt

作业1 例 构造一个文法G3使 L(G3)=anbn|n1 解; SaSb|ab 例 试构造生成语言L=anbnci|n1, i 0的文法 解：G(Z): ZAB A aAb|ab B cB| (1) an bn am bm | n，m=0 SAA AaAb| 或者 SAB AaAb| BaBb| (2) 1n 0m 1m 0n | n ，m=0 S1S0|A A0A1|,例 构造一个文法G3使 L(G3)=anbn|n1 解; SaSb|ab 例 试构造生成语言L=anbnci|n1, i 0的文法 解：G(Z): ZAB A aAb|ab B cB| (3) an b bn | n=1 a和b是以b为中心对称出现 S-aAb A-aAb|b (4) an b an | n=0 S-aSa|b| ,(5) an bn ci | n=1,i=0 SAB AaAb|ab BcB| (6) an bm | n=m=1 如果 n=m=1的文法为s-aSb|ab，现在n=m 说明还有往下推导产生a的产生式，因此加上 S-A,A-aA|a 所以文法为：G(s): S-ab S-A S-aSb A-a A-aA 或者S-aSb|aA A-aA|b,(7) 0n 1 | n=1 (8) an bm ck | n,m,k=0 (7) 0n 1 | n=1 S-0S|0A A-1 (8) S-aS|aA A-bA|bB B-cB|,作业2：设有文法G1 G1：SSaQ Q QQbR R RcSd e 1证明句型 QbRae 是规范句型 2给出句型 QbRae 的短语，直接短语和句柄。 答：因为句型 QbRae 可由文法开始符S经过规范推导产生，推导过程如下： S = SaQ = SaR = Sae = Qae = QbRae 所以句型 QbRae 是规范句型。 2给出句型 QbRae 的短语，直接短语和句柄： 短语：QbR e QbRae 直接短语：QbR e 句柄：QbR,作业3 ：有下面的文法G: GS: S-BA A-BS|d B-aA|bS|c （1）证明文法G为LL(1)文法 （第四章的作业） （2）构造LL(1)分析表 （第四章的作业） （3） 写出句子adccd的最左推导，并写出短语、直接短语和句病柄 答：S=BA=aAA=adA=adBS=adcS=adcBA=adccA=adccd 短语：ad,c,d,cd,ccd,adccd 直接短语：d,c 句柄：d,作业4（1）文法G: E- E+F+E | k F- F*k | k 求k+k*k+k的最右推导。 E=E+F+E=E+F+k=E+F*k+k=E+k*k+k=k+k*k+k （2）文法G: E- E-F-E | k F- F/k | k 求k-k/k-k的最右推导。 E=E-F-E=E-F-k=E-F/k-k=E-k/k-k=k-k/k-k,作业5：有下面的文法G: GS: S-aAcBe A-b A-Ab B-d 若有句型aAbcde, 试问b是它的直接短语吗? 它的短语是什么?句柄是什么? 答:不是,看图 句型的短语有:aAbcde,Ab,d 句柄是Ab,6 ：文法G