可爱的 Python: 了解 DParser for Python

文档选项 未显示需要 JavaScript 的文档选项

级别： 初级

David Mertz, Ph.D. (mertz@gnosis.cx), 开发者, Gnosis Software, Inc.

2004 年 8 月 23 日

首先初步了解 DParser 这一由 J. Plevyak 编写的简单而强大的解析工具。然后了解用于 Python 的DParser，它为 Python 程序员提供了一个访问 DParser 的无缝接口，并看看它与上一期中介绍的解析器的比较。语法规则以类似于 Spark 或 PLY 的方式通过 Python 函数文档字符串加入到 DParser 中。

有很多可用的 Python 解析器程序库。我已经在本专栏中讨论过 mx.TextTools、SimpleParse 和 SPARK， 并在我的书中介绍了 PLY（请参阅 参考资料，获得这些文档的链接）。 无需考虑，我也知道有 PyGgy、Yapps、PLEX、PyLR、PyParsing 和 TPG，而且我还模糊地记得读过半打其他 解析器的声明。用户可能会对此门类感到失落，不是因为缺少高质量程序库，而是太多了。

DParser 与所有其他解析器的不同之处是什么？是这样，类似于 PLY 和 Spark， 用于 Python 的 DParser 使用函数文档字符串 来表示其结果（productions）。这种风格使得您可以将动作代码直接插入到一个结果中， 以处理当一个特定的语法规则得到满足时将发生的事件。与 PLY 或 Spark 相反，DParser 本身 是用 C 编写的，因而可能会比纯粹的 Python 解析器快得多。用于 Python 的 DParser 是底层的 C 程序库之外的一个非常精简的包装器（wrapper） —— 对 Python 的回调需要一些额外的时间，但是基本的解析 是以 C 语言的速度来进行的。不过，就本文而言，我没有尝试进行任何具体的基准测试。所以，相对 于其他解析器来说，DParser 到底有多快或多慢不是我所能直接评论的。

就我自己而言，我仍是非常喜欢 SimpleParse 的方法。SimpleParse 是快速的 mx.TextTools 程序库（也是用 C 所编写的）的一个包装器，可以将 EBNF 语法语言从 Python 代码中完全分离 出来。一般来说，使用 SimpleParse 就意味着在一个函数调用中生成一个解析树，然后在分开的 代码中遍历这个树。对于特别大的被解析的文档来说，这种两步方法可能是低效的，但是我发现 这样更容易理解编写的代码。

尽管如此，还是有很多读者推荐说用于 Python DParaser 值得关注，虽然我更喜欢单独的 EBNF 定义。 顺便提一句，如您将在示例中所看到的，DParser 不使用任何单独的标记传递，而只是直接解析。您可以 通过定义保留的 d_whitespace() 函数来控制空格的识别（它分离解析符号）； 这样就使得您可以随意使用标记。

找到最长的结果

作为用于 Python 的 DParser 程序的第一个示例，我创建了一个查找几个模式的语法，这些模式依次为另一个的 子结果。这个语法处理的问题类似于很多解析器遇到的“dangling else”问题。具体说，也就是您如何才能知道什么时候 停止查找更长的结果？（例如，“if”后是否跟有“else”？）我的语法会去分析的短语可能按次序包括有以“a”、“b”和“c” 结尾的单词。所有没有被包括进来的单词只是短语的“head”或“tail”的部分。这需要一些例子来展示。首先， 程序本身：

#!/usr/bin/env python2.3
"Identify sequence of a-, b-, c- words"
#
#-- The grammar
def d_phrase(t, s):
    'phrase : words ( ABC | AB | A ) words'
    print "Head:", ''.join(s[0])
    print t[1][0]+":", ''.join(s[1])
    print "Tail:", ''.join(s[2])
def d_words(t):
    'words : word*'
def d_word(t):
    'word : "[a-z]+" '
def d_A(t):
    '''A : "a[a-z]*" '''
    return 'A'
def d_AB(t):
    '''AB : A "b[a-z]*" '''
    return 'AB'
