タイガーブックを読む(1)

タイガーブックが届いたので読んでいきたいと思います。
まずは、以下が目次です。

第1部 コンパイラ基礎編
1.はじめに slp.sml
2.字句解析 driver.sml errormsg.sml sources.cm tiger.lex tokens.sig tokens.sml
3.構文解析 errormsg.sml parsetest.sml sources.cm tiger.grm
4.抽象構文 absyn.sml errormsg.sml parse.sml prabsyn.sml sources.cm symbol.sml table.sig table.sml tiger.grm
5.意味解析 types.sml
6.駆動レコード
7.中間コードへの変換 printtree.sml temp.sig temp.sml tree.sml
8.基本ブロックとトレース canon.sml
9.命令選択 assem.sml canon.sml flowgraph.sml graph.sig graph.sml main.sml runtime.c
10.生存解析 graph.sml
11.レジタス割付け
runtime.c
12.コンパイラ製作
第2部 コンパイラ発展編
13.ごみ集め
14.オブジェクト指向言語
15.関数型プログラミング言語
16.多相型
17.データフロー解析
18.ループ最適化
19.静的単一代入形式
20.パイプライニングとスケジューリング
21.メモリ階層
付録A Tiger言語リファレンスマニュアル

第1部で基本的なコンパイラを作成し、第2部でより高度な拡張をするようです。
ソースファイルが以下の著者のサイトからダウンロードできます。

http://www.cs.princeton.edu/~appel/modern/ml/project.html

番号がそれぞれの章に対応しているようです。
第1部のソースが公開されていて、第2部のソースはないようです。

"はじめに"のslpをscalaに移植したのが以下のソースになります。

この例ではidはStringの別名で、binop,stm,expという３つのデータタイプがあります。
プログラムはstmで表現できて、progはプログラムを表した例になっています。

object slp {
	type id = String

	abstract sealed case class binop()
	case class Plus() extends binop
	case class Minus() extends binop
	case class Times() extends binop
	case class Div() extends binop

	abstract sealed class stm()
	case class CompoundStm(a:stm, b:stm) extends stm
	case class AssignStm(a:id, b:exp) extends stm
	case class PrintStm(a:List[exp]) extends stm
	
	abstract sealed class exp()
	case class IdExp(a:id) extends exp
	case class NumExp(a:Int) extends exp
	case class OpExp(a:exp, b:binop, c:exp) extends exp
	case class EseqExp(a:stm, b:exp) extends exp

	val prog:stm =
	  CompoundStm(
	    AssignStm(
	      "a",
	      OpExp(NumExp(5), Plus(), NumExp(3))
	    ),
	    CompoundStm(
	      AssignStm(
	        "b",
	        EseqExp(
	          PrintStm(
	            List(
	              IdExp("a"),
	              OpExp(IdExp("a"), Minus(),NumExp(1))
	            )
	          ),
	          OpExp(NumExp(10), Times(), IdExp("a"))
	        )
	      ),
	      PrintStm(List(IdExp("b")))
	    )
	  )
}