资源描述：
《编译原理复习题 新 优质文档.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、优质文档编译原理复习题1、文法G[S]为：S->cBdB->ab
2、a请写出L(G[S])的全部元素。2、文法G[S]为：S->Ec
3、aFE->abF->bc请写出L(G[S])的全部句子。3、与确定的有穷自动机DFA相比，不确定的有穷自动机NFA的不确定性，表现在哪些方面？Ø转换函数为多值函数，即某个状态有多个后继状态Ø包含e弧Ø初始状态不唯一4、典型的编译过程共包含哪些阶段？各阶段的任务和目标是什么？•典型的编译过程共包含以下六个阶段：……•词法分析阶段…•语法分析阶段…10优质文档5、令文法G[S]为:S->aAS
4、aA->SbA
5、b
6、a（1）给出句子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、bA10优质文档（1）请提取左公共因子，给出修改后的等价文法；（2）请判断修改后
12、的文法是否LL(1)文法。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；10优质文档直接短语为：a1,a2,b；句柄为：最左边的a112、文法G[S]为:S-
19、>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确定化：10优质文档（3）对其最小化：14、设有非确定的有自限动机NFA，M=({A，B，C}，{0，1}，d，{A}，{C})，其中：d(A，0)={C}，d(A，1)={A，B}，d(B，1)
22、={C}，d(C，1)={C}。请画出状态转换矩阵和状态转换图。解：状态转换矩阵为：10优质文档状态转换图为：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(ε)={ε}10优质文档FOLLOW(A)={b,#}FOLLOW(B)=
26、{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、ε10优质文档BàbAb
30、ε(1)请构造该文法的LR(0)项目集规范族；(2)请构造该文法改进的SLR(1)分析表
31、。18、请分别列出下列语句的后缀式表示和四元式表示：(1)T:=A+B*C/D(2)IFA<0THENX:=X+2ELSEY:=0解：（1）后缀式表示分别为TABC*D/+:=A0
32、2THENY:=Y-ZELSEX:=020、请画出以下基本块的DAG，并写出优化后的四元式序列（假设此后仅变量X会被用到）A:=3B:=2*AC:=X+YD:=B*CE:=2*AF:=X+YG
