梦想风暴

《探索Antlr》是两年前写的一篇文章，如今，Antlr 3.0已经发布了，有了一些变化，为了反映这些变化，我决定重写这篇《探索Antlr》。

探索Antlr（Antlr 3.0更新版） 

简介
Antlr（ANother Tool for Language Recognition）是一个工具，它为我们构造自己的识别器（recognizers）、编译器（compiler）和转换器（translators）提供了一个基础。通过定义自己的语言规则，Antlr可以为我们生成相应的语言解析器，这样便可以省却了自己全手工打造的劳苦。

目标
如同程序设计语言入门大多采用“Hello World”一样，编译领域的入门往往选择计算器。而这里迈出的第一步更为简单：一个只能计算两个数相加的计算器，也就是说，它可以计算“1+1”。

基础知识
先来考虑一下如何下手，如果你曾经接受过编译原理的教育，权当忆苦思甜了。这个计算器工作的前提是有一个需要计算的东西，不管我们是以文件的形式提供，还是手工输入，至少我们可以让我们的计算器知道“1+1”的存在。

有了输入之后，我们要先检查输入的正确性，只有对正确的输入进行计算才是有意义的。如同写文章有形式和内容之分，这里的检查也要细分一下，率先完成的检查当然是面子功夫——形式上的东西，看看是否有错别字的存在，我们要做的是数值相加，结果人家给出了一个字母，这肯定不是我们希望得到的，所以我们有权力拒绝这个不合法的东西。对于程序员来说，如果在自己的程序里写了一个语言不接受的标识符，比如在Java里用“123r”做标识符，那编译器肯定会罢工，拒绝让程序通过编译的。在编译原理里面，这个过程叫做词法分析。在我们的计算器中，我们只接受整数和加号，其它的一概不理。这里我们说的是“整数”，而非 “1”、“2”……，对我们来说，它们代表着同一类的东西，编译原理教导我们把这这种东西叫做token，那些数字对我们来说，都是一样的token，不同的仅仅是它们的值而已。

形式说得过去并不代表内容就可以接受，南北朝时期许多骈体文让我们看到了隐藏在华丽的外表下的空虚灵魂。你可以说 “我吃饭”，如果说“饭吃我”，除非是在练习反正话的场合，否则没有人会认为它是有意义的，因为显然这不是我们习惯的主谓宾结构。只有在闯过了词法分析的关口，才能到达这里，在编译原理里面，我们把这个阶段叫做语法分析。如果说词法分析阶段的输入是字符流的话，那么语法分析阶段的输入就是token流——词法分析的输出。我们这里接受的合法语法是“整数 加号 整数”。

编写语法文件
好了，制订好自己的语言规则之后，我们需要以Antlr的语言把它描述出来。下面便是以Antlr的语言描述的语法：
grammar Calculator;
 
expr:   INT PLUS INT;
 
PLUS  : '+' ;
INT   : ('0'..'9')+ ;

Antlr的语法文件通常会保存在一个“.g”的文件中，我们的语法文件叫做“Caculator.g”。
 
我们来看看这里的定义：
expr:   INT PLUS INT;
 
这条语句定义了expr，它等价于“:”右边的部分，也就是说，
* 一个INT，后面跟着一个PLUS，后面再接着一个INT。
 
至于INT和PLUS，它来自后面的定义：
PLUS  : '+' ;
INT   : ('0'..'9')+ ;
 
* PLUS定义的token，就是一个单一的“+”
* INT定义的token，由从'0'到'9'之间任意的数字组成，后面的加号表示它是可以重复一次到多次
 
如果你曾经与Antlr 2.x有过一面之缘，你会发现，这个语法文件与Antlr 2.x的语法文件有着些许不同。首先，我们没有区分词法分析和语法分析，由上面的代码可以看出，二者在形式上是一致的，不同的是，对于词法分析的输入是字符，而语法分析的输入是词法分析的结果，也就是token。Antlr 2.x必须显式的区分这二者，而在Antlr 3.0之后，Antlr会替你料理这一切。再有，这里的语法文件名必须与grammar定义的名字保持一致，对于Java程序员，这是一个顺其自然的选择。

编译语法文件
如同不编译的程序是无法发挥其威力一样，单单语法文件对我们来说，并没有很大的价值。我们的工作就是使用Antlr提供工具对我们的语法文件进行编译，不同于日常的编译器输出可执行文件，这里的输出是程序语言的源文件。Antlr缺省目标语言是Java语言，它也可以支持C，C#和Python语言，其他的语言尚在开发之中，从3.0发布包结构来看，Ruby的支持很快就会加进来。
 
