Python编写的强大的、通用的解析器
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 通知了这个问题，今后的版本会修正这个问题。同时，请在您自己的副本中作出修改。
让我们来看看
