java精神是什么?

java精神是什么?


一。释名。
为什么叫精神?
如果你熟悉c++,那么你可能知道一个叫做”spirit”的parser库。它利用c++的模板元编程能力,使用c++语言本身提供了一个递归下降文法解析的框架。

我这里介绍的jparsec库,就是一个java里面的递归下降文法解析框架。
不过,它并非是spirit的java版本。
Jparsec的蓝本来自Haskell语言的parsec库。Parsec是一个基于monad的parser组合子库。

这个库的目的是要在java中提供一个类似parsec, spirit的库,这种组合子库并非c++的专利,java/c#也可以做到。这个库还将在java5.0上被改写,类型安全上它将也不再逊色于c++。

那么,为什么叫“函数式”呢?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