如何处理Treetop左递归

Question

我有一个用于新的通用编程的 语法文件我正在尝试构建的语言。我试图使该语言变得健壮且易于使用（它很大程度上受到 Ruby 等的启发），为此我引入了一些左递归规则。

我看到一些例子似乎表明了以下左递归规则：

rule l_recurse
  l_recurse / 'something else'
end

可以通过将其更改为非左递归规则：

rule r_recurse
  'something else' / r_recurse
end

对我来说，这看起来会遇到不同的问题并且仍然会失败。我是对的，还是这“有效”？

我试图（查找和）消除的特定左递归可以在 语法文件。我不确定哪些规则受到影响，但至少一些规则被指出已经离开-递归。 （顺便说一句，我试图通过收紧范围规则来消除他提到的特定范围问题。）

Answer 1

特定情况

rule l_recurse
  l_recurse / 'something else'
end

简化为

rule l_recurse
   'something_else'
end

（正确的递归规则也是如此），所以我需要查看您的具体示例以找出您想知道的内容。 这个问题的答案给出了左递归消除的一般规则。

典型的易于消除的左递归情况之一是列表：

rule l_list
    item | l_list ',' item
end

并且可以将其更改为右递归

rule r_list
    item r_tail?
end

rule r_tail
    ',' r_list
end

（这是一般递归消除的特殊情况）。