2005年06月09日

MinCaml読解ノート: 構文解析

MinCamlとは関係ないが、祝、サッカー日本代表ワールドカップ予選突破。素晴らしい。

構文解析ではトークン列を受け取って構文木を構築する。 ソースコードとしてはparser.mlyに文法を記述。ocamlyaccというツールを使い構文解析器を生成する。

parser.mlyからアクションを省略してMinCamlの文法を拡張BNFのように書くと次のようになり、非常に短い。

「速攻MinCamlコンパイラ概説」で説明されているが、simple_expexpの違いは括弧で囲まなくても関数の引数になれるか否か。この区別が必要なのは、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には比較演算子はEqLEしかない。残りの<>, <, >, >=は、これら2つとNotの組み合わせで表現される。

MinCamlでの型を表すデータ型はType.t。基本のデータ型はUnit, Bool, Int, Floatのみで、これに関数Fun、タプルTuple、配列Array、それに変数や関数の型を表すための型変数Varが加わる。

変数や関数の型は構文解析の時点では定まらず、次の型推論のフェーズで決定される。そのためType.VarType.tオプション型への参照を取る構成子とされ、書き換えが可能である。構文解析中はaddtypを通して作成され、初めはNoneで初期化され型が未定であることを示す。型推論の段階で型が決定すればこれが書き換えられる。最終的には以後の扱いを簡単にするために、型変数を型そのもので置き換えることになる。

猶parser.mly中に出てくるVarSyntax.Var(変数の参照を示す)のことであって、Type.Varではない。

構文解析器のアクションではSyntax.tの構文ノードを作るだけである。

スタート規則がexpであるから、このコンパイラは式を一つだけしか読まない。だから変数や関数を定義してそれらを使ったプログラムを書くためには、letlet recを延々と入れ子にし一つの式として構成することになる(test/にあるサンプルを参照)。

OCamlメモ

オプション型: 'a option
'aの何れかの値、または無効値(None)になるような型。任意の型について自動で定義される。他の言語で、値が無効であることを示すためにnullnilを使うのに似ている。有効な値で構成するにはSomeというデータ構成子を使う。
オプション型の定義は書くとすれば次のようになる。
type 'a option = None | Some of 'a
レコード型
複数のフィールドを持つ。早い話が構造体である。type 型名 = { 名前1 : 型; 名前2 : 型; ... }という形で宣言する。プログラム中で値を作るには{ 名前1=値; 名前2=値; ... }と書く。パターンマッチでは { 名前1 = 変数; 名前2 = 変数; ... } -> 式のように書くことができる。

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。