gl5_progのメモ

自分のためのメモとかまとめとか

グローバルバックトラッキングをやめる方法( 適当訳 )

How to remove global backtracking from your grammar - ANTLR 3 - ANTLR Project
を適当に訳してみます。
誤訳いっぱいあると思います。


より複雑な文法、特にLR文法をANTLRへ移植した場合、このようなエラー文を出す。

"[fatal] rule compilation_unit has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option."
"Alternative 1: after matching input such as OP_LT decision cannot predict what comes next due to recursion overflow to rule2 from rule1"

グローバルバックトラッキングを有効にする(backtrack=true)という簡単な解決法は、エラーを隠し、パーサーの効率を悪化させる。このチュートリアルはこの問題をグローバルバックトラッキング無しで解決するための基本的な手順を説明する。読者はすでにANTLRの文法を理解していることを想定している。

このチュートリアルが扱うガイドラインはJim Idleが元になっているが、私個人のANTLRでの経験により補足されている。これが意味するのは、私はすべての問題、または、最適な解決法に出会っているわけではないということである。いつでも意見を聞かせてほしい。

準備

ヘッダー部分をコピーした新しいファイルを作成する。.tokensファイルがある場合はコピーして持っていく。文法名を変更する。左再帰ルールが含まれていないことを確認する。(左再帰は今回の方法では解決できない)

ステップ1

ルールの断片をコピーする。最初に開始ルールを含めることを推奨する。もしANTLRworksの機能によってルールがグループでソートされてしまったときは、グループを区切りとする。もしグループが巨大なら分割する。

ステップ2

文法の一部分のみをコピーするとANTLRworksが未知のルールだと文句を言ってくるかもしれない。警告を消すために新しいルールを作成する。これは、ルールのソロコンテントとしてキーワードを使うことと、それぞれのルールで違うキーワードを使うことを推奨する。これにより警告が抑制されるのと、空ルールにすることになっている新しい誤解エラーを防ぐ。

ステップ3

文法をチェックする。古いANTLRworksはたとえ警告があったとしてもパーサー生成の成功と報告することに注意する。赤くなっているルールをチェックしなければいけない。もしある場合はその場で直す。これをすべてのルールをコピーし終えるまで繰り返す。

曖昧性がない文法を作るためのANTLRの能力を左右する手法が4つある。左括りだし、統語的述語、バックトラッキング、kオプションを使うことだ。最後の一つは実際に曖昧性をなくすわけではないが、逆が本当なのかもしれない。kは先読みを確定させる。もし、先読みが指定されていなかったら、ANTLRは柔軟な先読み個数を使う。

先読み未指定の場合は、遅くなる傾向がある。多くの文法は、元々の文法でこの最適化を打ち負かす(??)。おすすめは、すべてが解決されるまで先読み未指定を使うことである。その後、警告がでない最小の先読み個数を決めて、そして、1ずつその値を減らしなさい。文句を言われているルールにlocal kオプションをその前の値で渡しなさい。これをkが1になるか直したルールの個数に満足するまで繰り返しなさい。

左括りだし( Left-factoring )

今から非決定論に対抗するツール3つを紹介する。1つめは左括りだし。以下のルールを見てほしい

a : L+ K
   | L+ M
   ;

見てのとおり、2つのLが先頭にあることによって、ANTLRがどちらが正しいのか判断できなくなっている。結果として、ANTLRは2つめのルールを除外する。左括りだしはこの問題を解決する。このテクニックの名前は、左にある共通部分を取り出すことが由来になっている。

a : L+ (K | M)
  ;

左括りだしは複数のルール間でも可能である。開始ポイントがそれから少し違うこれは

a : b
   | c
   ; 
b : L+ K
   ;
c : L+ M
   ;

こうする

a : L+ (b | c)
   ;
b : K
   ;
c : M
   ;

ルールは大きく変わっているので、私は変更する前にコメントアウトされたコピーを作った。さらに、この問題は別の解決法がある。統語的述語である。

統語的述語( Syntactic Predicates )

