Write a Scheme Interpreter in Ruby(1): Parser & Analyser

December 15, 2007 – 9:09 pm

leaf.gif也算是突然心血来潮吧,就想写一个 Scheme 的解释器,其实也是心血来潮了许多次了,只是一直都只是一个想法,最主要的原因还是因为自己对编译原理一无所知吧,也许明年上过编译原理课之后就好写了。不过这次真是心血来潮了,拦都拦不住,怕是等不到明年了。

不管写得出来写不出来,也都先试试吧!多次见石老师演示过 boost::spirit ,计算理论课上也学过了上下文无关文法,似乎还是知道个大概。于是我就开始找 Ruby 的 parser 库。

好像 parser 也有许多种,什么 Recursive Descent 之类的术语我也不懂,所以即使想去邮件列表里面问也不知道如何描述的好。找了半天似乎没有发现一个像 boost::spirit 那种级别的 parser 库,不过找到了 Peter Cooper 写的一个 Recursive Descent parser 实现(只有 255 行代码)。便下载下来,准备开工了!

似乎没有什么文档,不过作者给的例子就算是文档了。我就依样画葫芦,做了一个 scheme 的文法 :

      g.string          /"((\\.|[^\\"])*)"/
      g.symbol          /[^'`,@0-9"() \n][^ \n"'`,@()]*/
      g.number          /[+-]?\d+(\.\d+)?/
      g.quote           /,|'|`|,@/
      g.atom            'string | number | symbol'
      g.lparen          '"("'
      g.rparen          '")"'
      g.list            "lparen expressions rparen"
      g.expression      'atom | list | quoted_expr'
      g.quoted_expr     'quote expression'
      g.expressions     'expression(s?)'

其实我并不知道这个 RDParser 解析的结果是什么,我也不知道我自己期望得到什么样的结果。 -,-bb 总之一步一步来吧,我开始写测试代码,首先肯定是要失败的:

  def test_number
    [0, -10, 100, 5.5].each do |num|
      content = "#{num}"
      syntax_tree = @parser.parse(content)
      assert_equal "#{num}", syntax_tree
    end
  end

测试一下就可以看到结果了:

<"0"> expected but was
<[{:expression=>[{:atom=>[{:number=>"0"}]}]}]>.

可以看到它解析的结果其实是相当松散的一些 Hash 和 Array 嵌套的。我解析的顶层项目是 expressions

class SchemeParser < RDParser
  def parse(str)
    super(:expressions, str)
  end
end

expressions 是零个或者多个 expression ,于是结果是一个 Array (在这个例子中只有一个元素)。Array 的每一个元素自然就代表一个 expression 了,这里用一个 Hash 来表达,用 :expression 作为 key 就可以从 Hash 中取出这个 expression 的内容。为什么要用 Hash 呢?应该是为了保持一致性,因为下面的情况要用到 Hash 。

虽然 expression 只可能是atomlist 或者 quoted_expr ,但是还是用一个 Array 来表示,应该也是为了保持一致性了。不过这个时候如何判断这个 expressionatomlist 还是 quoted_expr 呢?Hash 就有作用了,分别用 :atom:list:quoted_expr 作为 key 从 Hash 中取值,如果能取出东西来的就是它没错了!

这样它解析生成的结果大概就知道是怎么回事了,测试也好写了:

  def test_number
    [0, -10, 100, 5.5].each do |num|
      content = "#{num}"
      syntax_tree = @parser.parse(content)
      assert_equal "#{num}", syntax_tree[0][:expression][0][:atom][0][:number]
    end
  end
 
  def test_string
    ['"foo"', '"foo\"bar"'].each do |content|
      syntax_tree = @parser.parse(content)
      assert_equal content, syntax_tree[0][:expression][0][:atom][0][:string]
    end
  end
 
  def test_symbol
    ['foo', 'nil?', 'set!', 'display-line!'].each do |sym|
      syntax_tree = @parser.parse(sym)
      assert_equal sym, syntax_tree[0][:expression][0][:atom][0][:symbol]
    end
  end
 
  def test_atoms
    atoms = ['atom-set!', '"string"', '-114.5']
    content = atoms.join(' ')
    syntax_tree = @parser.parse(content)
    assert_equal atoms[0], syntax_tree[0][:expression][0][:atom][0][:symbol]
    assert_equal atoms[1], syntax_tree[1][:expression][0][:atom][0][:string]
    assert_equal atoms[2], syntax_tree[2][:expression][0][:atom][0][:number]
  end

只是对于用字符串指定的规则它生成的结果有些奇怪,下面这个是测试列表的,其中左括号和右括号是字符串规则(参见上面的规则定义):

  def test_list
    syntax_tree = @parser.parse('(+ 1 2)')
    list = syntax_tree[0][:expression][0][:list]
    assert_equal '(', list[0][:lparen][0][:'"("']
    assert_equal '+', list[1][:expressions][0][:expression][0][:atom][0][:symbol]
    assert_equal '1', list[1][:expressions][1][:expression][0][:atom][0][:number]
    assert_equal '2', list[1][:expressions][2][:expression][0][:atom][0][:number]
    assert_equal ')', list[2][:rparen][0][:'")"']
  end

list[0][:lparen] 并不能得到 '(' ,而是需要再深入 [0][:'"("'] ,其中那个奇怪的语法是表示一个名字叫做 "(" (包含引号)的 Ruby symbol 。不过也不管那么多了,我现在的目的是弄清楚它解析出来的结果的格式,然后使用这个结果。

可是,究竟怎么用呢?似乎没有一个目标真的是不行。我仔细想想,如果要对 scheme 程序进行解析,首先要得到一个表达式,然后根据这个表达式的类型(像数字、字符串那样的 self-evaluating ,或者像 symbol 以及 list )来进行求值。

其实用它解析出来的这个结果已经能判断出类型了,不过它这个结果太过松散了,我想象中解析出来的结果是一个个的对象,解释的时候我只要调用它们的 eval 方法,并传递一个合适的环境(binding )进去就可以了。这样看来,我似乎还需要对结果进行一次处理,于是我便写了一个 SchemeCompiler ,后来意识到整个处理过程过于简单,不应该称作是 Compile ,于是又改作 SchemeAnalyser 。分析的结果应该是产生如下的几种类型的对象:

module SchemeVM
  class Symbol
    attr_reader :name
    def initialize(name)
      @name = name
    end
 
    def eval(binding)
      binding[self]
    end
  end
 
  class String
    attr_reader :content
    def initialize(content)
      # strip quote marks
      @content = content[1..-2]
    end
 
    def eval(binding)
      self
    end
  end
 
  class Number
    attr_reader :value
    def initialize(value)
      @value = value.to_i
    end
 
    def eval(binding)
      self
    end
  end
 
  class Cons
    attr_reader :car, :cdr
    def initialize(car, cdr)
      @car, @cdr = car, cdr
    end
 
    def eval(binding)
      func = @car.eval(binding)
      args = @cdr
      func.call(binding, args)
    end
  end
end

直接对分析的结果调用 eval 就可以完成解释的过程了!其实分析的过程也是比较简单的,就从分析一个 expression 开始:

  def analyse_expression(expression)
    if expression.atom?
      analyse_atom(expression.atom)
    elsif expression.list?
      analyse_list(expression.list)
    else
      analyse_quoted_expression(expression)
    end
  end

基本上就是一个简单分派了。为了避免使用 [:expressions][n][:expression][0] 这样丑陋的方式来引用,我做了一个 AnalyserHelper 的 module :

  module AnalyserHelper
    def atom?
      ! self[:atom].nil?
    end
    def atom
      self[:atom][0]
    end
 
    # ... etc.
  end

把那些东西包装起来,然后我对 SchemeAnalyser 类的所有以 analyse_ 开头的方法做了拦截,将其第一个参数用 AnalyserHelper 进行扩充,增加那些 helper 方法: :)

  instance_methods(true).select{|i| i =~ /^analyse_/}.each do |method|
    orig_method = instance_method(method)
    define_method method do |*args|
      args[0] = args[0].extend(AnalyserHelper) unless args[0].kind_of? AnalyserHelper
      orig_method.bind(self).call(*args)
    end
  end

