在日常的编程中，我经常需要标识存在于文本文档中的部件和结构，这些文档包括：日志文件、配置文件、定界的数据以及格式更自由的（但还是半结构化的）报表格式。所有这些文档都拥有它们自己的“小语言”，用于规定什么能够出现在文档内。我编写这些非正式解析任务的程序的方法总是有点象大杂烩，其中包括定制状态机、正则表达式以及上下文驱动的字符串测试。这些程序中的模式大概总是这样：“读一些文本，弄清是否可以用它来做些什么，然后可能再多读一些文本，一直尝试下去。”

解析器将文档中部件和结构的描述提炼成简明、清晰和 说明性的规则，确定由什么组成文档。大多数正式的解析器都使用扩展巴科斯范式（Extended Backus-Naur Form，EBNF）上的变体来描述它们所描述的语言的“语法”。基本上，EBNF 语法对您可能在文档中找到的 部件赋予名称；另外，较大的部件通常由较小的部件组成。小部件在较大的部件中出现的频率和顺序由操作符指定。举例来说，清单 1 是 EBNF 语法 typographify.def，我们在 SimpleParse 那篇文章中见到过这个语法（其它工具运行的方式稍有不同）：

清单 1. typographify.def

para    := (plain / markup)+
plain    := (word / whitespace / punctuation)+
whitespace := [ \t\r\n]+
alphanums  := [a-zA-Z0-9]+
word    := alphanums, (wordpunct, alphanums)*, 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 的工具相比缺点在于，它比较冗长，而且缺少直接的出现计量符（即表示存在的“+”，表示可能性的“*”和表示有限制性的“"codetitle">复制代码 代码如下: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" [ \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" ("
    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 算法全面得多，这是它速度慢的主要原因。还有可能的是，由于我经验不足，可能设计出低效的语法；不过就算是这样，大部分用户也很可能会象我一样。