一般資料都說，遞迴下降的程式寫法，就是為每個非終端符號寫一個 function 來做 parse。
這裡提醒一些小事項。
(1) 準備兩個function，一個 accept，一個 expect。(註1)
def accept(s):
global sym
if sym[0] == s:
print 'accept',sym
getsym()
return True
return False
def expect(s):
if accept(s):
return True
print "expect: unexpected symbol"
global sym
print sym
sym = None
return False
這些會有幾個用途：
(a)處理可省略項目的 rule，例如：
<host_type_msg> ::= eap_log_1 [xml_transaction]
accept 的意思是，如果傳入參數，是預期的就回 True，input 往下移動一個。
如果不是預期的，就回 False。呼叫的人看到回傳是 False 不停止動作。
expect 的意思是，如果傳入參數，是預期的就回 True，input 往下移動一個。
如果不是預期的，就回 False。呼叫的人看到回傳是 False 則停止動作。
所以 host_type_msg 的 parse function 寫成
def host_type_msg():
if expect("eap_log_1"):
accept("xml_transaction")
return True
else:
return False
(b)accept可當做look ahead的測試工具，例如：
<secs_msg_item> ::= secs_item_a
| secs_item_u
| secs_item_b
| secs_item_bool
| secs_item_f
| secs_item_i
| secs_list_start [secs_comment] {<secs_msg_item>} secs_list_end
secs_msg_item 的 parse function 裡面可寫成
if accept("secs_item_a"):
return True
elif accept("secs_item_u"):
return True
....省略
elif accept("secs_list_start"):
accept("secs_comment")
....省略
(2)每個 parse function 要回傳 True 或 False。
基本上，可以不用每個 parse function 都加。
但是有「出現0次或多次」這種規則的 parse function，需要回傳值才知道什麼時候要停下來。
因為這個規則的程式會轉換成迴圈，parse成功，才需要再 parse 否則就要停。
例如：
{<secs_msg_item>}
會轉成
r = secs_msg_item()
while r == True:
r = secs_msg_item()
(3)因為以下的規則，必須使用 look ahead。
<desc> ::= <secs_msg_name> colon <secs_SxFy_sym>
| normal_word {normal_word}
<secs_msg_name> ::= normal_word
因為 secs_msg_name() 的呼叫結果是 expect("normal_word")
在看到 input 的 normal_word 時，無法決定要呼叫 secs_msg_name()
還是 expect("normal_word")，可是往下看一個 input 若是 colon 就呼叫 secs_msg_name()，
否則呼叫 accept("normal_word")。
把 grammar 跟程式兩個互相比較，你就會知道有多直覺(前提是寫一些方便函數)
========================================================
<msg> ::= timestamp <secs_type_msg>
| timestamp <host_type_msg>
--------------------------------------------------------
def msg():
print 'msg()'
if expect("timestamp"):
if sym[0]=="eap_log_1":
host_type_msg()
else:
secs_type_msg()
print 'msg() complete'
========================================================
<host_type_msg> ::= eap_log_1 {xml_transaction}
--------------------------------------------------------
def host_type_msg():
print 'host_type_msg()'
expect("eap_log_1")
accept("xml_transaction")
========================================================
<secs_type_msg> ::= <desc> secs_comment <secs_msg>
--------------------------------------------------------
def secs_type_msg():
print 'secs_type_msg()'
desc()
accept("secs_comment")
secs_msg()
========================================================
<desc> ::= <secs_msg_name> colon <secs_SxFy_sym>
| normal_word {normal_word}
--------------------------------------------------------
def desc():
print 'desc'
global input_index
_sym = lookahead()
if _sym[0]=="colon":
secs_msg_name()
expect("colon")
secs_SxFy_sym()
else:
r = accept("normal_word")
while r == True:
r = accept("normal_word")
========================================================
<secs_SxFy_sym> ::= secs_SxFy {<secs_w_bit>}
--------------------------------------------------------
def secs_SxFy_sym():
print 'secs_SxFy_sym()'
expect("secs_SxFy")
secs_w_bit()
========================================================
<secs_msg_name> ::= normal_word
--------------------------------------------------------
def secs_msg_name():
print 'secs_msg_name()'
expect("normal_word")
========================================================
<secs_w_bit> ::= normal_word
--------------------------------------------------------
def secs_w_bit():
print 'secs_w_bit'
accept("normal_word")
========================================================
<secs_msg> ::= {<secs_msg_body>} secs_end
--------------------------------------------------------
def secs_msg():
print 'secs_msg()'
if accept("secs_end"):
pass
else:
secs_msg_body()
accept("secs_end")
========================================================
<secs_msg_body> ::= <secs_msg_item> {secs_comment }
--------------------------------------------------------
def secs_msg_body():
print 'secs_msg_body()'
secs_msg_item()
accept("secs_comment")
========================================================
<secs_msg_item> ::= secs_item_a {secs_comment}
| secs_item_u {secs_comment}
| secs_item_b {secs_comment}
| secs_item_bool {secs_comment}
| secs_item_f {secs_comment}
| secs_item_i {secs_comment}
| secs_list_start {secs_comment} {<secs_msg_item>} secs_list_end
--------------------------------------------------------
def secs_msg_item():
print 'secs_msg_item()'
if accept("secs_item_a"):
accept("secs_comment")
return True
elif accept("secs_item_u"):
accept("secs_comment")
return True
elif accept("secs_item_b"):
accept("secs_comment")
return True
elif accept("secs_item_bool"):
accept("secs_comment")
return True
elif accept("secs_item_f"):
accept("secs_comment")
return True
elif accept("secs_item_i"):
accept("secs_comment")
return True
elif accept("secs_list_start"):
accept("secs_comment")
r = secs_msg_item()
while r == True:
r = secs_msg_item()
expect("secs_list_end")
return True
else:
return False
========================================================
相信有仔細看程式的人會注意到，怎麼 accept 就只是把 input 接受而已，
怎麼沒有 output ？
對的，再來就是要產生 parser 的 output，通常是長成 tree，
叫做 contrete syntax tree 或 parse tree 或 parsing tree。
或者是abstract syntax tree(把 parse tree 中，將來不需要用到的資訊去除)。
這兩種 tree 的差異，我認為只是相對的。程式可以控制你想表現的是哪一種 tree。
所以重點是要把 parse 的結果表現成 tree，讓後續的動作能利用。
當然把所有accept 的 token 都呈現的 tree 是 parse tree。
我們先從這裡開始。
沒有留言:
張貼留言