TigerBook - U-Wiki+

Top > TigerBook

Counter: 7435, today: 1, yesterday: 0

Modern Compiler Implementation in ML

コンパイラの教科書である「Modern Compiler Implementation in ML」 (通称:タイガーブック)を読んで行く。某所で輪講を行っているのでその成果発表を兼ねて。

プログラム例は Standard ML of New Jersey による(って of New Jersey に特化したものが出てくるかどうか知らないけど)。ただしOCaml に逐語翻訳できるレベルの構文で書いていくつもり。

SML と OCaml の文法の違いは SML vs. OCaml が大いに参考になる。

国内で読んでいる人たち:

Modern compiler implementation in C を読む(WikiWikiする[・ _ゝ・]はやみずさん)

Exercise は基本問題のみ取り扱う。*印は難しいものが含まれるので基本的にはスルー。

Modern Compiler Implementation in ML
PROGRAMs
本文と練習問題

PROGRAMs

Chapter1
TestCase
Chapter2
Chapter3
Chapter4
Chapter5
Chapter6
Chapter7
Chapter8
Chapter9
Chapter10
Chapter11
Chapter12

本文と練習問題

Chapter 1

EXERCISE 1

(* Exercise 1.1a *)
type key = string
datatype tree =
         LEAF
       | TREE of tree * key * tree
val empty = LEAF

fun insert (key, LEAF)        = TREE (LEAF,key,LEAF)
  | insert (key, TREE(l,k,r)) =
    if key < k then TREE (insert(key,l),k,r)
    else if key > k then TREE (l,k,insert(key,r))
    else TREE (l,k,r)

fun member item tr =
    case tr of
        LEAF => false
      | TREE (l,k,r) => (item = k) orelse (member item l) orelse (member item r)
                       (* mendo *)

面倒だったので最後の行は条件判定で場合分けをしていない。

(* Exercise 1.1b *)
type key = string
datatype 'a tree =
         LEAF
       | TREE of 'a tree * key * 'a * 'a tree
val empty = LEAF

fun insert tr ky value =
    case tr of
        LEAF          => TREE (LEAF, ky, value, LEAF)
      | TREE(l,k,v,r) =>
        if ky < k then TREE (insert l ky value, k, v, r)
        else if ky > k then TREE (l, k, v, insert r ky value)
        else TREE (l,k,value,r)  (* override *)

exception NOT_FOUND
fun lookup tr ky =
    case tr of
        LEAF => raise NOT_FOUND
      | TREE(l,k,v,r) =>
        if k=ky then v else if k<ky then lookup l ky else lookup r ky

ちゃんと(?)ここでは例外を使った。

1.1c については省略。

Chapter 2

lexical analyzer (lexer) に関する章。輪講担当だったので資料を作った。

chap2.pdf

あ、読み直すといくつか誤記(文も図も)があるな。ただし今さら直す気はない。

EXERCISE 2

図が多いので PDF 貼り付けの予定。

※ 答え合わせの結果、誤りが多かったので後日に見送り。

2.1a
```
c*a[ac]*b[abc]*
```
2.1b
```
[bc]*(a[bc]*a[bc]*)*
```
2.1c
```
0|1[01]*00
```

2.1d

1[01][01][01][01][01][01][01]*|11[01][01][01][01]|1011[01][01]|10101[01]

2.1e これは難しい(後日書くかも)
2.1f
```
[1-9][0-9]*|0[0-7]
```
2.1g
```
好意的に解釈すれば 1|10。
```

2.2 2.2a について説明する。

正規表現で表せることは DFA で表せることと等価である。したがって、状態数 k の DFA で表せたと仮定する。

このとき、a. を満たす文字列のひとつとして、a^{k+1}b^k つまり 2k+1 の長さを持つ文字列 aa..ab...b を考える。このとき、a は k+1 個あるのに対し状態数は k しかないので、鳩ノ巣原理により i 個の文字を受理した状態と j 個の文字を受理した状態とが同じ遷移状態になるような組 i,j が存在する。このとき、$i$ から $j$ までの文字を切りぬいた文字列 a^{k+1-(j-i)}b^k もまたこの DFA に受理されるはずである。しかしこれはもとの受理すべき文字列の条件を満たしていない。故に背理法により Q.E.D.。