资源描述：
《编译原理复习题2.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1、（10分）下面的文法G[S]是否是LL（1）文法，说明理由，构造LL（1）分析表S→aBc
2、bABA→aAb
3、BbB→cB
4、e2、（5分）消除下列文法的左递归，消除左递归后判断是否是LL（1）文法。S→SaB
5、bBA→S
6、aB→Ac3、（5分）构造下面算符文法的优先矩阵，判断是否是算符优先文法S→A[]A→[A→aAA→B]B→a4、（10分）将表达式A+B*(C-D)-E/F↑G分别表示为三元式、四元式、逆波兰式序列5、（10分）现有文法如下：S→aS
7、bS
8、a判断该文法是哪一类LR文法，说明理由，并构造相应的分析表。1、
9、已知文法GA::=aABe
10、aB::=Bb
11、d（1）给出与上述文法等价的LL（1）文法G’。（2）构造预测分析表并给出输入串aade#分析过程。（10分）2、设已给文法G:E::=E+TE::=TT::=T*FT::=FF::=P↑FF::=PP::=(E)P::=i构造此文法的算符优先矩阵。（10分）3、有正规式b*abb*(abb*)*（1）构造该正规式所对应的NFA（画出状态转换图）。（2）将所求的NFA确定化。（画出确定化的状态转换图）。（3）将所求的NFA最小化。（画出最小化后的状态转换图）。（10分）4、若有文法G（
12、S）的产生式如下：S::=L=RS::=RL::=*RL::=iR::=L,构造识别所有项目集规范族的DFA。（15分）（1）判断该文法是否是LR（0）文法，说明理由。（2）判断该文法是否是SLR（1）文法，说明理由。（3）判断该文法是否是LR（1）文法，说明理由。（4）判断该文法是否是LALR（1）文法，说明理由1、（10分）将表达式（（B*D+A）/E+D）*F+G分别表示为三元式、四元式、逆波兰式序列2、（10分）对基本块P画出DAG图B:=3D:=A+CE::=A*CF:=E+DG:=B*FH:=A+CI:=A*CJ:=
13、H+IK:=B*5L:=K+JM:=L假定只有L在基本块出口之后活跃，写出优化后的四元式序列。3、（10分）对于文法G[S]：S→aBb
14、aAa
15、bAb
16、bBaA→xB→x（1）判断该文法是否是LR（1）文法，构造LR（1）分析表（2）判断该文法是否是LALR（1）文法，说明理由三、问答题：(共50分)1、已知文法GS::=bBc
17、aABA::=bAa
18、aB::=a
19、e写出所有非终结符号的First集和Follow集，构造预测分析表并给出输入串abbaaa分析过程。（10分）2、正规式0（0
20、1）*1构造该正规式所对应的NFA（
21、画出状态转换图）。将所求的NFA确定化和最小化。（分别画出确定化和最小化的状态转换图）。（10分）3、若有文法G（S）的产生式如下：S::=bASB
22、bAA::=dSa
23、bB::=cAa
24、c构造识别所有项目集规范族的DFA。（20分）判断该文法是否是LR（0）文法，说明理由。判断该文法是否是SLR（1）文法，说明理由。判断该文法是否是LR（1）文法，说明理由。判断该文法是否是LALR（1）文法，说明理由。4、简述编译的整个过程（10分）。1、已知文法G[S]S→eT
25、RTT→DR
26、eR→dR
27、eD→a
28、bd写出所有非终结符号的F
29、irst集和Follow集，构造LL(1)分析表，判断此文法是否是LL（1）文法。（10分）2、给出正规式(a
30、b)*bb(a
31、b)*构造该正规式所对应的NFA（画出状态转换图）。将所求的NFA确定化和最小化。（分别画出确定化和最小化的状态转换图）。（10分）3、若有文法G（S）的产生式如下：S→aAD
32、aBe
33、bBS
34、bAeA→gB→gD→d
35、e，构造识别所有LR(1)项目集规范族的DFA。（20分）判断该文法是否是LR（1）文法，说明理由，构造LR（1）表。判断该文法是否是LALR（1）文法，说明理由。4、简述编译的整个过程
36、（10分）。1、把下图确定化和最小化：（15分）0baaabbbbbaaa2、已知文法GS::=bBc
37、aABA::=bAa
38、aB::=a
39、e写出所有非终结符号的First集和Follow集，构造预测分析表并给出输入串abbaaa分析过程。（15分）3、若有文法G（S）的产生式如下：S::=bASB
40、bAA::=dSa
41、bB::=cAa
42、c构造识别所有项目集规范族的DFA。（20分）判断该文法是否是LR（0）文法，说明理由。判断该文法是否是SLR（1）文法，说明理由。判断该文法是否是LR（1）文法，说明理由。判断该文法是否是LA
43、LR（1）文法，说明理由。三、问答题：（共计50分）1、已知文法GA::=aABe
44、aB::=Bb
45、d（1）给出与上述文法等价的LL（1）文法G’。（2）构造预测分析表并给出输入串aade#分析过程。（10分）2、设S={0，1}上的正规集S由倒数第二个字符为1
