13 12, 2004
这个是根据pora的建议写的一个对parser combinator的概念和jparsec库的全面介绍。
刚刚完成了一点，先贴出来。
Java函数式高阶parser组合子逻辑
如果你熟悉c++，那么你可能知道一个叫做”spirit”的parser库。它利用c++的模板元编程能力，使用c++语言本身提供了一个递归下降文法解析的框架。
我这里介绍的jparsec库，就是一个java里面的递归下降文法解析框架。
不过，它并非是spirit的java版本。
Jparsec的蓝本来自Haskell语言的parsec库。Parsec是一个基于monad的parser组合子库。
那么，为什么叫“函数式”呢？java是面向对象的嘛。
如果你使用过haskell, lisp等语言，这个函数式不用解释你也知道是怎么回事了。
如果你是一个老牌的c++/java程序员，那么这里还要稍微解释一下。如果您对这些虚头八脑的名词不感兴趣，那么，你尽可以跳过这一章，不知道什么是“函数式”，并不会影响你对这个库的理解的。
C++这几年随着gp的普及，“函数式”这个老孔乙己逐渐又被人从角落里面拽了出来。一个c++程序员所熟悉的“函数式”很可能是stl的for_each, transform，count_if这些函数。
怎么说呢，就象我不能否定str.length()这个调用属于OO一样，我也无法说for_each, transform不是函数式。
但是，“函数式”的精髓不在于此。
一般归纳起来，就像我们说OO是什么多态，封装，继承一样，“函数式”的特征被总结为：
1。无副作用。
2。高阶函数。
3。延迟计算
而最最有意义的（至少我认为如此），是基于高阶函数的函数组合能力。一些人把这叫做glue。
简短地说，什么让函数式编程如此强大？是用简单的函数组合出复杂函数的能力。
我可以想象，说到这里，你还是一头雾水。“什么是组合？1+1不是也把两个1组合成2了吗？new A(new B(), new C())不也是从B和C组合成A了？”
为了直观，我们来举个例子吧。
假设，我们在package predicates内部有一个接口：interface SPredicate{
boolean is(String s);
}
我们有几个基本的实现：class IsEmpty implements Spredicate{
public boolean is(String s){return s.length()==0;}
}
这个实现判断字符串是不是空。
class IsCaptialized implements Spredicate{…}
这个实现判断这个字符串是不是大写打头。
class IsLowercase implements Spredicate{…}
这个实现判断字符串是不是全小写。
class IsEqual implements Spredicate{
Private final String v;
Public Boolean is(String s){return s.equals(v);}
IsEqual(String v){this.v = v;}
}
这个实现判断这个字符串是否和制定的字符串相等。
类似的基本实现还可以有很多。
下面，假如我们希望实现一个Spredicate，它要判断“这个字符串是个小写字符串，或者等于hello”。
我们怎么办呢？
我们当然可以这样：class Predicate1 implements Spredicate{
Boolean is(String v){
Return v.isLowercase() || v.equals(“hello”);
}
}
只不过，这样一来，我们没有重用IsEqual和IsLowercase这两个类的代码，虽然逻辑上我们是和这两个类有重叠。
我们当然也可以直接调用IsEqual和IsLowercase的代码，如：class Predicate1 implements Spredicate{
Boolean is(String v){
return new IsEqual().is(v) || new IsLowercase().is(v);
}
}
只不过，这样的代码是过程式的，非常死板。
如果我再有一个IsEqual或者IsCapitalized的逻辑呢？还要再写一个Predicate2类么？
如果你OO有一定功底，一定可以看出，这个代码不符合IOC原则，在不该new的地方new了。
好，知错就改，根据IOC原则，我们重构如下：
class OrPredicate implements Spredicate{
private final Spredicate p1;
private final Spredicate p2;
public Boolean is(String s){
return p1.is(s) || p2.is(s);
}
}
构造函数我就不写了。
如此，Predicate1我们就可以写成new OrPredicate(new IsLowercase(), new IsEqual(“hello”));
类似的，我们可以加上AndPredicate, NotPredicate, XorPredicate.
这样，基本上就可以覆盖所有的布尔操作了。
我们在写我们自己的Predicate的时候，就根本不必写is函数，甚至可以忘记is函数的存在。我们面对的不再是一个有着一个boolean is(String)签名的接口，而是一个可以通过各种规则组合的类型。
一个Predicate可以简单如new NotPredicate(p)，也可以复杂如：new AndPredicate(new OrPredicate(a,new XorPredicate(b,c), d));
擦擦眼睛，现在，我们等于自己制造出一个可以用一些特定规则组合的类型，而Spredicate的签名甚至都不再重要了。我们的客户程序从操作字符串变成了操作各种Spredicate对象，这已经是更高一级的抽象了。
为了表现这一点，让我们把Spredicate改成abstract class, 并把is()函数改成包私有（这样我们外面的用户程序就再也看不到这个函数了）。
等等！你可能发现了，现在我们虽然可以自由组合不同的Spredicate对象，但是组合之后有什么用呢？is函数看不见了，难道我们就是为了组合而组合吗？
不错，一个完整的组合子，还缺最后一小块。
让我们在predicates包内部再加上一个utility函数：public Boolean runPredicate(Spredicate p, String s){
Return p.is(s);
}
好了，功德圆满，我们可以用这个runPredicate函数来执行一个组合好了的Spredicate对象，而不用关心这个对象内部的is函数。
你可能有点怀疑。RunPredicate(p, s)和p.is(s)有什么区别？
呵呵，现在是没什么区别。下面我们来看看什么时候这种封装有明显的好处。
假设根据实现需要我们的Spredicate.is函数不是现在看到的这么简单，它可能是：
Boolean is(String s, PredicateContext ctxt);
PredicateContext对象负责存储并传递一些包局部的信息。
此时，我们很有可能不希望把这个签名对外公布。因为这个签名非常有可能变化，它是一个包的实现细节。PredicateContext甚至都是个包私有的类型。
此时，把is函数隐藏起来就是必要的了。对外，我们只公开一个runPredicate工具函数：
public Boolean runPredicate(String s, Spredicate p){
final PredicateContext ctxt = new PredicateContext();
return p.is(s, ctxt);
}
好，现在客户程序可以随意组合各个Predicate对象，最后用runPredicate函数运行。而包内部在演化时，完全可以根据需要随时改动is函数的签名，增加新的状态。
这，就是一个完整的组合子的例子。
有个比喻，基于过程的编程方法（比如fortran的方法），就象建造金字塔，你要从地基打起，一步一步向上修建，其中任何一步都不能失败。而金字塔一旦修好，就一直矗立在那里，风雨不变了。
而基于函数组合的编程方法，就象有机体的演化，每个小函数都是一个小的有机体，是个细胞，不同的细胞之间通过一些规则组合起来形成更大的有机体。如此往复，直到演化成足够复杂强大的有机体。而有机体的演化永远不会停止。这个过程等同于一个公理系统。一个欧几里得几何，就那么五个简单的公理，但是逐步推演，引理，定理，再定理，最终建立起了宏伟自恰的几何大厦。
过程式和函数式都是自底向上的解决问题方法，都要从最小的单元开始。区别在于函数式提供了不同单元之间灵活的组合能力。
面向对象的方法呢，则是一个自顶向下的分析问题方法。它着眼的不再是如何解决问题，而是这个问题怎样分解成子问题，每个子问题由谁负责的一个更加“人性”，“政治性”的方法论。
用人类社会或者公司的运作也许更能描述面向对象的思想。总统，ceo也许不懂编程序，不会看门，扫地，但是这不妨碍他们通过层层的分工调遣协作，让整个公司或者社会运行的井井有条。
好了，说到这里，我也口吐白沫了。你也许还在挠头，或者早已冲冲大怒：什么乱七八糟神神道道的，我看你象个江湖骗子！
好吧，看懂了当然好，看不懂也没有关系的。我们的目的不是贩卖一些似是而非的比喻来故作高深。只要后面具体的例子能说明怎么使用parsec库来做parser，那么实际的目的就达到了，谁在乎它到底叫什么呢？
二. parser的背景知识
先介绍一下产生式吧。
一个语法，可以用一系列产生式来表示（也就是BNF或者EBNF了）
比如，一个数字可以表示为：
number ::= ([0-9])+ （就是一个或多个0和9之间的字符）
一个c++/java中的变量名可以表示为：
alphanum ::= [_a-zA-Z] ([0-9_a-zA-Z])* （就是第一个字符是下划线或者字母，后面跟着0或者多个下划线，字母或者数字）
一个四则运算的运算符可以表示为：op ::= ‘+’ | ‘-‘ | ‘*’ | ‘/’
而四则运算表达式则可以用一系列产生式表示：term ::= number | ‘(‘ expr ‘)’
signed ::= （’+’ | ‘-‘)? signed
muldiv ::= muldiv (‘*’|’/’) signed
expr ::= expr (‘+’ | ‘-‘) muldiv
学过编译原理的，都知道parser分为top-down，bottom-up两大类。Bottom-up的parser有LR, LALR等，主要是分析产生式，然后根据分析的结果建立一个表，一个状态机。parser运行时读入一个字符，在表中查找下一步的动作。
Bottom-up的方法效率高，而且没有左递归的问题。
但是这类parser书写繁琐，代码的可读性，可维护性很差，调试起来也非常困难。
Top-down则反过来，从每个产生式出发，递归地判断当前读入的字符满足哪个产生式。这种parser叫做递归下降。
递归下降的一个问题是，读入一个字符，可能匹配不止一个产生式，此时对这种二义性的解决。
而更致命的问题，是左递归问题。
比如上面的四则运算表达式的产生式, expr就是一个左递归的产生式。
如果parser当前在试图parse expr, 那么为了parse expr, 它必须先parse它产生式右侧的第一个节点，而这个节点还是一个expr，这样parser就陷入了无穷递归。
递归下降的好处是：
代码容易写，易于理解，也容易维护。
不过，现实工作中，人们很少自己手工写bottom-up的parser（除非是对效率有非常高要求的工业强度的parser产品）。
往往大家都会选择用一个parser generator，比如yacc, JavaCC, ANTLR等。
使用这些parser generator，你只需要按照这个工具提供的语法来直接书写你的EBNF，然后这些工具会根据你提供的语法来生成parser 代码。（这个代码可以是bottom-up的，也可能是top-down的）
使用这些parser generator的好处是：
它节省了手工书写parser的时间，你只需要声明式地写出你需要的EBNF产生式，由专家实现好的generator就可以帮你生成最优化的代码。
这种生成的代码，效率仅仅比一个精通parser的人精心编写的手工parser稍逊。（注意是“精心”编写的，我手工写的parser肯定是没有generator生成出来的快的）
而维护上，你的语法如果有变化，只需要修改语法文件，然后用生成器重新生成一遍目标代码即可。
但是，parser generator也有一点点不足：
1。生成的代码往往不容易懂。如果你的语法有错，语法文件本身是不能debug的，而跟踪进生成的代码，跟读天书也差不多。
2。你需要提供语法文件。也就需要学习这个parser generator的各种规定，因为这个语法文件的写法完全是这个parser generator规定的。这个学习曲线也不可忽视。
3。有一个额外代码生成的步骤，发布，维护都略嫌繁琐。
4。有时候，项目中只需要处理一些简单的表达式evaluate之类的任务，用java.util.StringTokenizer有点不够，用parser generator又有点杀鸡用牛刀的感觉。
5。Parser generator往往只处理静态的语法。所有的产生式，优先级都要在语法文件里静态写好。很难处理在运行时修改语法的任务。
6。EBNF和目标语言（如java/c++) 不能很好的结合。很难对语法和语义动作进行代码重用。
由于这些问题，一种叫做”parser combinator”的技术被人们提了出来。
Combinator不同于generator。它完全基于目标语言，不生成任何代码。所以也就没有那个额外的代码生成的步骤。而且，因为parser完全用目标语言写，你也就可以利用目标语言里面所有的语言特性，而不必被局限于某个parser generator所提供的有限的表达功能。
Combinator是基于递归下降的一种parser技术。不同于传统的手写递归下降的过程形方法，combinator是一个函数形的方法。
一个combinator库往往提供很多的组合子，用来从已有的parser构造出新的parser出来。比如，ebnf的*, +, ?等符号，都可以被实现为一个一个的组合子。而这些库提供的组合子可都比ebnf那有限的几个符号丰富得多了。
用户程序关心的是根据逻辑组合各种parser对象，而不是递归调用一个一个的parse函数。这个动作是由这个combinator框架来完成的。
代表性的parser combinator库有c++的spirit库，有haskell的parsec库。我们这个库就脱胎于parsec库。
这些combinator库都提供了动态parser的能力，突破了parser generator和手工递归下降只能处理静态文法的限制。
我们后面会看到这种动态文法的一个非常有用的应用（算符优先文法）
combinator方法的问题：
1，效率低。其实这是递归下降方法固有的问题。
2。左递归。这还是递归下降方法的问题。
3。因为目标语言往往不是一个为表达产生式专门设计的语言（而是一个通用语言），所以对有些ebnf的表达就不是很直接，读起来往往不如读语法文件那样一目了然。
4。语言之间的移植性。用parser generator的话，它往往可以把一个语法文件翻译成若干种不同的目标语言。而parser combinator完全依赖于目标语言，如果你半途忽然决定更换语言，那么你的parser combinator的代码就白写了。
5。Combinator方法基于高阶组合子逻辑。作为更高一层的抽象，这种函数式的思想方法往往不如parser generator直观，容易理解。
好了，介绍完parser的背景知识，让我们落下云头，来看看这个jparsec库吧。
三． Jparsec的使用。
首先，我们看scanner。
Jparsec的scanner负责读入字符输入，识别输入是否符合语法。
比如对于number，
产生式我们前面已经写了，number ::= ([0-9])+,
我们可以写成Scanner number = Scanners.charRange(‘0’, ‘9’).many1();
这里， Scanners.charRange(‘0’, ‘9’) 就是[0-9]。
charRange()产生一个Scanner对象。这个对象识别一个字符，这个字符必须在0和9之间。
many1()是个组合子，表示前面写好的那个”+”。
Scanners.charRange(‘0’,’9’).many1()就表示1个以上的数字。
实际上，Scanners类里面已经预定义了一个对应整数的scanner: isInteger()。
再看java的变量名，alphanum ::= [_a-zA-Z] ([0-9_a-zA-Z])*
[_a-zA-Z]可以写成：Scanners.plus(Scanners.isChar(‘_’), Scanners.charRange(‘a’,’z’), Scanners.charRange(‘A’,’Z’))
Scanners.isChar() 负责识别一个字符，Scanners.isChar(‘_’) 负责识别下划线。
Scanners.charRange(‘a’,’z’) 和Scanners.charRange(‘A’, ‘Z’) 负责识别小写字符和大写字符。
Scanners.plus() 表示“或”的概念。Scanners.plus(a,b,c)表示或者a，或者b，或者c。
所以Scanner alpha = Scanners.plus(Scanners.isChar(‘_’), Scanners.charRange(‘a’,’z’), Scanners.charRange(‘A’,’Z’)) 就代表[_a-zA-Z]。
而[0-9_a-zA-Z] 就是在alpha的基础上再多一个数字。Scanner alphanum = Scanners.plus(Scanners.charRange(‘0’,’9’), alpha);
所以，alphanum可以表示为：Scanner varname = alpha.seq(alphanum.many());
Scanner.seq()函数是个表示“顺序”的组合子。Scanner s = a.seq(b)就相当于
S ::= a b
所以alpha.seq(alnumnum.many)就相当于alpha alphanum*。
同样，Scanners类里面对alphanum预定义了isAlphaNumeric() 函数。
对varname也预定义了isWord() 函数。
那么，一个四则运算的运算符呢，很简单了吧？Scanner op = Scanners.plus(Scanners.isChar(‘+’), Scanners.isChar(‘-‘), Scanners.isChar(‘*’), Scanners.isChar(‘/’));
下面再来看parser。
Parser不同于Scanner。一个Scanner只负责识别输入的字符串是否match，而不返回任何数据。
Parser则不同，它除了识别输入的token流，报告match成功还是失败，还要根据输入返回对象。
所有的Parser相关的组合子和基本Parser都定义在Parsers类中。
下面先简要介绍一下基本的parser 组合子：
1． retn(Object v)， retn 不识别任何输入，仅仅返回一个对象v。
2． one(), one也不识别任何输入，但是它永远报告match成功。
3． zero(), zero不读入任何输入，但是它永远报告失败。
4． token(), token() 读入一个token, 判断这个token是否符合某个要求，如果符合，则报告成功。
5． plus()， 有若干个针对不同个数参数的重载版本。和Scanners.plus() 类似，也表示“或者”的概念。它相当于EBNF里面的“|”符号。
6． seq(), 表示顺序，Parser p = p1.seq(p2) 等价于 p ::= p1 p2。P2返回的对象就作为p的返回对象。
7． map2, map3, …, map5, map它顺序执行若干个Parser对象，把这些Parser对象的返回结果传递给一个Map2, Map3, …, Mapn对象，转换成一个新的对象。
8．optional(). optional()代表EBNF里面的”?”。Parser p1 = p.optional() 就相当p1 ::= p?
9．many()。p.many() 相当于 P*。
10．many1()。p.many1()相当于P+。
下面，我们来看看怎么对付这个四则运算表达式。term ::= number | ‘(‘ expr ‘)’
signed ::= （’+’ | ‘-‘)? signed
muldiv ::= muldiv (‘*’|’/’) signed
expr ::= expr (‘+’ | ‘-‘) muldiv
在写这个表达式parser的时候，我们还有几个困难要处理。
1． 左递归。muldiv和expr的产生式都带有左递归。这是因为加减法，乘除法都是左结合的。1-1+2应该是(1-1)＋2, 而不是1-(1+2)。
对这种左递归，jparsec框架有预定义的组合子infixl。所谓infixl就表示中缀左结合操作符。
Muldiv 就可以表示为： Parser muldiv = Parsers.infixl(op_muldiv, signed);
Expr就可以表示为：Parser expr = Parsers.infixl(op_addsub, muldiv);
关于op_muldiv, op_addsub我们等一下再解释。现在我们只要知道op_muldiv对应乘除法操作符。op_addsub对应加减法操作符就可以了。
2． 循环依赖。Term的产生式依赖expr, 而expr的产生式又间接依赖着term。对这种循环依赖，需要用lazy组合子来打破这个循环依赖。
3． 递归。Signed的产生式不是一个左递归，但是仍然是递归。我们固然可以用递归来处理这个产生式，但是，jparsec框架早就提供了预定义的prefix组合子，signed可以表示为：Parser signed = Parsers.prefix(op_positive_negative, term);
也就是说，signed是一个term前面有若干个正负号。
下面我们来看看我们第一版的四则运算parser。
final Parser lazy_expr = Parsers.lazy(new ParserEval(){
public Parser eval(){return expr();}
});
final Parser term = Parsers.plus(number, Parsers.between(lparen, rparen, lazy_expr));
final Parser signed = Parsers.prefix(op_positive_negative, term);
final Parser muldiv = Parsers.infixl(op_muldiv, signed);
final Parser expr = Parsers.infixl(op_addsub, muldiv);
Parser expr(){return expr;}
这里的lazy_expr就是为了打破循环依赖引入的。Parsers.lazy()组合子接受一个ParserEval对象。ParserEval对象负责把一个Parser对象的求值延迟到实际parser运行的时候。
好，这样，一个四则运算的parser就算搞定了。
但是，这个parser, 要求我们手工地根据运算符的优先级和结合率来写产生式。消除左递归虽然有框架的infixl帮忙，程序员仍然需要分析考虑这个问题， 并且正确地调用infixl。
其实，根据结合率和优先级来产生产生式和调用infixl, infixr, infixn, prefix, postfix这些组合子，都可以被自动化。
框架预定义了一个Expressions类和一个OperatorTable类，就实现了这样的一个算符优先文法。
Expressions类作为jparsec的核心Parsers类的用户代码，使用的完全是标准的jparsec的组合子。这也说明，应用parsec组合子，客户完全可以构建自己的更方便的增值库。
下面看看使用Expressions类，我们怎样实现四则运算。
首先，定义每个操作符的优先级：
正负号的优先级最高，先定义为100；
乘法，除法的优先级次之，为80；
加法，减法的优先级最低，为50。
同时正负号为前缀运算符，加减乘除为中缀左结合运算符。
然后根据这个信息生成一个OperatorTable对象：
OperatorTable ops = new OperatorTable()
.prefix(op_positive, 100)
.prefix(op_negative, 100)
.infixl(op_add, 50)
.infixl(op_sub, 50)
.infixl(op_mul, 80)
.infixl(op_div, 80);
完全的声明式编程，这里面我们不再担心左递归啦，产生式啦，就是一门心思声明优先级和结合率。
然后，使用Expressions类来构建Expression的parser:
Parser expr = Expressions.buildExpressionParser(ops, term);
完整的代码如下：final Parser lazy_expr = Parsers.lazy(new ParserEval(){
public Parser eval(){return expr();}
});
final Parser term = Parsers.plus(number, Parsers.between(lparen, rparen, lazy_expr));
final OperatorTable ops = new OperatorTable()
.prefix(op_positive, 100)
.prefix(op_negative, 100)
.infixl(op_add, 50)
.infixl(op_sub, 50)
.infixl(op_mul, 80)
.infixl(op_div, 80);
final Parser expr = Expressions.buildExpressionParser(term, ops);
Parser expr(){return expr;}
至于number, lparen, rparen, op_add, op_div等等终结符，另外有一个Terms的辅助类，可以帮助生成这些终结符的parser：
private final Terms words = Terms.getOperators(new String[]{
“+”, “-“, “*”, “/”, “(“, “)”
});
private final Map2 add = new Map2(){
public Object map(final Object o1, final Object o2){
return new Long(((Number)o1).longValue() + ((Number)o2).longValue());
}
};
private final Map2 sub = new Map2(){
public Object map(final Object o1, final Object o2){
return new Long(((Number)o1).longValue() - ((Number)o2).longValue());
}
};
private final Map2 mul = new Map2(){
public Object map(final Object o1, final Object o2){
return new Long(((Number)o1).longValue() * ((Number)o2).longValue());
}
};
private final Map2 div = new Map2(){
public Object map(final Object o1, final Object o2){
return new Long(((Number)o1).longValue() / ((Number)o2).longValue());
}
};
Private final Map positive = Maps.id();
private static final Map negate = new Map2(){
public Object map(final Object o){
return new Long(-((Number)o).longValue());
}
};
private Parser make_op(final String op, final Map2 m2){
return words.getParser(op).seq(retn(m2));
};
private Parser make_op(final String op, final Map m){
return words.getParser(op).seq(retn(m));
};
private final Parser op_add = make_op(“+”, add);
private final Parser op_sub = make_op(“-“, sub);
private final Parser op_mul = make_op(“+”, mul);
private final Parser op_div = make_op(“-“, div);
private final Parser op_positive = make_op(“+”, positive);
private final Parser op_negative = make_op(“-“, negate);
所有这些Map2, Map，如add, sub, mul, positive等等，都是根据不同的运算符进行的不同的语义动作。
如此一来，一个完整的四则运算器就诞生了。
具体代码，请参看测试代码中的TestParser类。另外，TestSqlParser是一个non-trivial的sql select语句的parser，你可以看到更完整的对parsec的使用。
下载连接是：
http://sourceforge.net/project/showfiles.php?group_id=122347
原文地址：http://blogs.allaboutprogram.com/index.php?blog=6&title=soouparserteoito&more=1&c=1&tb=1&pb=1