ruby - 树顶语法无限循环

Question

我脑子里浮现出一些关于一种新编程语言的想法，所以我想我会尝试实现它。一位 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()

Answer 1

我要求 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...

Range 通过 special_literals、literal_object、object 和 compound_object 间接地左递归。 Treetop 在面对左递归时，会吃掉堆栈直到它吐出来。我没有针对该问题的快速解决方案，但至少您从现在开始有一个堆栈跟踪。

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