另一個 Python Parser Generator

by thinker

關鍵字:

我是屬於那種無法專心，容易偏離主題，被其它事情吸引心思的人。事情做到一半，就會被吸引去做其它事，把手頭上正在做的事放著。或許一放就是一年半載，回頭或遺忘。這次也是在做著其它事，正好需要一個 parser generator 。原本找一個現成的 generator 就可以，但一時玩心昇起，動手以 $Python$ 寫了一個 LR(1) 的 parser generator 。或許有人要罵我重新發明輪子，但我只是用樂趣在做這事。

以下簡單介紹這個 module 的用法。定義 context free grammar 的第一步，就是定義所有的 terminal 和 non-terminal 。
{{{#!python
from fun_parser import terminal, nonterminal

a = terminal('a')
b = terminal('b')
S = nonterminal('S')
E = nonterminal('E')
E1 = nonterminal('E1')
$C$ = nonterminal('$C$')
}}}
上面定義了 a 、 b 兩個 terminal 和 S 、 E 、 E1 、 $C$ 四個 non-terminal 。 terminal() 和 nonterminal() 必需傳入一個字串，做為符號 (symbol) 的名稱。

接著要定義語法了，假設我們要定義下面的語法
{{{
S -> E
E -> b E1 b $C$
E1 -> $C$ E1
E1 -> &#1013;
$C$ -> a
}}}
那麼就個別為這五個 production 建 rule
{{{#!python
from fun_parser import epsilon

S.add_rule((E,)) # S -> E
E.add_rule((b, E1, b, $C$)) # E -> b E1 b $C$
E1.add_rule(($C$, E1)) # E1 -> $C$ E1
E1.add_rule((epsilon,)) # E1 -> &#1013;
$C$.add_rule((a,)) # $C$ -> a
}}}
於是就定義好 context free grammar 了。

接著我們要產生 parsing table ，
{{{#!python
from fun_parser import LR1

parser = LR1()
parser.set_grammar(S)
}}}
S 是剛才定義的 start symbol ，呼叫 parser::set_grammar ，就會自動轉換成 parsing table 。也就是在課本上看到的 action table 和 goto table 。

產生的 parser 能 parse 所定義的語言，parser 透過一個 builder 輸出 parsing 的結果。programmer 透過定義 builder ，接收並處理 parser 的輸出。 builder 必需定義三個 method
* shift
* reduce_
* accept
對映 action table 裡面的三個動作。下面是一個$範例$
{{{#!python
from fun_parser import ptree_builder
class my_builder(ptree_builder):
    def shift(self, tkn):
        print 'get a token (%s, %s).' % (tkn.tkn_type, tkn.lexeme)
        pass
    def reduce_(self, sym, reduce_sz):
        print 'reduce last %d symbols to %s.' % (reduce_sz, sym)
        pass
    def accept(self, sym, reduce_sz):
        print 'reduce last %d symbols to %s and accept it.' % (reduce_sz, sym)
        pass
}}}

完成 builder 之後，我們就能開始 parsing 了， parse 的對象是一個序列的 token 。但 token 哪來？對了，就是從 lexical analyzer 產生的，但這個 module 並不提供 lexical analyzer ，所以必需自己產生。下面是一個使用 parser 的$範例$。
{{{#!python
from fun_parser import token

tokens = []
tokens.append(token('b', 'b'))
tokens.append(token('a', 'a'))
.....
tokens.append(token('$$', '$$'))  # this is endmarker that means end of source file.

parser = LR1()
parser.set_grammar(S)
parser.builder = my_builder()  # set a builder for parser before using it.
for tkn in tokens:
    parser.eat_token(tkn)
    pass
}}}
將 token 一個接著一個，依次序餵給 parser::eat_token() ，最後就完成 parsing 了。必需注意的是，最後一個 token 必需是 token('$$', ...) ，這代表檔案的結束。

除了設定 context free grammar 之外， parsing table 還可以在初始化時，傳給 __init__() 。例如下面 create 另一個 parser2 。
{{{#!python
action_tb = parser.action_tb
goto_tb = parser.goto_tb

parser2 = LR1(action_tb, goto_tb)
for ....
    parser2.eat_token(...)
}}}
換句話說，可以將 parser 的 action_tb 和 goto_tb 這兩個 attribute 的內容記錄下來，之後就透過這個方式，重建 parser 。

雖然這個 generator 是為 $Python$ 寫的，但產生的 parsing table ，要轉為 $C$ 或其它語言使用，應該也很容易。應該不用很久，我就會寫個 $C$ 的 library ，使用這個 module 產生的 parsing table 。

這個 parser generator 雖然沒幾行，卻也花了不少時間，重新回去看 The Dragon Book ，算是蠻有趣、但沒有生產力的事情。

== Download ==
 * http://master.branda.to/downloads/misc/fun_parser.tar

最後更新時間: 2007-09-23 11:43:40 CST | 引用

查詢:

COMMENTS: