ANTLR：回溯和向前查看之间有什么区别？

Question

我是一个相对新手，对于ANTLR不是很熟悉。我有一个非常简单的语法：

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

我认为我已经理解了向前和回溯的概念基础（这与语法谓词一起工作）。所以，该语法适用于k=4或backtrack=true。但是，确切的区别是什么，主要问题是何时使用什么？我尝试在互联网上找到答案，但没有成功。

- Veilchen4ever

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）的其他原因。

- Andy

---

谢谢。我会尝试使用递归规则来更好地理解它。但现在我有一个想法。谢谢。 - Veilchen4ever

你能解释一下第二个递归示例吗？因为我认为那不是一个左递归规则，ANTLR应该能够处理它吧？ - xi.lin

Answer 2

我在书籍《The definitive Antlr Reference》中找到了一个理论描述，对于我的问题很重要。也许对于其他类似问题的人来说，这本书的这一段内容也会有所帮助。 第262页。

- Veilchen4ever