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分）
1、 把下图确定化和最小化：（15分）
b b 0 a b a a a b a 密 封 线
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）文法，说明理由。 判断该文法是否是LALR（1）文法，说明理由。
二、综合题：（共35分） 1、(10分)对于文法G(S): S ?bMbM ?(L|aL ?Ma）
(1)写出句型b(Ma)b的最右推导并画出语法树。 (2)写出上述句型的短语，直接短语和句柄。
2、 (5分)对下面的文法G[S]构造状态转换图,并说明符号串aabca是否是该文法接受
的句子： S→Aa S→B A→Cc A→Bb B→Bb B→a C→D C→Bab D→d 3、 (10分)将下面具有?的NFA确定化
S0 m ? S1 S2 n S3 ? e
4、 (5分)求出下列文法所产生语言对应的正规式。
S→aS S→bA S→b A→aS 5、 (5分)构造识别下面正规式的NFA
ab（a|b）* 四、综合题（共45分）
1、(10分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)的，请说明理由。 G(M)：
a) M → TB
b) T → Ba | ?
c) B → Db | eT | ? d) D → d | ?
2、(15分)对文法G(S)： S → a | ^ | (T) T → T，S | S
(1) 构造算符优先表;
(2) 判断是算符优先文法吗?
(3) 构造优先函数。 3、（10分）将表达式A-B*(C+D)+E/F↑G分别表示为三元式、四元式、逆波兰式序列 4、（10分）设有文法G[S]
S→Ba|Bb|c B→Bd|Se|f
判断该文法是哪一类LR文法，说明理由，并构造相应的分析表 二、简答题：（每小题5分，共30分）
1、写一个文法使其语言为L(G)={ anbmambn | m,n≥1}。
2、对于文法G(E): E?T|E+T T?F|T*F F?(E)|i
（1） 写出句型(T*F+i)的最右推导并画出语法树。 （2） 写出上述句型的短语，直接短语、句柄和素短语。 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 c ε S2
三、问答题：（共计50分）
5、 已知文法G A::=aABe|a B::=Bb|d
（1） 给出与上述文法等价的LL（1）文法G’。 （2） 构造预测分析表并给出输入串aade#分析过程。（10分）
6、 设?={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(15分) 3、设文法G(S)：(10分)
S?SiA|AA?A?B|BB?)A*|(
构造算符优先关系表和优先函数。
4、构造文法G(S)：
(1) S ? BB (2) B ? aB
(3) B? b
的LR分析表。假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)（15分）。 二、简答题：（共30分）
7、 (5分) 证明下面文法是二义性的。P::=PaP|PbP|cP|Pe|f
8、 (10分) 对于文法G(E): E?T|E+T T?F|T*F
F?(E)|i
(1) 写出句型T*F+i1*i2的最右推导并画出语法树。
(2) 写出上述句型的短语，直接短语、句柄、素短语和最左素短语。 3、(5分) 求出下列文法所产生语言对应的正规式。
S::=aA A::=bA|aB|b B::=aA
4、(5分) 写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。 5、(5分)写一个文法使其语言为L(G)={anbncm| m,n≥1，n为奇数，m为偶数}。 三、问答题：（共计50分） 1、已知文法G S::=aBc|bAB A::=aAb|b B::=b|? 构造预测分析表并给出输入串baabbb分析过程。（10分）
2、构造正规式 (0|1)*00 相应的DFA并进行化简。(15分)
9、 若有文法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）文法，说明理由。 10、 （10分）对文法G(S)：
S ? S ? a T | a T | ? a T
T ? ? a T | ? a
(1) 消除该文法的左递归和提取左公因子；
(2) 构造各非终结符的FIRST和FOLLOW集合；
(3) 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。