MinCamlとは関係ないが、祝、サッカー日本代表ワールドカップ予選突破。素晴らしい。
構文解析ではトークン列を受け取って構文木を構築する。 ソースコードとしてはparser.mlyに文法を記述。ocamlyaccというツールを使い構文解析器を生成する。
parser.mlyからアクションを省略してMinCamlの文法を拡張BNFのように書くと次のようになり、非常に短い。
「速攻MinCamlコンパイラ概説」で説明されているが、simple_expとexpの違いは括弧で囲まなくても関数の引数になれるか否か。この区別が必要なのは、MLでは単にスペースで区切って並べるだけで関数適用になるためである。
simple_exp: | ( exp ) | () /* Unit */ | true | false | integer | float | identifier | simple_exp .( exp ) /* 配列の参照 */ exp: /* 一般の式 */ | simple_exp | not exp | - exp | exp + exp | exp - exp | exp = exp | exp <> exp | exp < exp | exp > exp | exp <= exp | exp >= exp | if exp then exp else exp | -. exp | exp +. exp | exp -. exp | exp *. exp | exp /. exp | let identifier = exp in exp | let rec fundef in exp | let ( identifier { , identifier }+ ) = exp in exp | exp simple_exp + /* 関数適用 */ | exp { , exp }* /* タプル */ | simple_exp . ( exp ) <- exp /* 配列への代入 */ | exp ; exp /* 順序評価 */ | Array.create simple_exp simple_exp /* 配列の作成 */ fundef: | identifier { identifier }+ = exp /* 関数名 引数リスト 本体 */ integer: | -?[0-9]+ float: | -?[0-9]+{.[0-9]*}?{[eE][+-]?[0-9]+}? identifier: | _ | [a-z][a-zA-Z0-9_]* /* 但し予約語を除く */
整数の乗算と除算がないことに気付く。
それはさておき、この構文解析器で生成する構文木のデータ型はSyntax.tである。
type t =
| Unit
| Bool of bool ← 定数値
| Int of int
| Float of float
| Not of t ← 単項演算子。型がtというのはオペランドが式。
| Add of t * t ← 二項演算子
| [...]
| Eq of t * t
| LE of t * t
| If of t * t * t ← 条件、THEN式、ELSE式
| Let of (Id.t * Type.t) * t * t ← 変数(名前(Id.t)、型(Type.t))、値、式
| Var of Id.t ← 変数の参照
| LetRec of fundef * t ← 関数定義、メインの式
| App of t * t list ← 関数、引数リスト(t list)
| Tuple of t list
| [...]
and fundef = { name : Id.t * Type.t; args : (Id.t * Type.t) list
↑ 構文木で関数を表すデータ型。name: 名前と型。args: 引数(名前と型)リスト
先に見た文法と異なり、Syntax.tには比較演算子はEqとLEしかない。残りの<>, <, >, >=は、これら2つとNotの組み合わせで表現される。
MinCamlでの型を表すデータ型はType.t。基本のデータ型はUnit, Bool, Int, Floatのみで、これに関数Fun、タプルTuple、配列Array、それに変数や関数の型を表すための型変数Varが加わる。
変数や関数の型は構文解析の時点では定まらず、次の型推論のフェーズで決定される。そのためType.VarはType.tのオプション型への参照を取る構成子とされ、書き換えが可能である。構文解析中はaddtypを通して作成され、初めはNoneで初期化され型が未定であることを示す。型推論の段階で型が決定すればこれが書き換えられる。最終的には以後の扱いを簡単にするために、型変数を型そのもので置き換えることになる。
猶parser.mly中に出てくるVarはSyntax.Var(変数の参照を示す)のことであって、Type.Varではない。
構文解析器のアクションではSyntax.tの構文ノードを作るだけである。
スタート規則がexpであるから、このコンパイラは式を一つだけしか読まない。だから変数や関数を定義してそれらを使ったプログラムを書くためには、letやlet recを延々と入れ子にし一つの式として構成することになる(test/にあるサンプルを参照)。
OCamlメモ
- オプション型:
'a option - 型
'aの何れかの値、または無効値(None)になるような型。任意の型について自動で定義される。他の言語で、値が無効であることを示すためにnullやnilを使うのに似ている。有効な値で構成するにはSomeというデータ構成子を使う。
オプション型の定義は書くとすれば次のようになる。type 'a option = None | Some of 'a
- レコード型
- 複数のフィールドを持つ。早い話が構造体である。
type 型名 = { 名前1 : 型; 名前2 : 型; ... }という形で宣言する。プログラム中で値を作るには{ 名前1=値; 名前2=値; ... }と書く。パターンマッチでは{ 名前1 = 変数; 名前2 = 変数; ... } -> 式のように書くことができる。
