1、令文法为
E?T|E+T|E-T
T?F|T*F|T/F F?（E）|i
1） 2）
给出i+i*i的最左推导和最右推导； 给出i-i-i的语法树。
∵E=>E+T=>E+T*F ∴E+T*F是文法G[E]的一个句型 ∴此句型相对于E的短语有:E+T*F；相对于T的短语有T*F, 直接短语为：T*F；。 句柄为：T*F
2、设有文法G[S]:（12分）
S?a|ε|(T) T?T,S|S
1）请给出句子(a,(a,a))的最左,最右推导 2）给出(a,(a,a))的语法树
3、下面的文法生成的是以x和y为操作数、二元运算符+、*和-为运算符的前缀表达式：
E?+EE|*EE|-EE|x|y
1） 给出串+*-xyxy的最左推导和最右推导； 2） 给出+*-xyxy的语法树。
4、将下图中的自动机确定化并最小化。
aXε5b
εa1b3b4aa2ε6bεY
5、将下图中的自动机确定化并最小化。
ε2ε4a3ε5ε0εε1ε6ε7a8b9b10b
6、设有DFA M=(K,∑,f,S,Z)
其中：
K={0，1，2，3} ∑={a,b} S=0 Z={3} f为：
f(0,a)=1 f(1,b)=1 f(0,b)=2 f(2,a)=1 f(1,a)=3 f(2,b)=3 试画出其状态转换矩阵和状态转换图。
7、将下图中的自动机确定化。
a,biε1ε2ab3b4a5εa,b6εf
8、考虑下面文法G1：（18分）
S?a|?|(T) T?T，S|S
1） 消去G1的左递归；
2） 经改写后的文法是否是LL(1)的？给出它的预测分析表(要求写出详细过程，应先
求出每个非终结符的FIRST和FOLLOW集合)。
9、构造正规式1(0|1)101相应的自动机
*
10、考虑下面文法G1：
E?E+T|T T?T*F|F F?i|(E)
3） 消去G1的左递归；
4） 经改写后的文法是否是LL(1)的？ (要求写出详细过程，应先求出改写后的每个非
终结符的FIRST和FOLLOW集合)。
11、对于文法G（S）： S?(L)|aS|a L?L,S|S
1）画出句型(S,(a))的语法树。
2）写出上述句型的所有短语、直接短语、句柄和素短语。
12、对于文法G（S）：
S?(L)|aS|a L?L,S|S
1）画出句型(S,(a))的语法树。
2）写出上述句型的所有短语、直接短语、句柄和素短语。
13、对于文法G（E）： E?T|E+T
T?F|T*F F?(E)|i|j|k
1）画出句型i*j+k的语法树。
2）写出上述句型的所有短语、直接短语、句柄和素短语。 14、设文法G（S）：
S?(A)|a A?A+S|S
1）构造各非终结符的FIRSTVT集合和LASTVT集合。 2）构造优先关系表。
15、设文法G（S）：
S?(A)|a A?A+S|S
1）构造各非终结符的FIRSTVT集合和LASTVT集合。 2）构造优先关系表。
16、设文法G（S）：
S?(A)|a A?A+S|S
1）构造各非终结符的FIRSTVT集合和LASTVT集合。 2）构造优先关系表。