Question

本章，我们已经手工构建了 Simple 程序的抽象语法树——通过手写 Assign.new(:x, Add.new(Variable.new(:x), Number.new(1))) 这样的普通 Ruby 表达式，而不是先写'x = x +1'这样原始的 Simple 源代码，然后使用一个语法解析器自动地把它转成语法树。

从头开始完整地实现一个 Simple 的语法解析器过于复杂，会分散我们讨论形式语义的注意力。尽管破解一个小编程语言很有趣，但是感谢解析工具和解析库的存在，在他人工作的基础上构造一个语法解析器并不是特别困难，因此下面将对其简单介绍一下。

Treetop（http://treetop.rubyforge.org/）是 Ruby 可用的语法解析工具中最好的一个，它是一种特定领域的语言，能让语法解析器自动生成。一种语言的 Treetop 描述会写成解析表达式语法（parsing expression grammar），这是一个简单的类正则表达式（regular-expressionlike）的规则集合，既易写又易理解。最好的是，这些规则能够使用方法定义作为注释，这样的话，就可以为语法解析过程中生成的 Ruby 对象定义行为。Treetop 既能定义语法结构，又能定义基于这些结构进行运算的 Ruby 代码集合，这使 Treetop 很适合描述一种语言的语法并赋予它可执行的语义。

为了让我们体验一下这是如何工作的，下面给出关于 Simple 的 Treetop 语法简装版，它只包含解析字符串“while (x < 5) { x =x * 3 }”所需要的规则：

grammar Simple
  rule statement
    while / assign
  end

  rule while
    'while (' condition:expression ') { ' body:statement ' }' {
      def to_ast
        While.new(condition.to_ast, body.to_ast)
      end
    }
  end

  rule assign
    name:[a-z]+ ' = ' expression {
      def to_ast
        Assign.new(name.text_value.to_sym, expression.to_ast)
    end
    }
  end

  rule expression
    less_than
  end

  rule less_than
    left:multiply ' < ' right:less_than {
      def to_ast
        LessThan.new(left.to_ast, right.to_ast)
      end
    }
    /
    multiply
  end

  rule multiply
    left:term ' * ' right:multiply {
      def to_ast
        Multiply.new(left.to_ast, right.to_ast)
    end
    }
    /
    term
  end

  rule term
    number / variable
  end

  rule number
    [0-9]+ {
      def to_ast
        Number.new(text_value.to_i)
      end
    }
  end

  rule variable
    [a-z]+ {
      def to_ast
        Variable.new(text_value.to_sym)
      end
    }
  end
end

这种语言看起来有点像 Ruby，但这种相似性只是表面的；语法是用特别的 Treetop 语言写出来的。关键字 rule 为分析一种特定种类的语法引入一个新的规则，并且每个规则里的表达式描述了它将要识别的字符串结构。规则可以递归地调用其他规则——例如 while 规则调用表达式（expression）规则和语句（statement）规则——而且分析从第一条规则开始，这是这种语法中的语句。

这些表达式语法规则彼此调用的顺序反应了 Simple 运算符的优先级。表达式语法调用less_than，然后 less_than 立即调用 multiply，在 less_than 对优先级更低的运算符< 进行匹配之前，multiply 能在字符串中匹配到 *运算符。这确保表达式'1 * 2 < 3'被解析成 «(1 * 2) < 3» 而不是 «1 * (2 < 3)»。

为了让事情简单，这个语法没有试图限制可以在一种表达式中出现的另一种表达式种类，这意味着这个表达式将会接受一些明显错误的程序。

例如，对于二元表达式less_than和 multiply，我们设定了两个规则——但是分别设立两个规则的唯一原因是为了强调运算符的优先级，这样每一个规则只要求一个更高优先级的规则匹配其左侧运算对象，然后同样或者更高优先级的规则匹配其右侧运算对象。这将使像 '1 < 2 < 3' 这样的字符串能成功通过解析，即便 Simple 的语义无法赋予这个表达式结果一个含义。

这些问题中有一些可以通过对语法稍作调整得以解决，但是总会有其他一些不正确的情况语法解析器不能识别。这一问题我们将分成两个关注点，首先保持语法解析器尽可能的自由，其次将在第 9 章使用一个不同的技术来检测无效的程序。

语法中大多数的规则都使用外边带上括号的 Ruby 代码标注。在每一个括号里，代码都定义一个叫 #to_ast 的方法，在解析一个 Simple 程序的时候，它能用在由 Treetop 构建的对应语法对象上。

