Flex (字句解析ジェネレータ)

Flex (高速字句解析器ジェネレータ) は、lexの代替となる無料のオープンソースソフトウェアです。^[2] これは、字句解析器(「スキャナ」または「レクサー」とも呼ばれる)を生成するコンピュータプログラムです。 ^{[3] [4]これは、} BSD派生のオペレーティングシステム ( と は両方ともPOSIXの一部であるため)上のBerkeley Yaccパーサジェネレータ と共に lex 実装として頻繁に使用されます。 ^{[5] [6] [ 7]または}*BSD ポート^{[8]および Linux ディストリビューションでは}GNU bison ( yaccのバージョン)と共に使用されます。 Bison とは異なり、 flex はGNU プロジェクトの一部ではなく、 GNU 一般公衆利用許諾書^[9]の下でリリースされていませんが、Flex のマニュアルは Free Software Foundation によって作成および公開されています。^[10] lexyacc

Flexは1987年頃にVern PaxsonによってC言語で書かれました^{[1] 。Van} Jacobsonの多くのアイデアとインスピレーションの助けを借りて書かれました。オリジナル版はJef Poskanzerによるものです。高速テーブル表現はVan Jacobsonの設計の部分的な実装です。実装はKevin GongとVern Paxsonによって行われました^{[11] 。}

これは、教育プログラミング言語PL/0用の Flex スキャナーの例です。

認識されるトークンは次のとおりです: ' +'、' -'、' *'、/' ='、' ' 、' '、' '、' (' 、' ' 、' '、' '、 ' '、 ' '、' '、' '、' '、' '、' '、' ' 、' ' 、' '、' ' 、' '、数字: ;識別子:およびキーワード: 、、、、、、、、、、、、、、。),;.:=<<=<>>>=0-9 {0-9}a-zA-Z {a-zA-Z0-9}begincallconstdoendifoddprocedurethenvarwhile

% { 
#include "y.tab.h" % } 


数字[ 0-9 ]文字[ a - zA - Z ]         
        

%% 
"+" { return PLUS ; } "-" { return MINUS ; } "*" { return TIMES ; } "/" { return SLASH ; } "(" { return LPAREN ; } ")" { return RPAREN ; } ";" { return SEMICOLON ; } "," { return COMMA ; } "." { return PERIOD ; } ":=" { return BECOMES ; } "=" { return EQL ; } "<>" { return NEQ ; } "<" { return LSS ; } ">" { return GTR ; } "<=" { return LEQ ; } ">=" { return GEQ ; } "begin" { return BEGINSYM ; } "call" { return CALLSYM ; } "const" { return CONSTSYM ; } "do" { return DOSYM ; } "end" { return ENDSYM ; } "if" { return IFSYM ; } "odd" { return ODDSYM ; } "procedure" { return PROCSYM ; } "then" { return THENSYM ; } "var" { return VARSYM ; } "while" { return WHILESYM ; } { letter }({ letter } | {数字}) * { yylval . id = strdup ( yytext ); IDENTを返します; }                           
                          
                          
                          
                         
                         
                      
                          
                         
                       
                            
                           
                            
                            
                           
                           
                   
                     
                   
                         
                       
                         
                       
                
                     
                       
                   
 
                         
                              
{ digit } + { yylval . num = atoi ( yytext ); return NUMBER ; } [ \ t \ n \ r ] /* 空白をスキップ */ . { printf ( "不明な文字 [%c] \n " , yytext [ 0 ]); return UNKNOWN ; } %%                
                             
             
                     
                            


int yywrap ( void ){戻り値1 ;}  

これらのプログラムは、決定性有限オートマトン(DFA)を使用して文字の解析とトークン化を実行します。DFA は、正規言語を受け入れる理論上のマシンです。これらのマシンは、チューリング マシンのコレクションのサブセットです。DFA は、読み取り専用の右移動チューリング マシンと同等です。構文は、正規表現の使用に基づいています。非決定性有限オートマトンも参照してください。

Flex 字句解析器は通常、入力の長さに応じて時間の計算量が決まります。つまり、入力シンボルごとに定数の操作を実行します。この定数は非常に低く、GCC はDFA 一致ループに 12 個の命令を生成します。^{[引用が必要]}この定数はトークンの長さ、正規表現の長さ、および DFA のサイズとは無関係であることに注意してください。 ${\displaystyle O(n)}$

しかし、非常に長いトークンにマッチする可能性のあるスキャナで REJECT マクロを使用すると、Flex は非線形パフォーマンスのスキャナを生成する可能性があります。この機能はオプションです。この場合、プログラマーは、Flex がすでに入力にマッチした後に「戻って再試行する」ように明示的に指示しています。これにより、DFA は他の受け入れ状態を見つけるためにバックトラックします。REJECT 機能はデフォルトでは有効になっていません。パフォーマンスへの影響のため、Flex マニュアルではその使用は推奨されていません。^[12]

デフォルトでは、Flex によって生成されたスキャナは再入可能ではありません。これは、生成されたスキャナを異なるスレッドから使​​用するプログラムに深刻な問題を引き起こす可能性があります。この問題を克服するために、Flex は再入性を実現するためにオプションを提供しています。これらのオプションの詳細な説明は、Flex マニュアルに記載されています。^[13]

通常、生成されたスキャナにはUnix固有のunistd.hヘッダーファイルへの参照が含まれています。unistd.h をインクルードするコードの生成を避けるには、%option nounistd を使用する必要があります。もう 1 つの問題は、生成されたコードで見つかるisatty (Unix ライブラリ関数)の呼び出しです。 %option never-interactive は、 flex にisatty を使用しないコードを生成するように強制します。^[14]

Flex はCおよびC++のコードのみを生成できます。他の言語から flex によって生成されたスキャナー コードを使用するには、SWIGなどの言語バインディングツールを使用できます。

Flexは1バイト（8ビット）のバイナリ値のマッチングに制限されているため、Unicodeをサポートしていません。^[15] RE/flexおよびその他の代替手段はUnicodeマッチングをサポートしています。

flex++はC++用の同様の字句スキャナで、flex パッケージの一部として含まれています。生成されたコードは、入力も依存しない限り、メモリ アロケータ ( mallocまたはユーザー提供の代替)を除いて、ランタイムや外部ライブラリに依存しません。これは、従来のオペレーティング システムやC ランタイム機能が利用できない 組み込みなどの状況で役立ちます。

flex++ で生成された C++ スキャナーには、FlexLexer.h2 つの C++ で生成されたクラスのインターフェースを定義するヘッダー ファイルが含まれています。

• パーサージェネレータの比較
• レックス
• ヤック
• GNUバイソン
• バークレーYacc

• レヴィン、ジョン（2009年8月）。flex & bison。オライリーメディア。ISBN 978-0-596-15597-1。
• ME Lesk と E. Schmidt、LEX - 語彙解析ジェネレーター
• Alfred Aho、Ravi Sethi、Jeffrey Ullman、「Compilers: Principles, Techniques and Tools」、Addison-Wesley (1986)。flex (決定論的有限オートマトン) で使用されるパターンマッチング手法について説明します。

• 公式サイト
• ANSI-C Lex仕様
• JFlex: Java 用高速スキャナ ジェネレーター
• Lex、Flex、YACC、Bison の簡単な説明 2005-05-07 にWayback Machineでアーカイブされました