将Antlr提供的JAR文件加入到classpath中，其中包括Antlr 2.7.7，Antlr 3.0与其runtime，stringtemplate。你没看错，除了3.0，这里还包含着2.7.7。原因很简单，Antlr 3.0是基于之前版本开发的。
 
然后把语法文件的名称作为参数传给语法编译器：
java org.antlr.Tool Caculator.g

在确保命令正确执行，且语法文件编写正确的情况下，Antlr为我们生成了几个文件：
* CalculatorLexer.java
* CalculatorParser.java
* Calculator__.g
* Calculator.tokens

正如前面说过的，Antlr替我们料理好了词法分析和语法分析，其中， CalculatorLexer.java就是我们的词法分析器，而CalculatorParser.java中包含了语法分析器，它们是我们这里关注的主要对象。至于另外两个文件，Calculator__.g是一个自动生成的lexer语法文件，而Calculator.tokens则是列出了我们定义的token，我们并不会在程序中和它们直接打交道，所以，让我们暂时忽略它们的存在。

运行程序
生成代码之后，就是如何使用这些生成的代码。下面就是我们的主程序，它负责将词法分析部分（Lexer）和语法分析部分（Parser）驱动起来：
public class Main {
    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        CalculatorLexer lexer = new CalculatorLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        CalculatorParser parser = new CalculatorParser(tokens);
 
        try {
            parser.expr();
        } catch (RecognitionException e) {
            System.err.println(e);
        }
    }
}
从这段代码中可以清晰的看出，Lexer的输入是一个字符流，而Parser则需要Lexer的协助来完成工作，用Lexer构造出的Token流作为其输入。一切就绪，我们让它跑起来，尝试输入一些内容，看它是否能够通过验证。事实证明，我们的程序可以轻松识别“1+1”，而对于不合法的东西，它会产生一些抱怨。

计算结果
还记得我们的目标吗？我们的目标是计算出“1+1”的结果，而现在这个程序刚刚能够识别出“1+1”，我们还要继续前进。

熟悉XML解析的朋友对于SAX和DOM一定不陌生，二者之间差别在于SAX属于边解析边处理，而DOM则是把所有的内容解析全部解析完（在内存中形成一棵树）之后，再统一处理。Antlr也有与之类似的两种处理方式，SAX的朋友是在Parser中加入处理动作（Action）处理将随着解析的过程进行，而DOM的伙伴则是解析形成一棵抽象语法树（Abstract Syntax Tree，简称AST），再对树进行处理。

加入Action
先来看看SAX的朋友。因为处理动作是加在expr上，其它部分保持不变。下面是修改过的expr：
expr returns [int value=0]
        : a = INT PLUS b = INT
          {
              int aValue = Integer.parseInt($a.text);
              int bValue = Integer.parseInt($b.text);
              value = aValue + bValue;
          }
        ;


看到常用的字符串转整数的方法，熟悉Java的朋友想必已经露出了会心的微笑。没错，这里定义Action的方法采用就是Java语言，因为我们生成的目标是Java，如果你期待另辟蹊径，那这里的代码就要用你的目标语言来编写。

仔细看一下不难发现，action完全是在原有的规则基础上改造的来。首先用returns定义了这个Action的返回值，它将返回value这个变量的值，其类型是int，我们还顺便定义这个变量的初始值——“0”。接下来，我们用a、b拿住了两个token的值，我们前面说过，在检查的过程中，我们并不关心每个token具体的内容，只要token的类型满足需要即可，但在action中，我们要计算结果，那必须使用token具体的内容，所以，我们用变量拿住了token。这里我们用$a.text获取这个token的具体值。剩下的动作就很简单了，把文本转换为数字，进行加法运算。
 
再给旧版本一些忆苦思甜的时间，Antlr 2.x写法有一些细微差别。首先，Antlr 2.x用“a : INT”将一个Token赋给一个变量，而这里用的是“a = INT”。再有，我们用$a.text获取token的值，而在Antlr 2.x中，我们会用a.getText()，当然，在Antlr 3.0中，我们也可以这么写，不过，a.getText()这种写法显然太过于Java。
 
是不是对我们的计算器有些迫不及待了，那就挥动工具生成全新的Parser。不过，在新的体验之前，我们还要稍微修改一下主程序，以体现我们的劳动成果。
public class Main {
    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        CalculatorLexer lexer = new CalculatorLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        CalculatorParser parser = new CalculatorParser(tokens);
 
        try {
            System.out.println(parser.expr());
        } catch (RecognitionException e) {
            System.err.println(e);
        }
    }
}