如果把这个语法保存到叫作simple.treetop的文件里，我们可以使用 Treetop 加载它来生成一个 SimpleParser 类。这个解析器可以把一个由 Simple 源代码组成的字符串转换成由Treetop 的 SyntaxNode 对象构建出来的一个表示：

>> require 'treetop'
=> true
>> Treetop.load('simple')
=> SimpleParser
>> parse_tree = SimpleParser.new.parse('while (x < 5) { x = x * 3 }')
=> SyntaxNode+While1+While0 offset=0, "...5) { x = x * 3 }" (to_ast,condition,body):
  SyntaxNode offset=0, "while ("
    SyntaxNode+LessThan1+LessThan0 offset=7, "x < 5" (to_ast,left,right):
    SyntaxNode+Variable0 offset=7, "x" (to_ast):
      SyntaxNode offset=7, "x"
        SyntaxNode offset=8, " < "
      SyntaxNode+Number0 offset=11, "5" (to_ast):
      SyntaxNode offset=11, "5"
        SyntaxNode offset=12, ") { "
      SyntaxNode+Assign1+Assign0 offset=16, "x = x * 3" (to_ast,name,expression):
      SyntaxNode offset=16, "x":
        SyntaxNode offset=16, "x"
          SyntaxNode offset=17, " = "
        SyntaxNode+Multiply1+Multiply0 offset=20, "x * 3" (to_ast,left,right):
        SyntaxNode+Variable0 offset=20, "x" (to_ast):
            SyntaxNode offset=20, "x"
        SyntaxNode offset=21, " * "
        SyntaxNode+Number0 offset=24, "3" (to_ast):
            SyntaxNode offset=24, "3"
    SyntaxNode offset=25, " }"

这个 SyntaxNode 结构是一个具体语法树：它专门为了Treetop 的处理而设计，并且含有关于这个具体语法树的节点是如何与生成它们的原始代码关联起来的大量信息。下面是Treetop 文档（http://treetop.rubyforge.org/using_in_ruby_html）不得不说的一些话：

请不要尝试自己向下遍历语法树，并且不要把这棵树的结构作为你自己常用的数据结构。它包含的节点比你应用程序所需要的要多得多，甚至为输入的每个字符都分配一个还绰绰有余。

但是，你可以为根规则增加方法，根规则以一种合理的格式返回你需要的信息。每个规则可以调用它的子规则，并且从外面尝试遍历树时，利用这些遍历语法树的方法是一个非常好的选择。

这就是我们已经做到的。我们没有直接操纵这棵乱糟糟的树，而是使用语法中的标记在每个节点上定义一个#to_ast方法。如果在根节点上调用这个方法，它会根据 Simple 的语法对象构建一棵抽象语法树。

>> statement = parse_tree.to_ast
=> «while (x < 5) { x = x * 3 }»

这样我们已经自动地把源代码转换成了一棵抽象语法树，并且现在可以使用这棵树以通常的方式查看程序的含义了：

>> statement.evaluate({ x: Number.new(1) })
=> {:x=>«9»}
>> statement.to_ruby
=> "-> e { while (-> e { (-> e { e[:x] }).call(e) < (-> e { 5 }).call(e) }).call(e);
e = (-> e { e.merge({ :x => (-> e { (-> e { e[:x] }).call(e) * (-> e { 3 }).call(e)
}).call(e) }) }).call(e); end; e }"

这个解析器和 Treetop 通常还有一个缺点，就是生成一个右结合的具体语法树。这意味着字符串'1 * 2 * 3 * 4'被解析时会被当成：'1 * (2 * (3 * 4))'：

> expression = SimpleParser.new.parse('1 * 2 * 3 * 4', root: :expression).to_ast => «1 * 2 * 3 * 4»
> expression.left
=> «1»
> expression.right
=> «2 * 3 * 4»

但是乘法通常是左结合的：写'1 * 2 * 3 * 4'的时候，我们实际的意思是'((1 * 2) * 3) * 4'，这里数字是从表达式的左边（而非右边）开始分组结合的。对乘法来说这没什么关系——求值的时候两种方式会产生同样的结果——但对像减法和除法这样的运算就有问题了，因为对 «((1 - 2) - 3) - 4»求值的结果与对 «1 - (2 - (3 - 4))»求值的结果并不相同。

为了修正这个缺点，我们不得不让这些规则和 #to_ast 实现得更加复杂一些。参考 6.2.3 节，那里有构建左结合 AST 的 Treetop 语法。

能够像这样解析 Simple 程序很方便，但是因为困难的工作都由 Treetop 做了，所以我们对一个语法解析器实际如何工作并没有了解多少。在 4.3 节，你将会看到如何直接地实现一个解析器。