ANTLR:回溯和前瞻的区别？

Question

我对 ANTLR 比较陌生。我有一个非常简单的语法:

start   :
('A' 'B' 'C' '1'
|'A' 'B' 'C' '2' 
|'A' 'B' 'C' '3'
)
;

我想我已经理解了前瞻和回溯(它与句法谓词一起工作)概念的基础知识。所以这个语法适用于 k=4 或 backtrack=true。但确切的区别是什么，主要问题是我什么时候使用什么？我试图在互联网上找到答案，但没有成功。

Answer 1

您的语法适用于 ANTLR v3，无需任何选项。

k 选项将 ANTLR 限制为经典的 LL(k) 解析。回溯意味着 - 如果解析器无法预测要使用哪个规则，它只会尝试、回溯并再次尝试。
当 ANTLR 无法为给定的语法构建前瞻 DFA 时，您应该使用回溯选项。 ANTLR v3 可以很容易地从正则表达式构建 DFA，但它在递归规则方面存在困难。例如，这个语法有效:

start: recursive_rule ';'
     | recursive_rule ':'
     ;

recursive_rule : (ID)* '%'
               ;

下面的语法是相同的，但通过递归表示。 ANTLR 无法为其构建 DFA(我实际上不知道为什么)，因此您需要打开回溯:

start options {backtrack=true;} : recursive_rule ';'
                                | recursive_rule ':'
                                ;

recursive_rule : ID recursive_rule
               |'%'
               ;

k 选项用于提高解析器性能。我不知道将 LL(*) 限制为 LL(k) 的任何其他原因。