编译原理复习题(5页).doc
-编译原理复习题-第 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）指出这个句子的所有短语、直接短语和句柄。6、已知文法GE:EàE+T|TTàT*F|FFài （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）请判断修改后的文法是否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）短语为：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）：S>aBc|bAB A>aAb|b B>b| （1）求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。（2）构造LL(1)分析表。 解：（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:SàABAàaBa | BàbAb | (1)请构造该文法的LR(0)项目集规范族；(2)请构造该文法改进的SLR(1)分析表。18、请分别列出下列语句的后缀式表示和四元式表示：(1)T:= A + B * C / D(2)IF A<0 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 < 0 GOTO （4）t3 := A+ t2 （2）t1 := 0T := t3 （3）GOTO （7） （4） t1 := 1 （5） t2 :=X+2 （6） X:= t2 （7） Y:= 019、请分别列出下列语句的后缀式表示和四元式表示：(1)X:=A+B*C/(D-E)/F(2)IF X>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
