如何删除以下语法中的左递归? [英] How to remove left-recursion in the following grammar?

问题描述

不幸的是，当规则传递了参数时， ANTLR 无法支持直接左递归.唯一可行的选择是删除左递归.有没有一种方法可以消除以下语法中的左递归?

Unfortunately, it is not possible for ANTLR to support direct-left recursion when the rule has parameters passed. The only viable option is to remove the left recursion. Is there a way to remove the left-recursion in the following grammar ?

a[int x]
    : b a[$x] c
    | a[$x - 1] 
    (
          c a[$x - 1]
        | b c
    )
    ;

---

问题出在第二种选择中，涉及左递归.任何帮助将不胜感激.

---

The problem is in the second alternative involving left recursion. Any kind of help would be much appreciated.

推荐答案

没有参数且格式更简单，它看起来像这样:

Without the parameters and easier formatting, it would look like this:

a
 : b a c
 | a (c a | b c)
 ;

当a的左递归替代项匹配 n 次时，这仅表示(c a | b c)将匹配 n 次，并在前面加上终止b a c(第一种选择).这意味着该规则将始终以b a c开头，然后出现零个或多个(c a | b c):

When a's left recursive alternative is matched n times, it would just mean that (c a | b c) will be matched n times, pre-pended with the terminating b a c (the first alternative). That means that this rule will always start with b a c, followed by zero or more occurrences of (c a | b c):

a
 : b a c (c a | b c)*
 ;

这篇关于如何删除以下语法中的左递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！