def d_ABC(t):
    '''ABC : AB "c[a-z]*" '''
    return 'ABC'
#
#-- Parse STDIN
from dparser import Parser
from sys import argv, stdin
phrase, arg = stdin.read(), argv[-1]
Parser().parse(phrase,
               print_debug_info=(arg=='--debug'))

让我们给出一些短语来运行这个解析器，如下：

$ echo -n "alpha" | ./abc.py
Head:
A: alpha
Tail:
echo -n "xavier alpha beta charlie will" | ./abc.py
Head: xavier
ABC: alpha beta charlie
Tail: will
$ echo -n "mable delta xavier bruce" | ./abc.py
Traceback (most recent call last): [...]
dparser.SyntaxError:
syntax error, line:1
mable delta xavier bruce[syntax error]

显然，到目前为止，一切都没问题。我的语法当其条件允许时找到了一个 ABC，但是当只能找到 A 或者 AB 时，也能满足于此。

不过说实话，当遇到含糊的短语时，我的语法会有很多问题。在大部分情况下，当 DParser 不能确定如何解析 一个短语时，它会陷入一个无限循环（可能是最坏的结果；至少回溯或者报告的错误可以告诉您哪里出现了问题）。 有时（至少在我的 Mac OSX 机器上），它会转而生成一个“Bus error”。那些情形我哪个都不喜欢。

回页首

处理含糊的短语

由于所有的最终结果都有相同的优先级，所以解析器不能确定如何解析类似如下的内容：

$ echo -n "alex bruce alice benny carl" | ./abc.py

AB 在前然后是单词？单词在前然后是 ABC？对于那个问题来说，它是全部都是单词吗（包括五个单词结果）， 它是不是应该引发一个 dparser.SyntaxError ？我最后会得到一个“Bus error” 或停止了的任务，而不是一个解析。在先前的例子中，含糊的短语碰巧被解析出来的原因在于每个结果的急切性（eagerness）； 一旦找到一个 ABC，则先导和结尾单词就都各就其位。

实际上，在先前的语法可以生效的情况下，要确切地理解为什么能够 生效很令人迷惑 —— 在某种程度上，比理解为 什么它有时不能生效更令人迷惑。

让我们假定我们希望解析一个短语，并当存在 ABC 结果时找它，即便在从左到右的遍历过程中，有一些其他的结果 （也就是 AB）得到了满足。我可以通过提高 ABC 最终结果的优先级来完成：

def d_ABC(t):
    'ABC : AB "c[a-z]*" $term 1'
    return 'ABC'

如果没有指定优先级，则结果的优先级是 0。否则，任何正整数或负整数都可以用来对结果 排序。现在我们可以运行：

$ echo -n "alex bruce alice benny carl" | ./abc2.py
Head: alex bruce
ABC: alice benny carl
Tail:

注意，在解析器寻找末尾的单词之前，会尝试（ABC|AB|A）系列中的全部可选项。所以这样不需要任何优先级规范 就可以成功。

$ echo -n "alex alice benny" | ./abc.py    Head: alex
AB: alice benny
Tail:

在处理含糊短语时 DParser 的行为中，我发现了一些难以解释的异常现象。例如，添加一个 绝对不是 A 的末尾单词，解析器可以工作 —— 但 只能 在有调试信息的条件下运行!

$ echo -n "alex bruce alice benny carl dave" | ./abc.py
[...process freezes...]
$ echo -n "alex bruce alice benny carl dave" | ./abc.py --debug
[...debugging trace of speculative and final productions...]
Head: alex bruce
ABC: alice benny carl
Tail: dave

abc2.py 中的优先级规范会完成任意一种情况下的解析。

含糊短语的解析相当难以捉摸，难以确切理解。基本上，结果的生成是按遍历的顺序从左到右 执行的，每一个结果都尝试去从左到右获取尽可能多的单词。只有当向前查找过程中发生明显 错误时，才会进行回溯。总之，这只是大概。

回页首

调试简介

