fslexとfsyaccを使って字句・構文解析して電卓っぽい計算をしてくれる奴を作成したい

F# | 16:49 |

DSL（Domain Specific Language)作成のための第一歩としてよくある電卓的なものを作るぞと。ネットで見かける日本語の情報は不勉強な私の知識を超えている内容なので、ここでは丁寧にまとめておきたい。環境はVisual Studio 2010 Shell版のF#（Not 製品版のVisual Studio)。

とりあえずF# PowerPackをインストールしていないのならば、F# PowerPack with F# Compiler Source Drops - HomeからF# PowerPackをインストールしておく。こいつの中にfslex.exeとfsyacc.exeが含まれていて*1、それぞれ

• fslex.exe : 字句解析
• fsyacc.exe:構文解析

を担当してくれるexe。

「新規のコンソールプロジェクト」を立ち上げたらとりあえず「F# PowerPack」への参照を設定しておく。

それからデフォルトである"Program.fs"はそっとしておいて、"AST.fs"として以下の内容を記述した新規のファイルを追加する。

module AST
//四則演算のための抽象構文木のための型
type Expression = 
    | Int    of int
    | Plus   of Expression * Expression 
    | Minus  of Expression * Expression 
    | Times  of Expression * Expression 
    | Divide of Expression * Expression 

今回は整数の四則演算をしたいので、この判別共有体一個で型に関しては全てOK。

そしてfslex.exeで字句解析処理させるためのファイルを"Lexer.fsl"としてプロジェクトに追加。記述内容の意味はコメント通り。

//各種宣言(ヘッダー）
{
module Lexer
//tokenの型を拾うために必要
open Parser
let lexeme = Lexing.LexBuffer<_>.LexemeString
}

//数字・空白・改行をそれぞれ定義
let intNum     = '-'? ['0'-'9']+
let whitespace = ' ' | '\t'
let newline    = '\n' | '\r' '\n'

//字句定義。マッチした内容に応じて{}の中のトークンが返ってくる
rule token = parse
    | intNum     { INT (lexeme lexbuf |> int) }
    | '+'        { PLUS }
    | '-'        { MINUS }
    | '*'        { TIMES }
    | '/'        { DIVIDE }
    | '('        { LPAREN }
    | ')'        { RPAREN }
    | whitespace { token lexbuf } //再帰呼び出しでスペースは無視
    | newline    { lexbuf.EndPos <- lexbuf.EndPos.NextLine; token lexbuf }
    | eof        { EOF }
    | _          { failwithf "unrecognized input: '%s'" <| lexeme lexbuf }

次にfsyaccで構文解析処理させるための文法ルールをParser.fsyとして以下のように記述する。これも記述内容の意味はコメント通り。

//yacc宣言部
//F#系のものを書いておく
%{ 
//抽象構文木の型を使いたいので読んでおく
open AST 
%} 
//構文規則の開始記号であることを宣言
%start Expr 
//以下のものがtoken（符）であると指定。INT・PLUS等の各要素のご本尊はLexer.fslに書いてる
%token <int> INT 
%token PLUS MINUS TIMES DIVIDE LPAREN RPAREN
%token EOF 
//結合順序の指定。下の方が優先度高い。（”掛算・割算の方”が”足算・引算”より優先されるように設定）
%left PLUS MINUS 
%left TIMES DIVIDE 
//戻り値の型
%type <Expression> Expr
 
%%
//文法規則部（ExpはINTかExpr + Expr等等であるべし）
Expr: INT                     { Int $1 } 
    | Expr PLUS Expr          { Plus ($1, $3) } 
    | Expr MINUS Expr         { Minus ($1, $3) } 
    | Expr TIMES Expr         { Times ($1, $3) } 
    | Expr DIVIDE Expr        { Divide ($1, $3) } 
    | LPAREN Expr RPAREN      { $2 } 

また内容は追記せず、デフォルトのままでいいので

• Parser.fs
• Lexer.fs

という空の２つのファイルを追加しておく。このファイルはfayacc, fslexがそれぞれParser.fsy, Lexer.fslを処理した際に自動更新される。これらのファイルはIDEに表示させない（開かない）ようにしておいた方が無難。開いたままにしておくとコンパイルするたびに

が出てきてうざいことになる。

F#では「ファイルの並び＝コンパイルの順番」なのでIDE使って依存関係を考慮した並びに並べ替える必要がある。今回は上から順に「AST.fs⇒Parser.fs⇒Lexer.fs⇒Program.fs」と並べておけばOK。

さらに「ビルド前のイベント」として、字句解析・構文解析を実施させる*2。「プロジェクト」の「プロパティ」の「ビルド前イベント」の箇所に下記を追加(F# PowerPackのインストールパスに応じて適当に変えてください）。

"C:\Program Files\FSharpPowerPack-2.0.0.0\bin\fslex.exe"  "$(ProjectDir)\Lexer.fsl" --unicode
"C:\Program Files\FSharpPowerPack-2.0.0.0\bin\fsyacc.exe" "$(ProjectDir)\Parser.fsy" --module Parser

これでコンパイルできる準備が整ったので、お試し計算させるために以下のようなコードをProgram.fsに記述。

//各種モジュールの読み込み
open AST
open Lexer
open Parser 

//文字列→抽象構文木へ
let parse txt =
  txt
  |> Lexing.LexBuffer<_>.FromString
  |> Parser.Expr Lexer.token

//評価器・数値に倒して実際の評価を実行
let rec eval = function
  | Int i        -> i
  | Plus (a,b)   -> eval a + eval b
  | Minus (a,b)  -> eval a - eval b
  | Times (a,b)  -> eval a * eval b
  | Divide (a,b) -> eval a / eval b
 
//試しの計算
do
  "(4 * (2 + 3))"
  |> parse 
  |> eval
  |> printfn "%d"

計算結果は

となってちゃんと「4 * (2 + 3) = 20」と計算されていることがわかる。

ここで作った完成品はteramonagi/ArithmeticEvaluation ? GitHubにUPしてありますので参考にしてください。fsyaccやfslexの使い方に関してはOCaml版の資料ですが、 lectures/CamlEnshu2011.ja ? Site of Yonezawa Group の第四回講義資料が比較的よくまとまっているような印象を受けました。

【参考】

• fslexとfsyaccが面白い - sciorの日記
• F#のfslexとfsyaccを用いたコンパイラ作成（1/4）：CodeZine
• lectures/CamlEnshu2011.ja ? Site of Yonezawa Group
• Yacc/Lexの使い方（簡略版）
• visual studio - FSLex example solution? - Stack Overflow
• Sorry

ツイートする