如何处理Treetop左递归

Question

我正在尝试构建一种新的通用编程语言，我有一个grammar file。我正在努力让这门语言变得健壮和易于使用(它的灵感主要来自Ruby等)，并在此过程中引入了一些左递归规则。

我看过一些例子，它们似乎表明了下面的左递归规则：

rule l_recurse
  l_recurse / 'something else'
end

可以通过将其更改为：

rule r_recurse
  'something else' / r_recurse
end

对我来说，这看起来像是有一个不同的问题，仍然会失败。我说的对吗，或者这“就是工作”吗？

在这个grammar file中可以找到我试图(查找和)消除的特定左递归。我不确定哪些规则会受到影响，但至少some were pointed out有左递归。(顺便说一句，我已经试图通过收紧range的规则来消除他提到的特定范围问题。)

Answer 1

特殊情况

rule l_recurse
  l_recurse / 'something else'
end

简化为

rule l_recurse
   'something_else'
end

(正确的递归规则也是如此)，因此我需要查看您的特定示例，以找出您想要了解的内容。this question的答案给出了左递归消除的一般规则。

lists是典型的易于删除的左递归案例之一：

rule l_list
    item | l_list ',' item
end

它可以改为右递归。

rule r_list
    item r_tail?
end

rule r_tail
    ',' r_list
end

(这是一般递归消除的一种特殊情况)。