编译原理考试重点题

《编译原理考试重点题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1、设正规式r=a(a

2、b)*,将r转换为相应的正规文法。令S为文法开始符，首先形成S→a(a

3、b)*,然后形成S→aA和A→(a

4、b)*,再变换成：S→aAA→εA→(a

5、b)A，进而变换成正规文法形式：S→aAA→εA→aAA→bA2、令文法G[S]S→cC,S→c,C→cC,C→dC,C→c,C→d，将该文法转换为相应的正规式。首先有S=cC

6、c，C=(cC

7、dC)

8、(c

9、d)=(c

10、d)C

11、(c

12、d)=(c

13、d)*

14、(c

15、d)=(c

16、d)+进一步有S=c(c

17、d)+

18、c=c(c

19、d)*c(c

20、d)*即为该文法所对应的正规式

21、令文法G[S]为:S->S+A

22、AA->A*B

23、BB->(S)

24、a

25、b(1)分析说明a*a+b是该文法的一个句型；(2)指出该句型的所有短语、直接短语和句柄。（1）该字符串对应的语法树为：所以a*a+b为该文法的句型。（2）短语为：a,a,a*a,b,a*a+b；直接短语为：a,a,b；句柄为：最左边的a令文法G[S]为:S->aCcDeC->b

26、CbD->d(1)分析说明aCbcde是它的一个句型；(2)指出该句型的所有短语、直接短语和句柄。（1）此句型对应语法树如下，故aCbcde为此文法的一个句型。（2）短语为：aCbcde

27、，Cb，d；直接短语：Cb，d；句柄:Cb。构造正规式(a

28、b)*相应的最小化DFA。1、首先构造对应的NFA：2、将NFA确定化：3、对其最小化：设有非确定的有自限动机NFAM=({A，B，C}，{0，1}，d，{A}，{C})，其中：d(A，0)={C}，d(A，1)={A，B}，d(B，1)={C}，d(C，1)={C}。请画出状态转换距阵和状态转换图。状态转换距阵为：状态转换图为：对表达式文法G：E→E+T

29、TT→T*F

30、FF→(E)

31、I（1）构造各非终结符的FIRSTVT和LASTVT集合；（2）构造文法的算符优先关系表

32、。各非终结符的FIRSTVT和LASTVT集合：算符优先关系表：设文法G[S]：S->aAA->aBb

33、bB->Cc

34、εC->aB

35、d证明：G是LL(1)文法。构造的LL(1)预测分析表为：由预测分析表中无多重入口判定该文法是LL(1)文法。设有文法G（S）：S—>aBc

36、bABA—>aAb

37、bB—>b

38、ε（1）求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。（2）构造LL(1)分析表。解：（1）FIRST(aBc)={a}FIRST(bAB)={b}FIRST(aAb)={a}FI

39、RST(A→b)={b}FIRST(b)={b}FIRST(ε)={ε}FOLLOW(A)={b,#}FOLLOW(B)={c,#}SELECT(S→aBc)={a}SELECT(S→bAB)={b}SELECT(A→aAb)={a}SELECT(A→b)={b}SELECT(B→b)={b}SELECT(B→)={c,#}（2）所得的LL(1)分析表如下所示：