C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|0 B::=BA|B0|ε A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9 5、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组_____、一组______。

a、字符串 b、字母数字串 c、产生式 d、结束符号 e、开始符号 f、文法 g、非终结符号 h、终结符号

6、现有前缀表示的表达式文法G1： E::=-EE E::=-E E::=a|b|c

则文法的句子—a-bc的所有可能语法树有______棵。 a、1 b、2 c、3 d、4

7、下列文法__________二义文法 E::=EiT|T T::=T+F|iF|F F::=E*|(

可选项有： a、是 b、不是 c、无法判断。 8、语法分析的常用方法是_________：

①自顶向下 ②自底向上 ③自左向右 ④自右向左 可选项有：

a、①②③④ b、①② c、③④ d、①②③ 9、LR（K）文法是_________。

a、从左到右分析，共经过K步的一种编译方法。

b、从左到右分析，每次向前预测K步的一种编译方法。

c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。 d、从左到右分析，每次走K步的一种编译方法。 10、素短语是指_______的短语。 ①至少包含一个符号

②至少包含一个非终结符号 ③至少包含一个终结符号

④除自身外不再包含其它终结符号 ⑤除自身外不再包含其它非终结符号 ⑥除自身外不再包含其它短语 ⑦除自身外不再包含其它素短语 可选项有：

a、①④ b、①⑤ c、①⑥ d、②④ e、③⑤ f、③⑦g、②⑦ 11、文法的二义性和语言的二义性是两个____________概念。 a、不同 b、相同 c、无法判断

12、在编译中产生语法树是为了____________。

a、语法分析 b、语义分析 c、词法分析 d、产生目标代码 13、下述正规表达式中________与(a*+b)*(c+d)等价。 ? a*（c+d）+b（c+d） ? a*（c+d）*+b（c+d）* ? a*（c+d）+b*（c+d） ? （a+b）*c+（a+b）*d ? （a*+b）*c+（a*+b）*d

可选项有:a、① b、② c、③ d、④ e、⑤ f、④⑤ g、③④⑤

线 封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分）

1、证明下面文法是二义性的。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)={ anbmambn

| m,n≥1}。 6、给出与下图的NFA等价的正规式。

b S0 a S1 S3 ε ε S2