编译原理第3章文法和语言(10)

状态转换表1 a b X124 1234 124Y 1234 1234 124Y 124Y 1234 124Y

状态转换表2 a B 1 2 3 2 2 3 3 2 3

由于2与3完全一样，将两者合并，即见下表 a b 1 2 3 2 3 a b X12 12 12Y 12 12 12Y 12Y 12 12Y

可化简得下表 a b 1 2 3 2 2 3

得DFA图

两图完全一样，故两个自动机完全一样，所以两个正规文法等价。 对相应正规文法,令A对应1，B对应2 故为： A→aA|bB|b B→aA|bB|b

即为S→aS|bS|B,此即为所求正规文法。 问题6：

考虑正规表达式r=a*b(a|b)，构造可以生成语言L(r)的一个正规文法。 答案： S→a*b(a|b)

变换为S→aA,S→b(a|b),A→aA,A→b(a|b)

变换为S→aA,S→bB,B→(a|b),A→aA,A→bC,C→(a|b)

变换为S→aA,S→bB,B→a,B→b,A→aA,A→bC,C→a,C→b 所以，一个可能的正规文法为G[S]：

S→aA,S→bB,B→a,B→b,A→aA,A→bC,C→a,C→b 或表示为：

S→aA|bB,B→a|b,A→aA|bC,C→a|b

（适当等价变换也可以，但要作说明，即要有步骤）

问题7：

考虑下图所示的NFA N，构造可以生成语言L(N)的一个正规文法。 答案： G[P]:

P→0 P.1 P.1 Q Q→0 R.1 R R→ε 问题8：

考虑如下文法G[S]： S→0S.1S.1A A→0B.1B B→ε

a)试构造语言为L(G)的一个正规表达式。 b)试构造语言为L(G)的一个有限自动机。 答案： a)

由A→0B，B→ε得A→0; 由A→1B，B→ε得A→1; 由A→0，A→1得A→0.1;

由S→1A，A→0.1得S→1(0.1); 由S→1A，A→0.1得S→1(0.1); 由S→0S，S→1(0.1)得S→0*1(0.1); 由S→1S，S→1(0.1)得S→1*1(0.1);

由S→0*1(0.1)，S→1*1(0.1)得S→0*1(0.1).1*1(0.1); 所以，一个可能的正规表达式为：

0*1(0.1).1*1(0.1) b)

第5章自顶向下语法分析方法 第1题

对文法G[S] S→a|∧|(T) T→T,S|S

(1)给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。

(2)对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (3)经改写后的文法是否是LL(1)的?给出它的预测分析表。

(4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。 答案：

(1)对(a,(a,a)的最左推导为： S(T) (T,S) (S,S) (a,S) (a,(T)) (a,(T,S)) (a,(S,S)) (a,(a,S)) (a,(a,a))

对(((a,a),∧,(a)),a)的最左推导为： S(T) (T,S) (S,S) ((T),S) ((T,S),S) ((T,S,S),S) ((S,S,S),S) (((T),S,S),S) (((T,S),S,S),S) (((S,S),S,S),S) (((a,S),S,S),S) (((a,a),S,S),S) (((a,a),∧,S),S) (((a,a),∧,(T)),S) (((a,a),∧,(S)),S)