オフサイドルールの処理

予習編．たまーに，YAMLのパーサとか欲しくなるんだけど，インデントの処理をどうやったら良いのかよくわからなくなって困っていたんだけど，勉強になった．

Haskell 98 Syntaxにこと細かに書いてあるので，適当に実装してみた．

http://svn.soutaro.com/has/tags/offside-rulesにありますので，適当にチェックアウトして，ocaml-3.10とかfindlibとかextlibとかインストールしたうえでmakeしたらできます．標準入力からHaskellプログラムを読み込んで，オフサイドルールを処理したやつ，つまり適当に{}とか;とか追加したトークン列を出力します．

let fac3 0 = 1
    fac3 n | n > 0 = n * fac (n-1)

みたいのが，

{ let { fac3 0 = 1; fac3 n | n > 0 = n * fac (n-1) }; }

みたいになります．良くわからんけど，多分Haskellになってると思う．

まあ全部sampou.orgの資料に書いてあるんですけど，ざっくり説明すると，字句解析は要するに3passくらいになってます．一旦，通常の字句解析をやったあとで，インデントの数を数えて{n}やら<n>やら入れる処理を行ない，最終的にそれを{とか;とか使ったプログラムに変換している．

1パス目は通常の字句解析．空白とか改行とかも，読み飛ばさないで，ちゃんとトークンにしてあげるのがポイント．

{n}は，letとかwhereとかの後に入れておく．<n>は行頭の連続するスペースの後に入れる．あと特殊なルールがあって，モジュール(というのが良くわからないんだけど，多分コンパイル単位，つまりファイルのことだと思う)の先頭にも{n}を入れる．これが2パスめ．この変換は，Main.insert_col1とかで実装した．

3パスめは，いよいよ{n}みたいな気持ち悪いやつを消して，{，}，;を入れていく．ルールは読めばわかるんだけど，細かなエラー処理を除くと次みたいな感じになると思う．

L (:ts) (m:ms) = ; : (L ts (m:ms)) if m = n

= } : (L (:ts) ms) if n < m

L ({n}:ts) (m:ms) = { : (L ts (n:m:ms)) if n > m (Note 1)

L (t:ts) ms = t : (L ts ms)

L [] (m:ms) = } : L [] ms if m /=0 (Note 6)

(ry

Lというのがこの変換を行う関数で，ちなみに私が実装したやつだとMain.transformで，L tokens stackという形で使う．返り値が，変換の結果のトークン列．stackに現在読んでいるトークンがどのカラムの影響を受けるか，みたいな情報が入ってる．一番わかりやすいのが，1行目と2行目じゃないかと思う．1行目は，<n>を読んだら，nとスタックトップmを比較して同じだったら;を入れる，という処理．2行目は，<n>を読んだら，まずnとスタックトップmを比較して，mの方が大きかったら}を入れるという処理．

let {5}f 0 = 1
    <5>f n = n + 1

みたいのに該当するのが，1行目．

let {5}f n = n
  <3>a x = f x

に該当するのが，2行目．

あとはletの後には{を入れてスタックを積むとか(3行目)，{n}とかじゃなかったら何もしないとか(4行目)，最後まで来たらスタックの深さの分だけ}を詰むとか(5行目)，そんな感じ．

ここまでできてしまえば，あとはyaccに通すだけなので，いつものパーサ作成と変りませんね．

追記：

shiroさんに指摘された通り，Note5の「if m /= 0 and parse-error(t)」という条件は実装するのが難しいです．

副次的な条件 parse-error(t) は次のように解釈される。もし、次のトークンが t であるような L によって生成されたトークンが Haskell の文法の不正な接頭辞を表わしている場合、および、「}」トークンが続く L によって生成さたトークンの Haskell 文法の正しい接頭辞である場合、parse-error(t) は真となる。

と書いてあるのですが，そんなもん知るかよ，と．ですので，私が書いた上の字句解析器では実装していません．どうやら，パースするときにエラーになるやつをリカバリするようですが，私の興味とはまた外れるので良いかぁ…と．どうせおもちゃの処理系ですし……