文法和语言习题讲解

《文法和语言习题讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、作业1例构造一个文法G3使L(G3)={anbn

2、n≥1}解;S→aSb

3、ab例试构造生成语言L={anbnci

4、n1,i0}的文法解：G(Z):ZABAaAb

5、abBcB

6、(1){anbnambm

7、n，m>=0}S→AAA→aAb

8、ε或者S→ABA→aAb

9、εB→aBb

10、ε(2){1n0m1m0n

11、n，m>=0}S→1S0

12、AA→0A1

13、ε例构造一个文法G3使L(G3)={anbn

14、n≥1}解;S→aSb

15、ab例试构造生成语言L={anbnci

16、n1,i0}的文法解：G(Z):ZABAaAb

17、abBcB

18、(3){anbbn

19、n

20、>=1}a和b是以b为中心对称出现S->aAbA->aAb

21、b(4){anban

22、n>=0}S->aSa

23、b

24、(5){anbnci

25、n>=1,i>=0}S→ABA→aAb

26、abB→cB

27、ε(6){anbm

28、n>=m>=1}如果n=m>=1的文法为s->aSb

29、ab，现在n>=m说明还有往下推导产生a的产生式，因此加上S->A,A->aA

30、a所以文法为：G(s):S->abS->AS->aSbA->aA->aA或者S->aSb

31、aAA->aA

32、b(7){0n1

33、n>=1}(8){anbmck

34、n,m,k>=0}(7){0n1

35、n>=1}S->0S

36、0A

37、A->1(8)S->aS

38、ε

39、aAA->bA

40、ε

41、bBB->cB

42、ε作业2：设有文法G1G1：S→SaQ∣QQ→QbR∣RR→cSd∣e1．证明句型QbRae是规范句型2．给出句型QbRae的短语，直接短语和句柄。答：因为句型QbRae可由文法开始符S经过规范推导产生，推导过程如下：S=>SaQ=>SaR=>Sae=>Qae=>QbRae所以句型QbRae是规范句型。2．给出句型QbRae的短语，直接短语和句柄：短语：QbReQbRae直接短语：QbRe句柄：QbR作业3：有下面的文法G:G[S]:S->BAA->BS

43、dB->aA

44、bS

45、c（1）证明

46、文法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

47、kF->F*k

48、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

49、kF->F/k

50、k求k-k/k-k的最右推导。

51、E=>E-F-E=>E-F-k=>E-F/k-k=>E-k/k-k=>k-k/k-k作业5：有下面的文法G:G[S]:S->aAcBeA->bA->AbB->d若有句型aAbcde,试问b是它的直接短语吗?它的短语是什么?句柄是什么?答:不是,看图句型的短语有:aAbcde,Ab,d句柄是Ab6：文法G1:P->PaP

52、PbP

53、cP

54、Pe

55、f证明文法G1是二义文法因为文法存在句型fbfbf对应2棵不同的语法树，如图，所以文法是二义的。