Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

ANTLR: Difference between backtrack and look-ahead?

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.

like image 801
Veilchen4ever Avatar asked Nov 16 '12 10:11

Veilchen4ever


2 Answers

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).

like image 113
Andy Avatar answered Sep 20 '22 18:09

Andy


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.

Snippet from the Book "The definitive Antlr Reference"

Page 262

like image 23
Veilchen4ever Avatar answered Sep 20 '22 18:09

Veilchen4ever