統語的述語はANTLRに「先に行く前に入力が次のルールに一致するかどうかチェックしてよ。もし一致するなら、それにして。一致しないなら、次のを試して。」と伝える。統語的述語の構文はこのようになる

a : (L K)=> b
   | c
   ;
b : L K
   ;
c : L M
   ;

述語を持たないような影響を受けたサブルールに指示することをおすすめする。これは他のルールが選択されなかったときにANTLRの実行速度をあげる。

残った問題点:2つの解決法があると疑問がわく。いつ、どちらを使えばいいのか。私は簡単にできるのであれば(ルールの境界を超えたとしても)左括りだしを好む。左括りだしは述語やバックトラッキングよりも速い。しかし複雑すぎて文法の意味を変えずに共通項を分割できない場合がある。または、分割するルールは実際の文法ルールとして表現できない。

そのときは述語が正しい解決法だ。述語は()内に記述する。そして、通常のレキサー、パーサールールを記述する。cast_expressionとprimary_expressionの曖昧性をなくしたい場合、以下のような書き方できる。

unary_expression
         // "(x)y"のような入力がcastなのかexpressionなのかの曖昧性をなくすための統語的述語ルール
         // | 入力シーケンスが型の文法を満たすが、式ではない場合。
    :    (scan_for_cast_generic_precedence | OPEN_PARENS predefined_type)=> cast_expression
    |    primary_expression
    |    PLUS unary_expression
    |    MINUS unary_expression
    |    BANG unary_expression
    |    TILDE unary_expression
    |    pre_increment_expression
    |    pre_decrement_expression
    |    pointer_indirection_expression
    |    addressof_expression
    ;
 
// 入力シーケンスが型の文法を満たし、')' の直後が '~', '!', '(', 識別子, リテラル, 予約語の場合
scan_for_cast_generic_precedence
options {
    k = 1;
}
    :    OPEN_PARENS type CLOSE_PARENS cast_disambiguation_token
    ;
 
// 文法の曖昧性をなくすために、これらは式の中で正しいキャストの後に続かなければならない。
cast_disambiguation_token
    :    (TILDE | BANG | OPEN_PARENS | IDENTIFIER | literal | ABSTRACT | BASE | BOOL | BREAK | BYTE | CASE | CATCH
         | CHAR | CHECKED | CLASS | CONST | CONTINUE | DECIMAL | DEFAULT | DELEGATE | DO | DOUBLE | ELSE | ENUM
         | EVENT | EXPLICIT | EXTERN | FINALLY | FIXED | FLOAT | FOR | FOREACH | GOTO | IF | IMPLICIT | IN | INT
         | INTERFACE | INTERNAL | LOCK | LONG | NAMESPACE | NEW | OBJECT | OPERATOR | OUT | OVERRIDE | PARAMS
         | PRIVATE | PROTECTED | PUBLIC | READONLY | REF | RETURN | SBYTE | SEALED | SHORT | SIZEOF | STACKALLOC
         | STATIC | STRING | STRUCT | SWITCH | THIS | THROW | TRY | TYPEOF | UINT | ULONG | UNCHECKED | UNSAFE
         | USHORT | USING | VIRTUAL | VOID | VOLATILE | WHILE
         )
    ;

バックトラッキング

バックトラッキングは選択肢のなかで一番遅い。パーサーは単純にそれぞれが正しいのかテストする。実際、私はこれを使わなくてはならないことはなかった。なので、いつこれが必要になるのか説明はできない。私のお勧めは可能な限り左括りだしと統語的述語を使うことだ。バックトラッキングと統語的述語に関して若干混乱があることを付け加えておく。

Terence Parr は、バックトラッキングは迷路で分かれ道があるごとに先に進み、正しい道をノートに記すまで壁が現れるごとに印をつけるようなイメージで、一方、統語的述語は訓練されたお猿さんを決まった分かれ道に送り、OKが出るまで待つようなイメージだと言っている。私が理解するかぎり、バックトラッキングと統語的述語の違いは、バックトラッキングは暗黙的なスタックを使い、実際に部分的なルールの実行を行う。また、バックトラッキングは曖昧性がない選択肢で述語を作成し、必要なトークンだけを調べる代わりに、全体のルールを調べる。

