编译原理课后答案

if sym='*'

then begin advance; F' end end

procedure P; begin

if sym='a' or sym='b' or sym='^' then advance

else if sym='(' then begin

advance; E;

if sym=')' then advance else error end

else error end;

3.下面文法那些是LL（1）文法？

（1）S →Abc A →a|ε B→b|ε

没有左递归且FIRST 候选集不冲突且

FIRST(A)∩FOLLOW(A)={ a, ε} ∩ { b }=Ф FIRST(B)∩FOLLOW(B)={ b, ε} ∩ { c }=Ф 所以该文法为LL（1）文法

（2）S →Ab A →a|B|ε B→b|ε

FIRST(B)＝{ b, ε} ∩ FIRST(ε) ={ε} ≠Ф 所以该文法不是LL（1）文法

（3）S →ABBA A →a |ε B→b|ε

没有左递归且FIRST 候选集不冲突

FIRST(A)∩FOLLOW(A)={ a, ε} ∩{b,#} =Ф FIRST(B)∩FOLLOW(B)={ b, ε}∩{b,a,#} ≠Ф 所以该文法不是LL（1）文法

(4) S →aSe|B B →bBe |C C→cCe|d

没有左递归且FIRST 候选集不冲突 所以该文法为LL（1）文法

4.Expr→_Expr

Expr→(Expr)| Var ExprTail ExprTail→_ Expr|ε Var→id VarTail VarTail→(Expr)| ε （1）构造LL（1）分析表

（2）给出对句子id_ _id((id)) 的分析过程

解答：（1）FIRST(Expr)={_ , ( , id } FIRST(ExprTail)={_ , ε } FIRST(Var)={id} FIRST(VarTail)={ ( , ε}

FOLLOW(Expr)={# , ) } FOLLOW(ExprTail) ={# , ) } FOLLOW(Var) ={_ , # , ) } FOLLOW(VarTail) ={_ , # , ) }

预测分析表如下： Expr — Expr→_Expr id ( ） # Expr→Var Expr→ExprTail (Expr) Var→VarTail id VarTail→(Expr) ExprTail ExprTail→_ Expr Var VarTail VarTail→ε ExprTail→ε ExprTail→ε VarTail→ε

(3) 对句子id_ _((id)) 的分析过程：

步骤 符号栈 输入串 所用产生式 0 ＃Expr id_ _id((id))＃

1 # ExprTail Var id_ _id((id))＃ Expr→Var ExprTail 2 # ExprTail VarTail id id_ _id((id))＃ Var→id VarTail

3 # ExprTail VarTail _ _id((id))＃

4 # ExprTail _ _id((id))＃ VarTail→ε

5 6 7 8 9 10 11 12 13 14 15 16

# Expr_ _ _id((id))＃ ExprTail→_ Expr _id((id))＃

_id((id))＃ Expr→_Expr id((id))＃

id((id))＃ Expr→Var ExprTail

# Expr # Expr_ # Expr # ExprTail Var

17 18 19 20 21 22 23

# ExprTail VarTail id id((id))＃ Var→id VarTail # ExprTail VarTail ((id))＃

# ExprTail )Expr( ((id))＃ VarTail→(Expr) # ExprTail )Expr (id))＃

# ExprTail ) )Expr( (id))＃ Expr→(Expr) # ExprTail ) )Expr id))＃

# ExprTail ) )

ExprTail Var id))＃ Expr→Var ExprTail

# ExprTail ) )

ExprTail VarTail id id))＃ Var→id VarTail # ExprTail ) )

ExprTail VarTail ))＃

# ExprTail ) )

ExprTail ))＃ VarTail→ε

# ExprTail ) ) ))＃ ExprTail→ε # ExprTail ) # ExprTail #

)＃

ExprTail→ε 分析成功 第五章

# #

1. E?E?T?E?T*F 短语: E+T*F, T*F, 直接短语: T*F 句柄: T*F

2 （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 ) )

最右推导：S => ( T ) =>( T,S ) => ( T, (T) ) =>( T, (T, S) ) =>( T, (T, a) ) =>( T,

(S, a) ) => ( T,(S, a ) ) => ( T,( a ,a ) ) => (S,( a ,a ) ) => ( 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 ),^ ，a ),S ) =>(( ( a ,a ),^ ，a ),a )

最右推导：S => ( T ) =>( T,S ) =>( T, a ) =>( S ,a ) =>( (T) , a ) =>( (T, S) , a ) =>( (T, ( T )) , a ) =>( (T, ( a )) , a ) =>( (T, S, ( a )) , a ) =>( (T, ^, ( a )) , a ) =>( (S, ^, ( a )) , a ) =>( ((T), ^, ( a )) , a ) =>( ((T,S), ^, ( a )) , a ) =>( ((T ,a), ^, ( a )) , a ) =>( ((S ,a), ^, ( a )) , a ) =>( ((a ,a), ^, ( a )) , a )

(2) (((a, a),^,(a)),a)的规范规约及每一步的句柄为： (((a, a),^,(a)),a) a ( ((S ,a), ^, ( a )) , a ) S ( ((T ,a), ^, ( a )) , a ) a ( ((T,S), ^, ( a )) , a ) T,S ( ((T), ^, ( a )) , a ) (T) ( (S, ^, ( a )) , a ) S ( (T, ^, ( a )) , a ) ^ ( (T, S, ( a )) , a ) T,S ( (T, ( a )) , a ) a ((T,(S)),a) S

( (T, ( T )) , a ) (T) ( (T, S) , a ) T,S ( (T) , a ) (T) ( S ,a ) S ( T, a ) a ( T,S ) T,S ( T ) (T) S

步骤 符号栈 输入串 动作 0 # (((a, a),^,(a)),a)# 预备 1 #( ((a, a),^,(a)),a)# 进 2 #(( (a, a),^,(a)),a)# 进 3 #((( a, a),^,(a)),a)# 进 4 #(((a , a),^,(a)),a)# 进

5 #(((S , a),^,(a)),a)# 规约 S→a

6 #(((T , a),^,(a)),a)# 规约T