使用 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 由于可从 ALT 1,2 访问递归规则调用，因此具有非 LL（*） 决策。 通过左分解或使用语法谓词或使用 backtrack=true 选项来解决。 |---> list_element： '

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

有人可以帮忙吗？

Answer 1

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

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

这是通过添加

backtrack=true; 

到语法选项。