この記事は言語実装 Advent Calendar 2016の１日目の記事です。
２週間前くらいからFortran 90の規格に準拠したパーサーを書こうとして苦労した話を書きます。
あまり大変だよ～という読み物になっており結論はありません。
なお実装は未完成です、、、
GitHub - nomaddo/f90: a tiny subset of fortran 90 written in ocaml.
経緯
SIMDの論文を読んでいたら実験したくなっていい感じのフロントエンドが欲しかった。
が、当初の目的は明後日に行ってパーサーを書いている。
道具
案の定OCaml + Menhirです。
私はヴァリアントのない言語でバグらずに実装できる気がしません。
（最近はCで書かれたコンパイラもよく読むのですが）
OCamlでコンパイラを作るというのは僕の中では普通の選択肢です。 世間の皆様はCやC++で書くようですが、最近だと
などがあります。Coqの作者なんかは、OCamlのようなシンボリックな操作が簡単にできなければ
Coqの実装は難しかった、みたいなことを言っていた気がします。
Menhir
文法定義
Menhirは便利なツールです。ocamlyaccより楽ちんに色々な表現を書き下すことが出来ます。
例えばFortran 90のentity-decl-listみたいな文をパースすることを考えてみます。
entity-decl-listはFortran 90で変数宣言の部分に出現します。
例えばinteger :: a = 12, b(3, 3), c(4) = 123の::以降です。
ちなみに意味は「整数aを宣言し12で初期化、3x3の整数の2次元配列bを宣言、整数の長さ4の1次元配列cをすべての様子を123で初期化」です。
entity-decl-listはentity-declをコンマで区切ったものです。
entiy-declは仕様書を見てみると以下のように表されています。
entity-decl is object-name [(array-spec)] [* char-length] [initialization]
or function-name [ * char-length ]
array-spec、つまりb(3,3)のカッコの配列の形状についての記述や文字型だった場合の文字の長さ、 初期化というのはオプショナルであると言うわけです。entity-declをocamlyaccで書き下すと
entity_decl: | object_name array_spec_opt char_length_opt initialization_opt { ... } | function_name char_length_opt { ... } array_spec_opt: | LPAREN array_spec RPAREN { $1 } | /* empty */ { ... } char_length_opt: | AST char_length { $2 } | /* empty */ { ... } initialization_opt: | initialization { ... } | /* empty */ { ... } /* object_name, array_spec, char_length, initialization の定義は省略 */
めっちゃ冗長になりました。XXX_optみたいなスタブなコードをたくさん書かなければなりません。
この程度ではあまり大変さが分からないかもしれないのですが、文法が巨大だととにかく簡潔に書きたいです。
このようなパーサーの実装によく出現するパターンはマクロのようなものが用意されています。
Menhirを用いると、以下のように書き下せます。
entity_decl: | object_name option(array_spec) option(AST; char_length { $2 }) option(initialization) { ... } | function_name option(AST char_length { $2 }) { ... }
option(rule)は文字とおり上のようなスタブコードを自動で生成していい感じにやってくれます。 option(AST; char_length)のように複数のルールを書くときには、返す値の部分も option(AST; char_length { $2 })のように書く必要があります。
entity_declを定義するとあとはentity_decl_listはocamlyaccだと
entity_decl_list: | entity_decl { [$1] } | entity_decl COMMA entity_decl_list { $1 :: $2 }
Menhirにはこのようなパターンのためにlistキーワードや、 nonempty_list、separated_listとseparated_nonempty_listがあります。
entity_decl_list: | separated_nonempty_list(COMMA, entity_decl) { $1 }
これで終わりです！このようなパターンは大量に出現するため、 parserのコード量を大幅に抑えてくれます。。。
optionと組み合わせてoption(list(nonempty_list(...))みたいな書くことが出来、 すごく冗長なコードを書くことを抑えてくれます。
デバッグ
Menhirを使っているとデバッグが楽ちんです。
menhir --interpret --interpret-show-cst --interpret-error test.mly
のように実行すると対話的にシンボルを入力して、それがどのようにパースされるのか見ることが出来ます。
%token LPAREN RPAREN
%token <string> IDENT
%token <int> INT
%start sexpr
%type <([> `Int of int | `List of 'a list | `Symbol of string ] as 'a)> sexpr
%%
sexpr:
| IDENT { `Symbol $1 }
| INT { `Int $1 }
| LPAREN list(sexpr) RPAREN
{ `List $2 }
みたいなS式のパーサーを書いてみた時、TOKEN列を与えて対話的に動作を確かめることが出来ます。
[/tmp] menhir --interpret --interpret-show-cst --interpret-error test.mly
LPAREN IDENT INT LPAREN INT IDENT INT RPAREN INT RPAREN
ACCEPT
[sexpr:
LPAREN
[list(sexpr):
[sexpr: IDENT]
[list(sexpr):
[sexpr: INT]
[list(sexpr):
[sexpr:
LPAREN
[list(sexpr):
[sexpr: INT]
[list(sexpr):
[sexpr: IDENT]
[list(sexpr): [sexpr: INT] [list(sexpr):]]
]
]
RPAREN
]
[list(sexpr): [sexpr: INT] [list(sexpr):]]
]
]
]
RPAREN
]
コンパイルしたプログラムがパースできないなぁと困ったときにlexerの問題なのか、
parserの問題なのか切り分けるのに使っていました。
Fortran 90
文法の愚痴
ここからは愚痴タイムです。
Fortran 90の規格というのはとにかく無駄に大きいと感じます。
例えば、Cではmallocは普通の関数ですがFortranでは専用のステートメントです。
このへんとか見てほしいのですが
なぜならばallocate(a(-1:3), STAT = status_variable) のように
配列の下限：上限の指定から、この割付に失敗したときに
実行時エラーを表す整数を代入する変数(この場合status_variable)を書き下す
機能があるからです！！！！！！
このようにとにかく宣言文に種類が多いのです。
R215 executable-construct is action-stmt
or case-construct
or do-construct
or forall-construct
or if-construct
or where-construct
R216 action-stmt is allocate-stmt
or assignment-stmt
or backspace-stmt
or call-stmt
or close-stmt
or continue-stmt
or cycle-stmt
or deallocate-stmt
or endfile-stmt
or end-function-stmt
or end-program-stmt
or end-subroutine-stmt
or exit-stmt
or forall-stmt
or goto-stmt
or if-stmt
or inquire-stmt
or nullify-stmt
or open-stmt
or pointer-assignment-stmt
or print-stmt
or read-stmt
or return-stmt
or rewind-stmt
or stop-stmt
or where-stmt
or write-stmt
or arithmetic-if-stmt
or computed-goto-stmt
とにかく多い！readやwrite, printですら専用の構文です！
exitとかstopとかその辺も関数とか普通のサブルーチン扱いで良かったんじゃないのって気持ちになります！
なにげに混じっているend-function-stmtとかに嫌な感じがありますね！！！！！！
またそれぞれにそれなりに複雑な定義を要ししてくれちゃって怒り大爆発です。 例えばread,write,printの場合
read-stmt is READ ( io-control-spec-list ) [ input-item-list ]
or READ format [ , input-item-list ]
write-stmt is WRITE ( io-control-spec-list ) [ output-item-list ]
print-stmt is PRINT format [ , output-item-list ]
規格の定義の仕方への愚痴
BNFっぽい何かは形式的に定義されているのですがそれに現れない制約が多いのです。
例えば変数宣言ではinteger,parameter :: i = 12みたいに書きますが、
形式的定義だけだとinteger i = 12と書けるように見えます、
なぜならi = 12の部分のentity-declは以下のように定義されているからです。
entity-decl is object-name [(array-spec)] [* char-length] [initialization]
or function-name [ * char-length ]
initialization is = specificaiton_expr
or => ()
しかし下に、
Constraint: If initialization appears, a double colon separator shall appear before the entity-decl-list.
とか書いてあって激おこです。 このようなルールが数個だったらそれも形式的定義で書き下せばいいんじゃないすか～ みたいな気持ちで読むことが出来るのですが、変数宣言である type-declaration-stmtの部分には22個のConstraintが書いてあります。
他の例として、同じような話がspecification-exprにもあります。
specification-exprは、初期化部分にかける式を表すルールなのですが、
これのルールが「expr、ただし以下の制約（自然言語）」という形で書かれています。
パースはexprとしてパースするとして、、、、 制約を満たしているかどうかチェックするのは型検査なんかよりよほど大変そうです。
結論
パーサーを書くのはつらいよ、でもそれなりに楽しいよ。
細かい部分に詳しく慣れてヲタクに成れるよ。
余談ですがまだまだこの辺は序の口で、
真の恐怖はスペースをがあった場合と無い場合を区別なくパースする固定形式というものをサポート場合に訪れます……。
某商用コンパイラではこれをサポートしますが、
時々このせいでスペースがあったから出る不具合みたいなものがあります。
