跳转到主要内容 IBM® * 中国 * [ 选择 ] Search in: [dW 全部内容.....] 搜索: ____________________ 搜索 * 首页 * 业务解决方案 * IT 服务 * 产品 * 支持与下载 * 个性化服务 * developerWorks 中国 * Linux * 文档库可爱的 Python: 使用 SimpleParse 模块进行解析一种简明易读的 EBNF 样式的封装器 David Mertz，博士 (mertz@gnosis.cx), 分析员, Gnosis Software，Inc. David Mertz 喜欢以尼采的风格写作，其作品就象古代哲学家的冥想，但其中的谬误也会自己暴露出来。但也许他的（正在这里免费宣传）即将完成的书籍： Text Processing in Python，某天将被误认为是哲学的控制论变体。可以通过 mertz@gnosis.cx和 David 联系；在 http://gnosis.cx/publish/上了解他的生活。欢迎提出关于本栏过去、现在和将来的意见和建议。简介：为 Python 编写的解析工具很多。本专栏讨论了一种构建在 Python 之上的高级解析语言。 SimpleParse 在 mxTextTools 之上提供了一种 EBNF 样式的句法，从而很清晰地阐明了语法的表达式。标记本文！发布日期： 2002 年 1 月 01 日级别：初级访问情况 522 次浏览建议: 与大多数程序员一样，我经常需要标识存在于文本文档中的部件和结构，这些文档包括：日志文件、配置文件、分隔的数据以及格式更自由的（但还是半结构化的）报表格式。所有这些文档都拥有它们自己的“小语言”，用于规定什么能够出现在文档内。我编写处理这些非正式解析任务的程序的方法总是有点象大杂烩，其中包括定制状态机、正则表达式以及上下文驱动的字符串测试。这些程序中的模式大概总是这样：“读一些文本，弄清是否可以用它来做些什么，然后可能再多读一些文本，一直尝试下去。” 各种形式的解析器将文档中部件和结构的描述提炼成简明、清晰和说明性的规则，该规则规定了如何标识文档的组成部分。这里，说明性方面是最引人注目的。我所有的旧的特别的解析器都采用了这种风格：读一些字符、作决定、累加一些变量、清空、重复。正如本专栏关于函数型编程的部分文章中所评述的，程序流的方法风格相对来说容易出错并且难以维护。正式解析器几乎总是使用扩展巴科斯范式（Extended Backus-Naur Form(EBNF)）上的变体来描述它们所描述语言的“语法”。我们在这里研究的工具是这样做的，流行的编译器开发工具 YACC（及其变体）也是这样做的。基本上，EBNF 语法对您可能在文档中找到的部件赋予名称；另外，经常将较小的部件组成较大的部件。由运算符 ― 通常和您在正则表达式中看到的符号相同 ― 来指定小部件在较大的部件中出现的频率和顺序。在解析器交谈（parser-talk）中，语法中每个命名的部件称为一个“产品（production）”。可能读者甚至还不知道 EBNF，却已经看到过运行的 EBNF 描述了。例如，大家熟悉的 Python 语言参考大全（Python Language Reference）定义了浮点数在 Python 中是什么样子： EBNF 样式的浮点数描述 floatnumber: pointfloat | exponentfloat pointfloat: [intpart] fraction | intpart "." exponentfloat: (nonzerodigit digit* | pointfloat) exponent intpart: nonzerodigit digit* | "0" fraction: "." digit+ exponent: ("e"|"E") ["+"|"-"] digit+ 或者您可能见过以 EBNF 样式定义的 XML DTD 元素。例如，developerWorks 教程的类似于： developerWorks DTD 中 EBNF 样式的描述拼写稍有不同，但是量化、交替和定序这些一般概念都存在于所有 EBNF 样式的语言语法中。 _________________________________________________________________ 回页首使用 SimpleParse 构建标记列表 SimpleParse 是一个有趣的工具。要使用这个模块，您需要底层模块 mxTextTools ，它用 C 实现了一个“标记引擎”。 mxTextTools （请参阅本文后面的参考资料）的功能强大，但是相当难用。一旦在 mxTextTools 上放置了 SimpleParse 后，工作就简单多了。使用 SimpleParse 确实很简单，因为不需要考虑 mxTextTools 的大部分复杂性。首先，应该创建一种 EBNF 样式的语法，用来描述要处理的语言。第二步是调用 mxTextTools 来创建一个标记列表，当语法应用于文档时，该列表描述所有成功的产品。最后，使用 mxTextTools 返回的标记列表来进行实际操作。对于本文，我们要解析的“语言”是“智能 ASCII”所使用的一组标记代码，这些代码用来表示诸如黑体、模块名以及书籍标题之类的内容。这就是先前使用 mxTextTools 来标识的同一种语言，在先前的部分中，使用正则表达式和状态机。该语言比完整的编程语言简单得多，但已经足够复杂而有代表性。这里，我们可能需要回顾一下。 mxTextTools 提供给我们的“标记列表”是什么东西？这基本上是一个嵌套结构，它只是给出了每个产品在源文本中匹配的字符偏移量。 mxTextTools 快速遍历源文本，但是它不对源文本本身做任何操作（至少当使用 SimpleParse 语法时不进行任何操作）。让我们研究一个简化的标记列表：从 SimpleParse 语法生成的标记列表 (1, [('plain', 0, 15, [('word', 0, 4, [('alphanums', 0, 4, [])]), ('whitespace', 4, 5, []), ('word', 5, 10, [('alphanums', 5, 10, [])]), ('whitespace', 10, 11, []), ('word', 11, 14, [('alphanums', 11, 14, [])]), ('whitespace', 14, 15, [])]), ('markup', 15, 27, ... 289) 中间的省略号表示了一批更多的匹配。但是我们看到的部分叙述了下列内容。根产品（“para”）取得成功并结束于偏移量 289 处（源文本的长度）。子产品“plain”的偏移量为 0 到 15。“plain”子产品本身由更小的产品组成。在“plain”产品之后，“markup”产品的偏移量为 15 到 27。这里省略了详细信息，但是第一个“markup”由组件组成，并且源文本中稍后还有另外的产品取得成功。 _________________________________________________________________ 回页首 “智能 ASCII”的 EBNF 样式的语法我们已经浏览了 SimpleParse + mxTextTools 所能提供的标记列表。但是我们确实需要研究用来生成这个标记列表的语法。实际工作在语法中发生。EBNF 语法读起来几乎不需加以说明（尽管确实需要一点思考和测试来设计一个语法）： 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 := [!@#$%^&()+=|\{}:;<>,.?/"] 这种语法和您口头描述“智能 ASCII”的方式几乎完全相同，非常清晰。段落由一些纯文本和一些标记文本组成。纯文本由某些字、空白和标点符号的集合组成。标记文本可能是强调文本、着重强调文本或模块名等等。着重强调文本由星号环绕。标记文本就是由诸如此类的部分组成的。需要考虑的是几个特性，类似于到底什么是“字”，或者可以用什么符号结束缩写，但是 EBNF 的句法不会成为障碍。相比之下，使用正则表达式可以更精练地描述同类规则。“智能 ASCII”标记程序的第一个版本就是这样做的。但是编写这种精练难度大得多，并且以后调整也更为困难。下列代码表示了很大程度上（但不精确地）相同的规则集：智能 ASCII 的 Python regexs # [module] names re_mods = r""'([$\s'/">]|^)\[(.*?)\]([<\s\.$,:;'"?!/-])""" # *strongly emphasize* words re_strong = r""'([$\s'/"]|^)\*(.*?)\*([\s\.$,:;'"?!/-])""" # -emphasize- words re_emph = r""'([$\s'/"]|^)-(.*?)-([\s\.$,:;'"?!/])""" # _Book Title_ citations re_title = r""'([$\s'/"]|^)_(.*?)_([\s\.$,:;'"?!/-])""" # 'Function()" names re_funcs = r""'([$\s/"]|^)'(.*?)'([\s\.$,:;"?!/-])""" 如果您发现或发明了该语言的某种经过微小更新的变体，将它和 EBNF 语法一起使用要比和那些正则表达式一起使用简单得多。此外，通常使用 mxTextTools 执行模式操作甚至更快些。 _________________________________________________________________ 回页首生成和使用标记列表对于样本程序，我们将实际语法放置在一个单独的文件中。对于大多数用途而言，这种组织比较好，便于使用。通常，更改语法和更改应用程序逻辑是不同种类的任务；这些文件反映了这一点。但是我们对语法所做的全部处理就是将它作为一个字符串传递给 SimpleParse 函数，因此我们大体上可以将它包括到主应用程序中（或者甚至以某种方式动态生成它）。让我们研究完整的（简化）标记应用程序： typographify.py import os from sys import stdin, stdout, stderr from simpleparse import generator from mx.TextTools import TextTools input = stdin.read() decl = open( 'typographify.def' ).read() from typo_html import codes parser = generator.buildParser(decl).parserbyname( 'para' ) taglist = TextTools.tag(input, parser) for tag, beg, end, parts in taglist[1]: if tag == 'plain' : stdout.write(input[beg:end]) elif tag == 'markup' : markup = parts[0] mtag, mbeg, mend = markup[:3] start, stop = codes.get(mtag, ( '' , '' )) stdout.write(start + input[mbeg+1:mend-1] + stop) stderr.write( 'parsed %s chars of %s\n' % (taglist[-1], len(input))) 这就是它所做的。首先读入语法，然后根据语法创建一个 mxTextTools 解析器。接下来，我们将标记表／解析器应用于输入源来创建一个标记列表。最后，我们循环遍历标记列表，并且发出一些新的标记文本。当然，该循环可以对遇到的每个产品做我们所期望的任何其它事情。由于智能 ASCII 所使用的特殊语法，源文本中的任何内容都可归类于“plain”产品或“markup”产品。因此，对于循环遍历标记列表中的单个级别，它已经足够了（除非我们正好寻找比特定标记产品级别低一级的级别，譬如“title”）。但是格式更自由的语法 ― 譬如出现在大多数编程语言中的语法 ― 可以轻松地在标记列表中向下递归，并在每个级别上寻找产品名称。例如，如果一种语法中允许嵌套标记代码，或许可以使用这种递归风格。您可能会喜欢弄清如何调整语法的练习（提示：请记住允许各产品彼此递归）。转至输出的特殊标记代码还是存储到另一个文件中了，这是由于组织的原因而非本质原因。在这里我们使用了一个技巧，就是用一个字典作为一个 switch 语句（尽管示例中的 otherwise 情况还是太狭窄了）。这个想法就是：将来我们可能希望创建多种“输出格式”的文件，比如说 HTML、DocBook、LaTeX 或者其它格式。用于示例的特殊标记文件类似于： typo_html.py codes = \ { 'emph' : ( '' , '' ), 'strong' : ( '' , '' ), 'module' : ( '' , '' ), 'code' : ( '

' ), 'title' : ( '' , '' ), } 把这种格式扩展到其它输出格式很简单。 _________________________________________________________________ 回页首结束语 SimpleParse 为含义模糊的 mxTextTools C 模块的基本功能和速度提供了一种简明的并且十分易读的 EBNF 样式的封装器。此外，即使只是顺便学会的，许多程序员也已经相当熟悉 EBNF 语法了。关于什么更容易理解，我不能提供证明 ― 这一点因各人的直觉而异 ― 但是我可以根据源代码长度给出量化评估。先前手工开发的 mxTypographify 模块的大小如下： wc mxTypographify.py 199 776 7041 mxTypographify.py 这 199 行中，相当数量的行是注释。这些行中有 18 行是标记函数所包含的正则表达式版本，包含该标记函数是用于计时比较。但是该程序的功能基本上和上面列出的 typographify.py 的功能相同。相比之下，我们的 SimpleParse 程序，包括其支持文件在内，大小如下： wc typo*.def typo*.py 19 79 645 typographify.def 20 79 721 typographify.py 6 25 205 typo_html.py 45 183 1571 total 换句话说，行数大约只有前者的四分之一。这个版本的注释较少，但是那主要是因为 EBNF 语法的自我描述能力很强。我不希望太过强调代码行数 ― 显然，您可以通过最小化或最大化代码长度做手脚。但是通常对程序员的工作进行研究，少数实际经验结论之一是：“千行代码／人月”相当接近于常数，和语言以及库关系不大。当然，依次地，正则表达式版本是 SimpleParse 版本长度的三分之一 ― 但是我认为其表达式的密度使得它极难维护并且更难编写。总而言之，我认为 SimpleParse 是所考虑的方法中最好的。参考资料 * 您可以参阅本文在 developerWorks 全球站点上的英文原文. * 请阅读 developerWorks上 David 的上一篇可爱的 Python 专栏文章：可爱的 Python：使用 Python 进行文本处理，概述了 Python 的文本处理工具。 * mxTextTools 现在是更大的 eGenix 扩展包的一部分。要获得更多信息，请阅读 mxTextTools - Fast Text Manipulation Tools for Python。 * 引用模块 mxTypographify 是直接使用 mxTextTools 构建的。 SimpleParse 版本变得更容易阅读： http://gnosis.cx/download/mxTypographify.py * 请访问 John Aycock 的 Spark 模块主页。 Spark 是一个在很多方面比 SimpleParse 更成熟的解析框架。许多 Python 开发人员推荐 Spark ，它具有一个额外的优势 ― 它是纯 Python（因此在速度方面具有天生的劣势）。 * 请访问 ISO 14977 standard for EBNF syntax以获得更多信息。 * 请浏览 developerWorks上更多 Linux 参考资料。 * 请浏览 developerWorks上更多开放源码参考资料。关于作者 David Mertz 喜欢以尼采的风格写作，其作品就象古代哲学家的冥想，但其中的谬误也会自己暴露出来。但也许他的（正在这里免费宣传）即将完成的书籍： Text Processing in Python，某天将被误认为是哲学的控制论变体。可以通过 mertz@gnosis.cx和 David 联系；在 http://gnosis.cx/publish/上了解他的生活。欢迎提出关于本栏过去、现在和将来的意见和建议。建议 _________________________________________________________________ _________________________________________________________________ 回页首商标 | My developerWorks 使用条款与条件 static.content.url=http://www.ibm.com/developerworks/js/artrating/ SITE_ID=10 Zone=Linux ArticleID=21798 ArticleTitle=可爱的 Python: 使用 SimpleParse 模块进行解析 publish-date=01012002 author1-email=mertz@gnosis.cx author1-email-cc=mertz@gnosis.cx 内容 * 使用 SimpleParse 构建标记列表 * “智能 ASCII”的 EBNF 样式的语法 * 生成和使用标记列表 * 结束语 * 参考资料 * 关于作者 * 建议标签 Help 使用搜索文本框在 My developerWorks 中查找包含该标签的所有内容。使用滑动条调节标签的数量。热门标签显示了特定专区最受欢迎的标签（例如 Java technology，Linux，WebSphere）。我的标签显示了特定专区您标记的标签（例如 Java technology，Linux，WebSphere）。使用搜索文本框在 My developerWorks 中查找包含该标签的所有内容。热门标签显示了特定专区最受欢迎的标签（例如 Java technology，Linux，WebSphere）。我的标签显示了特定专区您标记的标签（例如 Java technology，Linux，WebSphere）。搜索所有标签 _________________ Search _________________________________________________________________ 热门文章标签 | 我的文章标签跳转到标签列表热门文章标签 | 我的文章标签跳转到标签列表 * 关于IBM * 隐私条约 * 联系IBM * 使用条款