好了，让这个计算器来为我们求证“1+1”吧！

AST
SAX的朋友表演完了，下面就是DOM的伙伴登场了。

建立AST的方式很简单，只要我们加上一个AST的选项即可，不过，同DOM的处理方式一样，前面的解析只是为了后面的处理做准备，所以，这里我们要修改一下之前编写的语法文件，下面就是我们的新语法文件：
grammar Calculator;
 
options {
    output=AST;
    ASTLabelType=CommonTree;
}
 
expr : INT PLUS^ INT;
 
PLUS  : '+' ;
INT   : ('0'..'9')+ ;

稍微有些不同的地方是，我们加上了两个选项，告诉Antlr，我们要输出的是一个普通的AST。再有，在PLUS上面的“^”，这个符号用来告诉Antlr创建一个节点，以此作为当前树的根节点。

你也许会有些疑问，怎么没看到计算的加法的地方？正如前面所说，这里只描述了语法结构，这是为了后面的处理在做准备，那么后面如何处理呢？别急，大戏要压轴。下面登场的是Antlr整个故事最后一个大角，TreeParser：
tree grammar CalculatorTreeParser;
 
options {
  tokenVocab=Calculator;
  ASTLabelType=CommonTree;
}
 
expr returns [int value]
    : ^(PLUS a=INT b=INT)  
      {
          int aValue = Integer.parseInt($a.text);
          int bValue = Integer.parseInt($b.text);
          value = aValue + bValue;
      }
    ;
 
Antlr 可以接受三种类型语法规范——Lexer、Parser和Tree-Parser。如果说Lexer处理的是字符流、Parser处理的是Token流，那么TreeParser处理的则是AST。前面Action的处理方式中，我们看到，规则同处理放到了一起，显得有些混乱，而采用了AST的处理方式，规则同处理就完全分离了：在Parser中定义规则，在TreeParser中定义处理，如果我们需要对同样的语法进行另外的处理，我们只要重新 TreeParser，而不必在规则与Action混合的世界中苦苦挣扎。

有了前面Action的基础，再来看TreeParser也就简单许多，需要说明的就是：
^(PLUS a=INT b=INT)
除去变量的说明，简化一下这段代码
^(PLUS INT INT)
第一个符号PLUS对应了表示着根节点，两个INT则分别代表了两棵子树，这样刚好与前面生成的语法树对应上。

再来看看重新打造的主程序：
public class Main {
    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        CalculatorLexer lexer = new CalculatorLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        CalculatorParser parser = new CalculatorParser(tokens);
 
        try {
            CommonTree t = (CommonTree)parser.expr().getTree();
            CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
            CalculatorTreeParser walker = new CalculatorTreeParser(nodes);
            System.out.println(walker.expr());
        } catch (RecognitionException e) {
            System.err.println(e);
        }
    }
}

结语
体验过最简单的Antlr程序，我们就有了让它更为丰富的基础，接下来便是自己动手的时间了。

参考资料
《ANTLR入门》 2004年第三期《程序员》
《ANTLR Reference Manual》
《The Definitive ANTLR Reference》

写程序的时候，经常遇到这样的代码。处理之前，先检验一下一些参数，之后再进行处理。下面是一段这样的Java程序。

public class Service {
  public void approve() {
    Target[] targets = getTargets();
    if (targets.length == 0) {
      reportNoTarget();
      return;
    }

    actualApprove(targets);
  }

  public void reject() {
    Target[] targets = getTargets();
    if (targets.length == 0) {
      reportNoTarget();
      return;
    }

    actualReject(targets);
  }

  ...
}

这段代码不够漂亮，这是显然的，因为其中存在重复代码，参数检验的部分是完全相同的，这两个函数的真正的差别只是在检验后的处理。但是在

Java中，想简单的解决这种重复并不是一件容易的事情。我脑子里想到的方案包括用异常和接口，不过，这两种方法都不够优雅，其主要原因还是因

为Java的函数并不容易操作。如果你有什么好的解决方案，不妨告诉我。

如果我们用的是C#，这段代码可以这样来写。

public class Service
{
  private delegate void ActualOperationDelegate(Target[] targets);

  public void Approve()
  {
    OperateOnTarget(ActualApprove);
  }

  public virtual void RejectTrades()
  {
    OperateOnTarget(ActualReject);
  }

  private void OperateOnTarget(ActualOperationDelegate operation)
  {
    Target[] targets = GetTargets();
    if (targets.length == 0) {
      ReportNoTarget();
      return;
    }

    operation(trades);
  }

  ...
}

这段C#代码用delegate轻松的解决了重复代码的问题。

