robot
最新文章(10)
Mqskit 和其它相關工具
CPython 的 GC 二、三事
寫 Mecurial Extension 是件快樂的事!
Mozilla 台灣辨公室徵人啟事
關於 Apple 的兩項專利
core dump 之前的 frame
怎麼發出 beep 聲?
先承認你要找的是奴才吧!
程式碼要清的多乾淨?
FreeBSD 的 Thread-Local Storage 實作
首頁
新編
最新留言
Entries RSS
重要關鍵字(10)
coding (122)
Python (93)
FreeBSD (71)
WEB (61)
URL (48)
hardware (46)
javascript (36)
Linux (34)
blog (30)
C++ (16)
所有關鍵字
新增 URL
另一個 Python Parser Generator
by thinker
2 Columns
關鍵字:
Python
coding
我是屬於那種無法專心,容易偏離主題,被其它事情吸引心思的人。事情做到一半,就會被吸引去做其它事,把手頭上正在做的事放著。或許一放就是一年半載,回頭或遺忘。這次也是在做著其它事,正好需要一個 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 -> ϵ $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 -> ϵ $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: