Electronic Joint Business

Solution for E-Business

lex

利用 Python 工具和库实现语法解析

想用 Python 来解析编程语言或者文档,一般有三种做法:1

  • 利用现成的库来支持语言的解析,如 XML 类库:对于那些使用广泛的语言如 XML 和 HTML,这是无疑是最好的选择。好的类库通常还会包括创建或修改语言的可编程 API,这要比基础解析器的功能多得多。不过只有最常见的语言才有这种类库。
  • 从头构造一个解析器:有时候你可能要自己构造解析器。比如语言无法用传统的解析器生成器来解析,或者生成器的功能无法满足性能需求或者无法和其他组件深度集成。
  • 利用工具或者库来帮助生成解析器,例如 ANTLR 可以为任何语言生成解析器。

在前两种选项之外的场合,生成器应该是默认的选择,因为它既灵活又可以大大缩短开发时间。这就是为什么本文重点关注此种类库和工具的原因。

用工具创建解析器
在后续的章节中我们会看到:

  • 利用工具来生成 Python 可用(或其他语言可用)的解析器
  • 用来创建解析器的 Python 类库

生成解析器代码的工具称一般为解析器生成器(parser generators)或者编译器的编译器(compiler compiler)。生成解析器的类库则称为解析器组合器(parser combinator)。

不管是生成器还是组合器都不是易上手的工具,你需要花时间学习它们的使用方法。请注意并不是所有生成器都适用于所有的语言。在这里, 我们列出了一些最常见的生成器并对它们逐一进行简单介绍。并且我们的目标语言定为 Python。这意味一般来说这些工具和库自身也是用 Python 编写的。

>>> 阅读全文

 

, , , , , ,

Flex 和 Bison 简介 (二)

在上一篇文章中,我们讨论了如何用 flex 和 Bison 来 创建词法分析器(标记识别器)和解析器。本文是本系列文章的第二篇,我们将会看到如何用这些工具来创建可以读取 Visual Studio 6 资源文件的解析器。本文将重点关注于词法分析器。

不过考虑到这两个工具的密切联系,我们会在解析器和词法分析器之间来回跳转。在本文的最后,你可以下载到词法分析器和解析器的源代码。

如我们在第一篇文章中讨论的,词法分析器负责从某处读取输入流,并将其分解成一连串的标记。每个标记代表着最底层的构造块,用于表示诸如字符串、 数字或关键字等等东西。词法分析器通过将输入数据和一系列正则表达式 (规则) 相匹配来实现实现这一点。当它找到和特定规则的一个匹配时,它会执行将程序员所编写的一些执行代码,并向解析器返回一个标记,用于表明哪个规则被匹配了。它还可能会返回一些与规则关联的数据。

例如下面的正则表达式。

/* Decimal numbers */
-?[09]+    {
        yylval.ival = atoi(yytext);
        return NUMBER;
    }

该表达式会匹配以负号开头的包含至少一个数的十进制数序列。(有关正则表达式的含义和格式,你可以参考:http://www.monmouth.com/~wstreett/lex-yacc/flex_1.html 并搜索的”模式”)。当找到匹配时,它会调用 atoi 函数并将字符串 yytext 传递给它作为参数,yytext 正好是符合规则的字符串。另一方面,atoi 的返回值被赋给在解析器中定义的联合 yylval 的成员 ival。最后该操作会返回一个 NUMBER 标记给解析器并终止。

>>> 阅读全文

 

, , , , ,

Flex 和 Bison 简介(一)

文章评价:
我最近有个项目需要一个对话框编辑器,客户要求该编辑器能够加载对话框模板,并显示出相应的对话框。

具体的实现方法有简单的,也有复杂的。简单的方法只需将资源脚本编译成 .res 文件,然后让程序读取这些编译过的模板,由此得到对话框模板的句柄,并传递给 CreateDialogIndirect 函数。这样就可以用代码来检查每个控件的属性。但这种方法有个缺点:一旦修改过模板就必须重新编译资源脚本,否则将导致严重的逻辑错误。

有鉴于此,我舍易求难:实现一个能读取 Visual Studio6 资源文件 (.rc 文件)的解析器来检查每个控件的属性,然后再返回编译过的对话框模板。

如果你浏览过资源模板文件的源文件,你会发现自己动手从头开始实现这样一个解析器是不可能的。资源文件包含各种文本块,其中有注释、工具栏资源、菜单、对话框等等。每种文本块都有固定的格式。要用面向过程的方法来编写解析这些文本块的程序,要解决的问题实在多如牛毛。还好我们有 Flex 和 Bison 来提供支持。

什么是 Flex 和 Bison?
既然提到 Flex 和 Bison 就不能不说到其前身 Yacc 和 Lex 。Yacc 和 Lex 来自 UNIX。Yacc 是 “yet another compiler compiler” 的缩写,而 Lex 则是 ‘lexical analyser’ 的简称。仅仅它们的名称就已经说明了很多问题 !你可以参阅 compilertools 站点 ,该站点提供了适合不同水平用户的范例,而且还有很详细的说明和解释。

>>> 阅读全文

 

, , , , ,

.NET编译器构造工具Irony

简介
Irony(不是 IronRuby),是个全新的 .NET 开源项目,其设计目的是为了提供一整套库和工具,以方便在 .NET 平台上实现自己的语言。目前它处于开发的第一阶段,即包括构造编译器的两个前端模块 — 扫描器和解析器。本文将对其技术稍作概述,并着重关注用 Irony 实现解析器。你可以在 CodePlex上找到该项目

Irony 在编译器构造方面引入了许多规则创新。和广泛使用的解析器创建工具类似,Irony 也基于语法规范来产生出可工作的解析器。不同的是,Irony 并不采用独立的元语言来编码目标语法。反之, 在 Irony 中,语法元素被表示为 .NET 对象,并用 C# 使用类 BNF 的表达式对目标语法进行编码。另外,Irony 不会生成额外代码 — Irony 的 LALR 解析器使用源自 C# 语法的编码信息来控制解析过程。

示例
本文所附的下载包中包含了 Irony 的核心装配件、语法浏览器和一系列解析器样例:包括数学表达式的解析器、Schema、Python 和 Ruby 的语法简化版解析器。利用语法浏览器,你可以查看语法案例的分析数据,并利用代码例子来测试解析器。下图是语法浏览器解析语法树的场景:

如果你想体验一下 Irony 项目,你只需要:

  • 1. 下载并解压源代码
  • 2. 用 Visual Studio 打开 Irony_all.sln 方案文件
  • 3. 将 GrammarExplorer 项目设为启动项目
  • 4. 按 F5 创建并运行应用
  • 5. 当语法浏览器的窗口出现的时候,在顶部的组合框内选择”grammer”,并浏览语法数据
  • 6. 从 Irony.Samples\SourceSamples 文件夹中加载源代码示例
  • 7. 解析源代码并浏览输出的语法树

背景
许多新潮的应用都用了这样或者那样的解析技术。比如编译器的开发就是严重依赖于解析器的一个现实例子。其他例子还包括了脚本引擎、表达式计算器(evaluator)、源代码分析和重构工具、基于模板的代码生成、格式化和彩色显示、数据导入和转换工具等等。因此,对于开发者来说,拥有快速直接的方法来实现所需的解析器就很重要了。不过不幸的是,就目前技术而言实现解析器仍然是个重大挑战。

>>> 阅读全文

 

, , , ,