期末考试编译原理试题
d、都不是
二、简答题：（每小题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）文法，说明理由。
4、简述编译的整个过程（10分）。
德州学院期末考试试题
（ 6 至学年第学期）
课程名称：考试对象：试卷类型：考试时间：分钟
一、填空题（每空1分，共20分）
1、假设G是一个文法，S是文法的开始符号，如果S*?X，则称X是。
2、乔姆斯基定义的四种形式语言分别为：文法、文法、文法、文法。
3、设有文法G[I]：
I→I1|I0|Ia|Ic|a|b|c ,下列符号串中是该文法的句子的有
（1）ab0 (2)a0c01 (3)aaa (4)bc10
4、一个上下文无关文法G包含四个组成部分依次为：一组，一组，一个，以及一组。
5、确定的有穷自动机是一个，通常表示为。
6、编译程序一般含有八部分，分别是、、、、、、
、。
二、简答题（每题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分）
1、把下图确定化和最小化：（15分）
2、已知文法G S::=bBc|aAB A::=bAa|a B::=a|ε
写出所有非终结符号的First集和Follow集，构造预测分析表并给出输入串abbaaa分析过程。（15分）
3、若有文法G（S）的产生式如下：S::=bASB|bA A::=dSa|b B::=cAa|c构造识别所有
项目集规范族的DFA。（20分）
判断该文法是否是LR（0）文法，说明理由。
判断该文法是否是SLR（1）文法，说明理由。
判断该文法是否是LR（1）文法，说明理由。