Python編寫的強大的、通用的解析器

Spark 是一種用 Python 編寫的強大的、通用的解析器／編譯器框架。在某些方面，Spark 所提供的比 SimpleParse 或其它 Python 解析器提供的都要多。然而，因為它完全是用 Python 編寫的，所以速度也會比較慢。David 在本文中討論了 Spark 模塊，給出了一些代
　　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])'(am|clock|d|ll|m|re|s|t|ve) "
　　　　　　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 通知了這個問題，今後的版本會修正這個問題。同時，請在您自己的副本中作出修改。
　　
　　讓我們來看看，WordPlusScanner 在應用到上面那個“智能 ASCII”樣本中後會發生什麼。它創建的列表其實是一個 Token 實例的列表，但它們包含一個 .__repr__ 方法，該方法能讓它們很好地顯示以下信息：
　　
　　清單 5. 用 WordPlusScanner 向“智能 ASCII”賦予記號
　　>>> from wordscanner import WordPlusScanner
　　>>> tokens = WordPlusScanner().tokenize(open('p.txt').read())
　　>>> filter(lambda s: s<>'whitespace', tokens)
　　[Text, with, *, bold, *, ,, and, -, itals, phrase, -, ,, and, [,
　　module, ], --, this, should, be, a, good, ', practice, run, ', .]
　　
　　值得注意的是盡管 .t_alphanums() 之類的方法會被 Spark 內省根據其前綴“t_”識別，它們還是正則方法。只要碰到相應的記號，方法內的任何額外代碼都將執行。.t_alphanums() 方法包含一個關於此點的很小的示例，其中包含一條 print 語句。
　　
　　生成抽象語法樹
　　查找記號的確有一點意思，但真正有意思的是如何向記號列表應用語法。解析階段在記號列表的基礎上創建任意的樹結構。它只是指定了表達式語法而已。
　　
　　Spark 有好幾種創建 AST 的方法。“手工”的方法是特化 GenericParser 類。在這種情況下，具體子解析器會提供很多方法，方法名的形式為 p_foobar(self, args)。每個這樣的方法的文檔字符串都包含一個或多個模式到名稱的分配。只要語法表達式匹配，每種方法就可以包含任何要執行的代碼。
　　
　　然而，Spark 還提供一種“自動”生成 AST 的方式。這種風格從 GenericASTBuilder 類繼承而來。所有語法表達式都在一個最高級的方法中列出，而 .terminal() 和 .nonterminal() 方法可以被特化為在生成期間操作子樹（如果需要，也可以執行任何其它操作）。結果還是 AST，但父類會為您執行大部分工作。我的語法類和如下所示的差不多：
　　
　　清單 6. 刪節後的 markupbuilder.py Spark 腳本
　　class MarkupBuilder(GenericASTBuilder):
　　　　"Write out HTML markup based on matched markup"
　　　　def p_para(self, args):
　　　　　　''
　　　　　　para　 ::= plain
　　　　　　para　 ::= markup
　　　　　　para　 ::= para plain
　　　　　　para　 ::= para emph
　　　　　　para　 ::= para strong
　　　　　　para　 ::= para module
　　　　　　para　 ::= para code
　　　　　　para　 ::= para title
　　　　　　plain　::= whitespace
　　　　　　plain　::= alphanums
　　　　　　plain　::= contraction
　　　　　　plain　::= safepunct
　　　　　　plain　::= mdash
　　　　　　plain　::= wordpunct
　　　　　　plain　::= plain plain
　　　　　　emph　 ::= dash plain dash
　　　　　　strong ::= asterisk plain asterisk
　　　　　　module ::= bracket plain bracket
　　　　　　code　 ::= apostrophe plain apostrophe
　　　　　　title　::= underscore plain underscore
　　　　　　''
　　　　def nonterminal(self, type_, args):
　　　　　　#　Flatten AST a bit by not making nodes if only one child.
　　　　　　if len(args)==1:　return args[0]
　　　　　　if type_=='para': return nonterminal(self, type_, args)
　　　　　　if type_=='plain':
　　　　　　　　args[0].attr = foldtree(args[0])+foldtree(args[1])
　　　　　　　　args[0].type = type_
　　　　　　　　return nonterminal(self, type_, args[:1])
　　　　　　phrase_node = AST(type_)
　　　　　　phrase_node.attr = foldtree(args[1])
　　　　　　return phrase_node
　　　　　　
　　我的 .p_para() 在其文檔字符串中應該只包含一組語法規則（沒有代碼）。我決定專門用 .nonterminal() 方法來稍微對 AST 進行平鋪。由一系列“plain”子樹組成的“plain”節點將子樹壓縮為一個更長的字符串。同樣，標記子樹（即“emph”、“strong”、“module”、“code”和“title”）折疊為一個類型正確的單獨節點，並包含一個復合字符串。
　　
　　我們已經提到過，Spark 語法中顯然缺少一樣東西：沒有計量符。通過下面這樣的規則，
　　
　　plain ::= plain plain
　　
　　我們可以成對地聚集“plain“類型的子樹。不過我更傾向於讓 Spark 允許使用更類似於 EBNF 風格的語法表達式，如下所示：
　　
　　plain ::= plain+
　　
　　然後，我們就可以更簡單地創建“plain 盡可能多”的 n-ary 子樹了。既然這樣，我們的樹就更容易啟動列，甚至不用在 .nonterminal() 中傳送消息。
　　
　　使用樹
　　Spark 模塊提供了幾個使用 AST 的類。比起我的目的來說，這些責任比我需要的更大。如果您希望得到它們，GenericASTTraversal 和 GenericASTMatcher 提供了遍歷樹的方法，使用的繼承協議類似於我們為掃描程序和解析器所提供的。
　　
　　但是只用遞歸函數來遍歷樹並不十分困難。我在文章的壓縮文件 prettyprint.py（請參閱參考資料）中創建了一些這樣的示例。其中的一個是 showtree()。該函數將顯示一個帶有幾個約定的 AST。
　　
　　每行都顯示下降深度
　　只有子節點（沒有內容）的節點開頭有破折號
　　節點類型用雙層尖括號括起
　　讓我們來看看上面示例中生成的 AST：
　　
　　清單 7. 用 WordPlusScanner 向“智能 ASCII”賦予記號
　　>>> from wordscanner import tokensFromFname
　　>>> from markupbuilder import treeFromTokens
　　>>> from prettyprint import showtree
　　>>> showtree(treeFromTokens(tokensFromFname('p.txt')))
　　 0　<<para>>
　　 1 - <<para>>
　　 2 -- <<para>>
　　 3 --- <<para>>
　　 4 ---- <<para>>
　　 5 ----- <<para>>
　　 6 ------ <<para>>
　　 7 ------- <<para>>
　　 8 -------- <<plain>>
　　 9　　　　　 <<plain>>　Text with
　　 8　　　　　<<strong>> bold
　　 7 ------- <<plain>>
　　 8　　　　　<<plain>> , and
　　 6　　　　<<emph>> itals phrase
　　 5 ----- <<plain>>
　　 6　　　　<<plain>> , and
　　 4　　　<<module>> module
　　 3 --- <<plain>>
　　 4　　　<<plain>> --this should be a good
　　 2　　<<code>> practice run
　　 1 - <<plain>>
　　 2　　<<plain>> .
　　　
　　理解樹結構很直觀，但我們真正要尋找的修改過的標記怎麼辦呢？幸運的是，只需要幾行代碼就可以遍歷樹並生成它：
　　
　　清單 8. 從 AST（prettyprint.py）輸出標記
　　def emitHTML(node):
　　　　from typo_html import codes
　　　　if hasattr(node, 'attr'):
　　　　　　beg, end = codes[node.type]
　　　　　　sys.stdout.write(beg+node.attr+end)
　　　　else: map(emitHTML, node._kids)
　　
　　typo_html.py 文件與 SimpleParse 那篇文章中的一樣 — 它只是包含一個將名稱映射到開始標記／結束標記對的字典。顯然，我們可以為標記使用除 HTML 之外的相同方法。如果您不清楚，下面是我們的示例將生成的內容：
　　
　　清單 9. 整個過程的 HTML 輸出
　　Text with <strong>bold</strong>, and <em>itals phrase</em>,
　　and <em><code>module</code></em>--this should be a good
　　<code>practice run</code>.
　　
　　結束語
　　很多 Python 程序員都向我推薦 Spark。雖然 Spark 使用的少見的協定讓人不太容易習慣，而且文檔從某些角度來看可能比較含混不清，但 Spark 的力量還是非常令人驚奇。Spark 實現的編程風格使最終程序員能夠在掃描／解析過程中在任何地方插入代碼塊 — 這對最終用戶來說通常是“黑箱”。
　　
　　比起它的所有優點來說，我發現 Spark 真正的缺點是它的速度。Spark 是我使用過的第一個 Python 程序，而我在使用中發現，解釋語言的速度損失是其主要問題。Spark 的速度的確很慢；慢的程度不止是“我希望能快一點點”，而是“吃了一頓長時間的午餐還希望它能快點結束”的程度。在我的實驗中，記號賦予器還比較快，但解析過程就很慢了，即便用很小的測試案例也很慢。公平地講，John Aycock 已經向我指出，Spark 使用的 Earley 解析算法比更簡單的 LR 算法全面得多，這是它速度慢的主要原因。還有可能的是，由於我經驗不足，可能設計出低效的語法；不過就算是這樣，大部分用戶也很可能會象我一樣。