递归树顶不起作用

发布于 2024-11-23 22:13:07 字数 461 浏览 2 评论 0原文

我正在尝试使用 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 指定此类递归定义的正确方法是什么？

原文

I'm trying to create a parser using Treetop that is somewhat recursive. An expression can be a number but it also can be an addition of expressions, so I wrote this:

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

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

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

  # space
  rule _
   ' '*
  end
end

That just doesn't work. Any time I'm trying to parse anything I get an exception "SystemStackError: stack level too deep" (stack overflow! yay!). Any ideas why? what's the correct way to specify such a recursive definition with Treetop?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

何以笙箫默 2024-11-30 22:13:07

您的语法是左递归的：即表达式可以立即成为加法，而加法又可以是表达式等。导致解析器进入无限循环。

尝试这样的事情（未经测试！）：

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

You grammar is left-recursive: i.e. a expression can immediately be an addition which in its turn can be an expression etc. causing the parser to go in an infinite loop.

Try something like this instead (untested!):

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

回复收藏 0 原文

~没有更多了~