在日常的編程中，我經(jīng)常需要標(biāo)識(shí)存在于文本文檔中的部件和結(jié)構(gòu)，這些文檔包括：日志文件、配置文件、定界的數(shù)據(jù)以及格式更自由的（但還是半結(jié)構(gòu)化的）報(bào)表格式。所有這些文檔都擁有它們自己的“小語(yǔ)言”，用于規(guī)定什么能夠出現(xiàn)在文檔內(nèi)。我編寫(xiě)這些非正式解析任務(wù)的程序的方法總是有點(diǎn)象大雜燴，其中包括定制狀態(tài)機(jī)、正則表達(dá)式以及上下文驅(qū)動(dòng)的字符串測(cè)試。這些程序中的模式大概總是這樣：“讀一些文本，弄清是否可以用它來(lái)做些什么，然后可能再多讀一些文本，一直嘗試下去?！?/p>

解析器將文檔中部件和結(jié)構(gòu)的描述提煉成簡(jiǎn)明、清晰和 說(shuō)明性的規(guī)則，確定由什么組成文檔。大多數(shù)正式的解析器都使用擴(kuò)展巴科斯范式（Extended Backus-Naur Form，EBNF）上的變體來(lái)描述它們所描述的語(yǔ)言的“語(yǔ)法”?；旧?，EBNF 語(yǔ)法對(duì)您可能在文檔中找到的 部件賦予名稱(chēng)；另外，較大的部件通常由較小的部件組成。小部件在較大的部件中出現(xiàn)的頻率和順序由操作符指定。舉例來(lái)說(shuō)，清單 1 是 EBNF 語(yǔ)法 typographify.def，我們?cè)?SimpleParse 那篇文章中見(jiàn)到過(guò)這個(gè)語(yǔ)法（其它工具運(yùn)行的方式稍有不同）：

清單 1. typographify.def

para    := (plain / markup)+
plain    := (word / whitespace / punctuation)+
whitespace := [ \t\r\n]+
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ǔ)法有一些共同之處，但它將解析／處理過(guò)程分成了比傳統(tǒng)的 EBNF 語(yǔ)法所允許的更小的組件。Spark 的優(yōu)點(diǎn)在于，它對(duì)整個(gè)過(guò)程中每一步操作的控制都進(jìn)行了微調(diào)，還提供了將定制代碼插入到過(guò)程中的能力。您如果讀過(guò)本系列的 SimpleParse 那篇文章，您就會(huì)回想起我們的過(guò)程是比較粗略的：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è)階段。本文討論的問(wèn)題只涉及到前面兩個(gè)半階段，這歸咎于兩方面原因，一是由于文章長(zhǎng)度的限制，二是因?yàn)槲覀儗⒅挥懻撉耙黄恼绿岢龅耐瑯拥南鄬?duì)來(lái)說(shuō)比較簡(jiǎn)單的“文本標(biāo)記”問(wèn)題。Spark 還可以進(jìn)一步用作完整周期的代碼編譯器／解釋器，而不是只用于我所描述的“解析并處理”的任務(wù)。讓我們來(lái)看看 Aycock 所說(shuō)的四個(gè)階段（引用時(shí)有所刪節(jié)）：

•     掃描，也稱(chēng)詞法分析。將輸入流分成一列記號(hào)。
•     解析，也稱(chēng)語(yǔ)法分析。確保記號(hào)列表在語(yǔ)法上是有效的。
•     語(yǔ)義分析。遍歷抽象語(yǔ)法樹(shù)（abstract syntax tree，AST）一次或多次，收集信息并檢查輸入程序 makes sense。
•     生成代碼。再次遍歷 AST，這個(gè)階段可能用 C 或匯編直接解釋程序或輸出代碼。

對(duì)每個(gè)階段，Spark 都提供了一個(gè)或多個(gè)抽象類(lèi)以執(zhí)行相應(yīng)步驟，還提供了一個(gè)少見(jiàn)的協(xié)議，從而特化這些類(lèi)。Spark 具體類(lèi)并不象大多數(shù)繼承模式中的類(lèi)那樣僅僅重新定義或添加特定的方法，而是具有兩種特性（一般的模式與各階段和各種父模式都一樣）。首先，具體類(lèi)所完成的大部分工作都在方法的文檔字符串（docstring）中指定。第二個(gè)特殊的協(xié)議是，描述模式的方法集將被賦予表明其角色的獨(dú)特名稱(chēng)。父類(lèi)反過(guò)來(lái)包含查找實(shí)例的功能以進(jìn)行操作的內(nèi)?。╥ntrospective）方法。我們?cè)趨⒖词纠臅r(shí)侯會(huì)更清楚地認(rèn)識(shí)到這一點(diǎn)。

識(shí)別文本標(biāo)記

