如何处理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

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