DParser 可以显示调试信息的选项，这是我所喜欢的它的一个方面。观察这些信息并不是直观地创建 正确语法所必需的，但是至少可以通过它洞察当处理特定的短语时解析器所采取的动作。例如：

#------- Showing a trace of speculative productions
$ echo -n "alex alice benny carl dave" | ./abc2.py --debug
               d_words --?:
                   d_A --?:     alex
                d_word --?:     alex
               d_words --?:
              d_phrase --?:     alex
               d_words --?:     alex
                   d_A --?:     alice
                d_word --?:     alice
               d_words --?:
               d_words --?:     alice
              d_phrase --?:     alex alice
              d_phrase --?:     alex alice
               d_words --?:     alex alice
                d_word --?:     benny
                  d_AB --?:     alice benny
               d_words --?:     benny
               d_words --?:     alice benny
               d_words --?:
              d_phrase --?:     alex alice benny
              d_phrase --?:     alex alice benny
              d_phrase --?:     alex alice benny
               d_words --?:     alex alice benny
                d_word    :     alex
               d_words    :     alex
                   d_A    :     alice
                  d_AB    :     alice benny
                 d_ABC --?:     alice benny carl
               d_words --?:
              d_phrase --?:     alex alice benny carl
                 d_ABC    :     alice benny carl
                d_word --?:     dave
               d_words --?:     dave
              d_phrase --?:     alex alice benny carl dave
                d_word    :     dave
               d_words    :     dave
              d_phrase    :     alex alice benny carl dave
Head: alex
ABC: alice benny carl
Tail: dave

后面跟有问号的结果是推测性的尝试；那些后面其实没有最终的结果。与此相关， DParser 让您有能力当结果成为推测的或者是最终解析时采取不同的动作。默认情况下， 函数体中的动作只作用于最终解析。不过，您可以向结果指定两个额外参数中的一个来 处理推测性解析。（还有很多本文中没有讨论的选项参数。）

def d_prod1(t, spec_only):
    'prod1 : this that+ other?'
    print "Speculative parse of prod1"
def d_prod2(t, spec):
    'prod2: spam* eggs toast'
    if spec:
        print "Speculative parse of prod2"
    else:
        print "Final parse of prod2"

当然，通过指定 dparser.Parser.parse() 的 print_debug_info 参数，我的推测性解析所显示的所有信息也都显示出来（以稍微不同的格式）。不过您也可以决定采取其他动作 —— 比如触发 外部事件。

回页首

深入探讨优先级

我承认，前面 ABC 结果所使用的指定优先级有些不太正统。但是假如是简单含糊短语， 则微调结束优先级是一个非常好的工具。让我来给出另一个关于简单含糊短语的语法：

def d_phrase(t, s):
    'phrase : word ( vowel | caps | threeletter ) word'
    print "Head:", ''.join(s[0])
    print t[1][0]+":", ''.join(s[1])
    print "Tail:", ''.join(s[2])
def d_word(t): 'word : "[A-Za-z]+" '
def d_vowel(t):
    'vowel : "[AEIOUaeiou][A-Za-z]*"'
    return 'VOWEL'
def d_caps(t):
    'caps : "[A-Z]+"'
    return 'CAPS'
def d_threeletter(t):
    'threeletter : "[A-Za-z][A-Za-z][A-Za-z]"'
    return '3LETT'
#-- Parse STDIN
from dparser import Parser
from sys import stdin
Parser().parse(stdin.read())

vowel 、 caps 和 threeletter 的结果不需要是确切的；它们全部都可以获取彼此有重叠的单词集合。例如：

$ echo -n "Read IBM developerWorks" | ./ibm.py
Traceback (most recent call last): [...]
dparser.AmbiguityException:  [...]

当然，您可能幸运地使用了特定的短语：

$ echo -n "Read GNOSIS website" | ./ibm.py
Head: Read
CAPS: GNOSIS
Tail: website

不要满足于祈祷好运，让我们来显式地指定结果之间的优先级：

