ANTLR: Różnica między wstecznym a wyprzedzeniem?

Question

Jestem względnie nowy w ANTLR. Mam bardzo łatwy Gramatyka:

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

myślę, że już zrozumieć podstawy koncepcji patrzeć w przyszłość i wycofywania (która współpracuje z składniowych orzeczników). Tak więc gramatyka działa z k = 4 lub z backtrack = true. Ale jaka jest dokładna różnica, a główne pytanie brzmi, kiedy używam czegoś? Próbowałem znaleźć odpowiedź w Internecie, ale nie udało mi się.

Answer 1

Znalazłem teoretyczny opis mojego pytania w książce "Definitve Antlr Reference", która była również ważna dla mojego zrozumienia. Być może inni, którzy zadają sobie podobne pytanie, pomogliby także w tym fragmencie książki.

Page 262

Answer 2

Gramatyka działa w ANTLR v3 bez żadnych opcji.

Opcja k ogranicza ANTLR do klasycznego parsowania LL (k). Backtracking oznacza - jeśli parser nie może przewidzieć, której reguły użyć, po prostu próbuje, backtracks i próbuje ponownie. Opcja cofania, której należy używać, gdy ANTLR nie może zbudować DFA z wyprzedzeniem dla danej gramatyki. ANTLR v3 może zbudować DFA z wyrażeń regularnych dość łatwo, ale ma trudności z regułami rekurencyjnymi. Na przykład ta gramatyka działa:

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

recursive_rule : (ID)* '%' 
       ; 

Gramatyka poniżej jest taka sama, ale wyraża się poprzez rekursji. ANTLR nie można budować na to DFA (I właściwie nie wiem dlaczego), więc trzeba przełączyć wycofywania:

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

recursive_rule : ID recursive_rule 
       |'%' 
       ; 

Opcja k służy do poprawy wydajności parsera. Nie znam żadnego innego powodu ograniczania LL (*) do LL (k).