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

你的语法是左递归的:即一个 expression 可以立即是一个 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