2011-2012编译原理考试题10套，很多高校都用这套(7)

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

可选项有：

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)={ abab | m,n≥1}。 6、给出与下图的NFA等价的正规式。

b S0 n

m

mn

a S1 S3 ε S2 ε c

三、问答题：(共计50分)

1、已知文法G S::=aBc|bAB A::=aAb|b B::=b|?

构造预测分析表并给出输入串baabbb分析过程。（10分） 2、 正规式（（0*|1）（1*0））*（10分）

（1） 构造该正规式所对应的NFA（画出状态转换图）。

（2） 将所求的NFA确定化。（画出确定化的状态转换图）。

3、 若有文法G（S）的产生式如下：S::=bASB|bA A::=dSa|b B::=cAa|c构造识别所

有项目集规范族的DFA。（15分）

（1） 判断该文法是否是LR（0）文法，说明理由。 （2） 判断该文法是否是SLR（1）文法，说明理由。 （3） 判断该文法是否是LR（1）文法，说明理由。 （4） 判断该文法是否是LALR（1）文法，说明理由。

4、 设已给文法G: E::=E+T E::=T T::=T*F T::=F F::=(E) F::=i 构造此文法的算符优先矩阵。（15分） 三、简答题（共35分） 5、 (10分)现有文法G[E]:

E→E+T|E-T|T T→T*F|T/F|F F→(E)|i

画出句型E+F*（E+i）的语法树,找出它的短语，直接短语，句柄和素短语

6、 (5分)对下面的文法G[S]构造状态转换图,并说明符号串aaba是否是该文法接受

的句子： S→aA S→B A→abS A→bB B→b B→cC C→D D→d D→bB

7、 (10分)将下面具有?的NFA确定化

S ? A ? a B b Z a

8、 (5分)求出下列文法所产生语言对应的正规式。S→aA A→bA|aB|b B→aA。 9、 (5分)构造识别下面正规式的NFA （a|b）*ba。 四、 综合题（共40分）

1、 （10分）下面的文法G[S]是否是LL（1）文法，说明理由，构造LL（1）分析表 S→aBc|bAB A→aAb|Bb B→cB|?

2、 （5分）消除下列文法的左递归，消除左递归后判断是否是LL（1）文法。 S→SaB|bB A→S|a B→Ac

3、 （5分）构造下面算符文法的优先矩阵，判断是否是算符优先文法

S→A[] A→[ A→aA A→B] B→a

4、 （10分）将表达式A+B*(C-D)-E/F↑G分别表示为三元式、四元式、逆波兰式序

列

5、 （10分）现有文法如下：

S→aS|bS|a 判断该文法是哪一类LR文法，说明理由，并构造相应的分析表。 二、简答题：（每小题5分，共35分）

1、 证明下面文法是二义性的。S::=ibtSeS|ibtS|a 2、 现有文法S::=SaA|A A::=AbB|B B::=cSd|e

请证实是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。 3、 求出下列文法所产生语言对应的正规式。

S::=bS|aA A::=aA|bB B::=aA|bC|b C::=bS|aA

4、 将表达式((a*d+c)/d+e)*f+g分别表示三元式、四元式、逆波兰式序列 5、 消除下列文法的左递归。

S::=SaP|Sf|P P::=QbP|Q Q::=cSd|e 6、 给出与下图的NFA等价的正规文法。

a S1 b ε S3 ε S0 S2 7、对基本块P画出DAG图

B:=3

D:=A+C E::=A*C F:=E+D G:=B*F H:=A+C I:=A*C J:=H+I K:=B*5 L:=K+J

M:=L

假定只有L在基本块出口之后活跃，写出优化后的四元式序列。

三、问答题：（共计45分）

1、 已知文法G A::=aABe|a B::=Bb|d

（1） 给出与上述文法等价的LL（1）文法G’。 （2） 构造预测分析表并给出输入串aade#分析过程。（10分）

2、 设已给文法G: E::=E+T E::=T T::=T*F T::=F F::=P↑F F::=P P::=(E)

P::=i

构造此文法的算符优先矩阵。（10分）

3、 有正规式babb(abb)

（1） 构造该正规式所对应的NFA（画出状态转换图）。

（2） 将所求的NFA确定化。（画出确定化的状态转换图）。 （3） 将所求的NFA最小化。（画出最小化后的状态转换图）。（10分）

4、 若有文法G（S）的产生式如下：S::=L=R S::=R L::=*R L::=i R::=L,构造

*

*

**

识别所有项目集规范族的DFA。（15分）

（1） 判断该文法是否是LR（0）文法，说明理由。 （2） 判断该文法是否是SLR（1）文法，说明理由。 （3） 判断该文法是否是LR（1）文法，说明理由。 判断该文法是否是LALR（1）文法，说明理由

二、（简答题，共计20分）

1、(10分)已知文法G（T)： T→T*F|F F→F↑P|P P→(T)|i (1)写出句型T *P↑（T*F）推导过程，画出语法树；

(2)写出句型T *P↑（T*F）的短语、直接短语、句柄和素短语。 2、(5分)构造识别下面正规式的NFA

b（aa|bb）*ab

3、（5分）消除 …… 此处隐藏：2230字，全部文档内容请下载后查看。喜欢就下载吧 ……