CodeZine(コードジン)

特集ページ一覧

F#のfslexとfsyaccを用いたコンパイラ作成

C#プログラマのためのF#入門(9)

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2010/08/17 14:00

目次

fslexを用いた字句解析

 トークンを構成する各文字列を表現する方法として、正則表現という方法があります。fslexはこの正則表現を決定性有限状態オートマトン(注2)に変換し、さらにそれをF#のプログラムに変換します。この作成されたF#プログラムがすなわち字句解析器、レキサです。

注2

 有限個の状態と遷移と動作の組み合わせを数学的に抽象化させたモデル。唯一の開始状態から入力の値ごとに異なる状態へと遷移していき、いずれかの状態で終了し、その終了状態によって成功か失敗か判断します。状態と入力によって次の状態が一意に決まる場合、決定性有限状態オートマトンといいます。

 fslexによる字句解析器の作成の大まかな手順としては、次のようになります。

  1. 作成する字句解析器の仕様(書)を定義
  2. fslex.exeの実行

字句解析器仕様書

 fslexはコマンドラインアプリケーションです。fslexで実行できる字句解析器仕様は.fslという拡張子を持ちます。このファイルをもとに、fslexは字句解析器を作成します。

[構文]字句解析器仕様(.fslファイル)
----------------------------------------------------------------
//宣言部
//モジュール読み込みなど字句解析器作成にあらかじめ必要な情報
{ヘッダー}

let [識別子] = [パターン] 
:
:

//正則表現部
rule [ルール名] [引数] = parse
    | [パターン] {[アクション]}
    | :
    | :
    | [パターン] {[アクション]}
and rule2 [ルール2名] [引数] = parse
:
:
----------------------------------------------------------------

 ファイルの中身は、純粋なF#コードで書かれたヘッダーで始まります。このヘッダーは、{}(カーリーブラケット)で囲まれ、モジュールを開いたりするために使うオプショナルです。

 宣言部では、正則表現部以降で使用する変数や関数を宣言します。正則表現部では、正則表現とそれがマッチした場合のアクションがペアで記述されます。この正則表現部分が字句解析器の核です。この部分がlexにてプログラムに変換されて字句解析器になります。

 testProjの字句解析仕様を見てみます。

[リスト2]Lexer.fsl
//宣言部
{
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#関数のようになり、字句解析器内、もしくは、他のモジュールからもアクセスすることが可能です。正則表現をまとめたものをルールと呼びます。

注3

 yaccにて自動的に宣言されているトークン種別についてはのちほど解説します。fsyaccと共に用いられない場合には、字句解析器仕様内にトークン種別を宣言する必要があります。

fslexの実行

 testProjはビルドごとにfslexを呼ぶように設定してありますが(字句解析仕様に変更があった場合のみ)、fslexのコマンドラインアプリケーションとしての使用方法についても説明します。

 fslex.exeの後に、fslファイル名を指定し、必要に応じてオプションを設定します。

[構文]fslex
-----------------------------------------------------------------
fslex <ファイル名>
        -o <出力ファイル名>
        --unicode: 16-bit unicode文字用の字句解析器作成
        --help: ヘルプを表示
-----------------------------------------------------------------

 以下はコマンド実行例です。

[リスト3]fslex 実行例
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関数を呼び出している例です。

[リスト4]Lexer呼び出し
let equation = Parser.start Lexer.tokenize lexbuff

 fslexとfsyaccはコマンドラインアプリケーションですが、Visual Studio 2010(以下VS2010)のプロジェクトに追加することも可能です。つまり、プロジェクトのビルドごとにこれらを呼ぶことが可能です。設定方法は次のようになります。

 プロジェクトファイルをメモ帳などで開いて、<ItemGroup>内に下記のように追記することで、ビルドの際に自動的にfslexとfsyaccを実行するように設定できます。

[リスト5]プロジェクトファイル(.fsproj)への追記例
<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ファイルの中身については後半で解説するので、とりあえずファイル名を書き換える必要があることを理解してください。

 この場合、字句解析器や構文解析器に変更がない限り、ファイルは再作成されることはなく、時間の節約になります。


  • LINEで送る
  • このエントリーをはてなブックマークに追加

バックナンバー

連載:C#プログラマのためのF#入門

もっと読む

著者プロフィール

  • 山田 祥寛(ヤマダ ヨシヒロ)

    静岡県榛原町生まれ。一橋大学経済学部卒業後、NECにてシステム企画業務に携わるが、2003年4月に念願かなってフリーライターに転身。Microsoft MVP for ASP/ASP.NET。執筆コミュニティ「WINGSプロジェクト」代表。 主な著書に「入門シリーズ(サーバサイドAjax/XM...

  • WINGSプロジェクト 星山 仁美(ホシヤマ ヒトミ)

    <WINGSプロジェクトについて> 有限会社 WINGSプロジェクトが運営する、テクニカル執筆コミュニティ(代表 山田祥寛)。主にWeb開発分野の書籍/記事執筆、翻訳、講演等を幅広く手がける。2018年11月時点での登録メンバは55名で、現在も執筆メンバを募集中。興味のある方は、どしどし応募頂...

あなたにオススメ

All contents copyright © 2005-2021 Shoeisha Co., Ltd. All rights reserved. ver.1.5