类型说明符语法中的相互左递归

Question

我正在尝试制定一个解析器规则来识别我的语言的类型说明符。这是我的规则：

type: TYPE | type '[' numexpr? ']' | MAP '(' TYPE ',' type ')';

TYPE : 'int'|'float'|'bool'|'string';

MAP: 'map'

有了这个，我试图解析像这样的表达式：

int
float[]
float[][][][][5][4][3]
map(string, int[][])
map(map(string,int), map(int[][], int[]))

但是 Antlr 告诉我：

error(210):  The following sets of rules are mutually left-recursive [type]

不过，我不完全确定问题出在哪里，因为我发现我的规则没有歧义，左递归只发生在数组的情况下。

我不仅想知道如何解决这个问题，而且想知道发生了什么，在这种情况下，左递归究竟在哪里是个问题。

Answer 1

左递归发生在你有一个非终结符 A 时，它可以通过任意数量的步骤派生到与它的最左边标记相同的非终结符的东西。

例如：A->*Aa （在此处查看更多信息：http://en.wikipedia.org/wiki/Left_recursion）

在你的情况下，问题出在第一个推导规则的第二个子句上：

类型 -> 输入“[”数字？ ']'

想象一下，尝试编写一个程序来解析它。它会是这样的：

ParseResult parseType(expr) {
     match(parseType(expr));
     //... other matches
}

如您所见，您将获得无限递归。当然，这只是 LL 解析器的问题。如果您使用的是 LL 解析器，则应该重写规则以避免左递归。例如，就在我的脑海中：

类型：TYPE arraybrackets

arraybrackets: '[' numexr? ']' 数组括号 |

Mutual left recursion in type specifier grammar