Geek Answers Handbook

ANTLR: Difference between backtrack and look-ahead?

I relative new to ANTLR. I have a very simple grammar:

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

I think I already understand the basics of the concept of looking forward and backward (which works with syntactic predicates). Thus, this grammar works with k = 4 or with backtrack = true. But what is the exact difference and the main question when I use what? I tried to find the answer on the Internet, but could not.

+6
source share
2 answers

I found a theoretical description of my question in the book "Define Antlr Link", which was also important for my understanding. Perhaps some others who ask themselves a similar question will also help in this fragment of the book.

Snippet from the Book "The definitive Antlr Reference"

Page 262

+1
source

Your grammar works in ANTLR v3 without any parameters.

The parameter k restricts ANTLR to the classical LL (k) analysis. Returning means - if the analyzer cannot predict which rule to use, it simply tries, retreats and tries again. The backtracking option that you should use when ANTLR cannot build the open source DFA for this grammar. ANTLR v3 can easily create DFAs from regular expressions, but 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 a DFA for it (I really don't know why), so you need to switch back:

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

The k parameter is used to improve analyzer performance. I do not know any other reason for restricting LL (*) to LL (k).

+3
source

More articles:


All Articles