Spark 是一種用 Python 編寫的強大的、通用的解析器/編譯器框架。在某些方面,Spark 所提供的比 SimpleParse 或其它 Python 解析器提供的都要多。然而,因為它完全是用 Python 編寫的,所以速度也會比較慢。David 在本文中討論了 Spark 模塊,給出了一些代碼樣本,解釋了它的用途,並對其應用領域提供了一些建議。 繼“可愛的 Python”系列中專門講述 SimpleParse 的前一篇文章之後,我將在本文中繼續介紹一些解析的基本概念,並對 Spark 模塊進行了討論。解析框架是一個內容豐富的主題,它值得我們多花時間去全面了解;這兩篇文章為讀者和我自己都開了一個好頭。 在日常的編程中,我經常需要標識存在於文本文檔中的部件和結構,這些文檔包括:日志文件、配置文件、定界的數據以及格式更自由的(但還是半結構化的)報表格式。所有這些文檔都擁有它們自己的“小語言”,用於規定什麼能夠出現在文檔內。我編寫這些非正式解析任務的程序的方法總是有點象大雜燴,其中包括定制狀態機、正則表達式以及上下文驅動的字符串測試。這些程序中的模式大概總是這樣:“讀一些文本,弄清是否可以用它來做些什麼,然後可能再多讀一些文本,一直嘗試下去。” 解析器將文檔中部件和結構的描述提煉成簡明、清晰和說明性的規則,確定由什麼組成文檔。大多數正式的解析器都使用擴展巴科斯范式(Extended Backus-Naur Form,EBNF)上的變體來描述它們所描述的語言的“語法”。基本上,EBNF 語法對您可能在文檔中找到的部件賦予名稱;另外,較大的部件通常由較小的部件組成。小部件在較大的部件中出現的頻率和順序由操作符指定。舉例來說,清單 1 是 EBNF 語法 typographify.def,我們在 SimpleParse 那篇文章中見到過這個語法(其它工具運行的方式稍有不同): 清單 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 簡介 Spark 解析器與 EBNF 語法有一些共同之處,但它將解析/處理過程分成了比傳統的 EBNF 語法所允許的更小的組件。Spark 的優點在於,它對整個過程中每一步操作的控制都進行了微調,還提供了將定制代碼插入到過程中的能力。您如果讀過本系列的 SimpleParse 那篇文章,您就會回想起我們的過程是比較粗略的:1)從語法(並從源文件)生成完整的標記列表,2)使用標記列表作為定制編程操作的數據。 Spark 與標准的基於 EBNF 的工具相比缺點在於,它比較冗長,而且缺少直接的出現計量符(即表示存在的“+”,表示可能性的“*”和表示有限制性的“?”)。計量符可以在 Spark 記號賦予器(tokenizer)的正則表達式中使用,並可以用解析表達式語法中的遞歸來進行模擬。如果 Spark 允許在語法表達式中使用計量,那就更好了。另一個值得一提的缺點是,Spark 的速度與 SimpleParse 使用的基於 C 的底層 mxTextTools 引擎相比遜色很多。 在“Compiling Little Languages in Python”(請參閱參考資料)中,Spark 的創始人 John Aycock 將編譯器分成了四個階段。本文討論的問題只涉及到前面兩個半階段,這歸咎於兩方面原因,一是由於文章長度的限制,二是因為我們將只討論前一篇文章提出的同樣的相對來說比較簡單的“文本標記”問題。Spark 還可以進一步用作完整周期的代碼編譯器/解釋器,而不是只用於我所描述的“解析並處理”的任務。讓我們來看看 Aycock 所說的四個階段(引用時有所刪節): 掃描,也稱詞法分析。將輸入流分成一列記號。 解析,也稱語法分析。確保記號列表在語法上是有效的。 語義分析。遍歷抽象語法樹(abstract syntax tree,AST)一次或多次,收集信息並檢查輸入程序 makes sense。 生成代碼。再次遍歷 AST,這個階段可能用 C 或匯編直接解釋程序或輸出代碼。 對每個階段,Spark 都提供了一個或多個抽象類以執行相應步驟,還提供了一個少見的協議,從而特化這些類。Spark 具體類並不象大多數繼承模式中的類那樣僅僅重新定義或添加特定的方法,而是具有兩種特性(一般的模式與各階段和各種父模式都一樣)。首先,具體類所完成的大部分工作都在方法的文檔字符串(docstring)中指定。第二個特殊的協議是,描述模式的方法集將被賦予表明其角色的獨特名稱。父類反過來包含查找實例的功能以進行操作的內省(introspective)方法。我們在參看示例的時侯會更清楚地認識到這一點。
識別文本標記 我已經用幾種其它的方法解決了這裡的問題。我將一種我稱之為“智能 ASCII”的格式用於各種目的。這種格式看起來很象為電子郵件和新聞組通信開發的那些協定。出於各種目的,我將這種格式自動地轉換為其它格式,如 Html、XML 和 LaTeX。我在這裡還要再這樣做一次。為了讓您直觀地理解我的意思,我將在本文中使用下面這個簡短的樣本: 清單 2. 智能 ASCII 樣本文本(p.txt) Text with *bold*, and -itals phrase-, and [module]--this should be a good 'practice run'. 除了樣本文件中的內容,還有另外一點內容是關於格式的,但不是很多(盡管的確有一些細微之處是關於標記與標點如何交互的)。
生成記號 我們的 Spark“智能 ASCII”解析器需要做的第一件事就是將輸入文本分成相關的部件。在記號賦予這一層,我們還不想討論如何構造記號,讓它們維持原樣就可以了。稍後我們會將記號序列組合成解析樹。 上面的 typographify.def 中所示的語法提供了 Spark 詞法分析程序/掃描程序的設計指南。請注意,我們只能使用那些在掃描程序階段為“原語”的名稱。也就是說,那些包括其它已命名的模式的(復合)模式在解析階段必須被延遲。除了這樣,我們其實還可以直接復制舊的語法。 清單 3. 刪節後的 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" (?<=[a-zA-Z])'(amclockdllmrestve) " self.rv.append(Token('contraction', s)) def t_mdash(self, s): r' -- ' self.rv.append(Token('mdash', s)) def t_wordpunct(self, s): ... 這裡有一個有趣的地方。WordScanner 本身是一個完美的掃描程序類;但 Spark 掃描程序類本身可以通過繼承進一步特化:子正則表達式模式在父正則表達式之前匹配,而如果需要,子方法/正則表達式可以覆蓋父方法/正則表達式。所以,WordPlusScanner 將在 WordScanner 之前對特化進行匹配(可能會因此先獲取一些字節)。模式文檔字符串中允許使用任何正則表達式(舉例來說,.t_contraction() 方法包含模式中的一個“向後插入”)。 不幸的是,Python 2.2 在一定程度上破壞了掃描程序繼承邏輯。在 Python 2.2 中,不管在繼承鏈中的什麼地方定義,所有定義過的模式都按字母順序(按名稱)進行匹配。要修正這個問題,您可以在 Spark 函數 _namelist() 中修改一行代碼: 清單 4. 糾正後相應的 spark.py 函數 def _namelist(instance): namelist, namedict, classlist = [], {}, [instance.__class__] for c in classlist: for b in c.__bases__: classlist.append(b) # for name in dir(c): # dir() behavior changed in 2.2 for name in c.__dict__.keys(): # <-- USE THIS if not namedict.has_key(name): namelist.append(name) namedict[name] = 1 return namelist 我已經向 Spark 創始人 John Aycock 通知了這個問題,今後的版本會修正這個問題。同時,請在您自己的副本中作出修改。 讓我們來看看