6. スキャナの最適化

デバッグをしている間は、 スキャナの性能は通常それほど重要ではなく、 Flexのデフォルトの設定で十分です。 しかしデバッグ終了後は、 スピード、 またはサイズの面でスキャナを最適化したくなることもあるでしょう。 ここでは、 スキャナを最適化するのによく使われる手法をいくつか紹介します。

6.1 スピードの最適化

多くのプログラムは、 字句解析の処理に多くの時間を費やします。 したがって、 スキャナの最適化はかなり大きな性能改善に結びつくことが多いのです。 Flexによるスキャナは、 Lexによるスキャナと比較するとかなり高速になる傾向がありますが、 特定の構成もしくはアクションによって、 性能に大きな影響を与えることができます。 注意すべき点は以下のとおりです。

1. テーブルの圧縮
   どのような圧縮も結果的にスキャナを遅くします。 したがって、 スピードのことが心配であるならば、 常にコマンドラインで‘-f’オプション、 または‘-F’オプションを使ってください。 テーブルの圧縮とスピードに関連するオプションに関する詳細な議論については、 See section テーブルの圧縮とスキャナのスピード。
2. REJECT
   スピードに対して最も大きな影響を及ぼします。 これが使われるとすべてのマッチ処理が遅くなります。 というのは、 スキャナは、 マッチする前の状態に自身を復旧する必要があるからで、 このようなことが必要ない場合と比較して、 より多くの内部的な保守作業を行わなければならないからです。 スピードが重要な場合には、 使わないようにしてください。
3. バックトラッキング
   スキャナがあるテキストにマッチするために「逆行」しなければならないことを、 バックトラッキングといいます。 これは、 スキャナの性能に悪い影響を及ぼしますので、 スピードが最も重要である場合には避けるべきです。 圧縮されたテーブルは常にバックトラッキングを発生させるので、 ‘-f’オプション、 または‘-F’オプションを使わない場合は、 ルールからバックトラッキングを削除しようとするのは時間の無駄です。 スキャナからバックトラッキングを削除することに関する詳細な情報については、 See section バックトラッキングの削除。
4. 可変長後続コンテキスト（variable trailing context）
   可変長後続コンテキストとは、 あるルールの先頭部分と後続部分の両方が固定長でないような場合を指します。 性能の観点からはREJECTと同じくらい悪影響を及ぼすもので、 可能な場合にはいつでも避けるべきです。 この例を示すと、 以下のようになります。

   %% linux|hurd/(OS|"Operating system")

   これは、 以下のように分割すべきです。

   linux/OS|"Operating system" hurd/OS|"Operating system"

   こうすることによって、 問題は解消されます。

5. 行の先頭を表す演算子
   ‘^’演算子は、 性能に不利な影響を及ぼします。 スピードが最も重要な場合には、 使わないでください。
6. yymore()
   yymoreを使うと性能を低下させます。 スピードが最も重要な場合には、 使わないでください。
7. テキスト長
   スキャナの性能は、 マッチするテキストの長さによっても影響を受けます。 常に長い文字列にマッチするような場合には、 スキャナは高速に実行されます。 というのは、 yytext環境をセットアップする必要がないからです。 スキャナの実行時間のほとんどは、 内部の高速なマッチング・ループの中で費やされることになります。
8. NUL
   Flexは、 NULを含むトークンをマッチするのに時間がかかります。 この場合には、 短いテキストにマッチするようルールを記述するほうが良いでしょう。

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.  

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

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

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

%%
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);

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

Compressed tables always backtrack.  

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

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

6.2 サイズの最適化

Flexは、 サイズの小さいスキャナよりも、 むしろ非常に高速なスキャナを作成することを目標としていますが、 いずれにしても、 作成されるテーブルのサイズはLexによるそれと比較しても、 通常はかなり小さいものになります。

デフォルトでは、 Flexは可能な限りサイズの小さいスキャナを作成します。 これは、 コマンドラインで‘-Cem’を使うのと同等です。 デフォルトを使うのであれば、 コマンドライン・オプションを気にする必要はありません。

さらにテーブルのサイズを小さくするには、 より大きなテキスト・グループにマッチするルールを使い、 字句の値を認識するためにCのサブルーチンを使うのが最も良い方法です。 この良い例がコンパイラで、 以下のようなルールを与えることができます。

%%
begin    return(BEGINSYM);
end      return(ENDSYM);
program  return(PROGSYM);
    … 

あるいは、 以下のようにテーブル検索を使うことも可能です。

[a-zA-Z][a-zA-Z0-9]*  return(lookup(yytext));

ここでは、 一般的なルールが指定されていて、 lookup()がテキストをキーワードにマッチさせ、 そのトークンが何であるかを示す整数値を返します。 これにより、 サイズのより小さいテーブルが生成されますが、 性能は悪くなる傾向があります。 また、 数が少なく複雑ではないルール集合については、 テーブル・サイズを縮小することの効果は、 シンボル・マッピング用の情報をプログラム中の他の領域に格納しなければならないという事実によって、 相殺されるかもしれません。 というのは、 シンボル・マッピング用の情報は、 Flexテーブルと比較して、 より多くのスペースを必要とする可能性があるからです。

この文書は新堂 安孝によって2009年9月22日にtexi2html 1.82を用いて生成されました。