一下分别是分析 list 的代码,就是简单地用 Cons 把 list 串联起来:

  def analyse_list(list, n=0)
    if n >= list.list_size
      return SchemeVM::Symbol.new("nil")
    else
      return SchemeVM::Cons.new(
        analyse_expression(list.expression(n)),
        analyse_list(list, n+1))
    end
  end

还有分析 atom 的代码,只是一个简单的转发,分派到 stringnumbersymbol

  def analyse_atom(atom)
    ATOMS.each do |type|
      return send("analyse_#{type}", atom[type]) unless atom[type].nil?
    end
  end

而三个类型的分析方法几乎是一样的,所以就不用分别写三次了:

  ATOMS.each do |type|
    define_method "analyse_#{type}" do |val|
      klass = SchemeVM.const_get(type.to_s.capitalize)
      klass.new(val)
    end
  end

其中 ATOMS 是一个常量:

  ATOMS = [:string, :symbol, :number].freeze

还有就是 quote 的支持,如果只是普通的 quote 的话,很好办,只要把 'foo 转换为 (quote foo) 的形式就可以了。不过我在解析器中还包括了 backquote ,把 `,,@ 也包括到这里面来了。因为我打算以后支持 Common Lisp 格式的宏(Scheme 的那种 syntax-rule 的宏似乎实现起来不容易,而且我自己都不会用 -,-bb )。不过现在还只支持普通的 quote

  def analyse_quoted_expression(expression)
    quote = expression.quote_symbol
    quoted = expression.quoted_expr
    if quote == "'"
      SchemeVM::Cons.new(SchemeVM::Symbol.new("quote"),
                         SchemeVM::Cons.new(analyse_expression(quoted),
                                  SchemeVM::Symbol.new("nil")))
    # TODO: support backquote and comma
    end
  end

