5

我对一种新的编程语言有一些想法在我脑海中浮现，所以我想我会尝试实现它。一位朋友建议我尝试使用 Treetop（Ruby gem）来创建解析器。Treetop 的文档很少，我以前从未做过这种事情。

我的解析器表现得好像它有一个无限循环，但没有堆栈跟踪；事实证明很难追踪。有人可以向我指出入门级解析/AST 指南的方向吗？我真的需要一些列出规则、常见用法等的东西来使用 Treetop 之类的工具。我的解析器语法在GitHub 上，以防有人希望帮助我改进它。

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

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

2 回答 2

8

我让 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

这间接允许语句为空字符串，并且顶级规则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。

于 2011-05-24T10:32:40.387 回答
1

我真的很喜欢Parr 的语言实现模式；由于 Parr 创建了ANTLR解析器生成器，它是他在整本书中使用的工具，但它应该足够简单，可以从中学习。

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

我希望它更深入地介绍一下人们可以编写的语言类型，并在设计语言时就该做和不该做的事情提供建议。我见过一些语言很难解析，我想更多地了解可能会做出不同的设计决策。

于 2011-05-24T01:43:33.703 回答