如何删除以下语法中的左递归? [英] 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 次时，这意味着 (ca | bc) 将被匹配 n 次，前面加上终止的 bac(第一个选项).这意味着这条规则总是以 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屋！