我脑子里浮现出一些关于新编程语言的想法,所以我想我会尝试实现它。一位朋友建议我尝试使用 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
然后我用这个小存根来重新创建循环:
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、对象和compound_object间接左递归的。 树梢,当面对左递归时,吃堆直到它呕吐。 我没有针对该问题的快速解决方案,但至少您现在有一个堆栈跟踪。
此外,这不是您眼前的问题,但digit
的定义很奇怪:它可以是一位数,也可以是多个数字。 这会导致digit*
或digit+
允许(大概)非法整数1________2
。
我真的很喜欢Parr的语言实现模式;自从Parr创建了ANTLR解析器生成器以来,它是他在整本书中使用的工具,但它应该足够简单,可以从中学习。
我真正喜欢的是每个示例在前一个示例的基础上发展的方式;他不是从一个巨大的支持AST的解析器开始的,而是慢慢引入需要越来越多的"后端智能"来完成这项工作的问题,因此这本书可以很好地与需要解析的语言一起扩展。
我希望它更深入地涵盖的是人们可以编写的语言类型,并在设计语言时就该做和不该做提供建议。我见过一些语言,解析起来非常痛苦,我想知道更多关于可能以不同方式做出的设计决策。