読者です 読者をやめる 読者になる 読者になる

type t (* void *)

関数型言語や英語学習の事とか。

プログラミング: Fortran 90のパーサーを実装しようとした話

この記事は言語実装 Advent Calendar 2016の1日目の記事です。
2週間前くらいから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としてパースするとして、、、、 制約を満たしているかどうかチェックするのは型検査なんかよりよほど大変そうです。

結論

パーサーを書くのはつらいよ、でもそれなりに楽しいよ。
細かい部分に詳しく慣れてヲタクに成れるよ。

余談ですがまだまだこの辺は序の口で、
真の恐怖はスペースをがあった場合と無い場合を区別なくパースする固定形式というものをサポート場合に訪れます……。
某商用コンパイラではこれをサポートしますが、
時々このせいでスペースがあったから出る不具合みたいなものがあります。