【deprecated】 主帖的四则运算有重大 bug （右结合……），正解请看 FX 的回帖 ……

用 treetop 写了个小小的解释器。过程中有几个小问题：

1. treetop 不支持 LR 的语法，如果把 exp 写成

rule exp
  exp op exp
end

就会 stack overflow，所以规则中左边不能出现自己。

2. 貌似需要一个能解析所有东西的规则放在开头，如果去掉下面的 rule all，就不能辨认了。一开始不知道弄得很郁闷。

3. 如果能快一些就好了 …… -_- 但是一直没见到 treetop 的 C-extension。

4. 如何报语法错误？

dzone 上的代码真是很赞

------------------------------------------------------------------------
语法中的一些缩写：
arg = argument
assign = assignment
exp = expression
idt = identifier
ids = identifiers
def = definition
func = function
num = number
l = left
r = right
op = operator
paren = parenthesis

完整代码如下。

little.tt

grammar Little
  rule all
    def
    /
    assign
    /
    exp
  end

  rule def
    'def' [\s]+ idt space '(' space def_args space ')' space exp {
      def eval
        args = def_args.names
        $def_table[idt.text_value] = [args, exp]
        "defined function: #{idt.text_value}"
      end
    }
  end

  rule def_args
    idt ([\s]+ idt)* {
      def names
        head, tail = elements
        [head.text_value, * tail.elements.map{|e| e.elements[1].text_value}]
      end
    }
    /
    '' {
      def names
        []
      end
    }
  end

  rule apply
    func:idt space '(' space apply_args space ')' {
      def eval
        arg_ids, exp = $def_table[func.text_value]
        unless arg_ids
          raise "function not defined: #{fun_name}"
        end

        args = apply_args.eval
        if arg_ids.size != args.size
          raise "args number wrong.\n" +
            "expected:#{arg_ids.size}, got:#{args.size}"
        end

        $binding.push Hash[arg_ids.zip args] do
          exp.eval
        end
      end
    }
  end

  rule apply_args
    exp ([\s]+ exp)* {
      def eval
        head, tail = elements
        [head.eval, * tail.elements.map{|e|e.elements[1].eval} ]
      end
    }
    /
    '' {
      def eval
        []
      end
    }
  end

  rule assign
    idt space '=' space exp {
      def eval
        $binding[idt.text_value] = exp.eval
      end
    }
  end

  rule exp
    term space op:[\+\-] space exp {
      def eval
        term.eval.send op.text_value, exp.eval
      end
    }
    /
    term
  end

  rule term
    l:paren space op:[\*\/] space r:paren {
      def eval
        l.eval.send op.text_value, r.eval
      end
    }
    /
    paren
  end

  rule paren
    '(' space exp space ')' {
      def eval
        exp.eval
      end
    }
    /
    num
    /
    apply
    /
    idt
  end

  rule idt
    [a-zA-Z_] [\w]* {
      def eval
        $binding[text_value] || 0.0
      end
    }
  end

  rule num
    [\+\-]? ( [0-9]+ '.' [0-9]+ / [0-9]+ ) {
      def eval
        text_value.to_f
      end
    }
  end

  rule space
    [\s]* {
      def eval
        raise 'empty'
      end
    }
  end
end

生成 little.rb

tt little.tt

repl.rb

require "treetop"
require "little.rb"

# invokation stack
class BindingStack
  def initialize
    @stack = [{}]
  end

  def []= idt, val
    @stack.reverse_each do |var_table|
      if var_table[idt]
        var_table[idt] = val
        return
      end
    end
    @stack.last[idt] = val
  end

  def [] idt
    @stack.reverse_each do |var_table|
      return var_table[idt] if var_table[idt]
    end
    nil
  end

  def push h
    @stack.push h
    res = yield
    @stack.pop
    res
  end
end

# runtime
$def_table = {}
$binding = BindingStack.new

