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

L:=K+J

M:=L

假定只有L在基本块出口之后活跃，写出优化后的四元式序列。 3、（10分）对于文法G[S]：S→aBb | aAa |bAb|bBa A→x B→x （1）判断该文法是否是LR（1）文法，构造LR（1）分析表

（2）判断该文法是否是LALR（1）文法，说明理由

二、简答题：（每小题5分，共30分）

1、证明下面文法是二义性的。P→PaP|PbP|cP|Pe|f

2、设一文法E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明E+T*(E-T)是它的一个句型，并指出该句型的全部短语，直接短语，句柄和素短语。 3、求出下列文法所产生语言对应的正规式。

S→bS|aA A→aA|bB B→aA|bC|b C→bS|aA 4、将表达式（（B*D+A）/E+D）*F+G分别表示为三元式、四元式、逆波兰式序列

5、消除文法G[S]的左递归(G[S])

G[S]：S→AB A→bB|Aa B→Sb|a 6、对下面的文法G[Z]

Z→aB A→aB B→bB B→aA B→b

构造状态转换图,并说明符号串aaaabbb是否是该文法接受的句子 三、问答题：(共50分)

1、已知文法G S::=bBc|aAB A::=bAa|a B::=a|?

写出所有非终结符号的First集和Follow集，构造预测分析表并给出输入串abbaaa分析过程。（10分） 2、正规式0（0|1）*1

构造该正规式所对应的NFA（画出状态转换图）。 将所求的NFA确定化和最小化。（分别画出确定化和最小化的状态转换图）。（10分）

3、若有文法G（S）的产生式如下：S::=bASB|bA A::=dSa|b B::=cAa|c构造识别所有项目集规范族的DFA。（20分） 判断该文法是否是LR（0）文法，说明理由。 判断该文法是否是SLR（1）文法，说明理由。 判断该文法是否是LR（1）文法，说明理由。 判断该文法是否是LALR（1）文法，说明理由。 4、简述编译的整个过程（10分）。

二、简答题：（每小题5分，共30分）

1、对于下面的文法G[S]

S→Sa|Ab|b|c A→Bc|a B→Sb|b

构造状态转换图,并说明符号串bcbabcba是否是该文法接受的句子

2、设一文法G[T]：T→T*F|F F→F↑P|P P→(T)|i 证明T*P↑(T*F)是它的一个句型，并指出该句型的全部短语，直接短语，句柄和素短语。 3、求出下列文法所产生语言对应的正规式。

Z→aZ|bZ|aA A→aB B→aA|b 4、将表达式（（A+B*D）/E+F）*F+G^E分别表示为三元式、四元式、逆波兰式序列。 5、（5分）消除文法G[S]的左递归

G[S]：S→SA|A A→SB|B|(S)|() B→[S] | [ ]

6、（5分）对下面的文法G[E]

E→E+T|T|@T T→T*F|F F→P↑F|P P→i (+、@、*、↑、i是终结符号) 构造文法的算符优先矩阵表，判断此文法是否是算符优先文法。 三、问答题：（50分） 1、已知文法G[S] S→eT|RT T→DR| ? R→dR|? D→a|bd

写出所有非终结符号的First集和Follow集，构造LL(1)分析表，判断此文法是否是LL（1）文法。（10分）

2、给出正规式 (a|b)*bb(a|b)*

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

将所求的NFA确定化和最小化。（分别画出确定化和最小化的状态转换图）。（10分） 3、若有文法G（S）的产生式如下：S→aAD|aBe|bBS|bAe A→g B→g D→d|?，构造识别所有LR(1)项目集规范族的DFA。（20分）

判断该文法是否是LR（1）文法，说明理由，构造LR（1）表。 判断该文法是否是LALR（1）文法，说明理由。 简述编译的整个过程（10分）。 二、 简答题（每题5分，共30分） 1、已知文法G[Z]：

Z→U0|V1

U→Z1|1 V→Z0|0

写出全部由此文法描述的只含有四个符号的句子。 2、文法G[N]为：

N→D|ND

D→0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ 3、设一文法G[S]

S→（AS） S→（b） A→（SaA）

A→（a） 对于句子（（（b）a（a））（b）），写出该句子的最左推导，画出语法树，写出其全部短语，直接短语和句柄。

4、 构造下述文法G[S]的自动机： S→A0

A→A0|S1|0

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

S::=SaP|Sf|P P::=QbP|Q Q::=cSd|e

三、 综合题（共计50分） …… 此处隐藏：129字，全部文档内容请下载后查看。喜欢就下载吧 ……