Treetop语法无限循环

我对于在我头脑中浮动的新编程语言有了一些想法，所以我认为我会在实现它的过程中采取一些措施。一位朋友建议我尝试使用Treetop（Ruby gem）创建解析器。 Treetop的文档很少，我从来没有做过这种事情。Treetop语法无限循环

我的解析器的行为就像它有一个无限循环，但没有堆栈跟踪;事实证明难以追查。有人可以将我指向入门级解析/ AST指南吗？我真的需要列出规则，常见用法等，以便使用像Treetop这样的工具。我的解析器语法为GitHub，以防有人希望帮助我改进它。

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

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

来源

2011-05-24 ravinggenius

我真的很喜欢Language Implementation Patterns by Parr;因为Parr创建了解析器生成器ANTLR，这是他在整本书中使用的工具，但它应该足够简单，以便从中学习。

我真正喜欢的是每个例子在前一个例子上的增长方式;他并没有从一个巨大的支持AST的解析器开始，而是慢慢地引入了需要越来越多“后端智能”来完成这项工作的问题，所以这本书可以很好地与需要解析的语言一起扩展。

我想什么它更深入一点覆盖的是类型的人能书写和提出建议的可为和不做的设计时语言的语言。我看到一些语言是一个巨大的解析痛苦，我希望更多地了解可能做出不同的设计决策。

来源

2011-05-24 01:43:33 sarnold

我看了第一个五六个教程视频，但到目前为止，我还没有能够得到一个工作安装程序。你是正确的，他没有开始太快。我会再给ANTLR一次尝试。 – ravinggenius 2011-05-24 15:16:31

@好吧，我喜欢你的'treetop'语法的外观，如果你想用Ruby编程，那么切换到ANTLR将无济于事。 :)我只是觉得他的书在讨论如何构建优秀的解析器方面表现出色，ANTLR是他选择使用的工具。 – sarnold 2011-05-24 20:44:37

我问treetop将您的语言编译成.rb文件。这给了我的东西钻进去：

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

然后我用这个小存根重新循环：

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

这间接地允许语句是一个空字符串，并且顶级规则永远消耗空语句。更改*到+修复的循环，但揭示了另外一个问题：

/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，对象和compound_object。 Treetop在面临左递归时会一直吃下去，直到它呕吐。我没有解决这个问题的快速解决方案，但至少你已经有了一个从现在开始的堆栈跟踪。

此外，这不是你的直接问题，但digit的定义很奇怪：它可以是一个数字，也可以是多个。这导致digit*或digit+允许（推测）非法整数1________2。

来源

2011-05-24 10:32:40

哇，非常感谢！我更新了有关数字的语法，但我不确定左递归。在继续之前，我必须多做一点教育。 – ravinggenius 2011-05-24 15:13:34

@保留G.我很高兴这对你有用，对不起，我不能给你更具体的建议。我所知道的关于左递归和Treetop的一切都在这里：http://treetop.rubyforge.org/pitfalls_and_advanced_techniques.html。一个新的问题，“如何处理树顶左递归”可能是好的。 – 2011-05-24 19:01:10

你运行了什么命令来获取堆栈跟踪？我一直在尝试我能想到的一切，但我无法获得比一个更长的踪迹。 – ravinggenius 2011-05-24 19:28:55

Treetop语法无限循环

回答

相关问题