Question

既然已经有了工作语义，我们就通过为lambda 演算表达式构建一个语法解析器来结束工作。像往常一样，我们可以使用Treetop 来写语法：

grammar LambdaCalculus
  rule expression
    calls / variable / function
  end

  rule calls
    first:(variable / function) rest:('[' expression ']')+ {
      def to_ast
        arguments.map(&:to_ast).inject(first.to_ast) { |l, r| LCCall.new(l, r) }
  end

  def arguments
    rest.elements.map(&:expression)
  end
  }
end

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

  rule function
    '-> ' parameter:[a-z]+ ' { ' body:expression ' }' {
    def to_ast
      LCFunction.new(parameter.text_value.to_sym, body.to_ast)
    end
  }
  end
end

就像在2.6 节中讨论的那样，Treetop 语法一般会产生右结合的树，因此为了适应lambda 演算的左结合函数调用语法，这个语法得做一些额外的工作。这个调用匹配一个或者多个连续的调用（如a[b][c][d]），而得到的具体语法树节点的#to_ast方法使用Enumerable#inject把这些调用的参数转成一个左结合的抽象语法树。

这个解析器和操作语义一起给出了lambda 演算的完整实现，这允许我们读取表达式并对其求值：

>> require 'treetop'
=> true
>> Treetop.load('lambda_calculus')
=> LambdaCalculusParser
>> parse_tree = LambdaCalculusParser.new.parse('-> x { x[x] }[-> y { y }]')
=> SyntaxNode+Calls2+Calls1 offset=0, "...}[-> y { y }]" (to_ast,arguments,first,rest):
  SyntaxNode+Function1+Function0 offset=0, "... x { x[x] }" (to_ast,parameter,body):
    SyntaxNode offset=0, "-> "
    SyntaxNode offset=3, "x":
      SyntaxNode offset=3, "x"
    SyntaxNode offset=4, " { "
    SyntaxNode+Calls2+Calls1 offset=7, "x[x]" (to_ast,arguments,first,rest):
      SyntaxNode+Variable0 offset=7, "x" (to_ast):
        SyntaxNode offset=7, "x"
      SyntaxNode offset=8, "[x]":
        SyntaxNode+Calls0 offset=8, "[x]" (expression):
          SyntaxNode offset=8, "["
          SyntaxNode+Variable0 offset=9, "x" (to_ast):
            SyntaxNode offset=9, "x"
          SyntaxNode offset=10, "]"
      SyntaxNode offset=11, " }"
  SyntaxNode offset=13, "[-> y { y }]":
    SyntaxNode+Calls0 offset=13, "[-> y { y }]" (expression):
      SyntaxNode offset=13, "["
      SyntaxNode+Function1+Function0 offset=14, "... { y }" (to_ast,parameter,body):
        SyntaxNode offset=14, "-> "
        SyntaxNode offset=17, "y":
          SyntaxNode offset=17, "y"
        SyntaxNode offset=18, " { "
        SyntaxNode+Variable0 offset=21, "y" (to_ast):
          SyntaxNode offset=21, "y"
        SyntaxNode offset=22, " }"
      SyntaxNode offset=24, "]"
>> expression = parse_tree.to_ast
=> -> x { x[x] }[-> y { y }]
>> expression.reduce
=> -> y { y }[-> y { y }]