Ruby 虽然没有 Common Lisp 那样强大的宏系统,但是由于它非常动态,许多用宏来做的事情基本上也可以直接完成,例如上面对于 numbersymbolstring 的分析函数的定义,正是宏的拿手活了 (肯定会写一个类似于 define-trivial-analyser 的宏 :D ),在 Ruby 里做其实也相当顺手!

另外就是我发现我已经开始渐渐习惯(并且喜欢上)一边写代码一边写测试了:

  def test_nested_list
    content = '(car (quote ("foo" 2)))'
    syntax_tree = @parser.parse(content)
    cons = @analyser.analyse_expression(syntax_tree[0][:expression][0])
    assert_equal "car", cons.car.to_s
    assert_equal "quote", cons.cdr.car.car.to_s
  end

正如我在单元测试的绿条条中提到的,看着测试代码通过实在是非常振奋人心的事情。并且在 Ruby 这样不需要编译的语言里运行一次测试的花费非常小,这也更加鼓励积极重构了!Ruby 内置的单元测试功能又非常实用,对于我来说非常符合 POLS ,我几乎没有看任何文档就直接开始用了。

说起 Ruby 的 principle of least surprise (POLS) ,似乎总是会引起无聊的争吵,以至于 Matz 都叫大家不要用 POLS 来说 Ruby 了

Since someone will surprise for any arbitrary choice, it is impossible to satisfy “least surprise” in his sense. The truth is two folds: a) when there are two or more choices in the language design decision, I take the one that makes _me_ surprise least. b) as a result, you will have less surprise in Ruby than other languages, once you have accustomed to it.

But I’m tired of explaining POLS again and again. I haven’t even used it first. I hope no one will use the term “POLS” any more to sell Ruby. It’s free after all.

OK! 似乎扯远了。 :D ,总之,parse 和 analyze 的过程差不多就完成了,不过我们还没有一个可运行的 scheme 解释器,事实上还有不少内容需要添加。那么就欲知后事如何,且听下回分解了! :D

  1. 7 Responses to “Write a Scheme Interpreter in Ruby(1): Parser & Analyser”

  2. parser一般都需要用到代码生成,简单地说 Recursive Descent 的最大好处就是生成的代码基本是人可以读的。

    你如果看过yacc生成的代码就知道是怎么回事了,尽管那类的效率很高,但生成的代码没法看,所以调试起来很麻烦。

    boost::spirit 尽管技术非常 cool ,但一旦出错在调试上很麻烦。我做项目时最终选了 antlr :
    http://seclib.blogspot.com/2005/09/thoughts-on-parser-generators.html
    http://seclib.blogspot.com/2005/06/parser-generator-used-for-popular.html

    By yawl on Dec 15, 2007

  3. This file (http://lib.store.yahoo.net/lib/paulgraham/jmc.lisp) might be helpful.

    By goncha on Dec 15, 2007

  4. 有趣,看看~

    By jiqihuman on Dec 16, 2007

  5. to yawl:
    非常抱歉一开始你的回复被 WP 误认为是 spam 了。谢谢你的解释。关于 antlr ,我也听 sishen 说起过,我看到你给的链接是 XRuby 的项目主页,是不是 XRuby 就是用 antlr 做的呢?

    antlr 似乎最开始是 Java 的吧?我之前也去看过它的页面,里面虽然有对 Ruby 的支持,但是似乎还不太完整的样子,所以就没有选用了。 :)

    By pluskid on Dec 16, 2007

  6. xruby的parser是用antlr写的。但antlr对ruby的支持一直没有人更新,我们本来想在个地方帮下忙,但时间关系一直只停留在想法阶段。

    真正商业编译器用的parser,基本都是手写的Recursive Descent parser,而不是编译原理课上一般用的yacc。主要就是在维护性上的好处。

    By yawl on Dec 16, 2007

  7. 我用Treetop编了一个
    http://dongbin.org/articles/2008/04/17/scheme_intepretor_with_treetop_1

    By dongbin on Apr 23, 2008

  8. @dongbin,
    呵呵,不错,不过其实我这个解释器后来也用 Treetop 重新写过的,从代码中可以看到。用 Treetop 之后中间去掉了一层,因为 Treetop 解析的时候就可以生成树了,而不是要再解析一边 sexp 。 :)

    By pluskid on Apr 23, 2008

Post a Comment