如果用Ruby，我们可以让程序更为优雅。
class Service
  def approve
    operation_on_target { |targets| actual_approve targets }
  end

  def reject
    operation_on_target { |targets| actual_reject targets }
  end

  def operation_on_target
    targets = get_target
    if (targets.length == 0)
      report_no_target
    end

    yield targets
  end

  ...
end

之前写过一篇关于程序设计语言表达的blog，这篇算是它的一个例子吧！

阅读Rails源码的时候，会发现代码中遍布着一些看上去比较奇怪的代码，大概会是这个样子：
  people.collect(&:name)

这段代码实际上等价于
  people.collect { |p| p.name }

但是，从Ruby的语法上来看，这行代码看上去是很难理解的，主要就是&:name。把这行代码当作Ruby脚本直接运行，你会发现，Ruby会向你报错，错误是：
  wrong argument type Symbol (expected Proc) (TypeError)

那么为什么这样的代码遍布于Rails，却能正常运行呢？

最初困扰人的可能主要是&:name的写法，这看上去根本不像正常的Ruby语法，但只要将它进行适当的分解，我们就豁然开朗了。在Ruby中，“&”通常用来表示后面跟的是Proc，而:name在Ruby中表示一个Symbol。把二者结合在一起，矛盾变产生了，”&”要的是一个Proc，而我们给的一个Symbol，这就是前面错误的来源。

知道了错误的来源，接下来的问题是，Rails里究竟变了怎样的魔术，让这段代码通过呢？

其实，“&”后面如果跟的不是一个Proc，那么它会试图找寻一个Proc，在Ruby中，这意味着它会调用to_proc方法。这是Ruby中的一种标准协议，关于这种转换协议，可以参考《Programming Ruby》中《Duck Typing》一章相关的介绍。

由于后面的是一个Symbol，结合前面的说法，只要为Symbol类提供一个to_proc方法，至少在语言层面上，就会变得正确起来。事实上，Rails正是这样做的。

class Symbol
  def to_proc
    Proc.new { |*args| args.shift.__send__(self, *args) }
  end
end
(activesupport/lib/active_support/core_ext/symbol.rb)

如果说to_proc仅仅是让这个魔术在语言层面上通过，那么上面这段代码也解开了其余部分的神秘面纱。不妨再进一步，看看它究竟是如何做到的。

通过开始的代码等价对比，我们已经知道了这行的代码意义，主要也就是调用了一个对象的方法。将它对应到Proc.new所附带的block上，我们便不难看出这段代码的意义所在了。

这里的*args是block的参数，在前面的例子中，p就是这个参数，我们要调用p的name方法，所以，p是作为receiver的，而args.shift正是将p提取了出来。通过__send__，我们就可以调用receiver的方法，而__send__需要一个Symbol指定要调用的方法，别忘了，我们正是在一个Symbol类中定义方法，于是self成为了一个自然的选择。至于剩余的参数（对*args调用shift之后），就作为参数传给方法了。实际上，大多数用法中，只有一个参数，所以，剩余的部分会是一个空数组。

通过这种变换，p.name就等价于args.shift.__send__(self, *args)了。

关于这段代码的实现，也许Ruby Extensions的实现更加清楚一些。
  def to_proc
    proc {|obj, *args| obj.send(self, *args) }
  end
这段代码将receiver分拆出来，所以，更加容易理解。当然，严格的说，二者还是稍有差别，这种实现必须要有一个参数。但是，在大多数情况下，这种实现已经足够了。

作为一个程序员，获取知识是让我不断前进的动力，而读书是我获取知识的一条重要途径。在这个“经典”、“必读”过剩的年代里，大多数的书都仅仅扮演着传播知识的角色，真正改变自己对某些问题看法的书其实少之有少。限于读书时的眼界和能力，在我列表中，让我拍案惊奇的书只有几本。Martin Fowler的《重构》，严格说来，我并没有完整的读完这本书，不过，正如作者自己所说，这样的书原本就不指望能够读完，因为有一大部分其实是参考手册。正是我读过的部分让我知道了重构，让我知道这么做可以把代码写得更好。Robert Martin的《敏捷软件开发》，这是一本名字赶潮流，内容很丰富的书，这本书让我开始理解软件设计，从此不再刻意追求设计模式。Kent Beck的《测试驱动开发》，我读的是英文版，因为当时中文版还没有出版，所以，我不敢说，我通过这本书很好的理解了测试驱动开发，但它却为我打开了一扇门，让我知道了一种更好的工作方式。

