ANTLR : 역 추적과 Look-ahead의 차이점은 무엇입니까?

Question

필자는 ANTLR에 대해 상대적으로 새로운 기능을 제공합니다. 나는 아주 쉬운 문법을 가지고

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

나는 이미 (문법 술어와 함께 작동) 미리보고 되돌아의 개념의 기초를 이해하고 있다고 생각합니다. 따라서이 문법은 k = 4 또는 backtrack = true와 함께 작동합니다. 그러나 정확한 차이점은 무엇이며 언제 무엇을 사용해야합니까? 나는 인터넷에서 대답을 찾으려했지만 노력하지는 않았다.

Answer 1

내 이해를 위해 중요한 책 "The Definitve Antlr Reference"에서 제 질문에 대한 이론적 설명을 발견했습니다. 어쩌면 비슷한 질문을하는 다른 사람들도이 책의 일부분을 도울 것입니다.

페이지 262

Answer 2

문법은 ANTLR v3에서 옵션없이 사용할 수 있습니다.

k 옵션은 ANTLR을 고전적인 LL (k) 구문 분석으로 제한합니다. 역 추적 (Backtracking) - 파서가 사용할 규칙을 예측할 수 없다면 다시 시도하고 역 추적하여 다시 시도합니다. ANTLR이 주어진 문법에 대해 미리보기 DFA를 빌드 할 수 없을 때 사용해야하는 역 추적 옵션입니다. ANTLR v3은 정규 표현식으로 DFA를 만들 수 있지만 재귀 규칙에는 어려움이 있습니다. 예를 들어,이 문법은 다음과 같이 작동합니다.

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

recursive_rule : (ID)* '%' 
       ; 

이 문법은 동일하지만 재귀를 통해 표현됩니다. 이 (내가 왜 실제로 모르는)에 대한 ANTLR은 DFA를 만들 수 없습니다, 그래서 당신은에 되돌아 전환 할 필요가 다음 K 옵션을 파서 성능을 향상하는 데 사용됩니다

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

recursive_rule : ID recursive_rule 
       |'%' 
       ; 

. 나는 LL (*)을 LL (k)로 제한하는 다른 이유를 모른다.