プログラミングと絵と音楽

コンピューター科学を専攻し、絵と音楽を趣味とするエンジニアのブログです。

MinCaml で学ぶ関数型言語コンパイラ(その1:字句解析と構文解析)

自作言語を作っている途中ですが、様々な手法を学習するため、 MinCaml という言語のコンパイラを作りながら関数型プログラミング言語のコンパイラ作成の概形と内容について学びます。

MinCaml というのは OCaml のサブセットのような言語で、検索するとわかりやすくホームページと GitHub のページにアクセスすることができます。

私が大学の学部生のときにある課題で MinCaml に触れました。プロセッサ・コンパイラ実験というものだったのですが、複数の班に別れて一人がコンパイラ係として主にこのコンパイラを改造していました。わたしはコンパイラ係ではなかったので全員共通のコンパイラ課題のみを解きましたが、流石にコンパイラも作らないままでは消化不良なので今回手を付けようと思いました。

MinCamlコンパイラOCaml で書かれています。ただ写経するだけでは学びがないので、 Haskell で書き換えてみようと思います。以下にコードがあります。

github.com

まず、字句解析と構文解析を行います。文字列をトークン列に変換し、さらにそれを抽象構文木に変換します。 OCaml では ocamllex と ocamlyacc がそれを行いますが、 Haskell では Haskell Platform に入っている alex と happy を用います。

Alex
Happy: The Parser Generator for Haskell

注意した点

私の Haskell に関する哲学として、プログラム自体の誤りの場合はエラーを起こし、入力などの誤りの場合はモナドを使ってエラーを表現するというようにしています。 Either String a という型に似た Result a というデータを定義します。

data Result a = Reject String | Accept a

instance Functor Result where
    fmap f (Accept a) = Accept $ f a
    fmap _ (Reject s) = Reject s

instance Applicative Result where
    pure = Accept
    Accept f <*> Accept a = Accept $ f a
    Accept _ <*> Reject s = Reject s
    Reject x <*> _ = Reject x

instance Monad Result where
    Reject s >>= _ = Reject s
    Accept a >>= f = f a
    return = Accept
    fail = Reject

instance Show a => Show (Result a) where
    show (Accept a) = "Accept $ " ++ show a
    show (Reject s) = "Reject $ " ++ s

計算が失敗した場合は文字列を使って Reject を与え、計算が成功した場合は Accept を与えます。
なぜ Either String a を使わないかというと、 fail のときにエラーを起こしてしまうからです。あと Result, Reject, Accept の語の選び方も気に入ってるし、型の一つに String を固定することで簡潔に表現できているのでお勧めです。

まず、 Tokenizer を作るために alex を用います。規則を書くことで Tokenizer を自動的に作成してくれます。
alex には幾つかの wrapper があり、それぞれ違ったフォーマットで結果を出力してくれるのですが、 "posn" や "monad" だとエラーが起きて使えなかったので、 "basic" を選択することにしました。これはトークンを Token として String -> [Token] という型になっているのですが、個人的にはモナドを使って Monad m => String -> m [Token] としたかったので、 alexScanTokens という関数を書き換えて実現しました。

alexScanTokens str = go ('\n',[],str)
  where go inp@(_,_bs,s) =
          case alexScan inp 0 of
                AlexEOF -> return []
                AlexError _ -> fail "lexical error"
                AlexSkip  inp' len     -> go inp'
                AlexToken inp' len act -> do
                  x <- go inp'
                  return $ act (take len s) : x

Parser を作るためには happy を用います。字句解析と違い、規則を与えるだけでも十分難易度が上がります。例えば、次のような注意をしなければなりません。
例えば 1 + 2 + 3 という式が与えられた時、 1 + (2 + 3) ではなく (1 + 2) + 3 と解釈するのかを規則として与える必要があります。また、 1 + 2 * 3 は 1 + (2 * 3) と解釈しなければなりません。
もし以下のような規則を与えると、足し算が左結合なのか、また掛け算のほうが結合が強いのかなど、様々な情報が抜け落ちてしまいます。

A:
  A plus A
  A times A
  B
B:
  int

では、少し変更してみましょう。

A:
  A plus B
  B
B:
  B times C
  C
C:
  int

こうすると、曖昧性が解消され、一意に構文木が定まります。
happy を含めた通常のパーサコンビネーターは %left %right などのデータを使うことで左右結合や結合強度などの情報を与えることができますが、これを多用し過ぎると難しくなってしまうので今回は使いませんでした。

MinCaml の結合強度でわからないことがいくつかあったので、 OCaml を使って結合強度を真似してみました。
例えばタプルのコンマと if then else の構文の結合強度はどうなっているのかということが挙げられます。実際に OCaml インタプリタに入力してみました。

1, 2, if true then 3, 4 else 5, 6, 7

これは、 3, 4 と 5, 6, 7 の型が合わないといわれます。つまり、タプルの結合強度の方が強いことが分かります。なぜならば、もし弱い場合は、 1, 2, (if true 3, 4 else 5), 6, 7 と解釈されるからです。

このような調査を加えて、規則を与えてパーサーを出力させました。ちなみに、 %monad というのを使うことで、 [Token] -> Result a という型の関数を作ってくれます。