ANTLR：バックトラックと先読みの違いは？

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）解析に制限します。バックトラックとは、パーザがどのルールを使用するかを予測できない場合、単に試行し、バックトラックして再試行することです。 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）に制限する他の理由はわかりません。