编译原理复习题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)构造优先关系表。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4