ANTLR3/先読みについて - bambooflow Note

ANTLR v3先読みについて

ANTLR LL(k)について、先読みを自分なりに理解してみました。

自動先読み

ANTLRは自動で先読みしてくれます。

たとえば、次の場合、

grammar A;
 
stat  : 'a' 'b'* 'c'
      | 'a' 'b'* 'd'
      ;
 

これだと'a' 'b'*までは同じなので、'c'もしくは'd'がくるまで、どちらでパースしてよいかわかりません。ですが、ANTLRはデフォルトで自動先読みして正しくパースしてくれます。

次の二つを試してみます。

abbbbbbc

abbbbbbd

Debug実行すると、一旦abbbbbbを先読みし、次がcなのかdなのか判断した後、マッチした方を再度abbbbb...とパースするのがわかります。

自動先読みは楽ですが、文法が複雑になるとバックトラック発生が増え、指数関数的に遅くなる傾向があります。

Syntactic Predicate

先読みのトークンの数をkで明示的に指定することができます。

grammar A;
 
options { k=3; }
 
stat  : 'a' 'b'* 'c'
      | 'a' 'b'* 'd'
      ;
 

このｔき先読みするトークン数は3です。

• 成功する例

abd

• 失敗する例

abbd

abbまでは先読みするが次がcなのかdなのか判断できず失敗します。
そんなときにSyntactic Predicateを使います。

(«subrule»)=>

grammar A;
 
options { k=3; }
 
stat  : ('a' 'b'* 'c') => 'a' 'b'* 'c'
      | 'a' 'b'* 'd'
      ;
 

すると、一旦('a' 'b'* 'c')がマッチするかを判断して分岐するので、abbbdを正しくパースします。
先読みしたトークンは消費しません。