Flexの正規表現マッチング速度と手動コードの比較

flexは、コンパイラおよび解釈プログラマの一般的なツールの1つである文法解析器ジェネレータです.flexのプログラムは主に命令(動作コードと呼ばれる)を伴う一連の正規表現から構成される.入力をマッチングすると、flexはすべての正規表現を確定的で貧しいオートマチックに翻訳し、flexなどの構文解析器生成器で生成された構文解析器が入力モードにマッチングする効率が非常に高い.もちろん、flexが柔軟ではなく、機能が限られていて、Javascript、C++などの言語の二義性の問題を解決できない問題が多いと非難されていますが、実際には多くのプログラム(例えばPythonの解釈器)の文法分析器がflexではなく手動コードで生成されています.これらはすべてこの文章の討論の範囲内ではなくて、私は主にflexと手書きのCコードに対してコンパイルする1つの語数統計プログラム(word counter)を通じてflexが正規表現に一致する速度を非常にざっと評価したいと思っています.
テスト方法:flexで生成されたCコードと手動Cコードでコンパイルされたプログラムをそれぞれ実行し、3種類の異なるサイズのファイルを設定し、shellのtime命令で2つのプログラムの実行にかかる時間をテストします.
次のソースコードは、flexソースflexwcです.l:

 1 /* flex           。
 2     flexwc.l
 3 */
 4 
 5 %{
 6 /*      ，       ，      */
 7 int chars=0;
 8 int words=0;
 9 int lines=0;
10 %}
11 %%
12 [a-zA-Z]+    { ++words; chars+=strlen(yytext);}/*           ，                  */
13 
            { ++chars; ++lines; }/*     ，      */
14 .            {++chars;}/*    */            
15 %%
16 
17 main(int argc,char **argv)
18 {
19     yylex();/*  flex     */
20     printf("%8d%8d%8d
",lines,words,chars);/*    ，   ，   */
21 }

コンパイル命令:

1 $flex flexwc.l
2 $gcc -o flexwc -O3 flexwc

次はCコード、manwcです.c:

 1 /*  C         
 2     manwc.c
 3 */
 4 
 5 #include <stdio.h>
 6 #include <ctype.h>/*  isalpha()*/
 7 
 8 /*    ，          ，      */
 9 int i_char=0,i_line=0,i_word=0;
10 
11 int main(void)
12 {
13     int inword=0;
14     /* inword==1              （           ）
15                    */
16     char ch;
17     while ((ch=getchar())!=EOF)/*     */
18     {
19         ++i_char;/*     */
20         if ('
'==ch)/*  */
21             ++i_line;
22         if (isalpha(ch) && !inword)/*       */
23         {
24             inword=1;
25             ++i_word;
26         }
27         if (!isalpha(ch) && inword)/*       */
28         {
29             inword=0;    
30         }
31     }
32     printf("%8d%8d%8d
",i_line,i_word,i_char);/*      、   、   */
33     return 0;
34 }

コンパイル命令:

1 $gcc -o manwc -O3 manwc.c

以下、第1回目のテストを行い、指令と結果は以下の通りである.

 1 $time ./autowc < foo.txt
 2        4       0       7
 3 
 4 real    0m0.014s
 5 user    0m0.000s
 6 sys    0m0.000s
 7 
 8 $ time ./manwc < foo.txt
 9        4       0       7
10 
11 real    0m0.024s
12 user    0m0.000s
13 sys    0m0.000s

なお、flexのデフォルト入力ストリームとCコードの入力ストリームはいずれもstdinであるため、ここでは入力ストリームリダイレクト'<'が用いられる.
次に2回目のテストを行い、指令と結果は以下の通りである.

 1 $time ./autowc < lex.yy.c 
 2     1823    6705   45887
 3 
 4 real    0m0.008s
 5 user    0m0.004s
 6 sys    0m0.000s
 7 
 8 $ time ./manwc < lex.yy.c 
 9     1823    6705   45887
10 
11 real    0m0.008s
12 user    0m0.004s
13 sys    0m0.000s

次に3回目のテストを行い、指令と結果は以下の通りである.

 1 $time ./autowc < MAINTAINERS 
 2     9721   46364  269584
 3 
 4 real    0m0.013s
 5 user    0m0.012s
 6 sys    0m0.000s
 7 
 8 $ time ./manwc < MAINTAINERS 
 9     9721   46364  269584
10 
11 real    0m0.019s
12 user    0m0.020s
13 sys    0m0.000s

(この結果は機械の影響が大きいので参考にしてください)
3回の規模の小さいものから大きいものまでのテストを経て,flexで生成された文法解析器が正規表現に一致する速度は,手作業Cコードよりもほぼ常に速いことが分かった.パターンがより複雑になると,flex生成コードの実行速度は純粋な手作業Cコードよりも効率的になることが予想される.これは、flexが正規表現を処理する内部フォーマット(すなわち、確定性に乏しいオートマチック)により、正規表現をマッチングする際に問題の規模にほとんど関係なく(すなわち、パターンが複雑であればあるほどマッチング時間が長くなるわけではないが、例外もある)、このような問題を手作業のCコードで処理する場合、常に文字ストリームを一歩一歩分析する傾向にあるためである.例えば、C言語の'/'記号を分析すると、最初の'/'を読み込むと、いったい何なのか(二義性がある)確定できず、次の文字を読み続けるしかありません.数字であれば、'/'は除算演算子です.「/」であれば、ローの注釈であり、ローの残りの内容を直接無視することができます.'*'であれば、どの位置に「*/」が現れたかを判断し、中間の注釈を無視し、一致する「*/」が見つからない場合は、エラーを報告する必要があります.flexでは、この3つの方法について明確な正規表現を定義できます.「/」、「//」、「/*」(最後の一致/**/注釈の場合は、開始状態の知識も使用します.ここでは説明しません).要するに、一度に大きなセグメントをマッチングするのは、ほとんどいつも1文字ずつマッチングし、複数回マッチングするよりも速いことを覚えておいてください.もちろん例外もあります.
まとめ:flexはフォーマットファイル処理ツールとして、生成されたコードをコンパイラ解釈器のプログラミング者の文法分析器の開発に使用するだけでなく、分析が必要なすべてのフォーマットファイルにも使用できます.例えば、ファイル内の特定のフォーマット、自動レイアウト、コード自動インデント、文法シェーディングなど、迅速に検索することができます.すべてはあなたが何ができるか次第です!