ANTLR:回溯与前瞻之间的区别？

Question

我是ANTLR的新手.我有一个非常简单的语法:

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

我认为我已经理解了前瞻和后退概念的基础知识(它与句法谓词一起使用).所以这个语法适用于k = 4或backtrack = true.但究竟是什么区别,主要问题是我何时使用什么？我试图在互联网上找到答案,但没有成功.

Answer 1

您的语法可以在 ANTLR v3 中运行，无需任何选项。

\n\n

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

\n\n

start: recursive_rule ';'\n     | recursive_rule ':'\n     ;\n\nrecursive_rule : (ID)* '%'\n               ;\n

\n\n

下面的语法是相同的，但是通过递归来表达。ANTLR无法为其构建DFA（我实际上不知道为什么），所以你需要打开回溯：

\n\n

start options {backtrack=true;} : recursive_rule ';'\n                                | recursive_rule ':'\n                                ;\n\nrecursive_rule : ID recursive_rule\n               |'%'\n               ;\n

\n\n

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

\n

Answer 2

我在《The definve Antlr Reference》一书中找到了对我的问题的理论描述，这对我的理解也很重要。也许其他一些问自己类似问题的人也会对本书的这个片段有所帮助。

第262页