今回扱う構文に対する字句解析器と構文解析器を作り，入力文字列を抽象構文木に変換できるようにする．抽象構文の意味は算術演算を定義するだけなので，この方針で一番難しいのは字句解析器と構文解析器を作るところである．なお，今回この問題を解いた動機は「オフサイドルールを含む構文をパーズする手法を勉強したい．また，今回扱う小さな言語ならパーザを手書きしてもいいが，複雑になりがちな実用的な言語の構文でそれはやりたくないので，今後のことを見据えて ocamllex と Menhir でパーズできるようになりたい」というものなので，ocamllex と Menhir を使う前提で話を進める．
難しさの要因は構文にオフサイドルールが含まれること（今回はピリオドの数や改行が構文的に意味を持つ）である．BNF ではこれを素直に表現できないので，BNF と似た記法を用いる Menhir でもまたオフサイドルールを素直に記述できない（よね？ 記述できたらごめん）．今回は，基本的にオフサイドルールが存在しない構文（具象構文・抽象構文）に変換して BNF で扱えるようにする方針でこの難しさに対処する．これの実現方法はいくつかあるため，以降ではその具体的な方法とその方法のハマりポイントを書き残す．
ハマりポイントなしの上手くやる方法は参考文献先の記事に全て置かれている．
具体的な方法の説明に入る前に，全ての方法で共通している考え方を説明する．
まず，オフサイドルールの処理は全て字句解析で行う．また，インデントの深さが変わったことを検知するため，スタックにインデントの深さを push/pop する．例えば，現在のインデントの深さがスタックのトップより大きかったらインデントが深くなったことがわかるし，逆に小さかったらインデントが浅くなったことがわかる．詳細はこちらの記事．
今回行ったアプローチである．例えば，以下の文字列
+
.1
.2を次のような字句の列に変換する（見やすさのために改行や空白を入れているが，これらに構文的な意味はない）．INPERIOD がインデントが深くなることを意味し，DEPERIOD がインデントが浅くなることを意味する．
かの Python もこの方法を採用しているっぽい（公式ドキュメント）．
PLUS NEWLINE
INPERIOD
(INTV 1) NEWLINE
(INTV 2) NEWLINE
DEPERIOD
EOFこの方法で問題になるのが，DEPERIOD を一度に 2 個以上生成しなければならない場合があることである．例えば以下の文字列
+
.+
..1
..+
...2
...3
.4は次のような字句の列に変換される．
PLUS NEWLINE
INPERIOD
PLUS NEWLINE
INPERIOD
(INTV 1) NEWLINE
PLUS NEWLINE
INPERIOD
(INTV 2) NEWLINE
(INTV 3) NEWLINE
DEPERIOD
DEPERIOD
(INTV 4) NEWLINE
DEPERIOD
EOFこの例の場合，入力文字列の ...3 における ... （参照が難しいね）に対して DEPERIOD を 2 つ生成する必要があるが，ocamllex ではマッチした文字列に対して 1 つのトークンしか生成できないため，これを素直に記述できない．レキサのエンドポイントの型を Lexing.lexbuf -> Parser.token list にしてパーザ側でよしなにやったらええやんという夢も，パーザのエンドポイントの要求する型が (Lexing.lexbuf -> Parser.token) -> Lexing.lexbuf -> Syntax.exp（Syntax.exp というのは抽象構文木を表す型）なので型パズルを突破できなくて叶わない．これの対処方法は，なんとか ... に対して 2 度 DEPERIOD を返せるようにする形となる．これを実現する方法もいくつかあるので全て書き残しておく．
今回採用した実現方法である．ざっくり説明すると，レキサの型 Lexing.lexbuf -> Parser.token list をラッパーで Lexing.lexbuf -> Parser.token に変換しちゃうのである．これならパーザのエンドポイントの型と整合する．ラッパーでやっていることは単純で，前回レキサを呼び出した結果の余りが残っているならば，次の字句を読まずにその余りを返している．詳しくはこちらの記事．
なお，最初にトークンをキューに全て詰め直し，キューからトークンを順次返すイテレータを作っても上手くいった．具体的なコードは以下．EOF の扱いがやや不恰好だったり，lexbuf を 2 回渡さなきゃいけないので嬉しさはあまりない．最初に思いついた方法がこれだったので，記念にダンプしただけである．
let create lexbuf =
let tokens = Queue.create () in
let rec queue_of_lexbuf lexbuf = function
| [ Parser.EOF ] -> ()
| tokens' ->
List.iter (fun token -> Queue.add token tokens) tokens';
queue_of_lexbuf lexbuf @@ sub lexbuf
in
queue_of_lexbuf lexbuf @@ sub lexbuf;
fun lexbuf ->
match Queue.take_opt tokens with None -> Parser.EOF | Some token -> tokenレキサが引数として受け取る lexbuf 型の値は可変なデータ構造であり，レキサで字句を読むたびに次に読むべきバッファの位置が更新される．この方法は，トークンを必要数生成するまでその位置を巻き戻せばええやん，というアイディアによる．例えば ... に対して DEPERIOD を 2 つ生成しなければならない場合，レキサで次の動作を行う:
- レキサのエンドポイントを叩く（1 回目）
...にマッチする- 次に読むべきバッファの位置を
...の先頭に更新する DEPERIODを返す- レキサのエンドポイントを叩く（2 回目）
...にマッチするDEPERIODを返す
この方法の利点は，オフサイドルールに関係する文字列に対するアクションのみ変更すればよいところにある．この利点のおかげで方法 1.1 のような変換を入れなくてよいし，オフサイドルールに関係しないところはいつも通り字句解析すればいいし，コード量も減る．欠点としては，標準モジュールだけではこの方法を実装できないことである（ここにジョジョの例の画像）．この方法を実現する場合は lexbuf 型の値をいい感じに扱う関数を自分で定義する必要がある．僕には lexbuf の深淵を覗きに行く勇気がなかったので今回はこの方法を避けた．
例えば，以下の文字列
+
.1
.2は次の中間構文に変換する．
(+ 1 2)基本的な考え方は方法 1 と同じだが，中間構文への変換に使用するレキサの返り値の型が string である点が異なる．この方法なら方法 1 の時の問題点「1 回のマッチに対して 2 つのトークンを生成しなければならない場合がある」は問題にならない．なぜなら，インデントが浅くなることを意味する複数の文字列を一つの文字列にまとめるのは容易だからである（(^): string -> string -> string で型パズルを突破できる）．
この方法の問題点は，インデントの深さが変わることを意味する文字を，元の構文の意味を変えないよう注意深く選択して中間構文を定義する必要がある点である．ただし，Haskell のように，オフサイドルールが働く構文と等価な構文が定義されている場合，方法 2 は真っ先に考慮すべき方法になりうる．なぜなら，シンタックスシュガーを外す処理と一緒に実装できて楽だからである，多分．
オフサイドルールを含む構文をパーズするの大変すぎ！という気持ちを込めてもっと簡単にパーズする方法を調べたら「Adams, Michael D., Principled parsing for indentation-sensitive languages: revisiting landin's offside rule, ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2013」って論文が見つかった．さすが人類．
色々と調べてると構文論の深淵が垣間見えて面白かったが，一方でユーザに S 式を書かせるのが言語作成者としては楽だなという気持ちも強まった．パーザ定義で苦しむたびに S 式の魅力が増している．ありがとう，いい構文です．