一道編譯原理習題及答案
以下是一道編譯原理習題，很具有代表性。
題目如下：
設有文法G1為：
S->a|^|(T)
T->T,S|S
（1）給出 (a,(a,a)) 的最右推導和規範歸約過程；
（2）給出 (((a,a),^,(a)),a) 的最左推導；
（3）畫出 (a,(a,a)) 最左推導的語法樹和 (((a,a),^,(a)),a)最右推導的語法樹，並指出規約過程中每一步的控制碼；
（4）判定G1是否是LL（1）文法，如果是構造LL（1）分析表，並分析輸入串（a,a）#；
（5）計算文法中各非終結符的FIRSTVT和LASTVT並構造算符優先表。
答案：
1）S=>(T) =>(T,S) =>(T,(T)) =>(T,(T,S)) =>(T,(T,a)) =>(T,(S,a)) =>(T,(a,a)) =>(S,(a,a)) =>(a,(a,a))
(a,(a,a))的規範歸約過程。
|
步驟 |
堆疊 |
輸 入 |
動 作 |
|
1 |
# |
(a,
(a, a))# |
移進 |
|
2 |
#( |
a,
(a, a))# |
移進 |
|
3 |
#(a |
,
(a, a))# |
歸約，S→a |
|
4 |
#(S |
,
(a, a))# |
歸約，L→S |
|
5 |
#(T |
,
(a, a))# |
移進 |
|
6 |
#(T, |
(a,
a))# |
移進 |
|
7 |
#(T, ( |
a,
a))# |
移進 |
|
8 |
#(T,
(a |
,
a))# |
歸約，S→a |
|
9 |
#(T,
(S |
,
a))# |
歸約，T→S |
|
10 |
#(T,
(T |
,
a))# |
移進 |
|
11 |
#(T,
(T, |
a))# |
移進 |
|
12 |
#(T, (T,a |
))# |
歸約，S→a |
|
13 |
#(T,
(T, S |
))# |
歸約，T→T,
S |
|
14 |
#(T,
(T |
))# |
移進 |
|
15 |
#(T,
(T) |
)# |
歸約，S→(T) |
|
16 |
#(T, S |
)# |
移進 |
|
17 |
#(T,
S) |
# |
歸約，T→T,
S |
|
18 |
#(T) |
# |
歸約，S→(T) |
|
19 |
#S |
# |
接受 |
2）
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）(a, ((a, a), (a, a)))的一個最右推導
| (a,a),^,(a)),a)的最右推導過程 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||
(((a,a),^,(a)),a)的推導樹如下圖所示:
(((a,a),^,(a)),a)的推導樹
(((a,a),^,(a)),a)的推導樹自下而上的構造過程
4）改寫文法為：
1) S->^
2) S->( T )
3) T->S N2
4) N2->, S N2
5) N2->ε
|
|
FIRST |
FOLLOW |
|
S |
a
^ ( |
# , ) |
|
T |
a
^ ( |
) |
|
N2 |
, ε |
) |
對左部為N2的產生式可知：
FIRST （->ε）={ε}
FOLLOW （N2）={)}
{，}∩ {)}=Ø
所以文法是LL(1)的。
Predicting Analysis Table
預測分析表
|
|
a |
^ |
( |
) |
, |
# |
|
S |
->a |
->^ |
->(
T ) |
|
|
|
|
T |
->S
N2 |
->S
N2 |
->S
N2 |
|
|
|
|
N2 |
|
|
|
->ε |
->,
S N2 |
|
(4) 對輸入串（a,a）#的分析過程為：
步驟 |
狀態堆疊 |
當前符號 |
賸餘輸入字串 |
操作 |
|
1 |
#S |
( |
a,a)# |
S->(T) |
|
2 |
#)T( |
( |
a,a)# |
匹配 |
|
3 |
#)T |
A |
,a)# |
T->SN2 |
|
4 |
#)N2S |
A |
,a)# |
S->a |
|
5 |
#)N2a |
A |
,a)# |
匹配 |
|
6 |
#)N2 |
, |
a)# |
N2->,SN2 |
|
7 |
#)N2S, |
, |
a)# |
匹配 |
|
8 |
#)N2S |
a |
)# |
S->a |
|
9 |
#)N2a |
a |
)# |
匹配 |
|
10 |
#)N2 |
) |
# |
N2->ε |
|
11 |
#) |
) |
# |
匹配 |
|
12 |
# |
# |
|
|
#S ( a,a)#
#)T( ( a,a)# S->(T)
#)T a ,a)#
#)N2S a ,a)# T->SN2
#)N
#)N2 , a)#
#)N2S, , a)# N2->,SN2
#)N2S a )#
#)N
#)N2 ) #
#) ) # N2->ε
# #
可見輸入串（a,a）#是文法的句子。
5）G[S]的FIRSTVT和LASTVT
LASTVT(S) ={ a , ^ , } } LASTVT(T) ={ a , ^ , } , , }
FIRSTVT和LASTVT
|
|
FIRSTVT |
LASTVT |
|
S |
a、^、（ |
a、^、） |
|
T |
，、a、^、（ |
，、a、^、) |
G[S]的算符優先關係表
算符優先關係
|
|
a |
( |
) |
, |
^ |
# |
|
a |
|
|
≯ |
≯ |
|
≯ |
|
( |
≮ |
≮ |
≡ |
|
≮ |
|
|
) |
|
|
≯ |
≯ |
|
≯ |
|
, |
≮ |
≮ |
≯ |
≯ |
≮ |
|
|
^ |
|
|
≯ |
≯ |
|
≯ |
|
# |
≮ |
≮ |
|
|
≮ |
|
G[S]的優先函數
對應的算符優先函數為：
|
|
a |
( |
) |
, |
^ |
# |
|
S |
2 |
1 |
2 |
2 |
2 |
1 |
|
T |
3 |
3 |
1 |
1 |
3 |
1 |
留言列表