ANTLR: Difference between backtrack and look-ahead?

Question

I relative new to ANTLR. I have an very easy grammar:

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

I think that I already understand the basics of the concept of look ahead and backtracking (which works with syntactic predicates). So this grammar works with k=4 or with backtrack=true. But what is the exact difference and the main question is when do I use what? i tried to find the answer on the internet but didn't succeded.

Answer 1

Your grammar works in ANTLR v3 without any options.

The k option limits ANTLR to classical LL(k) parsing. Backtracking means - if the parser cannot predict, which rule to use, it just tries, backtracks and tries again. The backtracking option you should use when ANTLR cannot build look-ahead DFA for the given grammar. ANTLR v3 can build DFAs from regular expressions pretty easy, but it has its difficulties with recursive rules. For example, this grammar works:

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

recursive_rule : (ID)* '%'
               ;

This grammar below is the same, but expressed through recursion. ANTLR cannot build DFA for it (I actually don’t know why), so you need to switch backtracking on:

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

recursive_rule : ID recursive_rule
               |'%'
               ;

The k option is used to improve the parser performance. I don’t know any other reason for restricting LL(*) to LL(k).

Answer 2

I found a theoretical description to my question in the Book "The definitve Antlr Reference", which was also important for my understanding. Maybe some others who asks themselves similar question would help this snippet of the book too.

Page 262