ruby - 递归树梢不起作用

Question

我正在尝试使用有点递归的 Treetop 创建一个解析器。表达式可以是数字，但也可以是表达式的加法，所以我写了这个：

grammar Language
  rule expression
    "(" _ expression _ ")" / addition / integer 
  end

  rule addition
    expression _ "+" _ expression
    /
    expression _ "-" _ expression
  end

  rule integer
    '-'? _ [0-9]+
  end

  # space
  rule _
   ' '*
  end
end

那是行不通的。每当我试图解析任何东西时，我都会得到一个异常“SystemStackError：堆栈级别太深”（堆栈溢出！耶！）。任何想法为什么？用 Treetop 指定这种递归定义的正确方法是什么？

Answer 1

您的语法是左递归的：即 aexpression可以立即成为 an addition，而后者又可以是expression等。导致解析器进入无限循环。

试试这样的东西（未经测试！）：

grammar Language

  rule expression
    addition
  end

  rule addition
    multiplication (_ [+-] _ multiplication)*
  end

  rule multiplication
    unary (_ [*/%] _ unary)*
  end

  rule unary
    "-"? _ atom
  end

  rule atom
    number / "(" _ expression _ ")"
  end

  rule number
    float / integer
  end

  rule float
    [0-9]+ "." [0-9]+
  end

  rule integer
    [0-9]+
  end

  rule _
    ' '*
  end

end