はじめに
F#では、fslexやfsyaccといったツールや、判別共用体などのF#固有の機能を用いることで、既存言語に新たな構造を簡単に追加したり、言語を作成したりできます。
今回はF#言語指向プログラミングを利用して、fslexとfsyaccを用いたコンパイラ作成について解説します。
fslexとfsyaccは、PowerPackに含まれています。PowerPackは、マイクロソフトのF#チームが用意したF#用ライブラリとツールを集めたものです。ダウンロードはこちらのURLからできます。
fslexとfsyacc
lexとyaccは字句解析器と構文解析器を自動生成する有名なツールですが、これらをF#用に移植したツールがfslexとfsyaccです(注1)。
人間がC言語やF#などで記述するソースコード(※1)をコンピュータが理解できるオブジェクトコードに変換するのがコンパイラです。コンパイラはまず、入力された文字列を単語単語に区切って抽出する必要があります。区切られた単語をトークン(※2)と呼び、この作業を字句解析と呼びます。字句解析を行うのが字句解析器で、それを作成するプロセスを自動化しているのがfslexです。
次に、字句解析された文字列、つまりトークンの集まりは、構文解析されます。構文解析では、トークンを構文木(※3)に変換します。この処理を行うのが構文解析器で、パーサとも呼ばれます。fsyaccは構文解析器の自動生成をサポートします。fslexとfsyaccはそれら自身がそれぞれの役目に特化されたDSLでもあります。構文解析で得られた構文木に情報を補足し各階層に意味を持たせるのが意味解析です。
その後、作成された構文木を用いて、オブジェクトコードを生成します。先に効率のよいコードを生成するための最適化処理を行い、最後にオブジェクトコードを作成します。
fslexとfsyaccツールは、F#配布ディレクトリのbinにfslex.exeとfsyacc.exeとして配置されています。
fslex、fsyaccスターターテンプレート
VS2010プロジェクトでのfslexとfsyaccツール使用に関するスターター用オンラインテンプレートがあります。
VS2010を起動し、新しいプロジェクトを作成します。今回はtestProjという名前にします。テンプレートの部分でオンラインテンプレートの、F# Parsed Language Starterを選択してください。作成されたプロジェクトは図のような構成になっていると思います。
これはfslexやfsyaccを用いて簡単な計算言語を作成するプロジェクトのテンプレートです。作成されるアプリケーションは次のように、標準入力から得られる文字列(四則演算)を計算して表示し、”quit”が入力されると終了します。
Calculator :2 + 3 * 5 Lexing [2 + 3 * 5] Parsing... Evaluating Equation... Result: 17 :quit Press any key to continue . . .
今回は、これらを用いて解説します。