週刊nmosh - パーサ作り - .mjtの日記復帰計画

というわけで今週はパーサ作り(とかいいつつ先週は1ミリも作業できなかったので今更)。

ステート出し

パーサは基本的に有限状態機械なので、作るためには状態を定義しないといけない。状態を手でつくるのとlexとかyaccで作ったものに手を加えるのとどちらが良いのかは何とも言えない。

 - Default
 - BlockComment            (#|)
 - BlockCommentBar         (|#)
 - LineComment             (;)
 - Sharp                   (# | #e | ...)
 - SharpSyntaxUnquote      (#,)
 - SharpChar               (#\)
 - SharpCharHexIndex       (#x11)
 - SharpRegEx              (#/)
 - SharpRegExTail          (/ | /i)
 - SharpByteVectorR6RS     (#vu8)
 - SharpUniformVector      (#u)
 - SharpUniformVector8     (#u8)
 - SharpDatumLabel         (#0= | #0#)
 - SharpLiteralTrue        (#t | #true)
 - SharpLiteralFalse       (#f | #false)
 - Symbol
 - SymbolEscape            (\t)
 - SymbolEscapeInlineHex   (\xYY;)
 - SymbolInBar
 - String
 - StringEscape            (\t)
 - StringEscapeInlineHex   (\xYY;)
 - StringEscapeWhitespace  (\)
 - Number             0 - 9 or leading HexadecimalNumber etc.
 - Plus               (+)
 - LiteralPlusI_nf    (+i | +inf.0)
 - LiteralPlusNan     (+nan.0)
 - Minus              (-)
 - LiteralMinusI_nf   (-i | -inf.0)
 - LiteralMinusNan    (-nan.0)

Schemeの文法はかなりシンプルなので状態の数もかなり少い。いくつかの状態は更に"level"で細分される。例えば、LiteralPlusNanは"+nan.0"を全て完成させるまでLevelを増やしつつ留まる。Levelはネスト可能コメントのネスト数にも流用される。
次は個々の状態に"文字グループgggが来たら、sss状態に遷移し、(可能なら)メッセージxxxを送信"を付けていけばパーサの完成。。というわけで今週はこれをやる(一日で終わりそう)。
いくつかのデザインチョイス:

ファイル中の全てのキャラクタをアノテートできるように努力する。コードのHTML化やリファクタリングツールを作るのに必要なため。
- コメントを読み飛さず、構文要素として出力する。
ファイルモードとストリームモード、コメントの出力の有無をパラメタとして取る。ファイルモードの場合、行番号のカウントを内部で行う。
暫くはstrictモードを実装しない。R6RSシンボルエスケープモードも無し。(bar単体のシンボルは常にエスケープする必要が有る。)
数値とregex以外は2パスのパースを避ける。-inf.0はメッセージNumberではなく、メッセージNumberMinusInfとなる。
StringとSymbolはpartに分割して出力する

制約: メッセージは2つ以上のファイルに跨ることができない。バランスされていないファイルをincludeすることでリストを分割したり、後続のストリームをブロックコメントすることができない。
この制約はR6RS/R7RSプログラムでは問題にならない。しかし、REPLがこの制約の影響を受ける。REPLでこのパーサを使用するにはdatumを得るまで1つのストリームを維持する必要があるため、例えば、"クリップボードから貼りつけた文字列"と"キーボードから入力した文字列"を区別したいケースに直接は対応できない。(しかし、この問題は比較的簡単に対処できる; 抽象化されたREPL入力ストリームを管理し、REPL入力ストリームのソースを別途トラックすれば良い。)

メッセージ形式: Head, Body, Tail

パーサは"メッセージ"を出力する。メッセージは、NumberとかStringPartとかCommentのような構文要素を表わすシンボルと、3つのファイル範囲Head/Body/Tailを含む。

;; 入力   => (シンボル           HEAD   BODY TAIL)

#vu8(1 2) => (UniformVector8R6RS "#vu8" ""  "") ;; 実際には文字列ではなくインデックスが使用される
             (ListBegin          "("    ""  "")
             (Number             ""     "1" "")
             (Number             ""     "2" "")
             (ListEnd            ")"    ""  "")

#/hoge/i =>  (RegExBegin         "#/"   ""     "")
             (RegExBody          ""     "hoge" "")
             (RegExEnd           "/"    "i"    "")

\x12;    =>  (SymbolPartHex     "#x"    "12"   ";")
#1#      =>  (DatumLabelRef     "#"     "1"    "#")
#1=      =>  (DatumLabelDef     "#"     "1"    "=")

実際にデータを得るためには、更にbody部分をパースするかstring→symbolのような手続きで実際のdatumに変換する必要がある。
逆に、HeadとTailは、パーサ出力からDatumを作るだけなら即捨てて良いことになる。しかし、コードの色分けのような目的にはHeadやTailも必要になる。また、オブジェクトの定義位置を設定する際や、エラー報告を行う際にも、多分有効だろう。