def d_vowel(t):
    'vowel : "[AEIOUaeiou][A-Za-z]*" $term 3'
    return 'VOWEL'
def d_caps(t):
    'caps : "[A-Z]+" $term 2'
    return 'CAPS'
def d_threeletter(t):
    'threeletter : "[A-Za-z][A-Za-z][A-Za-z]" $term 1'
    return '3LETT'

现在，每一个短语都将以特定的顺序识别出中间单词的类型（当然只是可能的那些）：

$ echo -n "Read IBM developerWorks" | ./ibm2.py
Head: Read
VOWEL: IBM
Tail: developerWorks
$ echo -n "Read XYZ journal" | ./ibm2.py
Head: Read
CAPS: XYZ
Tail: journal

回页首

做出决定

尽管得到了一些读者的建议，我还是不太看重 DParser。它有很多可以作用于结果的强大的开关和选项，我还没有 讨论到 —— 比如指定关联性。大体上，DParser 语言非常健壮，我非常怀疑用于 Python 的 DParser 是否会 比纯粹的 Python 解析器运行速度快得非常多。

无论如何，我仍然不能对函数文档字符串风格的解析器具有太多热情。显然，关于这一点，很多优秀的 Python 程序员不会赞同我。此外我还发现一些解析结果有些令人不解：为什么调试模式下可以成功，而 标准模式下却不能成功？含糊问题确切是什么时候发生的？使用任何解析工具开发语法都会有类似的意外， 但是我发现 DParser 不知何故尤其出乎意料；例如 SimpleParse，就不会让我那么感到惊讶。可能，如果 我了解了底层算法的更多复杂细节，它将会更具意义；不过，就我相对浅薄的学识而言，我可能与 95% 以 上的读者差不多。有人比我更加熟悉解析；但是实际上大部分程序员懂得更少。

参考资料

• 您可以参阅本文在 developerWorks 全球站点上的 英文原文.
  
  
• 参阅 SourceForge 上的 DParser 主页。
  
  
• 可以获得关于 Python 绑定的细节的文档。 不过，很多高级特性的最好文档位于 DParser 程序库文档中 —— Python 包装器是相当精炼的。
  
  
• Charming Python 一些早期的文章已经介绍了其他用于 Python 的解析器。 Spark 和 PLY 类似于 DParser，使用函数的文档字符串来描述结果。mx.TextTools 是一个低层状态系统， SimpleParse 利用非 Python EBNF 语法来描述语法（并在后台将其翻译为快速的 mx.TextTools 操作）。
  
  
• 浏览 developerWorks 上 Charming Python专栏 的全部文章。
  
  
• David 的 Text Processing in Python （Addison Wesley，2003 年）既讨论了 SimpleParse 也讨论了 mx.TextTools（浏览我相应的 developerWorks 文章），另外增加了对 PLY 的讨论。您可以 在线 阅读那本书，或者 到好书店中去购买它。
  
  
• 在 developerWorks Linux 专区 可以找到 更多为 Linux 开发者准备的参考资料。
  
  
• 在 Developer Bookstore Linux 区中定购 打折出售的 Linux 书籍。
  
  
• 从 developerWorks 的 Speed-start your Linux app 专区下载可以运行于 Linux 之上的经过挑选的 developerWorks Subscription 产品免费测试版本，包括 WebSphere Studio Site Developer、WebSphere SDK for Web services、WebSphere Application Server、DB2 Universal Database Personal Developers Edition、Tivoli Access Manager 和 Lotus Domino Server。要更快速地开始上手，请参阅针对各个产品的 how-to 文章和技术支持。
  

关于作者

		David Mertz 认为人工语言是极其自然的，而自然语言似乎有一点不自然。 您可以通过 mertz@gnosis.cx 与 David 联系； 您可以通过他的 个人主页 来全面了解他的生活。 阅读他的 Text Processing in Python 一书。欢迎对过去的或将来的专栏文章提出意见和建议。

对本文的评价

太差！ (1) 需提高 (2) 一般；尚可 (3) 好文章 (4) 真棒！(5) 建议？

回页首