编译原理复习题2（第二版张素琴吕映芝蒋维杜戴桂兰编著）

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）构造优先关系表。