2016第二章文法和语言习题讲解.ppt

作业1 例 构造一个文法G3使 L(G3)={anbn|n≥1} 解; S→aSb|ab 例 试构造生成语言L={anbnci|n?1, i ?0}的文法 解：G(Z): Z?AB A ?aAb|ab B ?cB|? (1) { an bn am bm | n，m=0 } S→AA A→aAb|ε 或者 S→AB A→aAb|ε B→aBb|ε (2) {1n 0m 1m 0n | n ，m=0 } S→1S0|A A→0A1|ε 例 构造一个文法G3使 L(G3)={anbn|n≥1} 解; S→aSb|ab 例 试构造生成语言L={anbnci|n?1, i ?0}的文法 解：G(Z): Z?AB 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} S→AB A→aAb|ab B→cB|ε (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：S→SaQ ∣ Q Q→QbR ∣ R R→cSd ∣ e 1．证明句型 QbRae 是规范句型 2．给出句型 QbRae 的短语，直接短语和句柄。 答：因为句型 QbRae 可由文法开始符S经过规范推导产生，推导过程如下： S = SaQ = SaR = Sae = Qae = QbRae 所以句型 QbRae 是规范句型。 2．给出句型 QbRae 的短语，直接短语和句柄： 短语：QbR e QbRae 直接短语：QbR e 句柄：QbR 作业3 ：有下面的文法G: G[S]: 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: G[S]: S-aAcBe A-b A-Ab B-d 若有句型aAbcde, 试问b是它的直接短语吗? 它的短语是什么?句柄是什么? 答:不是,看图 句型的短语有:aAbcde,Ab,d 句柄是Ab 6 ：文法G1: P-PaP|PbP|cP|Pe|f　　证明文法G1是二义文法 因为文法存在句型fbfbf对应2棵不同的语法树，如图，所以文法是二义的。 * * Evaluat