Top > TigerBook
Counter: 6698, today: 2, 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 が大いに参考になる。

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

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

もくじ

PROGRAMs

本文と練習問題

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) に関する章。 輪講担当だったので資料を作った。

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

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.。

  • 2.3a 4桁の二進数で 6 以外
  • 2.3b aの連続文字列であって、その文字数が5で割って1余るようなもの

2.4 以下は図があるので以下のPDFにまとめた。

Chapter 3

50ページもある。長い。 そのうちまとめる。

EXERCISE 3

特に前半の問題(3.3まで)は別解が色々ありえる。

Chapter 4

抽象構文の生成。

EXERCISE 4

4.3, 4.4 は ML-Yacc (.grm)内で表示させない場合、 int list を返した後に外側のプログラムで表示させてあげないと 結果が正しいのかどうかが分からない。

4.5 は演算順位の考慮(乗除算が加減算より高いはず) が抜けているがもう直す気がない。


Attach file: filechap4-ex.pdf 2615 download [Information] filechap3-ex.pdf 3353 download [Information] filechap2-ex-r2.pdf 2848 download [Information] filechap2.pdf 3354 download [Information]

Reload   New Lower page making Edit Freeze Diff Upload Copy Rename   Front page List of pages Search Recent changes Backup Referer   Help   RSS of recent changes
Last-modified: (4418d)