有好长一段时间，这个列表没再更新过，中间虽然我也读了很多书，也学到了很多东西，但却没有哪本书如这几本书一样给我带来巨大触动。新近加入我这个列表的书是《修改代码的艺术》，英文名是《Working Effectively with Legacy Code》。

对于很多软件开发人员来说，加入一个公司，通常意味要面对一大堆之前留下的代码。而面对沉重的负担，大多数人的感觉都是无可奈何。让无奈成为往事，也就是这本书的价值所在。

在我看来，这是一本讲解如何编写测试的书。之所以遗留代码让人头痛，除了复杂的逻辑，改动会带来怎样的后果是一件让人心里没底的事，而测试的存在可以大幅度降低这种恐惧。但是，许多代码在开发时并不考虑测试，这样做的结果就是让测试几乎成为一件不可能完成的任务，一个常见的例子就是代码中访问数据库。即便写出测试代码，漫长的测试过程也会让它失去一部分应有的作用，我们希望得到的是快速的反馈。所以，对于
无测试而言，知道编写测试是一种境界的提升，写好单元测试则是一种更高的境界。如果能够让测试驱动开发，从开发之初便考虑测试，并懂得如何写好测试，开发者应该不会陷自己于一种难为的境地，这也应该成为专业程序员应该具备的基本技能。

至于这本书的具体内容，我的评价是实用。具体的手法，很难在这里一一列举，但是，以我的开发经验来看，
许多似曾相识的代码不断的出现在书中，而作者举重若轻的处理手法，正是让我有拍案惊奇的地方。实际上，回味起来，每个手法都不是什么很高超的技法，但正是因为见识过类似的代码，才能体会到这种手法的价值所在。所以，相对于程序新人，它更适合有经验的人。

之所以说这本书更适合有经验的人还因为，这本书中谈及的内容涵盖设计、测试、重构等诸多方面：通过重构，解开代码内的耦合，让其可测。这恰恰是前面提到的那三本书所讲的内容。也只有懂得了这些基本内容才能体会到那些具体手法的价值所在。依然记得当年读《重构》时，在提取和内联之间迷茫了好久，直到后来经过了许多开发实践才体会到这些做法的真正含义。

如果说不足，那么，这本书缺乏一个列表，就像Martin Fowler为《重构》所做的那样，出什么样的问题，应该采用怎样的手法进行处理。

关于中译本，总的来说，翻译得很流畅，读起来比较舒服。不过，制作上还是有一些不太让人满意的地方。
* 译注太多，而且有些是低估读者智商的译注。
* 页边标有页码，似乎是为了与英文版对照，但文中的参考页码又是以中文版为准，显得有些乱。
* 书的装订不是特别令人满意，我一直担心从中间断开。

XRuby：享用JVM上的Ruby

在InfoQ China发了一篇介绍XRuby的文章。其实，对于之前听过我介绍XRuby的人来说，这篇文章的内容并不新鲜，因为基本上，这篇文章的内容脱胎于之前介绍XRuby的讲稿。虽然讲了几次，但还是应该把这篇文章写出来。一来，到场听介绍的人毕竟是少数，写出来看到的人应该可以更多，也让更多的人有机会了解XRuby，再有，内容写成文章需要比演讲时有更多的思考。所以，整体来说，内容叙述应该会更加准确。

这是一篇早就该写的文章，至少最初答应霍泰稳写这篇文章还是5月份的时候，7月份录我InfoQ访问的时候，又答应了Floyd完成这篇文章，可真正发布已经是十月份了。不过，这样一拖再拖也不是完全价值。在这段时间里，我在Agile Day讲了一次Ruby on JVM，让我对这个方面有了些新的思考，特别是把Ruby放在 JVM上的价值，这一点已经体现在这篇文章里了。另外，XRuby自身在这段时间中也发生了很大的变化，特别是Annotation的加入，让代码在表现形式上得到很大的进步。至少在我看来，最终体现在文章中的示例代码是可以接受的。

我希望，这篇文章可以成为一个起点。一方面，它可以作为让更多人了解XRuby的起点；另一方面，XRuby团队把它作为一个起点，向其它人展示XRuby中非常优秀的一面。当然，XRuby现在已经有了不少不错的文档。

已经有朋友给我建议，写一些更深入的东西，这也是我所希望的，只探讨一些比较浅的东西不过瘾。在XRuby开发过程中，有很多有趣的思考，我很愿意与人分享那种开发中的快乐。再有，写东西会促使人思考，随之而来的往往是发现不足，这也是有益于XRuby进一步改进的。

如果你希望了解或参与XRuby，不妨告诉我们，你想了解什么，也许，我们之后的文章会满足你！