# run
parser = LittleParser.new
puts 'Little lang. Type :q to quit.'
puts 'examples:'
puts '  a = 12 + 5 / 2 #=> 14.5'
puts '  def v(t) a*t'
puts '  v(12) #=> 174.0'
loop do
  print '>>'
  input = gets.strip
  if input == ':q'
    puts 'bye'
    exit
  end

  begin
    puts "=>#{parser.parse(input).eval}"
  rescue => e
    puts [e, * e.backtrace].join "\n"
  end
end

well...这个解释器是个典型的将tree-walker interpreter，其语义以SDT（syntax-directed translation）的方式嵌入在parser的语法里。

关于Treetop支持左递归语法的问题，其实已经有人在搞了。不过PEG经常会让人不小心写出性能很糟（也就是回溯过多）的语法，我原本想在毕业设计里实现一个PEG的解析器生成器，到最后还是变成实现了CFG的免得麻烦orz

有一点想提一下：Treetop支持的语法是PEG，parsing expression grammar。了解不多的同学可以wiki一下，或者读一下原论文。一个PEG的语法是一个四元组，G = (VN,VT,R,eS)，其中VN是非终结符号的集合，VT是终结符号的集合，R是一组语法规则（parsing expressions），eS是起始规则中的parsing expression；其中VN与VT应该是无交集的，而eS所在的规则属于R。

NS同学提到不给一个能解析所有东西的规则就不行，就是因为没提供合适的eS。eS就是starting expression，不指定它，其它规则就像空中楼阁一样 =_=|||

这种四元组的定义与传统的上下文无关语法（context-free grammar，CFG）非常类似。CFG里，一个语法是G = (VN,VT,P,S) ……って、おいおい，不是一模一样么？关键在于P里面的内容不同。PEG里最大的特征是只有带有优先顺序的选择结构“/”，而没有CFG中无优先顺序的选择结构“|”。这“小小的差异”足以让一个习惯了CFG语义的人在PEG里水土不服，也给PEG带来了语法模块化等一系列好处。

一想果然没 eS 是不行呢 …… 某些 rule 是不能放在全局的 ……

其实也不是需要很快，只要瓶颈部分是 C 就行了，不过经 profile 发现 treetop runtime 的瓶颈很均匀的分布在很多个函数中 ……

你说的瓶颈是解析的瓶颈还是包括eval的瓶颈？我还没读过Treetop内部的实现不知道它到底是怎么搞的，不过如果运行时间真的是很平均的分布在生成出来的各个方法中，这是递归下降式解析器最正常不过的情况了，说明你要解析的内容很平均的使用了各条语法规则。你试试解析个只有加减没有乘除的表达式就会发现sub_exp对应生成的方法完全没耗时间orz

代码更新了一点。添加了 def 语法，如：

def f(a b c d) a*b-c+d

比较的主要是 treetop 里面的方法调用时间，外面具体实现的先不管。我写的语法解析非常糟糕，所以希望 treetop 快一点，弥补我的糟糕实现 ……
感觉，如果是 GUI 的对响应时间要求很高的应用，就会比较紧张了 ……

可以贴个测试用例和对应的profile数据出来看看不？

P.S. 话说我真是不敏感，居然没有看到顶楼就想到是编辑器相关……嘿嘿

测试数据什么的就是 require 'profile' 粗粗的一看，很粗很粗 ……

此 treetop 纯练手用…… 正在往 happy 转移中。

hmm...要上Haskell的话，不考虑Parsec么？

happy 比较像 yacc，也是 packrat，用内存换速度，也包含在 haskell platform 包包中，比 parsec 更首选一点。

我对yacc系的解析器生成器的好感度都不高。而且与其写左递归语法，很多时候靠EBNF的*和+就够用了。
话说Happy不是GLR的么？是自底向上的诶……packrat是带回溯的自顶向下的解析方式，这两者混不到一起去 =__,=|||