fslexを用いた字句解析
トークンを構成する各文字列を表現する方法として、正則表現という方法があります。fslexはこの正則表現を決定性有限状態オートマトン(注2)に変換し、さらにそれをF#のプログラムに変換します。この作成されたF#プログラムがすなわち字句解析器、レキサです。
有限個の状態と遷移と動作の組み合わせを数学的に抽象化させたモデル。唯一の開始状態から入力の値ごとに異なる状態へと遷移していき、いずれかの状態で終了し、その終了状態によって成功か失敗か判断します。状態と入力によって次の状態が一意に決まる場合、決定性有限状態オートマトンといいます。
fslexによる字句解析器の作成の大まかな手順としては、次のようになります。
- 作成する字句解析器の仕様(書)を定義
- fslex.exeの実行
字句解析器仕様書
fslexはコマンドラインアプリケーションです。fslexで実行できる字句解析器仕様は.fslという拡張子を持ちます。このファイルをもとに、fslexは字句解析器を作成します。
---------------------------------------------------------------- //宣言部 //モジュール読み込みなど字句解析器作成にあらかじめ必要な情報 {ヘッダー} let [識別子] = [パターン] : : //正則表現部 rule [ルール名] [引数] = parse | [パターン] {[アクション]} | : | : | [パターン] {[アクション]} and rule2 [ルール2名] [引数] = parse : : ----------------------------------------------------------------
ファイルの中身は、純粋なF#コードで書かれたヘッダーで始まります。このヘッダーは、{}(カーリーブラケット)で囲まれ、モジュールを開いたりするために使うオプショナルです。
宣言部では、正則表現部以降で使用する変数や関数を宣言します。正則表現部では、正則表現とそれがマッチした場合のアクションがペアで記述されます。この正則表現部分が字句解析器の核です。この部分がlexにてプログラムに変換されて字句解析器になります。
testProjの字句解析仕様を見てみます。
//宣言部 { module Lexer //※1 open System open Parser //※2 open Microsoft.FSharp.Text.Lexing //※3 let lexeme lexbuf = LexBuffer<char>.LexemeString lexbuf } //基本正則表現を宣言 let digit = ['0'-'9'] //※4 let whitespace = [' ' '\t' ] let newline = ('\n' | '\r' '\n') //正則表現部には正則表現をまとめたルールが rule tokenize = parse | whitespace { tokenize lexbuf } | newline { tokenize lexbuf } // Operators | "+" { PLUS } //※5 | "-" { MINUS } | "*" { ASTER } | "/" { SLASH } // Misc | "(" { LPAREN } | ")" { RPAREN } // Numberic constants | ['-']?digit+ { INT32 (Int32.Parse(lexeme lexbuf)) } | ['-']?digit+('.'digit+)?(['e''E']digit+)? { FLOAT (Double.Parse(lexeme lexbuf)) } // EOF | eof { EOF }
- ※1のモジュール名をトップに記述するのを忘れないでください。
- ※2のヘッダー部分ですが、testProjの字句解析器仕様書(Lexer.fsl)のヘッダーでParserを読み込んでいるのは、yaccが自動生成するモジュールmodule Parserに定義されているトークン種別を使用するためです。
- ※3の「Microsoft.FSharp.Text.Lexing」は必須です。
- ※4宣言部にて基本正則表現が宣言されていますが、これは文字のグループに識別子を与え、それがその文字のグループにバインドされるように定義してあります。let digit = ['0'-'9']は0-9の数字はdigitにバインドされ、digitが字句解析の正則表現にて使用されます。
- 正則表現に対応するアクション部分にて(※5の{}内)、yaccにて自動的に宣言されているトークン種別(注3)を戻すように定義します。andを用いて複数設定できます。入力された文字とパターンがマッチした場合、ペアとなっているトークンが返されます。
このルールはF#関数のようになり、字句解析器内、もしくは、他のモジュールからもアクセスすることが可能です。正則表現をまとめたものをルールと呼びます。
yaccにて自動的に宣言されているトークン種別についてはのちほど解説します。fsyaccと共に用いられない場合には、字句解析器仕様内にトークン種別を宣言する必要があります。
fslexの実行
testProjはビルドごとにfslexを呼ぶように設定してありますが(字句解析仕様に変更があった場合のみ)、fslexのコマンドラインアプリケーションとしての使用方法についても説明します。
fslex.exeの後に、fslファイル名を指定し、必要に応じてオプションを設定します。
----------------------------------------------------------------- fslex <ファイル名> -o <出力ファイル名> --unicode: 16-bit unicode文字用の字句解析器作成 --help: ヘルプを表示 -----------------------------------------------------------------
以下はコマンド実行例です。
C:\Program Files\FSharpPowerPack-2.0.0.0\\bin\fslex.exe -o obj\x86\Debug\Lexer.fs --unicode Lexer.fsl
実は上記のコマンドは、testProjのプロジェクトフォルダ「Visual Studio 2010\Projects\testProj\testProj\obj\x86\Debug」配下にあるファイルを一度削除してから、ビルドを行った際に自動的に実行されたコマンドです。
fslexは仕様書Lexer.fslに基づいてlexer.fs(字句解析器プログラム)を作成します。これによって、字句解析関数tokenizeが使用可能になりました。tokenize関数は、fslexによって正則表現部(つまり基本正則表現部分とルール部)がF#関数に変換されたもの、と考えれば良いでしょう。
のちに、テンプレートのメインプログラムとなるProgram.fsからこのモジュールを呼び出して使用します。以下はtestProjのメインプログラムからLexer関数を呼び出している例です。
let equation = Parser.start Lexer.tokenize lexbuff
fslexとfsyaccはコマンドラインアプリケーションですが、Visual Studio 2010(以下VS2010)のプロジェクトに追加することも可能です。つまり、プロジェクトのビルドごとにこれらを呼ぶことが可能です。設定方法は次のようになります。
プロジェクトファイルをメモ帳などで開いて、<ItemGroup>内に下記のように追記することで、ビルドの際に自動的にfslexとfsyaccを実行するように設定できます。
<FsYacc Include="Parser.fsy"> //※1 <OtherFlags>--module Parser</OtherFlags> </FsYacc> <FsLex Include="Lexer.fsl" > //※2 <OtherFlags>--unicode</OtherFlags> </FsLex>
Parser.fsy(※1)とLexer.fsl(※2)の部分には、独自の構文解析器仕様ファイル名(xxx.fsy)、字句解析仕様ファイル名(xxx.fsl)を記述します。fsyファイルの中身については後半で解説するので、とりあえずファイル名を書き換える必要があることを理解してください。
この場合、字句解析器や構文解析器に変更がない限り、ファイルは再作成されることはなく、時間の節約になります。