Parsing a nested list with Antlr3, non-LL(*) decision due to recursive rule invocations

0
votes

I have the following grammar to parse a nested list using Antlr3

parse:
list
;

list:
LBRACK list_element* RBRACK
;

list_element:
tree_ | list
; 

tree_:
node | ATOM
;

node:
LBRACK tree_ SEPARATOR tree_ RBRACK 
;

ATOM: 'nil';
LBRACK: '(';
RBRACK:  ')';
SEPARATOR: '.'; 

WS : (' ' | '\f' | '\r' | '\n' | '\t')+{$channel = HIDDEN;};

I can't find out what is causing, or how to remove the error:

'/ListParseTest/src/ListParse.g:17:13: [fatal] rule list_element has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2. Resolve by left-factoring or using syntactic predicates or using backtrack=true option. |---> list_element: '

I recognize it has something to do with the recursive relationships between list, list_element and tree_, but I am not able to solve the problem.

Can anybody help?

1
antlr3left-recursion

1 Answers

0
votes

The problem is due to the nature of the input leading to a decision on which rule to take not always being immediately possible. (nil could either be the start of a new list, or the start of a new tree).

The solution is to enable the 'backtracking' option, which allows the parser to go back on itself when it realizes it has taken the wrong path.

This is achieved by adding 

backtrack=true;

to the grammar options.