Haskell: ミニコンパイラを試す

Haskellで実装された勉強用のコンパイラがないか探していたらありました。Haskellでコンパイラを書きたいと思っている方や、Pugsの実装に興味のある方は、今回紹介するミニコンパイラに興味を持ってもらえると思います。

• Simple compiler example

このコンパイラは、計算式を架空のスタックマシンのコードに変換するというものです。私たちが普段使っているPentiumマシンに搭載されているFPUもスタックマシンの一種ですね。(参考) 例えば、「1+2-3」をこの架空のスタックマシンのコードに変換すると、以下のようなコードに変換されます。

PushConst 1
PushConst 2
PushConst 3
SubToS
AddToS

では、ソースをゲットして、ghciで実際に試してみましょう。

% wget http://www.doc.ic.ac.uk/~phjk/CompilersCourse/SampleCode/Ex2-CodeGenInHaskell/SimpleCompilerV2.hs
% ghci SimpleCompilerV2.hs 
   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.4.1, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Compiling Main             ( SimpleCompilerV2.hs, interpreted )
Ok, modules loaded: Main.
*Main> 

ここまでできたら、プロンプトに「translate(parser(tokenise "1+2-3"))」と入力してみます。確かに、スタックマシンのコードが生成されています。

*Main> translate(parser(tokenise "1+2-3"))
Loading package haskell98-1.0 ... linking ... done.
[PushConst 1,PushConst 2,PushConst 3,SubToS,AddToS]

以下のように、段階を追ってみるのも面白いです。字句解析や構文解析の工程の結果をビジュアルで確認できます。

*Main> tokenise "1+2-3"
[NUM 1,PLUS,NUM 2,MINUS,NUM 3]
*Main> parser(tokenise "1+2-3")
Plus (Num 1, Minus (Num 2, Num 3))

あと、講義用のスライドも一緒に読むと理解が深まると思います。

• Compilers I - Chapter 2: An introduction to syntax analysis (and a complete toy compiler)

このコンパイラのHaskellのコードはまだ正確には読めませんが、やりたいことはわかりました。コードの意味がわからないにしても、たったこれだけのコードで、ここまでのことができるということは、Haskellはコンパイラを記述する能力に優れている感じがします。