Previous: Optimizing for Speed, Up: Optimizing for Speed


6.1.1 バックトラッキングの削除

スキャナからバックトラッキングを削除することは、 スキャナの性能にかなりの影響をもたらします。 残念ながら、 バックトラッキングの削除はかなり複雑な作業になる可能性があります。 例えば、

     %%
     hurd     return(GNU_OS);
     hurdle   return(JUMP);
     hurdled  return(JUMPED);

では、 バックトラッキングが発生します。 スキャナが‘hu’をマッチし、 次の文字が‘r’ではない場合、 マッチされなかったテキストをECHOするデフォルトのルールを使って‘h’と‘u’を処理するために、 スキャナはバックトラッキングを行わなければなりません。 同じことが‘d’と‘e’についても適用されます。 (これは、 何かにマッチするようスキャナが努力を継続するということが、 もはやできないからです。 この場合、 スキャナはデフォルトのルールを適用し、 yyext環境をリセットしなければなりませんが、 いずれも時間のかかる処理です。)

コマンドライン・オプション‘-b’を使うことで、 バックトラッキングを発生させている原因に関する情報を知ることができます。 これにより、 バックトラッキングに関する情報を含むlex.backtrackというファイルが生成されます。 上記の例の場合、 このファイルは以下のような情報を含みます。

     State #6 is non-accepting -
      associated rule line numbers:
             2       3       4
      out-transitions: [ r ]
      jam-transitions: EOF [ \000-q  s-\177 ]
     State #7 is non-accepting -
      associated rule line numbers:
             2       3       4
      out-transitions: [ d ]
      jam-transitions: EOF [ \000-c  e-\177 ]
     State #9 is non-accepting -
      associated rule line numbers:
             3       4
      out-transitions: [ e ]
      jam-transitions: EOF [ \000-d  f-\177 ]
     
     Compressed tables always backtrack.

バックトラッキング情報はセクションに分割され、 個々のセクションにおいて、 バックトラッキングを引き起こしている1つの状態のことが記述されています。 個々のセクションの最初の行から、 状態番号を知ることができます。 2行目からは、 記述ファイルの何行目が関連しているのかを知ることができます。 3行目からは、 バックトラッキングを発生させた文字を知ることができます。 よって、 最初のブロックからは、 文字‘r’でバックトラッキングが発生し、 それは記述ファイルの2,3,4行目に関連していることを見てとることができます。 最後の行は、 圧縮されたテーブルは常にバックトラッキングを発生させるので、 テーブル圧縮を引き起こすようなコマンドライン・オプションを使う場合には、 バックトラッキングを削除しようとして時間を費やすべきではないことを思い出させるためのものです。

バックトラッキングを削除するためには、 バックトラッキングが関与している状態をキャッチするルールを加える必要があります。 これは、 スキャナのスピードには影響を与えないということに注意してください。 スキャナのスピードは、 ルールの数や複雑さとはまったくといえるほど無関係です。

バックトラッキングを削除するためにルールを追加する方法は、 2種類あります。 第1の方法は、 以下のようなルールを追加することです。

     %%
     hurd     return(GNU_OS);
     hurdle   return(JUMP);
     hurdled  return(JUMPED);
     hu       return(OTHER);
     hur      return(OTHER);
     hurdl    return(OTHER);

別の方法として、 すべてをキャッチするようなルールを追加することもできます。

     %%
     hurd     return(GNU_OS);
     hurdle   return(JUMP);
     hurdled  return(JUMPED);
     [a-z]+   return(OTHER);

この第2の方法を適用できる場合は、 常にこれを使うべきです。 上記のどちらかと‘-b’オプションを一緒に使うと、

     Compressed tables always backtrack.

というメッセージだけが出力されるようになります。 これは、 バックトラッキング状態が存在しないことを示唆しています。

これに付随する問題の1つとして、 複雑なスキャナではバックトラッキング問題はカスケードする傾向があるので、 lex.backtrack内の情報が混乱をもたらすものになる可能性があります。 しかし、 バックトラッキングの原因は通常2、3個のルールにしぼることが可能なので、 バックトラック・データを調べようと努力するだけの値打ちはあります