一方、統語的述語は、入力シーケンスが「述語で記述されたトークン列を識別するDFA(決定性有限オートマトン)」によりマッチする場合に、パーサーに先読みを許す。DFAが選択されたサブルールに一致するシーケンスを認識できる場合のみ。事実上、バックトラッキングはよりパワフルであるが、統語的述語に比べて遅い。

バックトラッキングはローカルで使用することが可能である。これはグローバルに比べて好ましい。

曖昧性を解決するテクニック

  • A) 新しい曖昧性を作ってはいけない。当たり前のことのように思えるかもしれないが、他の曖昧性があるときに結構やってしまう。ANTLR(works)が先に警告を飲み込むのは可能。なので、その解決法は全く正しい。しかし、私の経験上、より一般的なケースは元々の文法にはない曖昧性が偶然つくられてしまうことである。たいていはそういう場合は間違った解決法を選んでしまったときである。私は、コンストラクタのルールがstaticコンストラクタのスーパーセットになったとき、"static" 修飾語をコンストラクタに追加した。コンストラクタルールをstaticコンストラクタ句に合わせたのである。解決法は「staticコンストラクタルールを通常のコンストラクタルールに含めること」と「コンストラクタの実際の種類を後で調べること」だった。
  • B) 文脈依存ルールがある文法の場合、2パスパーサーを作る。例えば、"foo"が変数を表しているのか、型を表しているのかの決定など。シンボルテーブルに"foo"が存在するなら決定できる。存在しないならプログラムはリジェクトする。Javaのような他の言語はより自由な配置ができる。メソッド"foo"ファイルの後の方に来るかもしれない。パーサーは名前と型をチェックのために記録できる。2回目のパスでのみ、パーサーは"foo"が定義されているかコンストラクタ風のメソッドなのかを知ることができる。通常は多段パスが同じトークンセットか重複を含む。?解決方法は構文的スーパーセットを作成することと共通部分の左括りだしである。2回目のパスは禁止された組み合わせの検知とより良いエラーメッセージの作成が可能である。例えば、C#でクラスとメソッドはpublic修飾語を持つ。メソッドだけは"virtual"修飾語をもつ。C#文法は特別修飾ルールがあるそれぞれのルールを提供する。この修飾ルールはすべての修飾語を持ち、親ルールに左括りだしされている。?
  • C) 依存性を考慮しなさい。いくつかのルールの最初で同じシンボルが出現左端曖昧性では。このような場合の問題は文脈が他のルールによって提供されることと新しい曖昧性が作られる可能性があることである。実例としては"s: A | ( A B )?;"である。左括りだしで解決するなら、"A? B?"のように作成し、不正な組み合わせをチェックする。残念ながら、この状況だといくつか相互作用がある。”r:A (s: A? B);”。今"A B"という入力はsとして認識される。元々の変形では不可能である。このルールを扱う適切な方法は統語的述語を使い左括りだしは行わないことである。
  • D) 統語的述語では"."は使わないこと。多くの場合、次のパスではなく最初のパスを選んでしまう。
  • E) 述語を使うことで重要でない警告を抑制することができる。if-then-elseのような曖昧性は他の場所でも発生する。私が経験したケースだと、"?:"と"?"演算子が相互作用していて、それに最初は気付かなかった。グローバルバックトラッキングより他の有効な選択肢は見つけられないと思う。そのような状況で確実に見つけるための方法がある。グローバルバックトラッキングは警告を抑制するがローカルバックトラッキングは違う。
  • F) すべての曖昧性を解決しなさい、ただし、解決法を知っているものから始めなさい。簡単な曖昧性の解決が難しい曖昧性を解決するかもしれない。もし良い方法が思いつかないなら、少し休んでまたあとで試してみよう。また、メーリングリストで聞いてみよう。

ステップ4

満足したら元のファイルに反映させる。