I'm trying to make a parser rule to recognise type specifiers for my language. This is the rule I have:
type: TYPE | type '[' numexpr? ']' | MAP '(' TYPE ',' type ')';
TYPE : 'int'|'float'|'bool'|'string';
MAP: 'map'
With this I'm trying to parse expressions like:
int
float[]
float[][][][][5][4][3]
map(string, int[][])
map(map(string,int), map(int[][], int[]))
But Antlr tells me:
error(210): The following sets of rules are mutually left-recursive [type]
I'm not entirely sure on what's the problem, though, because I see no ambiguity in my rules and left recursion only happens on the array case.
I'm not only interested in knowing how to fix this but telling what's going on, and where is the left recursion a problem exactly in this case.
Left recursion occurs when you have a non-terminal A that can be derived through any number of steps towards something with that same non-terminal as its' left most token.
For example: A->*Aa (see more information here: http://en.wikipedia.org/wiki/Left_recursion)
In your case, the problem is with the second clause of the first derivation rule:
type -> type '[' numepr? ']'
Imagine trying to write a program which parses this. It will go something like:
ParseResult parseType(expr) {
match(parseType(expr));
//... other matches
}
As you can see, you're getting an endless recursion. Of course this is only an issue with LL parsers. If you're using a LL parser, you should rewrite your rules to avoid left recursions. For instance and just off the top of my head:
type: TYPE arraybrackets
arraybrackets: '[' numexr? ']' arraybrackets |