Ruby解析与列表推导式实现

### Ruby 解析与列表推导式实现 #### 1. 解析代码尝试与左递归问题 在 Ruby 中进行解析时，我们可能会尝试编写如下代码： ```ruby require 'rubygems' require 'rparsec' module Dot extend Parsers class AST < Struct; end AST.new("Integer", :value) AST.new("Call", :target, :name) Dot = string(".") Word = word Integer = integer.map{|x| AST::Integer.new(x) } Call = sequence(lazy{Expr}, Dot, Word){|expr, dot, name| AST::Call.new(expr, name) } Expr = alt(Call, Integer) Parser = Expr << eof end Dot::Parser.parse("4.inc.recip") ``` 运行这段代码，会立即收到 “stack level too deep (SystemStackError)” 的错误信息。这是因为递归下降解析器从左到右解析输入，而这里出现了左递归循环。`Expr` 可以以 `Call` 开头，而 `Call` 又以 `Expr` 开头，这会导致递归下降解析器无限循环。即使重新排列 `Expr` 中 `alt` 的元素也无济于事，将 `Integer` 放在首位只会导致它被消耗，然后由于需要 `eof` 而抛出额外输入的错误。 #### 2. 消除左递归 可以将左递归语法转换为非左递归语法。原语法如下： ```plaintext Call = Expr "." Word Expr = Call | Integer ``` 转换后的语法： ```plaintext Call = "." Word CallChain CallChain = Call | Empty Expr = Integer CallChain ``` 其中，`Empty` 是一个特殊的解析器，它总是匹配且不消耗输入。以下是 Ruby 代码实现： 递归版本： ```ruby Empty = string("").map{|x| nil } Call = sequence(Dot, Word, lazy{CallChain}) CallChain = alt(Call, Empty) Expr = sequence(Integer, CallChain) ``` 使用 `many` 的简化版本： ```ruby CallChain = sequence(Dot, Word).many Expr = sequence(Integer, CallChain) ``` 不过，新的版本在构建抽象语法树（AST）时更复杂，因为 `Call` 匹配后难以访问方法调用的目标。可以通过返回 `proc` 对象来解决这个问题： ```ruby Empty = string("").map{|x| nil } Call = sequence(Dot, Word, lazy{CallChain}) do |dot, method_name, chain| proc do |target| call = AST::Call.new(target, method_name) return call if chain.nil? chain[call] end end CallChain = alt(Call, Empty) Expr = sequence(Integer, CallChain) do |expr, chain| return expr if chain.nil? chain[expr] end ``` 为了简化构建 AST，建议使用 `many` 版本： ```ruby CallChain = sequence(Dot, Word).many Expr = sequence(Integer, CallChain) do |expr, chain| chain.inject(expr){|chain, name| AST::Call.new(chain, name.to_sym) } end ``` #### 3. 列表推导式中的方法调用 ##### 3.1 无参数方法调用 首先编写单元测试： ```ruby def test_method_call answer = AST::Call.new(AST::Call.new(AST::Integer.new(1), :baz), :grr) result = Expr.parse("1.baz.grr") assert_equal(answer, result) end ``` 实现代码如下： ```ruby Literal = alt(Symbol, Number, String1, String2, Variable) Dot = string(".") CallChain = sequence(Dot, Word).many Expr = sequence(Literal, CallChain) do |expr, chain| chain.inject(expr){|target, name| AST::Call.new(target, name) } end ``` #####