antlr3 - 由于递归规则调用，使用 Antlr3 解析嵌套列表，非 LL(*) 决策

Question

我有以下语法来使用 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;};

我无法找出导致错误的原因或如何消除错误：

'/ListParseTest/src/ListParse.g:17:13: [fatal] 规则 list_element 具有非 LL(*) 决定，因为可以从 alts 1,2 访问递归规则调用。通过左分解或使用句法谓词或使用 backtrack=true 选项来解决。|---> 列表元素：'

我认识到这与list,list_element和之间的递归关系有关tree_，但我无法解决问题。

有人可以帮忙吗？

Answer 1

问题是由于输入的性质导致决定采用哪条规则并不总是立即可行。（nil 可以是新列表的开始，也可以是新树的开始）。

解决方案是启用“回溯”选项，当解析器意识到它走错了路径时，它允许解析器自行返回。

这是通过添加

backtrack=true; 

到语法选项。