Python 編寫的強(qiáng)大的、通用的解析器 -- SPARK (ZZ)

pascal4123

                Python 編寫的強(qiáng)大的、通用的解析器
Spark 是一種用 Python 編寫的強(qiáng)大的、通用的解析器／編譯器框架。在某些方面，Spark 所提供的比 SimpleParse 或其它
Python 解析器提供的都要多。然而，因?yàn)樗�完全是�?Python 編寫的，所以速度也會(huì)比較慢。David 在本文中討論了 Spark
模塊，給出了一些代碼樣本，解釋了它的用途，并對(duì)其應(yīng)用領(lǐng)域提供了一些建議。
　　
　　繼“可愛的 Python”系列中專門講述 SimpleParse 的前一篇文章之后，我將在本文中繼續(xù)介紹一些解析的基本概念，并對(duì)
Spark 模塊進(jìn)行了討論。解析框架是一個(gè)內(nèi)容豐富的主題，它值得我們多花時(shí)間去全面了解；這兩篇文章為讀者和我自己都開了一個(gè)好頭。
　　
　　在日常的編程中，我經(jīng)常需要標(biāo)識(shí)存在于文本文檔中的部件和結(jié)構(gòu)，這些文檔包括：日志文件、配置文件、定界的數(shù)據(jù)以及格式更自由的（但還是半結(jié)構(gòu)化的）
報(bào)表格式。所有這些文檔都擁有它們自己的“小語(yǔ)言”，用于規(guī)定什么能夠出現(xiàn)在文檔內(nèi)。我編寫這些非正式解析任務(wù)的程序的方法總是有點(diǎn)象大雜燴，其中包括定
制狀態(tài)機(jī)、正則表達(dá)式以及上下文驅(qū)動(dòng)的字符串測(cè)試。這些程序中的模式大概總是這樣：“讀一些文本，弄清是否可以用它來(lái)做些什么，然后可能再多讀一些文本，
一直嘗試下去�！�
　　
　　解析器將文檔中部件和結(jié)構(gòu)的描述提煉成簡(jiǎn)明、清晰和說明性的規(guī)則，確定由什么組成文檔。大多數(shù)正式的解析器都使用擴(kuò)展巴科斯范式（Extended
Backus-Naur Form，EBNF）上的變體來(lái)描述它們所描述的語(yǔ)言的“語(yǔ)法”。基本上，EBNF
語(yǔ)法對(duì)您可能在文檔中找到的部件賦予名稱；另外，較大的部件通常由較小的部件組成。小部件在較大的部件中出現(xiàn)的頻率和順序由操作符指定。舉例來(lái)說，清單
1 是 EBNF 語(yǔ)法 typographify.def，我們?cè)?SimpleParse
那篇文章中見到過這個(gè)語(yǔ)法（其它工具運(yùn)行的方式稍有不同）：
　　
　　清單 1. typographify.def
　　para　　　　:= (plain / markup)+
　　plain　　　 := (word / whitespace / punctuation)+
　　whitespace　:= [ tr]+
　　alphanums　 := [a-zA-Z0-9]+
　　word　　　　:= alphanums, (wordpunct, alphanums)*, contraction?
　　wordpunct　 := [-_]
　　contraction := "'", ('am'/'clock'/'d'/'ll'/'m'/'re'/'s'/'t'/'ve')
　　markup　　　:= emph / strong / module / code / title
　　emph　　　　:= '-', plain, '-'
　　strong　　　:= '*', plain, '*'
　　module　　　:= '[', plain, ']'
　　code　　　　:= "'", plain, "'"
　　title　　　 := '_', plain, '_'
　　punctuation := (safepunct / mdash)
　　mdash　　　 := '--'
　　safepunct　 := [!@#$%^&()+=|{}:;,.?/"]
　　
　　Spark 簡(jiǎn)介
　　Spark 解析器與 EBNF 語(yǔ)法有一些共同之處，但它將解析／處理過程分成了比傳統(tǒng)的 EBNF 語(yǔ)法所允許的更小的組件。Spark
的優(yōu)點(diǎn)在于，它對(duì)整個(gè)過程中每一步操作的控制都進(jìn)行了微調(diào)，還提供了將定制代碼插入到過程中的能力。您如果讀過本系列的 SimpleParse
那篇文章，您就會(huì)回想起我們的過程是比較粗略的：1）從語(yǔ)法（并從源文件）生成完整的標(biāo)記列表，2）使用標(biāo)記列表作為定制編程操作的數(shù)據(jù)。
　　
　　Spark 與標(biāo)準(zhǔn)的基于 EBNF
的工具相比缺點(diǎn)在于，它比較冗長(zhǎng)，而且缺少直接的出現(xiàn)計(jì)量符（即表示存在的“+”，表示可能性的“*”和表示有限制性的“?”）。計(jì)量符可以在
Spark 記號(hào)賦予器（tokenizer）的正則表達(dá)式中使用，并可以用解析表達(dá)式語(yǔ)法中的遞歸來(lái)進(jìn)行模擬。如果 Spark
允許在語(yǔ)法表達(dá)式中使用計(jì)量，那就更好了。另一個(gè)值得一提的缺點(diǎn)是，Spark 的速度與 SimpleParse 使用的基于 C 的底層
mxTextTools 引擎相比遜色很多。
　　
　　在“Compiling Little Languages in Python”（請(qǐng)參閱參考資料）中，Spark 的創(chuàng)始人 John
Aycock
將編譯器分成了四個(gè)階段。本文討論的問題只涉及到前面兩個(gè)半階段，這歸咎于兩方面原因，一是由于文章長(zhǎng)度的限制，二是因?yàn)槲覀儗⒅挥懻撉耙黄�文章提出的�?br /> 樣的相對(duì)來(lái)說比較簡(jiǎn)單的“文本標(biāo)記”問題。Spark
還可以進(jìn)一步用作完整周期的代碼編譯器／解釋器，而不是只用于我所描述的“解析并處理”的任務(wù)。讓我們來(lái)看看 Aycock
所說的四個(gè)階段（引用時(shí)有所刪節(jié)）：
　　
　　掃描，也稱詞法分析。將輸入流分成一列記號(hào)。
　　解析，也稱語(yǔ)法分析。確保記號(hào)列表在語(yǔ)法上是有效的。
　　語(yǔ)義分析。遍歷抽象語(yǔ)法樹（abstract syntax tree，AST）一次或多次，收集信息并檢查輸入程序 makes sense。
　　生成代碼。再次遍歷 AST，這個(gè)階段可能用 C 或匯編直接解釋程序或輸出代碼。
　　對(duì)每個(gè)階段，Spark 都提供了一個(gè)或多個(gè)抽象類以執(zhí)行相應(yīng)步驟，還提供了一個(gè)少見的協(xié)議，從而特化這些類。Spark
具體類并不象大多數(shù)繼承模式中的類那樣僅僅重新定義或添加特定的方法，而是具有兩種特性（一般的模式與各階段和各種父模式都一樣）。首先，具體類所完成的
大部分工作都在方法的文檔字符串（docstring）中指定。第二個(gè)特殊的協(xié)議是，描述模式的方法集將被賦予表明其角色的獨(dú)特名稱。父類反過來(lái)包含查找
實(shí)例的功能以進(jìn)行操作的內(nèi)�。╥ntrospective）方法。我們?cè)趨⒖词纠�的時(shí)侯會(huì)更清楚地認(rèn)識(shí)到這一點(diǎn)。
識(shí)別文本標(biāo)記
　　我已經(jīng)用幾種其它的方法解決了這里的問題。我將一種我稱之為“智能
ASCII”的格式用于各種目的。這種格式看起來(lái)很象為電子郵件和新聞組通信開發(fā)的那些協(xié)定。出于各種目的，我將這種格式自動(dòng)地轉(zhuǎn)換為其它格式，如
HTML、XML 和 LaTeX。我在這里還要再這樣做一次。為了讓您直觀地理解我的意思，我將在本文中使用下面這個(gè)簡(jiǎn)短的樣本：
　　
　　清單 2. 智能 ASCII 樣本文本（p.txt）
　　Text with *bold*, and -itals phrase-, and [module]--this
　　should be a good 'practice run'.
　　
　　除了樣本文件中的內(nèi)容，還有另外一點(diǎn)內(nèi)容是關(guān)于格式的，但不是很多（盡管的確有一些細(xì)微之處是關(guān)于標(biāo)記與標(biāo)點(diǎn)如何交互的）。
　　
　　生成記號(hào)
　　我們的 Spark“智能 ASCII”解析器需要做的第一件事就是將輸入文本分成相關(guān)的部件。在記號(hào)賦予這一層，我們還不想討論如何構(gòu)造記號(hào)，讓它們維持原樣就可以了。稍后我們會(huì)將記號(hào)序列組合成解析樹。
　　
　　上面的 typographify.def 中所示的語(yǔ)法提供了 Spark
詞法分析程序／掃描程序的設(shè)計(jì)指南。請(qǐng)注意，我們只能使用那些在掃描程序階段為“原語(yǔ)”的名稱。也就是說，那些包括其它已命名的模式的（復(fù)合）模式在解析
階段必須被延遲。除了這樣，我們其實(shí)還可以直接復(fù)制舊的語(yǔ)法。
　　
　　清單 3. 刪節(jié)后的 wordscanner.py Spark 腳本
　　class WordScanner(GenericScanner):
　　　　"Tokenize words, punctuation and markup"
　　　　def tokenize(self, input):
　　　　　　self.rv = []
　　　　　　GenericScanner.tokenize(self, input)
　　　　　　return self.rv
　　　　def t_whitespace(self, s):
　　　　　　r" [ tr]+ "
　　　　　　self.rv.append(Token('whitespace', ' '))
　　　　def t_alphanums(self, s):
　　　　　　r" [a-zA-Z0-9]+ "
　　　　　　print "{word}",
　　　　　　self.rv.append(Token('alphanums', s))
　　　　def t_safepunct(self, s): ...
　　　　def t_bracket(self, s): ...
　　　　def t_asterisk(self, s): ...
　　　　def t_underscore(self, s): ...
　　　　def t_apostrophe(self, s): ...
　　　　def t_dash(self, s): ...
　　
　　class WordPlusScanner(WordScanner):
　　　　"Enhance word/markup tokenization"
　　　　def t_contraction(self, s):
　　　　　　r" (?
               
               
               
               
               

本文來(lái)自ChinaUnix博客，如果查看原文請(qǐng)點(diǎn)：http://blog.chinaunix.net/u/16651/showart_464222.html