デバッグをしている間は、 スキャナの性能は通常それほど重要ではなく、 Flexのデフォルトの設定で十分です。 しかしデバッグ終了後は、 スピード、 またはサイズの面でスキャナを最適化したくなることもあるでしょう。 ここでは、 スキャナを最適化するのによく使われる手法をいくつか紹介します。
多くのプログラムは、 字句解析の処理に多くの時間を費やします。 したがって、 スキャナの最適化はかなり大きな性能改善に結びつくことが多いのです。 Flexによるスキャナは、 Lexによるスキャナと比較するとかなり高速になる傾向がありますが、 特定の構成もしくはアクションによって、 性能に大きな影響を与えることができます。 注意すべき点は以下のとおりです。
REJECT
と同じくらい悪影響を及ぼすもので、
可能な場合にはいつでも避けるべきです。
この例を示すと、
以下のようになります。
%% linux|hurd/(OS|"Operating system")これは、 以下のように分割すべきです。
linux/OS|"Operating system" hurd/OS|"Operating system"こうすることによって、 問題は解消されます。
yymore
を使うと性能を低下させます。
スピードが最も重要な場合には、
使わないでください。
yytext
環境をセットアップする必要がないからです。
スキャナの実行時間のほとんどは、
内部の高速なマッチング・ループの中で費やされることになります。
NUL
NUL
を含むトークンをマッチするのに時間がかかります。
この場合には、
短いテキストにマッチするようルールを記述するほうが良いでしょう。
スキャナからバックトラッキングを削除することは、 スキャナの性能にかなりの影響をもたらします。 残念ながら、 バックトラッキングの削除はかなり複雑な作業になる可能性があります。 例えば、
%% 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個のルールにしぼることが可能なので、
バックトラック・データを調べようと努力するだけの値打ちはあります。
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テーブルと比較して、
より多くのスペースを必要とする可能性があるからです。