而对正规式(2)可画NFA图，如图所示。
X12 12 12Y a 12 12 12 b 12Y 12Y 12Y 可化简得下表 1 2 a 2 2 b 3 3 得DFA图
两图完全一样，故两个自动机完全一样，所以两个正规文法等价。 对相应正规文法,令故为： A->aA|bB|b B->aA|bB|b
即为S->aS|bS|B,此即为所求正规文法。
A对应1，B对应2
四 1.文法
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) =>(((a,a),^,(a)),S) =>(((a,a),^,(a)),a) (3)改写文法为： 0) S->a 1) S->^
2) S->( T ) 3) T->S N2 4) N2->, S N2 5) N2->ε
对左部为N2的产生式可知：
FIRST （->, S N2）={，} FIRST （->ε）={ε} FOLLOW N2）={)}（
{，}∩ {)}=? 所以文法是LL(1)的。
可见输入串（a,a）#是文法的句子。
2．已知文法G[A]如下，试用类C或类PASCAL语言写出其递归下降子程序.(主程序不需写) G[A]: A→[B B→X]{A} X→(a|b){a|b} [答案]
不妨约定:在进入一个非终结符号相应的子程序前，已读到一个单词.word：存放当前读到的单词，Getsym()为一子程序，每调用一次，完成读取一单词的工作。error()为出错处理程序.FIRST(A)为终结符A的FIRST集. 类C程序如下：
3．文法：
S->MH|a H->LSo|ε K->dML|ε L->eHf M->K|bLM 判断G是否为LL(1)文法，如果是，构造LL(1)分析表。 [答案]
源文法G展开为： 0） S->M H 1） S->a
2） H->L S o 3） H->ε 4） K->d M L 5） K->ε 6） L->e H f 7） M->K
8） M->b L M
由预测分析表中无多重入口判定文法是LL(1)的。 4．设有文法G[A]的产生式集为:
A→BaC|CbB B→Ac|c C→Bb|b 试消除G[A]的左递归。 [答案]
提示：不妨以A、B、C排序.先将A代入B中，然后消除B中左递归；再将A、B代入C中。再消除C中左递归。 最后结果为:G[A]:
A→BaC|CbB B→CbBcB'|cB' B'→aCcB'|ε C→cB'bC'|bC' C'→bBcB'bC'|ε
五
1、对于文法S ? ( L ) | a L ? L, S | S
(1)给出句子(a, ((a, a), (a, a)))的一个最右推导，并指出右句型的句柄； (2)按照(1)的最右推导，说明移进－归约分析器的工作步骤。 [答案]
(1)S => ( L ) => (L, S) => (L, (L)) => (L, (L, S)) => (L, (L, (L))) => (L, (L, (L, S)))=> (L, (L, (L, a))) => (L, (L, (S, a))) => (L, (L, (a, a))) => (L, (S, (a, a)))=> (L, ((L), (a, a))) => (L, ((L, S), (a, a))) => (L, ((L, a), (a, a))) => (L, ((S, a), (a, a))) => (L, ((a, a), (a, a))) => (S, ((a, a), (a, a))) => (a, ((a, a), (a, a))) (注：句柄下面有下划线) (2)