第五章
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1．对文法G[S]
G: 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. [解答]
（1）① S
（ T ）
T , S S ( T ) a T , S S a a ① S=>(T) =>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) =>(a,(a,S)) =>(a,(a,a))
(2) 消除左递归
G': S→ a | ∧ | (T) T→ ST' T'→ ,ST' |ε
递归子程序：
program parser begin getsym; S end; ② S ( T ) T , S ②S=>(T) =>(T,S) =>(S,S) S a =>((T),S) =>((T,S),S) ( T ) =>((T,S,S),S) =>((S,S,S),S) T , S =>(((T),S,S),S)
=>(((T,S),S,S),S) T , S ( T ) =>(((S,S),S,S),S) =>(((a,S),S,S),S) S ^ S =>(((a,a),S,S),S) =>(((a,a),^,S),S) ( T ) a =>(((a,a),^,(T)),S) =>(((a,a),^,(S)),S) T , S =>(((a,a),^,(a)),S) =>(((a,a),^,(a)),a) S a a proceduce T;
begin
if sym in [a,^,() then begin S;
第五章
proceduce S; T; begin end;
if sym=’a’ or sym=’^’ then else getsym error; elseif sym=’(‘ end;
begin getsym; proceduce T’; T; begin
If sym=’)’ then if sym=’,’ then Getsym; begin
Else getsym; Error; S; End; T; Else end; Error; else
End; if sym=’)’ then else error; end;
(3) FIRST集 a ∧ ( a ∧ ( , ε FIRST集 a ∧ ( a ∧ ( , ε FOLLOW集 {#}∪FIRST(T')/{ε}∪FOLLOW(T)∪FOLLOW(T') ) FOLLOW(T)∪FOLLOW(T') FOLLOW集 # , ) ) ) # , ) ) ) S T FIRST(S) T' S T T' SELECT集合 S→a S→∧ S→(T) T→ST' T'→,ST' T'→ε a ∧ ( ) , # S →a →∧ →(T) T →ST' →ST' →ST' T' a ∧ ( a ∧ ( , ) →ε →,ST' 预测分析表不含多重定义入口, 所以该文法是LL(1)文法!
第五章
(4) 分析栈 余留串 所用产生式或动作 1 #S (a,a)# S—>(T) 2 #)T( (a,a)# (匹配 3 #)T a,a)# T—>ST’ 4 #)T’S a,a)# S—>a 5 #)T’a a,a)# a匹配
6 #)T’ ,a)# T’ —>,ST’ 7 #)T’S, ,a)# ,匹配 8 #)T’S a)# S—>a 9 #)T’a a)# a匹配 10 #)T’ )# 11 #) )# 12 # #
因为 （a,a）#分析成功 所以 步骤 分析栈 余留串 1 #S (a,a# 2 #)T( (a,a# 3 #)T a,a# 4 #)T’S a,a# 5 #)T’a a,a# 6 #)T’ ,a# 7 #)T’S, ,a# 8 #)T’S a# 9 #)T’a a# 10 #)T’ #
T’—>ε )匹配 接受 a,a）为文法的句子 所用产生式或动作 S→(T) ( 匹配 T→ST’ S→a a 匹配 T’ →,ST’ , 匹配 S→a a 匹配 出错 （ 第五章
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
2. G:
E E' T T' F F' P E E' T T' F F' P E→TE' E'→+E E'→ε T→FT' T'→T T'→ε F→PF' F'→*F' F'→ε P→(E) P→a P→b P→∧ E → TE'
E' → +E |ε T → FT' T' → T |ε F → PF' F' → *F' |ε
P → (E) | a | b |∧
FIRST集 ( a b ∧ + ε ( a b ∧ ( a b ∧ ε ( a b ∧ * ε ( a b ∧ FOLLOW集 # ) # ) + # ) + # ) ( a b ∧ + # ) ( a b ∧ + # ) * ( a b ∧ + # ) SELECT集 ( a b ∧ + # ) ( a b ∧ ( a b ∧ # ) + ( a b ∧ * ( a b ∧ + # ) ( a b ∧ 2. [解答] 可推出ε FIRST集 N Y N Y N Y N FIRST(T) + ε FIRST(F) FIRST(T) ∪{ε} FIRST(P) * ε ( a b ∧ FOLLOW集 { # }∪FOLLOW(E') ∪ { ) } FOLLOW(E) FIRST(E')/{ε} ∪FOLOW(E)∪FOLOW(T') FOLLOW(T) FIRST(T')/ {ε} ∪FOLOW(T) FOLLOW(F) FIRST(F')/ {ε} ∪FOLOW(F) SELECT集 FIRST(T) + FOLLOW(E') FIRST(F) FIRST(T) FOLLOW(T') FIRST(P) * FOLLOW(F') ( a b ∧ 第五章
预测分析表 E E' T T' F F' P E
→+E →ε →ε + →*F' * →FT' →T →PF' →ε →(E) →TE' ( →TE' →ε →ε →ε ) →FT' →T →PF' →ε →a →TE' a →TE' →FT' →T →PF' →ε →b →TE' b →TE' →FT' →T →PF' →ε →∧ →TE' ∧ →TE' →ε →ε →ε #