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

C#プログラマのためのF#入門（9）

fsyaccを用いた構文解析

　トークン列を受け取り抽象構文木（AST）を作成するのが構文解析器です。ASTとは、具象構文木から不要な情報を除いたりして変形した意味解析の処理に適した構文木のことです。

　fsyaccによる大まかな構文解析器の作成手順は、次のようになります。

1. 作成する構文解析器の仕様の定義
2. fsyacc実行

　構文解析器仕様（.fsyファイル）は主に、ヘッダー部、宣言部、ルール部の3部分から構成されます。

［構文］構文解析仕様（.fsyファイル）

----------------------------------------------------------------
//ヘッダー部 ※1
%{[コード]%} 

//宣言部 ※2
  //トークンとその型
%token <[型]> [トークン名]……. [トークン名]
…

    //トークンや優先順位(バインドの強度)の定義
%left [トークン名]
%right [トークン名]
….

   //スタートシンボルとその型
%start [スタートシンボル] //※3
%type <[型]> [スタートシンボル]

%%

//ルール部 ※4
非終端記号名(ルール名)1:　シンボル名1 {アクション1}
    |シンボル名2 {アクション2}  // 
    |
    :
非終端記号名(ルール名)2 …..
----------------------------------------------------------------

　ヘッダー（※1）には、言語の構文木などのモジュール読み込み、大域変数、関数など構文解析にあらかじめ必要な情報を記述し、宣言部（※2）では、トークンやその優先度などを記述します。そして最後のルール部には、構文解析の核となる文法を作る構文規則（ルール）が記述されます。

　宣言部とルール部は”%%”にて区切られます。fsyaccによって作成される構文解析器は開始記号として定義された関数（※3）のみを公開します。

　ルールの定義には、文脈自由文法を用います。文脈自由文法では、終端記号（トークン）と非終端記号（書き換えられる可能性がある記号）を用いて、構文規則を記述します。ルール部に記述された、各非終端記号を、構文規則名（ルール名）と呼び、1つの終端記号に対する記述部分を1構文規則とみなします。

　testProjの構文解析仕様（Parser.fsy）を見てみましょう。

［リスト6］ Parser.fsy

//宣言部
  //ヘッダー
%{
open Ast  //※1
%}

//startトークンはコンパイルされたコードで、構文解析関数になる。※2
%start start
//トークンとそれらの型
%token <System.Int32> INT32
%token <System.Double> FLOAT
%token PLUS MINUS ASTER	SLASH
%token LPAREN RPAREN
%token EOF
// 開始シンボルとその型
%type < Ast.Equation > start

%%

//非終端記号がどのようにトークン或いは非終端記号に書き換えられるか
//文脈自由文法を用いて定義する。
start: Prog { Equation($1) }  //※3

Prog:
    | Expr EOF            { $1 }

Expr: 
    | Expr PLUS  Term     { Plus($1, $3)  }  //※4
    | Expr MINUS Term     { Minus($1, $3) }
    | Term                { Term($1)      }

Term:
    | Term ASTER Factor   { Times($1, $3)  }
    | Term SLASH Factor   { Divide($1, $3) }
    | Factor              { Factor($1)     }
    
Factor:
    | FLOAT               { Float($1)  }
    | INT32               { Integer($1) }
    | LPAREN Expr RPAREN  { ParenEx($2) }

　ヘッダーでは、名前空間Astをopenしています（※1）。四則演算については既に、曖昧さのない正しい構文木を構築する文法が一般的に知られています。Ast.fsには、その曖昧さのない文法が構文木として判別共用体を用いて定義されています。

［リスト7］Ast.fs

namespace Ast 
open System

type Factor =
    | Float   of Double
    | Integer of Int32
    | ParenEx of Expr

and Term =
    | Times  of Term * Factor
    | Divide of Term * Factor
    | Factor of Factor

and Expr =
    | Plus  of Expr * Term
    | Minus of Expr * Term
    | Term  of Term
    
and Equation =
    | Equation of Expr

　※2では、トークンと、優先度と結合度（左結合、右結合など）付トークンなどが定義されています。下記のリスト8のようにPLUS MINUSなどの入力されるテキスト内のキーワードだけではなく、INT FLOATなど文字列や数字などで構成されたキーワードを表すトークンも定義します。そして入力の終わりを意味するトークンEOFを最後に定義します。開始記号として、startトークンを定義します。

　これらのトークンは、Lexer.fslの正則表現部のアクション部分で記述されている、戻り値である種別名に対応しています。ルール部1行目（※3）の左辺には、開始記号を記述します。その後に続く、各非終端記号（ルール名、構文規則名でもある）とそれを構成する要素（トークンもしくは非終端記号）は、”|”で区切られ1つの構文規則にまとめられます。この定義された構文規則は再帰的に利用することが可能です。非終端記号を非終端記号かトークンに書き換えることを還元といいます。

［リスト8］ルールの例

Expr: 
    | Expr PLUS  Term     { Plus($1, $3)  }//※1 アクション1
    | Expr MINUS Term     { Minus($1, $3) }//アクション2
    | Term                { Term($1)      }//アクション3

　上記リスト8はtestProjのParser.fsyのルール部の1構文規則ですが、構文規則とその規則で還元が起きるときのアクション（意味処理）が{}内に記述されています。非終端記号ExprがExpr PLUS Termに還元されると、続く{}内のアクションが実行されます。

　カッコ内のアクションに書かれている$マークは参照専用の擬似変数で、Plus($1, $3)は左にあるパターンの1つ目の要素（Expr）と3つ目の要素（Term）をPlusに渡し実行する、という意味です。

　1構文規則にアクションから戻される値はすべて同じ型である必要があります。上のアクション1-3はどれも、Exp型の値を戻します。

fsyaccの実行

　上記のように作成した.fsyファイルを使用して下記の構文に従い、VS2010経由もしくはコマンドラインからfsyaccを実行します。fsyacc.exeの後に、fsyファイル名を指定し、必要に応じてオプションを設定します。

［構文］fsyacc構文

-----------------------------------------------------------------
fsyacc <fsyファイル名>
        -o <出力ファイル名>
        -v: Produce a listing file.
        --module <作成された構文解析器用モジュール名>
        --help ヘルプを表示
-----------------------------------------------------------------

　testProjにてビルドを実行すると、構文解析器となるParser.fsプログラムファイルと作成された構文解析器用シグネチャーファイルParser.fsiが作成されます。シグネチャーファイルには、F#のプログラム要素のパブリックシグネチャに関する情報が格納されており、プログラム要素へのアクセスの際に使用できます。

［リスト9］fsyaccの実行例

C:\Program Files\FSharpPowerPack-2.0.0.0\\bin\fsyacc.exe -o obj\x86\Debug\Parser.fs --module Parser  Parser.fsy