ruby - treetop 语法无限循环

我曾想过一种关于新编程语言的想法，所以我想尝试一下它。一位 friend 建议我尝试使用Treetop(Ruby gem )创建解析器。 Treetop的文档很少，而且我以前从未做过这种事情。

我的解析器的行为就像是其中有一个无限循环，但是没有堆栈跟踪。事实证明很难追查。有人可以指出我入门级解析/AST指南的方向吗？我真的需要一些列出规则，常用用法等内容的工具来使用Treetop之类的工具。我的语法分析器位于GitHub上，以防有人希望帮助我改进它。

class {
  initialize = lambda (name) {
    receiver.name = name
  }

  greet = lambda {
    IO.puts("Hello, #{receiver.name}!")
  }
}.new(:World).greet()

最佳答案

我要求 treetop 将您的语言编译成.rb文件。这给了我一些启发:

$ tt -o /tmp/rip.rb /tmp/rip.treetop

然后，我使用了这个小 stub 来重新创建循环:

require 'treetop'
load '/tmp/rip.rb'
RipParser.new.parse('')

这挂了。现在，那不是很有趣!空字符串可以重现行为，就像问题中的十几行示例一样。

为了弄清它的挂起位置，我使用了一个Emacs键盘宏来编辑rip.rb，并在每个方法的入口添加了一条调试语句。例如:

def _nt_root
  p [__LINE__, '_nt_root'] #DEBUG
  start_index = index

现在我们可以看到循环的范围:

[16, "root"]
[21, "_nt_root"]
[57, "_nt_statement"]
...
[3293, "_nt_eol"]
[3335, "_nt_semicolon"]
[3204, "_nt_comment"]
[57, "_nt_statement"]
[57, "_nt_statement"]
[57, "_nt_statement"]
...

从那里进行的进一步调试显示，整数可以是空字符串:

rule integer
   digit*
end

这间接地允许一个语句为空字符串，并且顶层规则statement*永远消耗空语句。将*更改为+可以修复循环，但会发现另一个问题:

/tmp/rip.rb:777:in `_nt_object': stack level too deep (SystemStackError)
        from /tmp/rip.rb:757:in `_nt_compound_object'
        from /tmp/rip.rb:1726:in `_nt_range'
        from /tmp/rip.rb:1671:in `_nt_special_literals'
        from /tmp/rip.rb:825:in `_nt_literal_object'
        from /tmp/rip.rb:787:in `_nt_object'
        from /tmp/rip.rb:757:in `_nt_compound_object'
        from /tmp/rip.rb:1726:in `_nt_range'
        from /tmp/rip.rb:1671:in `_nt_special_literals'
         ... 3283 levels...

范围通过special_literals，literal_object，object和compound_object间接向左递归。面对左递归的 treetop 吃了很多东西直到吐出来。我没有快速解决该问题的方法，但是至少从现在开始您要进行堆栈跟踪。

另外，这不是您的直接问题，但是digit的定义很奇怪:它可以是一个数字或多个数字。这导致digit*或digit+允许(可能是)非法整数1________2。