我已經(jīng)用幾種其它的方法解決了這里的問(wèn)題。我將一種我稱(chēng)之為“智能 ASCII”的格式用于各種目的。這種格式看起來(lái)很象為電子郵件和新聞組通信開(kāi)發(fā)的那些協(xié)定。出于各種目的，我將這種格式自動(dòng)地轉(zhuǎn)換為其它格式，如 HTML、XML 和 LaTeX。我在這里還要再這樣做一次。為了讓您直觀(guān)地理解我的意思，我將在本文中使用下面這個(gè)簡(jiǎn)短的樣本：

清單 2. 智能 ASCII 樣本文本（p.txt）

除了樣本文件中的內(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)序列組合成解析樹(shù)。

上面的 typographify.def 中所示的語(yǔ)法提供了 Spark 詞法分析程序／掃描程序的設(shè)計(jì)指南。請(qǐng)注意，我們只能使用那些在掃描程序階段為“原語(yǔ)”的名稱(chēng)。也就是說(shuō)，那些包括其它已命名的模式的（復(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" [ \t\r\n]+ "
    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): ...

這里有一個(gè)有趣的地方。WordScanner 本身是一個(gè)完美的掃描程序類(lèi)；但 Spark 掃描程序類(lèi)本身可以通過(guò)繼承進(jìn)一步特化：子正則表達(dá)式模式在父正則表達(dá)式之前匹配，而如果需要，子方法／正則表達(dá)式可以覆蓋父方法／正則表達(dá)式。所以，WordPlusScanner 將在 WordScanner 之前對(duì)特化進(jìn)行匹配（可能會(huì)因此先獲取一些字節(jié)）。模式文檔字符串中允許使用任何正則表達(dá)式（舉例來(lái)說(shuō)， .t_contraction() 方法包含模式中的一個(gè)“向后插入”）。

不幸的是，Python 2.2 在一定程度上破壞了掃描程序繼承邏輯。在 Python 2.2 中，不管在繼承鏈中的什么地方定義，所有定義過(guò)的模式都按字母順序（按名稱(chēng)）進(jìn)行匹配。要修正這個(gè)問(wèn)題，您可以在 Spark 函數(shù) _namelist() 中修改一行代碼：

清單 4. 糾正后相應(yīng)的 spark.py 函數(shù)

  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

我已經(jīng)向 Spark 創(chuàng)始人 John Aycock 通知了這個(gè)問(wèn)題，今后的版本會(huì)修正這個(gè)問(wèn)題。同時(shí)，請(qǐng)?jiān)谀约旱母北局凶鞒鲂薷摹?/p>

讓我們來(lái)看看，WordPlusScanner 在應(yīng)用到上面那個(gè)“智能 ASCII”樣本中后會(huì)發(fā)生什么。它創(chuàng)建的列表其實(shí)是一個(gè) Token 實(shí)例的列表，但它們包含一個(gè) .__repr__ 方法，該方法能讓它們很好地顯示以下信息：

清單 5. 用 WordPlusScanner 向“智能 ASCII”賦予記號(hào)

>>> 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() 之類(lèi)的方法會(huì)被 Spark 內(nèi)省根據(jù)其前綴“t_”識(shí)別，它們還是正則方法。只要碰到相應(yīng)的記號(hào)，方法內(nèi)的任何額外代碼都將執(zhí)行。 .t_alphanums() 方法包含一個(gè)關(guān)于此點(diǎn)的很小的示例，其中包含一條 print 語(yǔ)句。

生成抽象語(yǔ)法樹(shù)

查找記號(hào)的確有一點(diǎn)意思，但真正有意思的是如何向記號(hào)列表應(yīng)用語(yǔ)法。解析階段在記號(hào)列表的基礎(chǔ)上創(chuàng)建任意的樹(shù)結(jié)構(gòu)。它只是指定了表達(dá)式語(yǔ)法而已。

Spark 有好幾種創(chuàng)建 AST 的方法?！笆止ぁ钡姆椒ㄊ翘鼗?GenericParser 類(lèi)。在這種情況下，具體子解析器會(huì)提供很多方法，方法名的形式為 p_foobar(self, args) 。每個(gè)這樣的方法的文檔字符串都包含一個(gè)或多個(gè)模式到名稱(chēng)的分配。只要語(yǔ)法表達(dá)式匹配，每種方法就可以包含任何要執(zhí)行的代碼。

然而，Spark 還提供一種“自動(dòng)”生成 AST 的方式。這種風(fēng)格從 GenericASTBuilder 類(lèi)繼承而來(lái)。所有語(yǔ)法表達(dá)式都在一個(gè)最高級(jí)的方法中列出，而 .terminal() 和 .nonterminal() 方法可以被特化為在生成期間操作子樹(shù)（如果需要，也可以執(zhí)行任何其它操作）。結(jié)果還是 AST，但父類(lèi)會(huì)為您執(zhí)行大部分工作。我的語(yǔ)法類(lèi)和如下所示的差不多：

