期末考试编译原理试题
18、_______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：
a、存在
b、不存在
c、无法判定是否存在
15、LL（K）文法________二义性的。
a、都是
b、都不是
c、不一定都是
16、下面的文法是__________。S::=aAa|aBb|bAb|bBa A::=x B::=x
可选项有：a、LR（1）文法b、LALR（1）文法c、都不是d、a和b
17、编译过程中，比较常见的中间语言有___________。
①波兰表示
②逆波兰表示
③三元式
④四元式
⑤树形表示
可选项有：a、①③④b、②③④c、③④①⑤d、②③④⑤
18、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。
a、abc*cd-b-a*+/--
b、a-bc*cd-b-a*+/-
c、a-bc*cd-/b-a*+-
d、a-bc*/cd-b-a*+-
19、在编译程序中安排中间代码生成的目的是_______________。
①便于进行存储空间的组织
②利于目标代码优化
③利于编译程序的移植
④利于目标代码的移植
⑤利于提高目标代码的质量
可选项有：
a、②④
b、①②③
c、③④①
d、②③④⑤
20、代码优化的主要目标是_____________。
①如何提高目标程序的运行速度
②如何减少目标程序运行所需的空间。
③如何协调①和②
④如何使生成的目标代码尽可能简短
可选项有：
a、②④
b、①②③
c、③④①
d、②③④
二、简答题：（每小题5分，共30分）
11、证明下面文法是二义性的。P::=PaP|PbP|cP|Pe|f
2、设一文法S→AB S→c A→bA A→a B→aSb B→c 对于句子bbaacb写出其全部短语，
直接短语和句柄。
3、求出下列文法所产生语言对应的正规式。
S::=aA A::=bA|aB|b B::=aA
4、表达式（a+b）*c/d-e*f分别表示三元式、四元式、逆波兰式序列
5、写一个文法使其语言为L(G)={ a n b m a m b n | m,n≥1}。
6、给出与下图的NFA等价的正规式。
c
三、已知文法G S::=aBc|bAB A::=aAb|b B::=b|
构造预测分析表并给出输入串baabbb分析过程。（10分）
四、正规式（（0*|1）（1*0））*（10分）
（1）构造该正规式所对应的NFA（画出状态转换图）。
（2）将所求的NFA确定化。（画出确定化的状态转换图）。
五、若有文法G（S）的产生式如下：S::=bASB|bA A::=dSa|b B::=cAa|c构造识别所有项目集规范
族的DFA。（15分）
i.判断该文法是否是LR（0）文法，说明理由。
ii.判断该文法是否是SLR（1）文法，说明理由。
iii.判断该文法是否是LR（1）文法，说明理由。
iv.判断该文法是否是LALR（1）文法，说明理由。
六、设已给文法G: E::=E+T E::=T T::=T*F T::=F F::=(E) F::=i
构造此文法的算符优先矩阵。（15分）