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

（这是一般递归消除的特例）。