资源描述：
《编译原理复习整理重点含答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1、给出下面语言的相应文法。L1={anbnci
2、n≥1,i≥0}从n，i的不同取值来把L1分成两部分：前半部分是anbn：A→aAb
3、ab后半部分是ci：B→Bc
4、ε所以整个文法G1[S]可以写为：G1(S):S→AB；A→aAb
5、ab；B→cB
6、ε3、构造一个DFA，它接受S={a，b}上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）4、对下面的文法G:E→TE’E’→+E
7、εT→FT’T’→T
8、εF→PF’F’→*F’
9、εP→(E)
10、a
11、b
12、∧（1）证明这个文法是LL(1)的。（2）构造它的预测分析表。(1)FIRST(E)={(,a,b,
13、^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε}FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#}(2)考虑下列产生式:FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIR
14、ST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,该文法式LL(1)文法.(3)+*()ab^#EE'TT'FF'P5、考虑文法:S→AS
15、bA→SA
16、a（1）列出这个文法的所有LR(0)项目。0.1.2.
17、3.4.5.6.7.8.9.10.11.(2)给出识别文法所有活前缀的DFA。1987SAS11100a432AS6b5确定化：SAab{0,2,5,7,10}{1,2,5,7,8,10}{2,3,5,7,10}{11}{6}{1,2,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{2,3,5,7,10}{2,4,5,7,8,10}{2,3,5,7,10}{11}{6}{2,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{2,3,5,7,9,10}{2,4,5,7,8,10}{2,3,5,7,10}{11
18、}{6}{2,4,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{11}φφφφ{6}φφφφAS3:5:6:SAabSaASbSAbaA4:0:7:ASbaabba2:1:DFA6、设有文法：P→P+Q
19、QQ→Q*R
20、RR→(P)
21、i（1）证明Q*R+Q+Q是它的一个句型。（3分)P=>P+Q=>P+Q+Q=>Q+Q+Q=>Q*R+Q+Q（2）给出Q*R+Q+Q的所有短语，直接短语和句柄。(4分)短语:Q*R,Q*R+Q,Q*R+Q+Q直接短语:Q*R句柄:Q*R（3）给出句子ｉ+ｉ*ｉ的最右推导。(4分)（4）给出句子ｉ+ｉ*ｉ的最左推导
22、。(4分)7、设有文法：E→E+T
23、TT→T*F
24、FF→(E)
25、i（1）证明E+T*F是它的一个句型。（3分)（2）给出E+T*F的所有短语，直接短语和句柄。(4分)短语:E+T*F,T*F,直接短语:T*F句柄:T*F（3）给出句子ｉ+ｉ*ｉ的最右推导。(4分)11、构造下面正规式相应的DFA1(0
26、1)*10114、对下面的文法G:Expr→-ExprExpr→(Expr)
27、VarExprTailExprTail→-Expr
28、εVar→idVarTailVarTail→(Expr)
29、ε（1）构造LL(1)分析表。（12分）（2）给出对句子id—id((id))的分析过程。（8
30、分）16、已知文法G[S]为：S->a
31、^
32、(T)T->T,S
33、S①消除文法G[S]中的左递归，得文法G´[S]。②文法G´[S]是否为LL(1)的？若是，给出它的预测分析表。FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST()={,,}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW()={)}预测分析表a^(),#ST是LL(1)文法17、对下面的文法G:S®SÚaT
34、aT
35、ÚaTT®ÙaT
36、Ùa(1)消除该文法的左递归和提取
