[链接] 可以在Python里用的parsing library

有室友的毕业设计是做程序切片相关的，需要对代码做解析；指导老师建议他们用Python为实现语言，所以看来是需要找点适合Python使用的parsing library。解析源码这种事情正好是我熟悉的领域，就自告奋勇说看看能不能帮上啥忙。不过听说要解析的源语言或许是C++我就冒冷汗……||||||

手写parser真是太痛苦了，虽然我已经做了很多次但我还是不想建议室友也重复我的痛苦。特别是像C++那么复杂的语言 =v=
总之调查一下有些什么可选项，先记在这边再说。

有点想推荐用ANTLR来生成lexer和parser，因为ANTLRWorks用于编写词法和语法规则相当方便。Jython的解析器就是用ANTLR来生成的，ANTLR官网首页上甚至有Python之父Guido van Rossum的赞词：

Guido van Rossum 写道

I'm actually really liking ANTLR! I have a pretty darn good velocity with...

我手写RD系解析器的时候一般也会用ANTLRWorks来写个语法来确认一下构思中的语法有没有错，然后再手工转换成具体实现。不过问题是ANTLR的库普遍都比较“大”，里面东西也挺多挺复杂的，或许上手要花点时间？
说到大，刚看了一下ANTLR的Python target，看来没我原本想像的那么大。antlr_python_runtime-3.1.2-py2.5.egg才145KB。还行。
要是室友用ANTLR，那我能跟他分享的经验就会多一些，例如说ANTLRWorks的使用之类。在ANTLR官网的Grammars一栏里有些现成的C/C++语法文件，包括Sun在NetBeans中使用C/C++预处理器和解析器的语法文件。可惜Sun的那两个文件是对应ANTLR v2.7的，而且有很重的NetBeans自身的痕迹，不能直接拿来用。
要开始用ANTLR与Python的组合很简单：
1、先到ANTLR官网的下载页面下载一个ANTLRWorks+ANTLR的包，用于进行语法编辑和调试；
2、到ANTLR的Python target页面下载对应Python 2.5的运行时库；
3、阅读ANTLR 3 Python Target的文档来了解使用Python target的注意点；
4、阅读Example: Book Examples Modified for Python来了解一个简单的lexer/parser的写法，找到感觉；
5、自己继续探索吧…… =w=

ANTLR之外，PLY看来也是个不错的选择。它可以看做是lex/yacc的纯Python实现，最大的优势就是它完全继承了lex/yacc系工具的特征，把符合lex/yacc的规则写在doc string里就行，这样就能最大限度的利用到处都能找到的lex/yacc相关的教学资料，包括我手上的几本书，以及许多现成的C/C++的lex/yacc例子；作者当初是为了教授编译器课程而编写这个库的，有较强的教学背景，适合学生使用；另外，作为纯Python实现的解析器库，它的速度在可接受范围内（作者提供的例子称它比ANTLR快）。
在Google Code上有个pycparser项目使用PLY来实现了C的解析和代码生成；SourceForge上也有个CppHeaderParser.py用PLY来解析C++头文件以获取类的结构信息。应该说还是有些实际应用的。
PLY-3.1的整个tarball才143KB，相当小。里面包括了一些例子，例如一个完整的Dartmouth BASIC解释器的Python实现。有lex/yacc基础的话这个库上手应该很快。不过用它来解析C++或许会比较吃力……

室友说最近的任务就是周末前用Python写一个C++的词法分析器，貌似是要输出关键字出现的行号还是怎样，具体要求还没问清楚。这个的话用ANTLR、PLY或者手写倒都不困难就是了。C++词法分析里最麻烦的或许是字符串的分析吧？里面的各种转义序列都得考虑到，规则写起来冗长。其它都还好，前提是代码已经经过了预处理……自己做预处理的话又是件超麻烦的事情。在当前C++规范下嵌套的泛型声明的尖括号间还是得有空白字符，所以这个现在还不是问题。

Ned Batchelder做了份颇有用的Python parsing tools列表，如果要找其它可选项的话可以从这个列表里发掘一下。
突然想起的事情：貌似不少库都对空白字符有自己的主张，喜欢自动忽略它们；很多时候这带来了方便，但如果要解析Python或者F#这些用缩进表示块结构的语言就麻烦了。到底是该让用户显式指定忽略规则，还是默认带有忽略空白字符的规则好呢？

有人推荐pyparsing，不过我稍微看了些例子，第一感觉是我不太喜欢它处理语法规则的方式：它主要通过运算符重载和一些工厂函数来实现fluent API式的internal DSL来表达语法规则，但我觉得这样的代码在Python里看起来挺怪的。
从官网上引用段例子过来：

pyparsing 写道

from pyparsing import Word, alphas
greet = Word( alphas ) + "," + Word( alphas ) + "!" # <-- grammar defined here
hello = "Hello, World!"
print hello, "->", greet.parseString( hello )
#=> Hello, World! -> ['Hello', ',', 'World', '!']

Python用来做internal DSL总觉得有点硬（语法层面上）然而又不够硬（类型层面上）。说语法硬主要是Python库能对语法做的定制余地不大，而且Python社区也比较喜欢统一的做事方式；说类型不够硬是指静态类型语言能够通过精巧的类层次/API设计来在编译时对fluent API做“语法检查”，而Python的变量没有类型所以fluent API要是写错了也得到运行时才能发现。嘛，静态/动态方面的观点总是有争议的，我这里纯粹是自己的感觉，没有想说服别人的意思。Boo用于internal DSL就比Python来得方便，多得语法宏。
呵呵，事实上我自己在写的一个库也是用fluent API来表达语法规则的；跟pyparsing一样，我也是重载了+来表示顺序结构、|来表示选择结构，等；但那样的代码出现在C#里我就没觉得很奇怪。呃诶……

可视化工具里除了ANTLRWorks之外我也很喜欢新的Oslo的Intellipad，不过Oslo的运行时依赖于.NET Framework，算了，不用来推荐给室友。据说Oslo team的人用MGrammar写过VB和C#的语法？呵呵，it's got all the potentials, let's just wait and see what comes out of it.
还有些别的语法编辑器不过貌似要收费……呜，收费的暂时无视。

今天先记这么多。要是有时间的话手写个简单的词法分析器作为例子也可以……不过现在我想睡觉了
P.S. Python自己的编译器是如何实现的呢？可以关注一下PEP-339的描述。是一个典型的LL(1)解析器解析出AST之后，生成CFG然后生成bytecode。