antlr - 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) 的任何其他原因。

Answer 2

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

第 262 页