编译原理复习题学习资料.doc

《编译原理复习题学习资料.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、编译原理复习题精品文档1、与确定的有穷自动机DFA相比，不确定的有穷自动机NFA的不确定性，表现在哪些方面？Ø转换函数为多值函数，即某个状态有多个后继状态Ø包含e弧Ø初始状态不唯一2、典型的编译过程共包含哪些阶段？各阶段的任务和目标是什么？•典型的编译过程共包含以下六个阶段：……•词法分析阶段…•语法分析阶段…3、文法G[S]为：S->cBdB->ab

2、a请写出L(G[S])的全部元素。4、文法G[S]为：S->Ec

3、aFE->abF->bc请写出L(G[S])的全部句子。5、令文法G[S]为:S->aAS

4、aA->SbA

5、ba（1）给出

6、句子aabbaa的最右推导；（2）画出这个句子的语法树；（3）指出这个句子的所有短语、直接短语和句柄。6、已知文法G[E]:EàE+T

7、TTàT*F

8、FFài（1）给出句子i*i+i的最左推导。（2）画出推导的语法树；（3）列出此句子的句柄。7、正规式a(bb)*（a

9、b）*，请将它转化为一个不确定的有穷自动机NFA,再确定化和最小化，获得其等价的最小DFA。8、构造正规式(ab)*ba*的最小DFA。9、已知文法G[S]:Sàad

10、AcAàaS

11、bA（1）请提取左公共因子，给出修改后的等价文法；（2）请判断修改后的文法是否LL(1)文法

12、。10、已知文法G[E]:E->E+F

13、FF->F*i

14、i（1）请消除文法中的左递归，给出修改后的等价文法（2）请判断修改后的文法是否LL(1)文法。11、文法G[S]为:S->S+A

15、AA->A*B

16、BB->(S)

17、a

18、b(1)分析说明a*a+b是该文法的一个句型；(2)指出该句型的所有短语、直接短语和句柄。收集于网络，如有侵权请联系管理员删除精品文档解：（1）该字符串对应的语法树为：所以a*a+b为该文法的句型。（2）短语为：a1,a2,a1*a2,b,a1*a2+b；直接短语为：a1,a2,b；句柄为：最左边的a112、文法G[S]

19、为:S->aCcDeC->b

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

21、b)*相应的最小化DFA解：（1）首先构造对应的NFA：（2）将NFA确定化：（3）对其最小化：收集于网络，如有侵权请联系管理员删除精品文档14、设有非确定的有自限动机NFA，M=({A，B，C}，{0，1}，d，{A}，{C})，其中：d(A，0)={C}

22、，d(A，1)={A，B}，d(B，1)={C}，d(C，1)={C}。请画出状态转换矩阵和状态转换图。解：状态转换矩阵为：状态转换图为：15、设有文法G（S）：S—>aBc

23、bABA—>aAb

24、bB—>b

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

26、LLOW(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)分析表如下所示：收集于网络，如有侵权请联系管理员删除精品文档16、已知文法G[S]:S->aA

27、bA->Abc

28、c（1）请构造该文法的LR(0)项目集规范族；（2）请构建该文法的改进的SLR(1)分析表。17、已知文法G[S]:SàABAàaBa

29、εBàbAb

30、ε(1)请构造该文法的LR(0)项目集规

31、范族；(2)请构造该文法改进的SLR(1)分析表。18、请分别列出下列语句的后缀式表示和四元式表示：(1)T:=A+B*C/D(2)IFA<0THENX:=X+2ELSEY:=0解：（1）后缀式表示分别为TABC*D/+:=A0

32、B*C/(D-E)/F(2)IFX>2THENY:=Y-ZELSEX:=020、请画出以下基本块的DAG，并写出优化后的四元式序列（假设此后仅变量X会被用到）A:=3B:=2*AC:=X+YD