清單 6. 刪節(jié)后的 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() 在其文檔字符串中應(yīng)該只包含一組語(yǔ)法規(guī)則（沒(méi)有代碼）。我決定專(zhuān)門(mén)用 .nonterminal() 方法來(lái)稍微對(duì) AST 進(jìn)行平鋪。由一系列“plain”子樹(shù)組成的“plain”節(jié)點(diǎn)將子樹(shù)壓縮為一個(gè)更長(zhǎng)的字符串。同樣，標(biāo)記子樹(shù)（即“emph”、“strong”、“module”、“code”和“title”）折疊為一個(gè)類(lèi)型正確的單獨(dú)節(jié)點(diǎn)，并包含一個(gè)復(fù)合字符串。

我們已經(jīng)提到過(guò)，Spark 語(yǔ)法中顯然缺少一樣?xùn)|西：沒(méi)有計(jì)量符。通過(guò)下面這樣的規(guī)則，

plain ::= plain plain

我們可以成對(duì)地聚集“plain“類(lèi)型的子樹(shù)。不過(guò)我更傾向于讓 Spark 允許使用更類(lèi)似于 EBNF 風(fēng)格的語(yǔ)法表達(dá)式，如下所示：

plain ::= plain+

然后，我們就可以更簡(jiǎn)單地創(chuàng)建“plain 盡可能多”的 n-ary 子樹(shù)了。既然這樣，我們的樹(shù)就更容易啟動(dòng)列，甚至不用在 .nonterminal() 中傳送消息。

使用樹(shù)

Spark 模塊提供了幾個(gè)使用 AST 的類(lèi)。比起我的目的來(lái)說(shuō)，這些責(zé)任比我需要的更大。如果您希望得到它們，GenericASTTraversal 和 GenericASTMatcher 提供了遍歷樹(shù)的方法，使用的繼承協(xié)議類(lèi)似于我們?yōu)閽呙璩绦蚝徒馕銎魉峁┑摹?/p>

但是只用遞歸函數(shù)來(lái)遍歷樹(shù)并不十分困難。我在文章的壓縮文件 prettyprint.py （請(qǐng)參閱 參考資料）中創(chuàng)建了一些這樣的示例。其中的一個(gè)是 showtree() 。該函數(shù)將顯示一個(gè)帶有幾個(gè)約定的 AST。

•     每行都顯示下降深度
•     只有子節(jié)點(diǎn)（沒(méi)有內(nèi)容）的節(jié)點(diǎn)開(kāi)頭有破折號(hào)
•     節(jié)點(diǎn)類(lèi)型用雙層尖括號(hào)括起

讓我們來(lái)看看上面示例中生成的 AST：

清單 7. 用 WordPlusScanner 向“智能 ASCII”賦予記號(hào)

 >>> 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>> .

理解樹(shù)結(jié)構(gòu)很直觀(guān)，但我們真正要尋找的修改過(guò)的標(biāo)記怎么辦呢？幸運(yùn)的是，只需要幾行代碼就可以遍歷樹(shù)并生成它：

清單 8. 從 AST（prettyprint.py）輸出標(biāo)記

  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 那篇文章中的一樣 — 它只是包含一個(gè)將名稱(chēng)映射到開(kāi)始標(biāo)記／結(jié)束標(biāo)記對(duì)的字典。顯然，我們可以為標(biāo)記使用除 HTML 之外的相同方法。如果您不清楚，下面是我們的示例將生成的內(nèi)容：

清單 9. 整個(gè)過(guò)程的 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>.

結(jié)束語(yǔ)

很多 Python 程序員都向我推薦 Spark。雖然 Spark 使用的少見(jiàn)的協(xié)定讓人不太容易習(xí)慣，而且文檔從某些角度來(lái)看可能比較含混不清，但 Spark 的力量還是非常令人驚奇。Spark 實(shí)現(xiàn)的編程風(fēng)格使最終程序員能夠在掃描／解析過(guò)程中在任何地方插入代碼塊 — 這對(duì)最終用戶(hù)來(lái)說(shuō)通常是“黑箱”。

比起它的所有優(yōu)點(diǎn)來(lái)說(shuō)，我發(fā)現(xiàn) Spark 真正的缺點(diǎn)是它的速度。Spark 是我使用過(guò)的第一個(gè) Python 程序，而我在使用中發(fā)現(xiàn)，解釋語(yǔ)言的速度損失是其主要問(wèn)題。Spark 的速度的確 很慢；慢的程度不止是“我希望能快一點(diǎn)點(diǎn)”，而是“吃了一頓長(zhǎng)時(shí)間的午餐還希望它能快點(diǎn)結(jié)束”的程度。在我的實(shí)驗(yàn)中，記號(hào)賦予器還比較快，但解析過(guò)程就很慢了，即便用很小的測(cè)試案例也很慢。公平地講，John Aycock 已經(jīng)向我指出，Spark 使用的 Earley 解析算法比更簡(jiǎn)單的 LR 算法全面得多，這是它速度慢的主要原因。還有可能的是，由于我經(jīng)驗(yàn)不足，可能設(shè)計(jì)出低效的語(yǔ)法；不過(guò)就算是這樣，大部分用戶(hù)也很可能會(huì)象我一樣。

最新評(píng)論