编译原理复习题(5页).doc

《编译原理复习题(5页).doc》由会员分享，可在线阅读，更多相关《编译原理复习题(5页).doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-编译原理复习题-第 5 页1、与确定的有穷自动机DFA相比，不确定的有穷自动机NFA的不确定性，表现在哪些方面？ 转换函数为多值函数，即某个状态有多个后继状态 包含e弧 初始状态不唯一2、典型的编译过程共包含哪些阶段？各阶段的任务和目标是什么？ 典型的编译过程共包含以下六个阶段： 词法分析阶段 语法分析阶段3、文法GS为： S-cBd B-ab | a请写出L(GS)的全部元素。4、文法GS为：S-Ec | aF E-ab F-bc 请写出L(GS)的全部句子。5、令文法GS为: S-aAS | aA- SbA | ba （1）给出句子aabbaa的最右推导；（2）画出这个句子的语法树；（3

2、）指出这个句子的所有短语、直接短语和句柄。6、已知文法GE:EE+T|TTT*F|FFi （1）给出句子i*i+i的最左推导。（2）画出推导的语法树；（3）列出此句子的句柄。7、正规式a(bb)*（a|b）*， 请将它转化为一个不确定的有穷自动机NFA,再确定化和最小化，获得其等价的最小DFA。8、构造正规式 (ab)*ba* 的最小DFA。9、已知文法GS:S ad | AcA aS | bA （1）请提取左公共因子，给出修改后的等价文法；（2）请判断修改后的文法是否LL(1)文法。10、已知文法GE:E - E+F|FF - F*i|i （1）请消除文法中的左递归，给出修改后的等价文法（2

3、）请判断修改后的文法是否LL(1)文法。11、文法GS为: S-S+A|A A-A*B|B B-(S)|a|b (1)分析说明a*a+b是该文法的一个句型；(2)指出该句型的所有短语、直接短语和句柄。解：（1）该字符串对应的语法树为：所以a*a+b为该文法的句型。（2）短语为：a1,a2,a1*a2,b,a1*a2+b； 直接短语为：a1,a2,b； 句柄为：最左边的a112、文法GS为: S-aCcDe C-b|Cb D-d(1)分析说明aCbcde是它的一个句型；(2)指出该句型的所有短语、直接短语和句柄。 解：（1）此句型对应语法树如下，故aCbcde为 此文法的一个句型。 （2）短语为

4、：aCbcde，Cb，d； 直接短语：Cb，d； 句柄: Cb。 13、构造正规式(a|b)*相应的最小化DFA解：（1）首先构造对应的NFA：（2）将NFA确定化：（3）对其最小化： 14、设有非确定的有自限动机NFA ，M=(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。请画出状态转换矩阵和状态转换图。 解：状态转换矩阵为：状态转换图为 ：15、设有文法G（S）：SaBc|bAB AaAb|b Bb| （1）求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。（2）构造LL(1

5、)分析表。 解：（1）FIRST(aBc)=aFIRST(bAB)=bFIRST(aAb)=aFIRST(Ab)=bFIRST(b) = bFIRST()= FOLLOW(A)=b, #FOLLOW(B)=c, #SELECT(SaBc)=aSELECT(SbAB) =bSELECT(AaAb)=aSELECT(Ab)=bSELECT(Bb)=bSELECT(B)=c, #（2）所得的LL(1)分析表如下所示：16、已知文法GS:S-aA | bA-Abc | c （1）请构造该文法的LR(0)项目集规范族；（2）请构建该文法的改进的SLR(1)分析表。17、已知文法GS:SABAaBa |

6、BbAb | (1)请构造该文法的LR(0)项目集规范族；(2)请构造该文法改进的SLR(1)分析表。18、请分别列出下列语句的后缀式表示和四元式表示：(1)T:= A + B * C / D(2)IF A0 THEN X:= X + 2 ELSE Y:=0解：（1）后缀式表示分别为 T A B C * D / + :=A 0 X X 2 + := Y 0 := ￥（2）四元式表示分别为 t1 := B*C 令t1 := A 0t2 := t1 /D （1）IF A 2 THEN Y:=Y-Z ELSE X:=020、请画出以下基本块的DAG，并写出优化后的四元式序列（假设此后仅变量X会被用到）A:=3B:=2*AC:=X+YD:=B*CE:=2*AF:=X+YG:=E*FX:=D*G21、请画出以下基本块的DAG，并写出优化后的四元式序列（假设在此后只有变量H会被用到）：PI:=3.14B:=A+2 F:=B+CC:=B+C G:=B/CD:=B/C H:=D*GE:=A+2