Python中用Spark模块的使用教程
在日常的编程中，我经常需要标识存在于文本文档中的部件和结构，这些文档包括：日志文件、配置文件、定界的数据以及格式更自由的（但还是半结构化的）报表格式。所有这些文档都拥有它们自己的“小语言”，用于规定什么能够出现在文档内。我编写这些非正式解析任务的程序的方法总是有点象大杂烩，其中包括定制状态机、正则表达式以及上下文驱动的字符串测试。这些程序中的模式大概总是这样：“读一些文本，弄清是否可以用它来做些什么，然后可能再多读一些文本，一直尝试下去。”
解析器将文档中部件和结构的描述提炼成简明、清晰和说明性的规则，确定由什么组成文档。大多数正式的解析器都使用扩展巴科斯范式（ExtendedBackus-NaurForm，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?
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引擎相比逊色很多。
在“CompilingLittleLanguagesinPython”（请参阅参考资料）中，Spark的创始人JohnAycock将编译器分成了四个阶段。本文讨论的问题只涉及到前面两个半阶段，这归咎于两方面原因，一是由于文章长度的限制，二是因为我们将只讨论前一篇文章提出的同样的相对来说比较简单的“文本标记”问题。Spark还可以进一步用作完整周期的代码编译器／解释器，而不是只用于我所描述的“解析并处理”的任务。让我们来看看Aycock所说的四个阶段（引用时有所删节）：
- 扫描，也称词法分析。将输入流分成一列记号。
- 解析，也称语法分析。确保记号列表在语法上是有效的。
- 语义分析。遍历抽象语法树（abstractsyntaxtree，AST）一次或多次，收集信息并检查输入程序makessense。
- 生成代码。再次遍历AST，这个阶段可能用C或汇编直接解释程序或输出代码。
对每个阶段，Spark都提供了一个或多个抽象类以执行相应步骤，还提供了一个少见的协议，从而特化这些类。Spark具体类并不象大多数继承模式中的类那样仅仅重新定义或添加特定的方法，而是具有两种特性（一般的模式与各阶段和各种父模式都一样）。首先，具体类所完成的大部分工作都在方法的文档字符串（docstring）中指定。第二个特殊的协议是，描述模式的方法集将被赋予表明其角色的独特名称。父类反过来包含查找实例的功能以进行操作的内省（introspective）方法。我们在参看示例的时侯会更清楚地认识到这一点。
识别文本标记
我已经用几种其它的方法解决了这里的问题。我将一种我称之为“智能ASCII”的格式用于各种目的。这种格式看起来很象为电子邮件和新闻组通信开发的那些协定。出于各种目的，我将这种格式自动地转换为其它格式，如HTML、XML和LaTeX。我在这里还要再这样做一次。为了让您直观地理解我的意思，我将在本文中使用下面这个简短的样本：
清单2.智能ASCII样本文本（p.txt）
Textwith*bold*,and-italsphrase-,and[module]--this shouldbeagood'practicerun'.
除了样本文件中的内容，还有另外一点内容是关于格式的，但不是很多（尽管的确有一些细微之处是关于标记与标点如何交互的）。
生成记号
我们的Spark“智能ASCII”解析器需要做的第一件事就是将输入文本分成相关的部件。在记号赋予这一层，我们还不想讨论如何构造记号，让它们维持原样就可以了。稍后我们会将记号序列组合成解析树。
上面的typographify.def中所示的语法提供了Spark词法分析程序／扫描程序的设计指南。请注意，我们只能使用那些在扫描程序阶段为“原语”的名称。也就是说，那些包括其它已命名的模式的（复合）模式在解析阶段必须被延迟。除了这样，我们其实还可以直接复制旧的语法。
清单3.删节后的wordscanner.pySpark脚本
classWordScanner(GenericScanner):
"Tokenizewords,punctuationandmarkup"
deftokenize(self,input):
self.rv=[]
GenericScanner.tokenize(self,input)
returnself.rv
deft_whitespace(self,s):
r"[\t\r\n]+"
self.rv.append(Token('whitespace',''))
deft_alphanums(self,s):
r"[a-zA-Z0-9]+"
print"{word}",
self.rv.append(Token('alphanums',s))
deft_safepunct(self,s):...
deft_bracket(self,s):...
deft_asterisk(self,s):...
deft_underscore(self,s):...
deft_apostrophe(self,s):...
deft_dash(self,s):...
classWordPlusScanner(WordScanner):
"Enhanceword/markuptokenization"
deft_contraction(self,s):
r"(?<=[a-zA-Z])'(am|clock|d|ll|m|re|s|t|ve)"
self.rv.append(Token('contraction',s))
deft_mdash(self,s):
r'--'
self.rv.append(Token('mdash',s))
deft_wordpunct(self,s):...
这里有一个有趣的地方。WordScanner本身是一个完美的扫描程序类；但Spark扫描程序类本身可以通过继承进一步特化：子正则表达式模式在父正则表达式之前匹配，而如果需要，子方法／正则表达式可以覆盖父方法／正则表达式。所以，WordPlusScanner将在WordScanner之前对特化进行匹配（可能会因此先获取一些字节）。模式文档字符串中允许使用任何正则表达式（举例来说，.t_contraction()方法包含模式中的一个“向后插入”）。
不幸的是，Python2.2在一定程度上破坏了扫描程序继承逻辑。在Python2.2中，不管在继承链中的什么地方定义，所有定义过的模式都按字母顺序（按名称）进行匹配。要修正这个问题，您可以在Spark函数_namelist()中修改一行代码：
清单4.纠正后相应的spark.py函数
def_namelist(instance):
namelist,namedict,classlist=[],{},[instance.__class__]
forcinclasslist:
forbinc.__bases__:
classlist.append(b)
#fornameindir(c):#dir()behaviorchangedin2.2
fornameinc.__dict__.keys():#<--USETHIS
ifnotnamedict.has_key(name):
namelist.append(name)
namedict[name]=1
returnnamelist
我已经向Spark创始人JohnAycock通知了这个问题，今后的版本会修正这个问题。同时，请在您自己的副本中作出修改。
让我们来看看，WordPlusScanner在应用到上面那个“智能ASCII”样本中后会发生什么。它创建的列表其实是一个Token实例的列表，但它们包含一个.__repr__方法，该方法能让它们很好地显示以下信息：
清单5.用WordPlusScanner向“智能ASCII”赋予记号
>>>fromwordscannerimportWordPlusScanner
>>>tokens=WordPlusScanner().tokenize(open('p.txt').read())
>>>filter(lambdas: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.pySpark脚本
classMarkupBuilder(GenericASTBuilder): "WriteoutHTMLmarkupbasedonmatchedmarkup" defp_para(self,args): ''' para::=plain para::=markup para::=paraplain para::=paraemph para::=parastrong para::=paramodule para::=paracode para::=paratitle plain::=whitespace plain::=alphanums plain::=contraction plain::=safepunct plain::=mdash plain::=wordpunct plain::=plainplain emph::=dashplaindash strong::=asteriskplainasterisk module::=bracketplainbracket code::=apostropheplainapostrophe title::=underscoreplainunderscore ''' defnonterminal(self,type_,args): #FlattenASTabitbynotmakingnodesifonlyonechild. iflen(args)==1:returnargs[0] iftype_=='para':returnnonterminal(self,type_,args) iftype_=='plain': args[0].attr=foldtree(args[0])+foldtree(args[1]) args[0].type=type_ returnnonterminal(self,type_,args[:1]) phrase_node=AST(type_) phrase_node.attr=foldtree(args[1]) returnphrase_node
我的.p_para()在其文档字符串中应该只包含一组语法规则（没有代码）。我决定专门用.nonterminal()方法来稍微对AST进行平铺。由一系列“plain”子树组成的“plain”节点将子树压缩为一个更长的字符串。同样，标记子树（即“emph”、“strong”、“module”、“code”和“title”）折叠为一个类型正确的单独节点，并包含一个复合字符串。
我们已经提到过，Spark语法中显然缺少一样东西：没有计量符。通过下面这样的规则，
plain::=plainplain
我们可以成对地聚集“plain“类型的子树。不过我更倾向于让Spark允许使用更类似于EBNF风格的语法表达式，如下所示：
plain::=plain+
然后，我们就可以更简单地创建“plain尽可能多”的n-ary子树了。既然这样，我们的树就更容易启动列，甚至不用在.nonterminal()中传送消息。
使用树
Spark模块提供了几个使用AST的类。比起我的目的来说，这些责任比我需要的更大。如果您希望得到它们，GenericASTTraversal和GenericASTMatcher提供了遍历树的方法，使用的继承协议类似于我们为扫描程序和解析器所提供的。
但是只用递归函数来遍历树并不十分困难。我在文章的压缩文件prettyprint.py（请参阅参考资料）中创建了一些这样的示例。其中的一个是showtree()。该函数将显示一个带有几个约定的AST。
- 每行都显示下降深度
- 只有子节点（没有内容）的节点开头有破折号
- 节点类型用双层尖括号括起
让我们来看看上面示例中生成的AST：
清单7.用WordPlusScanner向“智能ASCII”赋予记号
>>>fromwordscannerimporttokensFromFname
>>>frommarkupbuilderimporttreeFromTokens
>>>fromprettyprintimportshowtree
>>>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>>Textwith
8<<strong>>bold
7-------<<plain>>
8<<plain>>,and
6<<emph>>italsphrase
5-----<<plain>>
6<<plain>>,and
4<<module>>module
3---<<plain>>
4<<plain>>--thisshouldbeagood
2<<code>>practicerun
1-<<plain>>
2<<plain>>.
理解树结构很直观，但我们真正要寻找的修改过的标记怎么办呢？幸运的是，只需要几行代码就可以遍历树并生成它：
清单8.从AST（prettyprint.py）输出标记
defemitHTML(node): fromtypo_htmlimportcodes ifhasattr(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输出
Textwith<strong>bold</strong>,and<em>italsphrase</em>,
and<em><code>module</code></em>--thisshouldbeagood
<code>practicerun</code>.
结束语
很多Python程序员都向我推荐Spark。虽然Spark使用的少见的协定让人不太容易习惯，而且文档从某些角度来看可能比较含混不清，但Spark的力量还是非常令人惊奇。Spark实现的编程风格使最终程序员能够在扫描／解析过程中在任何地方插入代码块—这对最终用户来说通常是“黑箱”。
比起它的所有优点来说，我发现Spark真正的缺点是它的速度。Spark是我使用过的第一个Python程序，而我在使用中发现，解释语言的速度损失是其主要问题。Spark的速度的确很慢；慢的程度不止是“我希望能快一点点”，而是“吃了一顿长时间的午餐还希望它能快点结束”的程度。在我的实验中，记号赋予器还比较快，但解析过程就很慢了，即便用很小的测试案例也很慢。公平地讲，JohnAycock已经向我指出，Spark使用的Earley解析算法比更简单的LR算法全面得多，这是它速度慢的主要原因。还有可能的是，由于我经验不足，可能设计出低效的语法；不过就算是这样，大部分用户也很可能会象我一样。