実践コンパイラ構成法 Compiler Construction through Practice

正誤表

四則演算インタプリタ

抽象構文木のインタプリタ

• interp.ml
• 実行（OCaml上）：

  # #use "interp.ml" ;;
  # let prog = Stmts (Assign ("x",Plus (Num 1,Times (Num 2,Num 3))), 
                        Stmts (Assign ("y",Div (Id "x",Num 4)), Print (Id "y")))  ;;
  # interp prog ;;
  1
  - : id -> int = 
  

• 練習問題
  1. 「文」を「式」に埋め込む値構成子「StmtExp (文，式)」（「式」の値 を返す）を付加し，「文」の中で代入した変数を「式」で利用できる ようにしなさい．
     「StmtExp (文, 式)」を，四則演算言語で「(文，式)」と記述することにす ると，例えば，「y = (x = 1 + 2, x); print (y)」に相当する構文木は，次のようにする．

     # let prog1 = Stmts (Assign ("y",
           StmtExp (Assign ("x", Plus (Num 1, Num 2)), Id "x")), Print (Id "y")) ;;
     # interp prog1 ;;
     3
     

     注：上記の例の変数「x」は，文をまたがって使用できない．例えば， 「y = (x = 1 + 2, x); print (x)」に相当する構文木の評価結果は，次のとおりでよい．

     # let prog2 = Stmts (Assign ("y",
           StmtExp (Assign ("x", Plus (Num 1, Num 2)), Id "x")), Print (Id "x")) ;;
     # interp prog2 ;;
     Exception: No_such_symbol.
     

  2. 「StmtExp (文, 式)」の文の影響が，後続の文にも反映されるよう にしなさい．
     例えば，上記 prog2 は，次のようにする．

     # interp prog2 ;;
     3
     

フロントエンド+構文木インタプリタ

• 字句解析器：lexer1.mll
• 構文解析器：parser1.mly
• 構文木インタプリタ ：interp.ml
• メイン：calc1.ml
• makeファイル： Makefile
• ビルド： make
• 実行：

  calc
  

FIRST集合とFOLLOW集合

• nullable，FIRST，FOLLOWの計算関数：firstFollow.ml
• サンプル文法：

  S -> E $
  E -> id
  E -> id ( E )
  E -> E + id
  

• 実行（OCaml上）：

  # #use "firstFollow.ml";;
  # let rule =
  [  ["S"; "E"; "$"];
     ["E"; "id"];
     ["E"; "id"; "("; "E"; ")"];
     ["E"; "E"; "+"; "id"]
  ];;
  # firstFollow rule;;
  nullable(S):false
  nullable(E):false
  
  FIRST(S):id
  FIRST(E):id
  
  FOLLOW(S):
  FOLLOW(E):$ ) +
  - : unit = ()
  

• 練習問題： 四則演算言語の文法について，空導出可能性，FIRST集 合，FOLLOW集合を自分で計算し，正しいかどうかfirstFollowを用いて確認しなさい．

Simpleコンパイラ

サンプルプログラム

• sort.spl， sample.spl

フロントエンド

• 字句解析器：lexer.mll
• 構文解析器：parser.mly
• 抽象構文木：ast.ml
• メイン：print_ast.ml
• makeファイル：Makefile
• ビルド： make
• 実行： print_ast sample.spl
  
  
• 練習問題
  1. 「//」から行末までをコメントにできるようにしなさい．
  2. 構文エラーの際に，行番号と直後の字句を印字するようにしなさい．
  3. 生成規則に，エラー回復を考慮してerrorトークンを挿入しなさい．

バックエンド

• 意味解析器： semant.ml， table.ml， types.ml
  注：古いOCamlには，こちらのsemant.ml， table.mlを使用．
• コード生成器：emitter.ml （MacOS X：emitter.ml， Cygwin：emitter.ml）
  注：古いOCamlには，こちらのemitter.mlを使用．
• メイン：sim.ml
• makeファイル：Makefile
• ビルド： make
• 実行：

  simc sample.spl
  a.out
  

• 練習：次のようにSimpleを拡張しなさい．
  1. 「式1 % 式2」 とすることによって，「式1」 を 「式2」 で 割っ た余りを計算する演算子「%」を付加しなさい.
  2. 「int 変数 = 式」とすることによって，変数を宣言するとともに， 「式」の値を初期値として設定できるようにしなさい．
  3. 「式1 ^ 式2」 とすることによって，「式1」 を 「式2」 乗する 演算子「^」を付加しなさい．
  4. 「変数 ++」 とすることによって，「変数」 の値を 1 増加させ，増加 前の値を返す演算子「++」を付加せよ.
  5. 「変数 += 式」 とすることによって，「変数」 の値に 「式」 の 値 を加算し，その結果で「変数」を更新する文を付加しなさい．
  6. 「do 文 while ( 条件 )」 とすることによって，「条件」 が満たさ れている間 「文」 を繰り返し実行するような文を付加しなさい（while 文と違い，「文」が少なくとも1回は実行されることに注意）．
  7. 「for (変数 = 式1 .. 式2) 文」 の構文で，for文を実現しなさい． ただし，このfor文は次のようなステップで実行するものとする．
     1. 「変数」に「式1」の値を初期値として代入する．
     2. 「変数」の値が「式2」の値に一致すれば終了，そうでなければ次を実行する．
     3. 「文」を実行する．
     4. 「変数」の値を1増やして更新する．
     5. ステップ2に戻る．
     
     例：

     {
        int x, rlt;
     
        rlt = 1;
        for (x = 0 .. 5) 
             rlt = rlt * 3;
        iprint(rlt);
     }
     

  8. ここで示したSimpleコンパイラは，関数内の「return e」の「e」 の型と，関数の返戻値の型の一致を調べていない．この型検査を 付加しなさい．
  9. その他

覗き穴最適化

• サンプル：tmp.s
• 最適化器：peephole.mll
• ビルド： ocamllex peephole.mll; ocaml -o peephole peephole.ml
• 実行：

  peephole < tmp.s > opt.s
  gcc opt.s
  a.out