計算機科学実験及び演習3
ソフトウェア 資料
1 実験の目標
2 Small C
3 字句解析
3.1 概要
3.2 実際に使ってみる
3.3 Racketコードの説明
3.4 コンパイラにおける字句解析器の働き
4 構文解析
4.1 実際に使ってみる
4.2 parser関数
4.3 抽象構文木
5 シンタックスシュガー
6 意味解析
6.1 オブジェクト情報の収集
6.2 名前に関する意味解析の実装
6.3 式の形の検査
6.4 型検査
7 バックエンド
7.1 中間表現
7.2 データフロー解析と最適化
7.3 相対番地の計算
7.4 MIPSコードの生成
8 付録A:   Racket Cheat Sheet
8.1 リスト
8.2 ベクタ
8.3 集合
8.4 辞書
8.5 文字列
8.6 構造体
8.7 バッククォート・アンクォート
8.8 エラー・例外処理
8.9 パターンマッチ
8.10 トレース
9 付録B:   Small Cコンパイラ要求仕様
9.1 演習室の計算機環境
9.2 要求仕様
9.2.1 コンパイラ実装言語がRacketの場合
9.2.2 コンパイラ実装言語がRacket以外の場合
9.3 Small Cコンパイラ起動ユーティリティ
6.4

計算機科学実験及び演習3
ソフトウェア 資料

馬谷 誠二 <umatani@kuis.kyoto-u.ac.jp>

最終更新: Monday, May 16th, 2016

    1 実験の目標

    2 Small C

    3 字句解析

      3.1 概要

      3.2 実際に使ってみる

      3.3 Racketコードの説明

      3.4 コンパイラにおける字句解析器の働き

    4 構文解析

      4.1 実際に使ってみる

      4.2 parser関数

      4.3 抽象構文木

    5 シンタックスシュガー

    6 意味解析

      6.1 オブジェクト情報の収集

      6.2 名前に関する意味解析の実装

      6.3 式の形の検査

      6.4 型検査

    7 バックエンド

      7.1 中間表現

      7.2 データフロー解析と最適化

      7.3 相対番地の計算

      7.4 MIPSコードの生成

    8 付録A: Racket Cheat Sheet

      8.1 リスト

      8.2 ベクタ

      8.3 集合

      8.4 辞書

      8.5 文字列

      8.6 構造体

      8.7 バッククォート・アンクォート

      8.8 エラー・例外処理

      8.9 パターンマッチ

      8.10 トレース

    9 付録B: Small Cコンパイラ要求仕様

      9.1 演習室の計算機環境

      9.2 要求仕様

        9.2.1 コンパイラ実装言語がRacketの場合

        9.2.2 コンパイラ実装言語がRacket以外の場合

      9.3 Small Cコンパイラ起動ユーティリティ


課題一覧

*印のついているものは選択課題.通常,文字の大きな課題はそれ以外の課題より時間がかかる.

課題1*課題2*課題3*課題4課題5*課題6*課題7課題8*課題9課題10課題11課題12課題13課題14*課題15課題16*

1 実験の目標

この実験ではC言語のサブセット言語であるSmall Cのコンパイラを作成する.

Small C言語は,型はint,一次元配列,ポインタのみ,制御構造はifwhileforのみ,演算子も基本的なもののみを持った小さなプログラミング言語である.Small Cの詳細については次章で示すが,プログラムの意味は原則としてC言語の仕様に従うものとする.たとえば,次は正しいSmall Cのプログラムである.

test.sc

int f(int x) {

  while(x > 1) {

    x = x - 2;

  }

  return x;

}

 

void main() {

  int x;

  print(f(9));

}

この実験では,Small Cプログラムを含んだソースファイルの名前(たとえば上記のプログラムは"test.sc"という名前のファイルに含まれているとする)を受け取り,標準出力にコンパイルした結果のMIPS11 D.A.Patterson and J.L.Hennessy, コンピュータの構成と設計 第5版,日経BP社, (付録Aの原文PDFはSPIMのホームページにも置かれている.)コードを返すようなコンパイラを,Racket言語上で作成する.生成されたコードの動作確認にはSPIMシミュレータを用いる.上のプログラムをRacket対話環境で

> (compile "test.sc")

としてコンパイルした結果は,たとえば次のようになる.

        .text

        .globl    main

  f:    subu  $sp,$sp,24

        sw    $ra,4($sp)

        sw    $fp,0($sp)

        addiu $fp,$sp,20

  L0:   move  $t0,$a0

        li    $t1,1

        sgt   $t0,$t0,$t1

        beqz  $t0,L1

        move  $t0,$a0

        li    $t1,2

        sub   $t0,$t0,$t1

        move  $a0,$t0

        j    L0

  L1:   move  $v0,$a0

        lw    $fp,0($sp)

        lw    $ra,4($sp)

        addiu $sp,$sp,24

        jr    $ra

  main: subu  $sp,$sp,24

        sw    $ra,4($sp)

        sw    $fp,0($sp)

        addiu $fp,$sp,20

        li    $a0,9

        jal   f

        sw    $v0,0($fp)

        li    $v0,1

        lw    $a0,0($fp)

        syscall

        lw    $fp,0($sp)

        lw    $ra,4($sp)

        addiu $sp,$sp,24

        jr    $ra

生成されるコードにおいて,関数呼出し,引数渡しなどはMIPSの呼出し規約1に沿うように出力するものとする.

本実験で作成するコンパイラは,字句解析部,構文解析部,意味解析部,コード生成部から成る.このうち,字句解析部と構文解析部の作成にはそれぞれparser-tools/lexparser-tools/yaccというRacketの標準ライブラリを利用する.

注意: 本資料の解説はあくまでも一つの実装方法を提示しただけであり,Small Cコンパイラとして正しく動作するものを作成すれば,本資料の方法に従う必要はない.さらに,コンパイラの実装言語がRacketである必要もなく,好きなプログラミング言語を使ってかまわない.

2 Small C

Small Cの文法を以下に示す....は非終端記号を表し,...は終端記号を表すものとする.また,...optは,...があってもなくてもどちらでも良いことを意味する.

文法中のidentifierは英字,数字と下線記号_の列であり,最初の文字は英字とする.大文字と小文字は区別される.constant0か,あるいは0以外の数字から始まる数字の列である.終端記号の区切りは任意個のスペース,タブまたは改行とする.

 

program

 ::= 

external-declaration

 

  |  

program external-declaration

 

external-declaration

 ::= 

declaration

 

  |  

function-prototype

 

  |  

function-definition

 

declaration

 ::= 

type-specifier declarator-list ;

 

declarator-list

 ::= 

declarator

 

  |  

declarator-list , declarator

 

declarator

 ::= 

direct-declarator

 

  |  

* direct-declarator

 

direct-declarator

 ::= 

identifier

 

  |  

identifier [ constant ]

 

function-prototype

 ::= 

type-specifier function-declarator ;

 

function-declarator

 ::= 

identifier ( parameter-type-listopt )

 

  |  

* identifier ( parameter-type-listopt )

 

function-definition

 ::= 

type-specifier function-declarator compound-statement

 

parameter-type-list

 ::= 

parameter-declaration

 

  |  

parameter-type-list , parameter-declaration

 

parameter-declaration

 ::= 

type-specifier parameter-declarator

 

parameter-declarator

 ::= 

identifier

 

  |  

* identifier

 

type-specifier

 ::= 

int  |  void

 

statement

 ::= 

;

 

  |  

expression ;

 

  |  

compound-statement

 

  |  

if ( expression ) statement

 

  |  

if ( expression ) statement else statement

 

  |  

while ( expression ) statement

 

  |  

for ( expressionopt ; expressionopt ; expressionopt ) statement

 

  |  

return expressionopt ;

 

compound-statement

 ::= 

{ declaration-listopt statement-listopt }

 

declaration-list

 ::= 

declaration

 

  |  

declaration-list declaration

 

statement-list

 ::= 

statement

 

  |  

statement-list statement

 

expression

 ::= 

assign-expr

 

  |  

expression , assign-expr

 

assign-expr

 ::= 

logical-OR-expr

 

  |  

logical-OR-expr = assign-expr

 

logical-OR-expr

 ::= 

logical-AND-expr

 

  |  

logical-OR-expr || logical-AND-expr

 

logical-AND-expr

 ::= 

equality-expr

 

  |  

logical-AND-expr && equality-expr

 

equality-expr

 ::= 

relational-expr

 

  |  

equality-expr == relational-expr

 

  |  

equality-expr != relational-expr

 

relational-expr

 ::= 

add-expr

 

  |  

relational-expr < add-expr

 

  |  

relational-expr > add-expr

 

  |  

relational-expr <= add-expr

 

  |  

relational-expr >= add-expr

 

add-expr

 ::= 

mult-expr

 

  |  

add-expr + mult-expr

 

  |  

add-expr - mult-expr

 

mult-expr

 ::= 

unary-expr

 

  |  

mult-expr * unary-expr

 

  |  

mult-expr / unary-expr

 

unary-expr

 ::= 

postfix-expr

 

  |  

- unary-expr

 

  |  

& unary-expr

 

  |  

* unary-expr

 

postfix-expr

 ::= 

primary-expr

 

  |  

postfix-expr [ expression ]

 

  |  

identifier ( argument-expression-listopt )

 

primary-expr

 ::= 

identifier

 

  |  

constant

 

  |  

( expression )

 

argument-expression-list

 ::= 

assign-expr

 

  |  

argument-expression-list , assign-expr

とくに断らない限り,Small Cの各構文の意味はC言語に準拠するものとする.Small CがC言語ならびに2回生講義「コンパイラ」22 PandAの実験3のリソースに講義資料ファイル一式を置いてある.で扱ったTiny Cと異なる主な点は次のとおりである.

まずは,以降のコンパイラ作成に用いるテスト用に簡単なSmall Cプログラムを作成してみよう.Small CはC言語のサブセットなので,print関数さえ適当に定義すれば,gccなど通常のCコンパイラで動作確認できる.

【課題1】(選択) Small Cでソートプログラムを書け.ソート対象のデータは,サイズが8の一次元int配列の大域変数に格納することとし,main()関数の冒頭で適当な値で埋めることとする.ソートした結果をprint関数を使って昇順で画面に表示せよ.ソーティング・アルゴリズムは好きなものを使って良い.

【課題2】(選択) Small Cへの言語拡張について検討し,その文法を定義せよ.言語拡張としては,たとえば
  • float型(intfloatの間の演算も行えるようにする)

  • 多次元配列

  • ポインタへのポインタ

  • 構造体型

などが考えられる.

なお,課題2では文法定義のみを要求しているが,検討した拡張機能を実際にSmall Cコンパイラで実装するのであれば,以降のSmall Cコンパイラ実装に関わるすべての課題において,拡張機能をどのようにして実現したかについて説明すること(以降の課題でも,その都度,加点する).

3 字句解析

字句解析とは,ソースプログラム(文字列)を入力として受け取り,数・識別子・キーワードなどの意味のある単位(トークンと呼ばれる)に切り分け,その結果のトークンの列を返す処理である.返されるトークン列中には,通常,ソースプログラム中でそれらが出現したのと同じ順番にトークンを並べる.本章では,Racketに標準で含まれているライブラリを用いて,字句解析を行うRacket関数(字句解析器と呼ぶ)を作成する方法について説明する.

3.1 概要

最初に,parser-tools/lexモジュールを用いた字句解析器の作成について説明する.字句解析器は,Small Cコンパイラにおいて構文解析器から呼び出される形で使用されるため,構文解析器を作成するためのライブラリであるparser-tools/yaccモジュールを使ったコードとのやり取りの仕方についても同時に説明する.

parser-tools/yaccが生成する構文解析器は,字句解析器であるRacket関数を引数に受け取る,Racketの高階関数として定義される.構文解析時には,入力されたソースの先頭からトークンを取得するために,構文解析器の内部で引数として受け取った字句解析を行なう関数を呼び出す.したがって,一般的な字句解析器の働きは,入力ソースの先頭からパターンに適合する字句要素を切り出しそのパターンに対応するアクションを実行することであるが,コンパイラ作成において典型的なアクションは,その字句要素を構文解析に適したデータ(トークン)として構文解析器に返すことである.

字句解析関数を機械的に作成するためのRacketライブラリがparser-tools/lexモジュールである.本資料ではparser-tools/lexモジュールの機能のうち,Small Cを実装するために最低限必要な部分についてのみ説明する.より詳しく知りたい場合には,Racket公式ドキュメントの該当個所を参照すると良い(本資料中に現れる各種シンボルからも,公式ドキュメント中の該当ページへのリンクが張られている).

3.2 実際に使ってみる

字句解析器の簡単な例として以下のRacketプログラム"calc0.rkt"を使ってみる.

calc0.rkt

#lang racket
(require parser-tools/lex
         (prefix-in : parser-tools/lex-sre))
(provide (all-defined-out))
 
(define-lex-abbrevs
  (digit   (char-range "0" "9")))
 
(define calc-lexer
  (lexer
   ((:+ digit)    lexeme)
   ((:or "+" "*") lexeme)
   (whitespace    (calc-lexer input-port))
   ((eof)         'eof)))

このファイルをRacket対話環境に読み込み,適当な入力文字列に対して実行すると次のようになる.

> (define p (open-input-string "12 + 3 * 456 + 7"))
> (calc-lexer p)

"12"

> (calc-lexer p)

"+"

> (calc-lexer p)

"3"

> (calc-lexer p)

"*"

> (calc-lexer p)

"456"

> (calc-lexer p)

"+"

> (calc-lexer p)

"7"

> (calc-lexer p)

'eof

3.3 Racketコードの説明

まず,ファイル先頭のrequireによって字句解析器生成に必要な2つのモジュールを読み込んでいる.parser-tools/lex-sreモジュールは様々な正規表現用の演算を含んだモジュールであり,:をプレフィックスに指定して読み込むことで,その中で定義されているor+といった演算子を:or:+のように参照できる.parser-tools/lex-sreを使った正規表現の記述方法の例を以下の表に示す.

正規表現(pattern

一致する文字列

"abc"

abc

(:: "a" "b" (:* "c"))

ab, abc, abcc, abccc, ...

(:: "a" "b" (:+ "c"))

abc, abcc, abccc, ...

(:: "a" (:+ (:: "b" "c")))

abc, abcbc, abcbcbc, ...

(:: "a" (:? (:: "b" "c")))

a, abc

(:or "a" "b" "c")

a, b, c

(char-set "abc")

a, b, c

(char-range "a" "z")

a, b, c, ..., x, y, z

whitespace

空白文字(スペース,タブ,改行)

any-char

任意の文字

(:~ "a" "b")

abを除く任意の文字

define-lex-abbrevsを用いると正規表現に名前をつけることができ,次のlexer定義中のパターンでその名前を使用することができる.たとえば"calc0.rkt"では,「0から9までの(1文字からなる文字列としての)数字のいずれか」という正規表現にdigitという名前をつけている.

lexerは,(pattern action)の並びを引数として受け取り,そこに記述された規則に従って字句解析を行なう関数を生成して返す.actionにはRacketの任意の式を記述可能であり,入力文字列からpatternに一致する文字列を切り出したときにその式が評価され,字句解析関数の結果として返される.

字句解析関数が呼び出されると,与えられたパターンpatternに一致する最長の文字列が見つかるまで文字が読み込まれる.最長の文字列と一致するパターンが複数個存在する場合は,lexerの引数に指定した順番に従い,より先頭に近いパターンが優先して選ばれる.一致するパターンが決まると,対応するactionが実行される.この時,パターンに一致した文字列は,アクション中でlexemeという名前の変数に束縛されている.

また,アクション中ではRacket実行環境における入力ソースをあらわすportオブジェクトがinput-portという名前の変数に束縛されている.生成される字句解析関数はportオブジェクトを引数として受け取る1引数関数であり,たとえば"calc0.rkt"では空白文字を読み飛ばすためにcalc-lexerを再帰的に呼び出しているが,その引数にinput-portを使用している.portオブジェクトは,先程の使用例のように文字列からopen-input-string関数を使って生成することが可能である.それ以外にも,ファイルの内容を読み出すためのopen-input-file関数などがある(この実験で作成するSmall Cコンパイラはファイルから読み出さなくてはいけない).

(eof)というパターンは,portオブジェクトがあらわす入力ソースが尽きたことを意味し,"calc0.rkt"では,その場合は単にシンボルeofを返している(これは(eof)のケースを指定しない場合のデフォルトの動作であるが,明示的に書く方が望ましいスタイルである).

3.4 コンパイラにおける字句解析器の働き

3.2節"calc0.rkt"のアクションでは切り出した字句要素をそのまま文字列として返すだけであったが,parser-tools/yaccモジュールを用いたコンパイラの作成では,切り出した字句要素を構文解析に適したデータ(トークン)に適宜変換し(たとえば識別子なら識別子名を表すシンボル,数値ならその値等),それを構文解析器に渡す必要がある.トークンの値の他にトークンの種類(識別子,数値等)も渡す必要がある.次章で述べるが,構文解析器ではトークンの種類を表すシンボルを終端記号として扱う.

parser-tools/lexparser-tools/yaccの間でやり取りするトークンの種類を定義するため,Racketにはdefine-tokensdefine-empty-tokensが用意されている.define-tokensで定義されたトークンは値を持ち,define-empty-tokensで定義されたトークンは値を持たない.構文解析器と一緒に用いる字句解析器では,トークンオブジェクトを生成するようなアクションを記述すれば良い.

例として"calc0.rkt"を修正することを考える.数字の列を整数値を値に持つトークンへ,文字"+""*"を値を持たないトークンへと変換するには,"calc0.rkt"を次のように修正すれば良い(ファイル名を"calc1.rkt"に付け替えるものとする). なおここでは,入力の終端を表すeofオブジェクトも統一的に扱い,専用のトークンへ変換することにしている.

calc1.rkt

#lang racket
(require parser-tools/lex
         (prefix-in : parser-tools/lex-sre))
(provide (all-defined-out))
 
(define-empty-tokens tokens-without-value
  (+ * EOF))
 
(define-tokens tokens-with-value
  (NUM))
 
(define-lex-abbrevs
  (digit   (char-range "0" "9")))
 
(define calc-lexer
  (lexer
   ((:+ digit) (token-NUM (string->number lexeme)))
   ("+"        (token-+))
   ("*"        (token-*))
   (whitespace (calc-lexer input-port))
   ((eof)      (token-EOF))))

define-empty-tokensの第1引数として渡しているtokens-without-valuedefine-tokensの第1引数として渡しているtokens-with-valueは,そこで定義しているトークンの集合につけられるグループ名であるが,本実験で作成するコンパイラではこれら(値ありとなしの2グループ)以外のトークングループを扱う必要はないため,適当な名前をつけている.

lexer中のアクションでトークンオブジェクトを生成するには,token-トークンの種類名という名前のコンストラクタ関数を呼び出す.define-empty-tokensによって定義された値を持たないトークンの場合には無引数で呼び出し,define-tokensによって定義された値を持つトークンの場合には持たせる値を引数にして呼び出す. ここでは,NUMトークンの値として文字列ではなく整数値が必要なため,string->number関数により変換した値を使ってトークンを生成している.

先程と同じようにRacket対話環境に読み込んで実行すると次のようになる.

> (define p (open-input-string "12 + 3 * 456 + 7"))
> (calc-lexer p)

(token 'NUM 12)

> (calc-lexer p)

'+

> (calc-lexer p)

(token 'NUM 3)

> (calc-lexer p)

'*

> (calc-lexer p)

(token 'NUM 456)

> (calc-lexer p)

'+

> (calc-lexer p)

(token 'NUM 7)

> (calc-lexer p)

'EOF

値を持つトークンオブジェクトが(token トークンの種類名 トークンの値)と表示されるtoken構造体として返ってくることが確認できる.それぞれのフィールドは,token-nametoken-value関数で取り出すことができる.一方,値を持たないオブジェクトは実は,単にトークンの種類名を名前に持つシンボルに過ぎないことが見て取れる(が,この例のように,シンボルとしてではなくトークンとして統一的に扱う方が分かりやすくて良い).

意味解析部などのコンパイラの後ろのフェーズでプログラム中にエラーが存在することが判明した場合,ソースファイルの何行目の何文字目にエラーがあるか(位置情報)とともにエラー表示をするのが望ましい.そこで,字句解析器への最後の機能追加として,トークンオブジェクトにソースファイル中の位置情報を埋め込むことを考える.

parser-tools/lex(およびparser-tools/yacc)モジュールで位置情報を含んだトークンオブジェクトを扱うのは非常に簡単である.字句解析器の作成では先程のコード中のlexerlexer-src-posに置きかえるだけで良い.ただし,空白の扱いには注意が必要である.これまでの"calc0.rkt""calc1.rkt"では空白を読み飛ばすために再帰呼出しを行っていたが,位置情報を自動で埋め込むようにすると,すべての空白に対しても位置情報が埋め込まれてしまい,字句解析器の出力であるトークン列が煩雑になる.そのような無駄な位置情報の埋め込みを避けるには,再帰呼出しが返す値を

(return-without-pos (calc-lexer input-port))

のようにしてreturn-without-pos関数に渡せば良い.

位置情報を埋め込むよう修正した"calc1.rkt"を,

test.calc

12

  + 3 * 456

+ 7

という内容のファイル"test.calc"を入力として実行すると次のようになる.

> (define p (open-input-file "test.calc"))
> (port-count-lines! p)
> (calc-lexer p)

(position-token (token 'NUM 12) (position 1 1 0) (position 3 1 2))

> (calc-lexer p)

(position-token '+ (position 6 2 2) (position 7 2 3))

> (calc-lexer p)

(position-token (token 'NUM 3) (position 8 2 4) (position 9 2 5))

> (calc-lexer p)

(position-token '* (position 10 2 6) (position 11 2 7))

> (calc-lexer p)

(position-token (token 'NUM 456) (position 12 2 8) (position 15 2 11))

> (calc-lexer p)

(position-token '+ (position 16 3 0) (position 17 3 1))

> (calc-lexer p)

(position-token (token 'NUM 7) (position 18 3 2) (position 19 3 3))

> (calc-lexer p)

(position-token 'EOF (position 20 4 0) (position 20 4 0))

トークンオブジェクトが2つの位置情報(トークンの開始位置と終了位置)と一緒にposition-token構造体オブジェクトとして返されていることが分かる.位置情報はposition構造体オブジェクトにより表され,各フィールドはそれぞれファイル先頭からのオフセット(何文字目か),行数,その行の何文字目かを意味している.ここで,portオブジェクトをcalc-lexerで使用する前に呼び出しているport-count-lines!は,入力中の改行の個数を数えるようセッティングするための準備関数である(先にこれを呼び出しておかないと行数や桁数が#fとなってしまう).

位置情報つきトークンオブジェクト(position-token構造体)や位置情報オブジェクト(position構造体)の各フィールドは,それぞれ,position-token-token(位置情報つきトークンオブジェクトのトークン),position-token-start-pos(位置情報つきトークンオブジェクトの開始位置),position-token-end-pos(位置情報つきトークンオブジェクトの終了位置),position-offset(位置情報オブジェクトのオフセット),position-line(位置情報オブジェクトの行数),position-col(位置情報オブジェクトのその行の何文字目か)で取り出すことができる.

4 構文解析

構文解析とは,入力としてトークン列を受け取り,より大きなコードのまとまりやそれらの間の関係(プログラムの構造)を識別する処理である.コンパイラにおける構文解析の典型的な出力結果は,プログラムの構造を表現する木構造データ(抽象構文木)の形を取る.たとえば,「プログラム全体は複数の関数定義の並びからなり,それぞれの関数定義は名前と引数宣言リストと関数本体からなり,…」のようなプログラムの場合,抽象構文木は,「プログラム全体を表すノードをルートとし,その複数の子ノードは関数定義を表すノードとし,それらのノードはさらに子ノードとして名前のノードと引数宣言リストのノードと関数本体のノードを持ち,…」のような構造の木とする.本章では,Racketに標準で含まれているライブラリを用いて,構文解析を行うRacket関数(構文解析器と呼ぶ)を作成する方法について説明する.

4.1 実際に使ってみる

まず,"calc1.rkt"を字句解析部とする構文解析器をparser-tools/yaccを使って作成してみよう.ここでは,構文解析の結果をコンパイラのように抽象構文木として出力するのではなく,電卓のように数式を計算した結果を表示するようにしてみる.

受理する構文の文法定義は次のとおりである.

 

program

 ::= 

expression

 

expression

 ::= 

multiplicative-expr

 

  |  

multiplicative-expr + expression

 

multiplicative-expr

 ::= 

constant

 

  |  

constant * multiplicative-expr

この文法で定義される式(program)を受理し計算結果を返すプログラムは,ファイル先頭のrequireparser-tools/yaccも読み込み,さらに以下の関数定義を"calc1.rkt"に追加することにより作成できる.以降,位置情報を埋め込むための修正を適用した上で,以下の定義を追加したファイルを"calc2.rkt"と呼ぶことにする.

(define calc-parser
  (parser
   (start program)
   (end EOF)
   (src-pos)
   (debug "simple-parser.tbl")
   (error (lambda (tok-ok? tok-name tok-value start-pos end-pos)
            (error "parse error:" tok-name tok-value)))
   (tokens tokens-with-value tokens-without-value)
   (grammar
    (program ((expression) $1))
    (expression ((multiplicative-expr) $1)
                 ((multiplicative-expr + expression) (+ $1 $3)))
    (multiplicative-expr ((NUM) $1)
                          ((NUM * multiplicative-expr) (* $1 $3))))))
 
(define (parse-string s)
  (let ((p (open-input-string s)))
    (calc-parser (lambda () (calc-lexer p)))))

文字列を入力として受け取り構文解析を行なう関数parse-stringを,適当な文字列を使って実行すると次のようになる.

> (parse-string "1+2*3+4")

11

【ミニ課題】 上の例で,「1+2*3+4」の足し算と掛け算の優先順位が何故正しく反映されているのか,考察せよ.

4.2 parser関数

parser関数では,(属性 )の形式のいくつかの引数を指定して文法を定義する.以下,"calc2.rkt"で用いている属性について順に説明する.parser関数には,これら以外にもいくつかの属性を指定できる.詳しくはRacket公式ドキュメントの該当個所を参照してほしい.

grammar属性で指定する生成規則の形式は次のとおりである.

    (nonterminal ((rule1) action1)

                   ...

                   (rulen) actionn)))

これは非終端記号nonterminalの生成規則の定義である.rulei は,終端記号(トークンの種類名)または非終端記号を任意個並べて表現する.actioninonterminalへ還元されるときに評価されるRacketの式であり,nonterminalの属性値となる.

parser-tools/yaccが生成する構文解析器はLALR(1)構文解析を行なう.たとえば,生成規則:
(expr ((NUM) $1)
      ((expr + NUM) (+ $1 $3))
      ((expr - NUM) (- $1 $3)))
に対して,入力"1-2+3"が与えられると次のように構文解析される(字句解析には"calc2.rkt"-演算子の字句定義を追加したものを用いるものとする).

・1-2+3

    

NUM・-2+3

    

シフト

expr・-2+3

    

還元

expr-・2+3

    

シフト

expr-NUM・+3

    

シフト

expr・+3

    

還元

expr+・3

    

シフト

expr+NUM・

    

シフト

expr・

    

還元

actioni中に現れる $nrulein番目の記号(終端記号または非終端記号)の属性値を表す.n番目の記号が終端記号の場合,$nの値はトークンの値(つまり,トークンオブジェクトからtoken-valueで取り出せる値)である.また,アクション中では変数$n-start-posおよび$n-end-posにより,n番目のトークンオブジェクトに含まれている位置情報を取得できる.

上記のようにして作成した構文解析器(Racket関数)は,字句解析を行なう無引数の関数(内部で入力portオブジェクトに対し字句解析器を呼び出す)を引数として受け取る.引数の関数は,呼び出されるたびに入力中の次のトークンを返す.構文解析器が返す値は,文法中の開始記号の属性値である.

【課題3】(選択) "calc2.rkt"をRacket上で実際に実行してみよ.

4.3 抽象構文木

前節で作成した構文解析器ではアクション部分で算術式の計算を行っていたが,コンパイラにおいて,構文解析器はソースプログラムを受け取り,構文的に正しければ,抽象構文木(abstract syntax tree)を返す.

抽象構文木は,ソースプログラムの内部表現である.入力であるソースプログラムは単にトークンを表す文字と空白文字の羅列に過ぎなかったが,構文木はソースプログラムの構造を反映した木構造を持っているため,構文解析の後に行なわれる処理(意味解析やコード生成,最適化)に適した形をしている.

抽象構文木を表すデータ構造の定義の仕方については,2回生講義「コンパイラ」で学んだとおりである.講義資料として配布されたTiny Cの抽象構文木定義ファイル"syntax.rkt"2を参考にしつつ,Small C の構文定義に沿うよう適宜追加・修正すれば良い.

たとえば"syntax.rkt"2中において,算術式のためのデータ型は

(struct aop-exp (op left right pos) #:transparent)

と定義されており,これをそのまま用いると,4.1節expressionの規則の場合には

(expression ((multiplicative-expr) $1)
            ((multiplicative-expr + expression) (aop-exp 'add $1 $3 $2-start-pos)))

のようにして木を構築すれば良い. ここでは,式の位置情報として+演算子トークンの開始位置を指定している.

【課題4】 2章の仕様に従い,Small Cの字句解析器および構文解析器を作成せよ.構文解析器は抽象構文木を生成し,返すものとする.生成される抽象構文木の各ノードには,ソースファイル中の位置情報を必ず含めなくてはいけない.抽象構文木に位置情報を含めておくと,この後の意味解析部でのエラー表示に用いることができる.該当する構文要素の中からどのトークンの位置を記録すべきか(たとえば式「x * y」の場合,先頭のxか演算子*か)は適当だと思うものを自由に選んでかまわない.

重要: フルセットのSmall C構文解析器のソースコード"parser.rkt"を公開する.ただし,抽象構文木を生成するアクション部分は空である.これをもとにして課題4に取り組むと多少手間が省けるはずである.

【課題5】(選択) 課題4で作成した構文解析器を用いていくつかのソースコードのパースを試みよ.また,構文的に誤りを含んだソースコードを与えた場合の動作についても何が起きるか確認せよ.

【課題6】(選択) 抽象構文木を受け取り,元のSmall Cプログラムを表示するプログラムを作成せよ.表示にあたっては,可能ならインデントを揃えたり適宜改行を挿入するなど読みやすさを工夫せよ.

なお,このような抽象構文木を巡回しながら行なう処理は次章以降の構文木変換,意味解析,コード生成でも頻繁に行なわれるため,木巡回処理をRacketの高階関数として汎用化しておくと便利である(高階関数で実装することをこの課題の必須要件とはしない).

5 シンタックスシュガー

Small Cの構文のうち,
  • 単項の-演算

  • else節のないif

  • for

  • 配列参照式

の4つについては,他の言語機能の組み合わせにより等価な動作を記述可能である.このような構文をシンタックスシュガーと呼ぶ.シンタックスシュガーを実装する場合,構文解析の直後に,抽象構文木のそれぞれ該当する部分を同等の動作を行なうコードの構文木表現へと変換しておけば,この後の処理で扱わなければならない構文の種類を減らすことができるため,コンパイラ全体がより簡単になる.

メモ: 別の方法として,前節の構文解析処理において,シンタックスシュガーに対応する非終端記号へ還元する際のアクションで,この節で説明している変換先の形の抽象構文木を構築して返すようにしても良い.その場合,シンタックスシュガーの実装のための独立したフェーズは不要となり,また,シンタックスシュガーのための抽象構文木の構造体を定義する必要もなくなる.(ただし,そのように実装すると,課題6において,元と全く同じプログラムを表示できなくなるが,それはかまわないものとする.)

単項の-演算の場合は非常に単純で,式 -e(を表す部分木)を二項演算式 0-e(を表す部分木)に置き換えれば良い.else節のないif文も単純であり,else節に空文 ; を含んでいると考えれば良い.

for文の場合,

  for(e1; e2; e3) s

  e1; while(e2){s e3;}

に置き換えれば良い(sが複文(compound statement)ならe3s中の文の並びの末尾に追加するのでも良い).

配列参照式e1[e2]は,間接参照式*(e1 + e2)に置き換えることができる.さらに,置き換えた結果,構文木中に&(*e)の形の式があらわれるなら,それはeへと置き換えることができる.

最後に,シンタックスシュガーとは異なるが,構文木に対する変換処理の一部としてSmall Cに組み込みのprint関数に関する次の暗黙のプロトタイプ宣言をプログラムの先頭に追加しておくことにする.こうしておけば,次章の意味解析において,printという名前を他の関数の名前と統一的に扱うことができる.

  void print(int i);

【課題7】 本節で説明した抽象構文木の変換処理を実装せよ.

【課題8】(選択) インクリメント演算子,do-while文等々,C言語にあってSmall Cにはない言語機能を検討し,抽象構文木の変換によって実現できるものをSmall Cに拡張機能として追加せよ(文法定義への対応する文法規則の追加や,字句解析器・構文解析器への機能追加が必要となることは言うまでもない).

6 意味解析

課題4の構文解析器は,構文的なエラーはチェックしているが,意味上のエラーについてはチェックしていない.また,この構文解析器が生成する構文木のままでは,コード生成のための情報が不足している.本節では意味解析によって意味上のエラーをチェックし,さらに,コード生成のために必要な情報を収集する.具体的には:

などを行なう.なお,局所変数の相対番地(オフセット)の計算ついては,中間表現への変換時に追加される一時変数の扱いも考慮しなければならないので,ここでは扱わない.

6.1 オブジェクト情報の収集

前章までは,オブジェクト(Small Cの場合,変数と関数)の情報としてその名前(本資料における実装ではRacketシンボル)のみを扱った.ここでは,コード生成に必要なその他の情報の取得と管理の方法について述べる.

名前とオブジェクトの対応づけは,講義「コンパイラ」の記憶領域割り当て(名前と相対番地の対応づけ)と同様の方法を(中間表現ではなく)抽象構文木を対象にして行えば良い.すなわち,抽象構文木を巡回しながら,"addr.rkt"2で用いられているdelta関数と同様の仕組み(一般に環境,あるいはシンボルテーブルと呼ばれる)によって,名前に関する諸々の情報を追加登録・検索してプログラム中に現れるすべての名前を管理する.ただし,Tiny Cの言語仕様では,宣言と参照が区別されておらず,プログラム中の最初の参照で環境に追加を行っていたが,Small Cでは環境への追加は,変数や関数の宣言(定義)時にのみ行い,参照時には環境の検索のみを行わなければならない(検索して見つからなければ,未宣言の名前を使っているのでエラーとする).

環境中でそれぞれの名前に対応づけるオブジェクト情報を格納するためのデータ型として,次のような構造体を用意する(以降,decl構造体あるいは単にオブジェクトと呼ぶことがある).

(struct decl (name lev kind type) #:transparent)

name: オブジェクトの名前(Racketシンボル)を含む.4章で作成した構文解析器(講義「コンパイラ」"syntax.rkt"2と同等の抽象構文木を出力するものとする)が返す抽象構文木のvar-expの唯一のフィールドtgtに含まれているのと同じものである.

lev: オブジェクトが宣言されているブロックのレベル(深さ)を表す.ブロックのレベルは:
  • 大域変数と(大域)関数のレベルは0

  • 関数のパラメータ宣言のレベルは1

  • 関数本体のブロックのレベルは2

  • 関数本体中の入れ子ブロックのレベルは3以上(深さに応じる)

とする.このフィールドに適切な値をセットするには,意味解析を行なうRacket関数に追加の引数を用意し,解析中の現在のブロックレベルを保持するようにすれば良い.たとえば,declarationstatementを意味解析するRacket関数をそれぞれsem-declarationsem-statementとすると,複文の解析を行なう時のレベルの調整は
(define (sem-statement stat lev ...)
  ...
  (if (compound-statement? stat)
      (begin
        ...
        (map (lambda (s)
               (sem-statement s (+ lev 1) ...))
             (compound-statement-stats stat))
        ...))
  ...)
のようになる(レベルの調整と無関係のコードについては省略).

kind: オブジェクトの種類を表す以下のいずれかのシンボルを含む.
  • var: 変数

  • parm: パラメータ

  • fun: 関数定義

  • proto: プロトタイプ宣言

たとえば,意味解析中に変数宣言を見つけたら,kindvarであるようなオブジェクトを生成する.パラメータや関数定義,プロトタイプ宣言についても同様である.

type: オブジェクトの型情報を含む.型情報は次のように再帰的に定義されたリスト構造データにより表現されるものとする.
  • int: int

  • (pointer t): 参照先の型がtであるようなポインタの型

  • (array t n): 要素の型がt,サイズがnであるような配列型

  • (fun r a1 ... an): 返り値の型がr,引数の型がそれぞれa1 ... anであるようなn引数関数の型.ただし,値を返さない関数の場合,rvoidとする.

注意: 言語拡張を行わない場合,Small Cのポインタが指す対象のデータ型はintのみであるが,拡張可能なようにpointerを表現している.また,後述の型検査において配列名をポインタと見なす際,int以外を指すpointer型を用いることになる.

それぞれの宣言のtypeフィールドは,その宣言に含まれる情報だけから簡単に求めることができる.

6.2 名前に関する意味解析の実装

ここでは,本章の冒頭で述べた意味解析のうち,名前とオブジェクトの対応づけ,オブジェクト情報の収集,ならびに重複定義の検査について説明する.

プログラム中で名前(識別子)が現れるのは,変数宣言,パラメータ宣言,関数定義,関数のプロトタイプ宣言,変数参照,関数呼出しの6種類である.それぞれの場合に応じて以下のとおり処理すれば良い.

変数宣言 変数宣言については以下のようにすれば良い.
  1. もし,その名前が初めて現れたものであれば(環境にまだ登録されてなければ),nameがその名前,kindvarlevがこの変数宣言のレベル,typeが宣言されている型のデータ表現にし,環境に追加する.

  2. 既にその名前が関数として定義されている(環境にfunあるいはprotoとして登録されている)場合,もし変数宣言されているのがレベル0(すなわち大域変数として宣言されている)ならば,二重宣言であるからエラー.そうでなければ,1と同様,変数として新たなオブジェクトを作成し環境に追加する.

  3. 既にその名前が変数として宣言されている(環境にvarとして登録されている)場合,同じレベルで宣言されているなら二重宣言であるからエラー.そうでなければ,1と同様,変数として新たなオブジェクトを作成し環境に追加する.すなわち,既に登録されている変数の名前を隠蔽するものとして扱う.

  4. 既にその名前がパラメータとして宣言されている(環境にparmとして登録されている)場合,1と同様,変数として新たなオブジェクトを作成し環境に追加する.ただし,この場合,パラメータが隠されてしまうので(エラーではなく)警告を発する.コンパイル時エラーは,1つでもあればそこでコンパイル処理を中断すれば良いが,警告はいくつあってもそのままコンパイル処理を続けてかまわない点が異なる.

ここで,新たにオブジェクトを生成した場合には,変数宣言ノード中の名前(シンボル)が入っていたフィールドには,代わりにオブジェクト(への参照)を格納する.

なお,変数宣言が局所変数である場合,その宣言のスコープに注意すること.つまり,宣言の追加された環境の下で意味解析するプログラムの範囲は,該当する複文に含まれる(さらに複文が入れ子になっている場合も含む)文に限られる.次のパラメータ宣言も同様に,そのパラメータを持つ関数定義の本体だけがその宣言のスコープである.

パラメータ宣言 パラメータ宣言についても変数宣言と(kindparmである等,自明な差異を除き)同様である.ただし,パラメータ宣言はブロックレベルが1の場合しかあり得ないので,二重宣言が起こるのはパラメータ同士の場合に限られることに注意.

プロトタイプ宣言 プロトタイプ宣言の場合も(kindprotoである,typeは返り値や引数に関する宣言内容を正しく反映している等,自明な差異を除き)同様である.プロトタイプ宣言は,ブロックレべルが0の場合しかあり得ないので,二重宣言が起こるのは関数定義,他のプロトタイプ宣言,大域変数宣言との間だけである.ただし,型に関する情報が同じである限り,プロトタイプ宣言は何度書いてもかまわず,エラーとはならない.また,関数定義の後に,型に関する情報の一致しているプロトタイプ宣言を書いてもかまわない.

関数定義 プロトタイプ宣言の場合と(kindfunである等,自明な差異を除き)ほぼ同じである.ただし,関数定義は1つだけでないといけないため,(型が一致していたとしても)同じ名前の関数定義が既に登録されていた場合には二重定義エラーである.

変数参照 変数やパラメータの参照時には,既に宣言された同名のオブジェクトが環境中に登録されているはずである.さもなければ,それは未宣言の変数を参照しているのでエラーである.このため,変数参照に対する解析は以下のようになる.
  • 環境中で同名のオブジェクトが変数またはパラメータとして宣言されている場合,そのオブジェクトを参照しているものとみなせば良い.変数参照(var-exp)ノード中の名前(シンボル)が入っていたフィールド(tgt)には,代わりに見つかったオブジェクト(への参照)を格納する.

  • 関数として定義されている場合,関数を変数として参照しているのでエラー.

  • 環境中に同名のオブジェクトが存在しない場合,未宣言の変数を参照しているのでエラー.

関数呼出し 関数呼出しの場合も変数参照の場合と同様である.

エラーおよび警告の表示方法については付録Bで詳しく説明している.提出するSmall Cコンパイラの表示は,必ずそこに書かれた方法に従うこと.

6.3 式の形の検査

文脈自由文法であるという理由から構文解析部では取り除くことのできなかったいくつかの「正しくないコード」も,前節の名前の参照と宣言の対応づけが解決した後でなら検出可能である.ここでは,メモリ参照に関する以下の2つの正しくないコードの検出を行なう.

まず,単項&演算子のオペランドはメモリ上の場所を表わすような式でないといけない.具体的には,任意の式ではなく変数参照式(たとえばa),配列参照式(たとえばa[2]),間接参照式(たとえば*p)のいずれかでなくてはいけない.ただし,配列参照式や間接参照式についてはシンタックスシュガーの実装の説明のところで説明したとおりに実装していれば,変換中に&演算子と*演算子が打ち消しあって消えているはずである.結局,この段階で許される&演算子のオペランドとしては変数参照式のみとなる.

次に,代入式の左辺は *e か,あるいは(関数名ではなく)変数名でなければならない.なおかつ後者の場合,その型がarrayであってはならない.

6.4 型検査

意味解析部で行なう処理の一部として最後に型検査を説明する.

Small CはC言語同様,静的に型付けされた言語であり,変数や関数がどのような型を持つかがソースプログラム中で明示的に宣言されている.型検査は,それらの宣言に基づいてプログラムが正しく書かれているかや,演算子が正しいオペランドに対して適用されているかなどをチェックする.

たとえば,

  int i, *p;

と2つの変数が宣言されているとき,式 i - *p は正しいが,i - p は正しくない.また,

  int f(int a);

と関数fが宣言されているとき,f(i)という呼出し式は正しいが,f(p)f(i, p) はどちらも正しくない(後者は引数の個数が宣言と合っていない).また,

  void f(int a);

と関数fが宣言されているなら,f(i) + 1 のようにfの返り値を足し算に使うような式も正しくない.

上記のように,プログラム中の構成要素について型に関して整合が取れている(以降,「well-typedである」と言う)か確認し,型に関する様々なプログラムエラーを検出するのが型検査の役割である.

Small Cプログラムは以下の条件を満たすとき,well-typedである.

【課題9】 本章で説明したすべての意味解析(名前とオブジェクトの対応づけ,オブジェクト情報の収集,重複定義の検査,式の形の検査,型検査)を実装せよ.実装する意味解析部は,おかしな箇所が検出されたプログラムに対してソースプログラム中の位置情報とともに適切なエラー表示をしなければならない(エラー表示の詳細は付録B参照). また,作成した意味解析部の出力する抽象構文木が収集したオブジェクト情報をきちんと含んでいることを確認せよ(サンプルプログラムを用意し,その実行例を示せ).

なお,本資料では説明を分かりやすくするため各意味解析処理を単独の処理として説明したが,いくつかの処理を一度の構文木巡回にまとめて行ってもかまわない.

7 バックエンド

Small Cの意味解析以降,コード生成までの処理については基本的に講義「コンパイラ」のTiny Cと同様の方法で行えば良い.つまり,より低レベルな中間表現へと変換し,中間表現を対象にデータフロー解析を行い,その結果を用いて最適化を施し,最適化後の中間表現を対象に局所変数の相対番地の計算を行った後,中間表現のそれぞれの文を対応するMIPS1コードへ変換する.

7.1 中間表現

Small Cのための中間表現は次のとおりである.ここでは中間表現の具象構文を気にする必要はないため,Racketの構造体定義のみ示す.

; ; プログラムは var-decl と fun-def のリスト
; 変数宣言
(struct var-decl (var) #:transparent)
; 関数定義
(struct fun-def (var parms body) #:transparent) ; parms は var-decl のリスト
 
; ; 文
; 変数への代入: <var> = <exp>;
(struct assign-stmt (var exp) #:transparent)
; メモリへの書き込み: *<dest> = <src>;
(struct write-stmt (dest src) #:transparent)
; メモリ参照: <dest> = *<src>;
(struct read-stmt (dest src) #:transparent)
; ラベル: <name>:
(struct label-stmt (name) #:transparent)
; 条件分岐: if(<var>){ goto <tlabel>; } else { goto <elabel>; }
(struct if-stmt (var tlabel elabel) #:transparent)
; 無条件分岐: goto <label>;
(struct goto-stmt (label) #:transparent)
; 関数呼出し: <dest> = <tgt>(<var1>, <var2>, <var3>, ...);
(struct call-stmt (dest tgt vars) #:transparent) ; vars は var のリスト
; リターン: return <var>;
(struct ret-stmt (var) #:transparent)
; 値の出力: print(<var>);
(struct print-stmt (var) #:transparent)
; 複文: {<decls> <stmts>}
(struct cmpd-stmt (decls stmts) #:transparent) ; decls は var-decl のリスト,stmts は文のリスト
 
; ; 式
; 変数参照
(struct var-exp (var) #:transparent)
; 整数即値
(struct lit-exp (val) #:transparent)
; 算術演算
(struct aop-exp (op left right) #:transparent)
; 比較演算
(struct rop-exp (op left right) #:transparent)
; アドレス取得: &<var>
(struct addr-exp (var) #:transparent)

ここでTiny Cの実装とは異なり,この定義中のdestsrcvarvar1var2は名前(Racketシンボル)ではなく,decl構造体であり,対応づけられているvar-decl宣言中のvarと同じdecl構造体を指すようにする.

これまで,print関数は暗黙のプロトタイプ宣言がなされていることを除き,通常の関数呼出しと同等に扱ってきたが,SPIMシミュレータ上では画面への値の出力に特別な扱いが必要なため,別の中間表現を与えている.

aop-expの演算子opには,Small Cと同じ+-*/のいずれかが入るので,抽象構文木から中間表現への変換は簡単である.ただし,ポインタへの加減算については注意が必要である.ポインタではない方のオペランドは(バイト数ではなく)要素数をあらわしているため,低レベルのアドレス演算として正しく機能するためには,3 Small Cは言語仕様により配列の要素として含まれるもののサイズは全て4バイトであるため,このような単純な方法で良い.もし,言語拡張を行い他のデータ型を追加しているようであれば,この限りではない.4を掛ける必要がある.たとえばpがポインタ型の変数,aが整数型の変数だとすると,p + a(に相当する抽象構文木)は p + 4*a(に相当する中間表現)へ変換しなくてはならない.3

rop-expの演算子opには,Small Cと同じ==!=<><=>=のいずれかが入るので,抽象構文木から中間表現への変換は簡単である.

中間表現に論理演算子&&||が含まれていないことに注意して欲しい.これは,それらを用いた式を等価な中間表現文の列で置き換えることが可能だからである.たとえば v = e1 || e2 なら次のようなコードを実行すると考えればよい.

  if(e1)

    v = 1;

  else if(e2)

    v = 1;

  else

    v = 0;

なお,中間表現への変換にあたり生成される一時変数用に新しくdecl構造体を生成しなければいけないが,levkindを用いた意味解析は既に済んでいるのでそれらの値は適当でかまわない.ただし,この後の相対番地を計算する時に配列型と区別できるよう,typeには区別可能な適当な値(たとえばシンボルtemp)を入れておく必要がある.さらに,相対番地の計算のためには,生成したdecl構造体を指すvar-decl構造体も中間表現中に新たに追加しなければならないが,単純には,その一時変数が含まれる関数本体(cmpd-stmt構造体)のdeclsに追加すれば良い.メモリ領域を確保する期間をより短くしたければ,関数本体全体ではなく,より狭い範囲に限定された複文を適宜挿入し,そこへvar-decl構造体を追加するなどの工夫が必要である.

【課題10】 中間表現への変換処理を実装せよ.

7.2 データフロー解析と最適化

抽象構文木から構文主導翻訳によって生成された中間表現には無駄が多い.そこで,本節では講義「コンパイラ」で学んだデータフロー解析および最適化を中間表現に対して行い,無駄なコードを取り除くことにする.

データフロー解析および最適化の手法については,講義資料(スライド207ページ目以降)に詳しく書かれている.本実験では,それらの手法を実際のプログラムとして実現するための素材として,簡単なデータフロー解析を行うプログラムを配布することにする.最適化については,データフロー解析の解析結果を参照しつつ中間表現を書き換えるだけであるため,講義資料に書かれた方針に従えば実装は難しくない(プログラム変換の一種なので,シンタックスシュガーの実装と本質的には同じ).

本実験で用意しているデータフロー解析プログラムは,ここからダウンロードできる.このプログラムでは,Tiny Cの中間表現(のサブセット)を対象に,符号解析と呼ばれる簡単な解析を行う.符号解析では,プログラムの各地点において変数に格納されている整数値の符号(正・負・ゼロ)を求める.ただし,一般にデータフロー解析では正確な情報を求められないため,(変数名,符号の集合)の組をデータフロー値として用いる.配布プログラム中では,プログラムの各地点におけるデータフロー値の集合をプロパティと呼ぶ.

配布プログラムを試しに使ってみよう.配布ファイル中に含まれている"test.rkt"の中で定義されている中間表現プログラムpgm1

    t = (x < 0);

    if(t) L1 L2;

  L1:

    y = -1;

    return y;

    goto L3;

  L2:

  L3:

    y = 1;

    goto L5;

  L4:

    y = y * x;

    x = x - 1;

  L5:

    t = (x > 1);

    if(t) L4 L6;

  L6:

    t = 0;

    return y;

を用いることにする.まず,このプログラムから制御フローグラフを生成するには:

> (display-cfg pgm1 #:analyzer #f)

と実行する.図1のような制御フローグラフが画面に表示44 グラフ描画アプリケーションGraphvizがPCにインストール済みで,/usr/bin/dotコマンドがあることを前提.演習室の端末にはインストールされている.自分のPCにインストールする方法が分からなければ教員・TAに相談すれば良い.されるはずである.また,

> (display-cfg pgm1 #:analyzer #f #:gui #f)

と実行すると,代わりに文字列表現がREPLに出力される.

CFG

図1: pgm1の制御フローグラフ.

制御フローグラフ中の<BEGIN><END>は,それぞれプログラムの先頭と末尾に追加したダミーの文である.制御フローグラフの入口と出口のノードをこのように単一のノードにまとめ,入口ノードへ入ってくるエッジや出口ノードから出ていくエッジをなくすことで,データフロー解析が簡単になることが多い(配布プログラム中のソースコードをよく読み,どこが簡単になっているか考えてみて欲しい).とくに<END>を単一の出口とするため,すべてのreturn文からエッジが張られている. なお,「goto L3;」のノードは入口ではなく,到達不可能な無駄な文である.

次に,同じプログラムpgm1に対し符号解析を行うには,

> (display-cfg pgm1 #:analyzer 'sign)

と実行する.解析結果の埋め込まれた図2のような制御フローグラフが画面に表示55 言うまでもなく,Small Cコンパイラ内部で使用するのは表示されるイメージではなく,その元となったデータやデータ構造である.グラフを描画する機能は,コンパイラ開発の利便性のために(またレポートを書くための便利な道具として)用意している.されるはずである.

CFG with Property

図2: pgm1のプロパティつき制御フローグラフ.

各文の前後に埋め込まれている[...]が,そのプログラム地点におけるプロパティを示している.プロパティ中のデータフロー値は「変数名 -> 符号」という記法を用いて表されている.各変数が束縛されている値はそれぞれ,正(pos),負(neg),ゼロ(zero),正かゼロ(non-neg),負かゼロ(non-pos),正か負(non-zero),任意の符号(any)を意味する.

たとえば,L1で始まる基本ブロック中の文「y = -1;」の直後のプロパティ中ではyは必ずnegとなる.同様に,L5で始まる基本ブロック中の文「t = (x>1);」の直後のプロパティ中では,(xの符号が何であれ)関係演算の結果は必ず01のどちらかであるため,tnon-negだと分かる.もし仮に,この文の直前のプロパティ中でxの符号がzeronegnon-posのいずれかであったなら,x>1は必ず0に評価されることが分かるため,直後のプロパティ中のtzeroとなっていたはずである.

また,たとえばL1で始まる基本ブロックの末尾のプロパティ中でynegであるにも関わらず,制御フローの先にある<END>直前のプロパティ中のyanyであるのは,もう一方の制御フロー元であるL6で始まる基本ブロックの末尾のプロパティ中でyanyだからである.他の変数,他の制御フローの合流ポイントについても同様に,すべての制御フローの可能性を考慮した上での符号を計算する必要がある.

ここで示した符号解析はデータフロー解析の簡単な一例に過ぎないが,配布プログラム全体は,講義で学んだ不動点反復に基づく一般的手法(monotone frameworkと呼ばれる)を実現した汎用的なコードとなっている.このコードをきちんと理解すれば,他のデータフロー解析をその上で実現するのはそれほど難しくない.

講義初回に述べたとおり,課題11課題12を後回しにして課題15までを先に済ませ,まずは最後まで動作するコンパイラを完成させるのが良い.
【課題11】 Tiny Cに対する符号解析プログラムを基に,講義で学んだ以下のデータフロー解析のうち1つ以上をSmall Cコンパイラに実装せよ.
  • 到達可能定義解析

  • 到達コピー解析

  • 生存変数解析

【課題12】 講義で学んだ以下の最適化のうち1つ以上をSmall Cコンパイラに実装せよ.
  • 定数畳み込み

  • コピー伝搬

  • 無駄な命令の除去

Small C言語のポインタ間接参照・ポインタ間接代入・関数呼出しに対する伝達関数(transfer function)の定義には注意が必要である.たとえば:

  int a, *x;

  ...(1)...

  a = *x;

  ...(2)...

のような代入を考えると,(1)xにどのようなアドレス値を代入しているか(複数の可能性があるかも知れない)によって(2)におけるaの値は異なるはずである.さらに,仮にアドレスを特定できたとしても,その同じ場所が別のポインタ(これも複数あるかも知れない)からも指されていて,なおかつ,それらを経由して値が書き込まれている可能性があるなら,結局のところこの間接参照で取り出される値が何なのかを特定するのは容易ではない.このような場合にもっとも簡単なアプローチの一つは,「(2)におけるaの値は任意の整数である」という大雑把な近似を行う方法である.

ポインタ間接代入についても同様に,たとえば:

  int *x;

  ...(1)...

  *x = 1;

  ...(2)...

のような場合,(1)でxには(大域変数も含め)任意のint型の変数のアドレスを代入している可能性があるため,簡単に済ませるなら,「(2)において,あらゆるint型の変数の値は1になっているかも知れない」と近似せざるを得ない.

関数呼出しについても,関数の引数や返り値についてポインタの場合と同様の考察を行うことで伝達関数を求めることができる.

上記のような非常に簡単な方法を採用すると,ポインタや関数呼出しを多用するプログラムでは多くの場合に有用な情報を得られないかも知れないが,課題11課題12ではそれでもかまわないものとする.つまり,ポインタを使わず,関数呼出しもしない単純なプログラムで解析や最適化の効果を示せれば十分とする.余力のある場合には,ポインタの取り得る値や,関数呼出しによる引数と返り値の受け渡しまで考慮したデータフロー解析・最適化を実現することにチャレンジしてみて欲しい.その場合,この書籍6などのコンパイラに関する専門書が参考となる.あるいは,「ポインタ解析(pointer analysis)」「エイリアス解析(alias analysis)」「shape analysis(適切な日本語訳不明)」「手続き間解析(interprocedural analysis)」といった用語を手掛かりに検索しても,数多くの有益な情報が得られるはずである.

なお,講義資料中では中間表現中の文を行番号によって区別していたが,Small C の中間表現では,たとえば,文をあらわす構造体それぞれにidフィールドを追加し,構造体を生成する際にユニークなID(整数値)をセットすることで区別すれば良い.あるいは,もっと単純に,eq?により要素の区別を行うデータ構造(たとえばhasheqハッシュテーブル)を使って,文をあらわす構造体オブジェクトそのものをIDとして用いてもよい.たとえば:

> (define s (cmpd-stmt '() (list (goto-stmt 'L1)
                                 (label-stmt 'L1)
                                 (goto-stmt 'L1))))
> (define h (hasheq (first (cmpd-stmt-stmts s)) 'g1
                    (third (cmpd-stmt-stmts s)) 'g2))
> (dict-ref h (first (cmpd-stmt-stmts s)))

'g1

> (dict-ref h (third (cmpd-stmt-stmts s)))

'g2

のように,同じ「goto L1;」をあらわす文であっても異なるキーとして区別できる.

参考: Racketの構造体定義に後からフィールドを追加すると,構造体を生成する全てのコンストラクタ呼出しについても,適切な初期値を追加の引数として渡す必要が生じる.しかし,もし追加されたフィールドの初期値を生成する式が全ての構造体で同じなら,構造体を定義する際に#:auto#:auto-valueを指定することにより,コンストラクタ呼出しの引数を省略できる.#:auto#:auto-valueの詳細については,Racket公式ドキュメントのstruct付録Aを参照.

7.3 相対番地の計算

中間表現中の局所変数や関数パラメータに対し,fpレジスタからの相対番地(オフセット)を求める方法は,基本的に講義「コンパイラ」で学んだTiny Cの方法と同じであるが,宣言という概念のないTiny Cとは異なり,Small Cでは相対番地の計算には中間表現中のvar-decl構造体にだけ注目すれば良い.ただし,大域変数はスタックとは別の場所に確保されるため,中間表現のトップレベルのvar-declについては考慮する必要はない.

配列型以外のvar-decl構造体については1ワード分の領域を用意するだけなので単純である.

配列をスタック上に確保する際には,要素の並び順に注意が必要である.たとえば:

  int foo(int a, int b, int c, int *d, int *e, int *f) {

    int x, y[4];

    ...

  }

と定義された関数fooに対するフレームの確保は図3のようにすると良い(MIPS1の呼出し規約に従い,第4引数まではレジスタ渡しとしている).スタックは上位アドレスから下位アドレスへと伸びることに注意して欲しい.そのためスタック上に確保される配列は先頭要素がスタックトップ側に配置される.配列名は先頭の配列要素へのポインタと同じであるから,名前に対応づけられる相対番地は先頭要素のもの(図では$fp-16)となる.

スタック

図3: スタック領域における配列の確保.

なお,Tiny Cでは局所変数,パラメータ,一時変数のためのスタック上のメモリ領域の割り当ては関数本体の先頭で一括して行っているが,Small Cの中間表現ではソースプログラム中の変数宣言のブロック構造がそのまま保持されているので,(生存解析のような複雑な解析をせずとも)同時に存在しない変数の組み合わせを見つけるのは比較的簡単である.たとえば,

  int f(){

    {

      int x;

      x = 1;

    }

    {

      int y;

      y = 2;

    }

  }

のような場合,xyは同時には存在しないため,スタック上の同じ位置に場所を割り当てることが可能である.

【課題13】 局所変数,パラメータ,一時変数の相対番地を計算せよ.
なお,講義「コンパイラ」では単にvar-exp構造体を計算したオフセット(を含んだofs構造体)に置き換えていたが,Small Cではこの後のコード生成でdecl構造体中の情報を用いるため,置き換えるのではなくdecl構造体に相対番地を格納するためのフィールドoffsetを追加するようにせよ.

【課題14】(選択) 講義「コンパイラ」で触れられたとおり,局所変数や一時変数の一部をスタックに確保する代わりに汎用レジスタに割り当てると,計算速度が大幅に向上する.汎用レジスタへの変数の割り当てを行なうよう,課題13の相対番地計算モジュールを改良せよ.レジスタ割り当ての詳細については,たとえばこの書籍66 演習室の本棚に数冊置いてある.に詳しい.

7.4 MIPSコードの生成

中間表現からMIPSコードを生成する方法,およびSPIMシミュレータの使い方については講義「コンパイラ」で詳しく説明されており,Small Cを実装するのに必要な知識は殆んど含まれているため,本資料では詳しく触れない.詳しくは,計算機アーキテクチャの教科書1講義「コンパイラ」配布資料の中の"gen.rkt"2等を参考にすること.とくに大域変数の領域を確保するための方法や配列名への参照方法については講義のTiny Cには含まれていないが,計算機アーキテクチャの教科書の付録AにあるMIPSアセンブリおよびSPIMシミュレータに関する説明中にきちんと含まれている(ヒント:.dataセクション,la命令).また付録Aには,SPIMシミュレータ上で標準出力に値を表示するためのシステムコールに関する説明も含まれており,適切なシステムコールを行うことがprint関数の実現には必要である(print関数の出力は末尾に改行を含むことにも注意).

【課題15】 Small Cコンパイラのコード生成部を作成せよ.

【課題16】(選択) 生成されたMIPSコードに対し,覗き穴最適化を実装せよ.覗き穴最適化についてはこの書籍77 これも演習室の本棚に数冊置いてある.に詳しい.

8 付録A: Racket Cheat Sheet

Racket が提供する様々な関数のうち,とくにコンパイラ作成に役立つと思われるいくつかの関数を簡単に紹介する.各関数の機能の詳細については,Racket公式ドキュメントを参照すること(関数名が公式ドキュメント中へのリンクになっている).当然のことながら,ここに挙げている以外にも数多くの便利な関数が用意されており,それらも積極的に利用してかまわない.

8.1 リスト

> (define l '(1 2 3 4 5 6))
> (length l)

6

> (reverse l)

'(6 5 4 3 2 1)

> (append l '(a b c))

'(1 2 3 4 5 6 a b c)

> (map (lambda (x) (* x x)) l)

'(1 4 9 16 25 36)

> (filter even? l)

'(2 4 6)

> (foldl (lambda (x acc) (string-append (number->string x) acc)) "" l)

"654321"

> (foldr (lambda (x acc) (string-append (number->string x) acc)) "" l)

"123456"

> (member 4 l)

'(4 5 6)

> (range 0 10)

'(0 1 2 3 4 5 6 7 8 9)

> (append-map (lambda (x) (range 0 x)) l)

'(0 0 1 0 1 2 0 1 2 3 0 1 2 3 4 0 1 2 3 4 5)

8.2 ベクタ

> (define v #(1 2 3 4 5))
> (make-vector 5 0)

'#(0 0 0 0 0)

> (vector->list v)

'(1 2 3 4 5)

> (equal? (list->vector '(1 2 3 4 5)) v)

#t

> (equal? '(1 2 3 4 5) v)

#f

> (vector-length v)

5

> (vector-ref v 2)

3

> (build-vector 5 (lambda (i) (* i i)))

'#(0 1 4 9 16)

> (vector-map (lambda (i) (* i i)) v)

'#(1 4 9 16 25)

vector-map以外にも,各種リスト操作関数のベクタ版が存在.

8.3 集合

集合として利用できるRacketのデータ型には,リストやhashsetがある.ここでは,リストを使った例を示す.

> (define s '(a b c d))
> (set-member? s 'b)

#t

> (set-member? s 'e)

#f

> (set-add s 'b)

'(a b c d)

> (set-add s 'e)

'(e a b c d)

> (set-remove s 'b)

'(a c d)

> (set-remove s 'e)

'(a b c d)

> (define t '(c d e f))
> (set-union s t)

'(f e a b c d)

> (set-intersect s t)

'(d c)

> (set-subtract s t)

'(b a)

> (subset? s t)

#f

> (subset? (set-intersect s t) t)

#t

8.4 辞書

辞書として利用できるRacketのデータ型には,連想リスト(キーと値のコンスペアのリスト)やhashがある.ここでは,連想リストを使った例を示す.

> (define s '((a . 1) (b . 2) (c . 3) (d . 4)))
> (dict-ref s 'c)

3

> (dict-ref s 'e)

dict-ref: no value for key: 'e in: '((a . 1) (b . 2) (c . 3)

(d . 4))

> (dict-ref s 'e 0)

0

> (dict-set s 'e 5)

'((a . 1) (b . 2) (c . 3) (d . 4) (e . 5))

> (dict-remove s 'c)

'((a . 1) (b . 2) (d . 4))

> (dict-has-key? s 'b)

#t

> (dict-keys s)

'(a b c d)

> (dict-values s)

'(1 2 3 4)

8.5 文字列

> (define s "Hello world.")
> (string-length s)

12

> (string-ref s 4)

#\o

> (string->list s)

'(#\H #\e #\l #\l #\o #\space #\w #\o #\r #\l #\d #\.)

> (string=? "foo" "Foo")

#f

> (string-append "one" "two")

"onetwo"

> (format "~a:~a: ~a\n" "a.c" 8 "unknown identifier")

"a.c:8: unknown identifier\n"

> (display (format "~a:~a: ~a\n" "a.c" 8 "unknown identifier"))

a.c:8: unknown identifier

> (string-join '("one" "two" "three") ",")

"one,two,three"

> (string-join '("one" "two" "three") " " #:before-first "(" #:after-last ")")

"(one two three)"

8.6 構造体

> (struct point (x y) #:transparent)
> (define p (point 1 2))
> (point-x p)

1

> (struct point (x (y #:auto)) #:auto-value (random 1 10) #:transparent)
> (define q (point 0))
> q

(point 0 1)

> (struct point (x (y #:mutable)) #:transparent)
> (define r (point 3 4))
> (set-point-y! r 0)
> r

(point 3 0)

8.7 バッククォート・アンクォート

> (define a 1)
> (define b 2)
> (define c 3)
> (list a b c)

'(1 2 3)

> (list 'a 'b 'c)

'(a b c)

> '(a b c)

'(a b c)

> `(a b c)

'(a b c)

> `(a ,b c)

'(a 2 c)

> `(a ,(+ a b c) c)

'(a 6 c)

> `(a ,(list a b c) c)

'(a (1 2 3) c)

> `(a ,'(a b c) c)

'(a (a b c) c)

> `(a ,@(list a b c) c)

'(a 1 2 3 c)

> `(a ,@'(a b c) c)

'(a a b c c)

8.8 エラー・例外処理

> (begin
    (error "something wrong")
    'done)

something wrong

引数で指定したメッセージが即座に標準エラー出力へ表示されているのではないことに注意.メッセージを含む例外が投げられ,なおかつ,プログラム中でwith-handlers等により補足されなかった場合にREPLが表示している.
> (define (wrong)
    (error "something wrong"))
> (with-handlers ((exn:fail? (lambda (e) 'recovered)))
    (wrong) 'done)

'recovered

exn:fail?は全ての例外を意味する.捕捉する例外の種類を細かく指定することも可能.

> (begin
   (eprintf "~a:~a: ~a\n" "a.c" 8 "unknown identifier")
   'done)

a.c:8: unknown identifier

'done

例外は投げず,引数で指定したメッセージを即座に標準エラー出力へ表示する.

8.9 パターンマッチ

> (define (my-length l)
    (match l
      ('() 0)
      ((cons a d) (+ 1 (my-length d)))))
> (my-length '())

0

> (my-length '(a b c))

3

> (define (even-ones? l)
    (match l
      ('() #t)
      ((cons 1 (cons 1 r)) (even-ones? r))
      (else #f)))
> (even-ones? '())

#t

> (even-ones? '(1))

#f

> (even-ones? '(1 1))

#t

> (even-ones? '(1 2))

#f

> (struct lit-exp (val) #:transparent)
> (struct add-exp (left right) #:transparent)
> (define (my-eval exp)
    (match exp
      ((lit-exp v) v)
      ((add-exp l r) (+ (my-eval l) (my-eval r)))
      (else (error "unknown exp:" exp))))
> (my-eval (lit-exp 3))

3

> (my-eval (add-exp (lit-exp 3) (lit-exp 4)))

7

8.10 トレース

前節lit-expadd-expの定義をそのまま用いる.

> (define (my-eval-lit n) (* n 1.0))
> (define (my-eval exp)
    (match exp
      ((lit-exp v) (my-eval-lit v))
      ((add-exp l r) (+ (my-eval l) (my-eval r)))
      (else (error "unknown exp:" exp))))
> (my-eval (add-exp (add-exp (lit-exp 1) 2)
                    (lit-exp 3)))

unknown exp: 2

> (require racket/trace)
> (trace my-eval my-eval-lit)
> (my-eval (add-exp (add-exp (lit-exp 1) 2)
                    (lit-exp 3)))

>(my-eval (add-exp (add-exp (lit-exp 1) 2) (lit-exp 3)))

> (my-eval (add-exp (lit-exp 1) 2))

> >(my-eval (lit-exp 1))

> >(my-eval-lit 1)

< <1.0

> >(my-eval 2)

unknown exp: 2

> (untrace my-eval-lit)
> (my-eval (add-exp (add-exp (lit-exp 1) (lit-exp 2))
                    (lit-exp 3)))

>(my-eval (add-exp (add-exp (lit-exp 1) (lit-exp 2)) (lit-exp 3)))

> (my-eval (add-exp (lit-exp 1) (lit-exp 2)))

> >(my-eval (lit-exp 1))

< <1.0

> >(my-eval (lit-exp 2))

< <2.0

< 3.0

> (my-eval (lit-exp 3))

< 3.0

<6.0

6.0

9 付録B: Small Cコンパイラ要求仕様

この付録では,本実験で作成するSmall Cコンパイラを実行するためのユーティリティについて説明する.提出するSmall Cコンパイラは,このユーティリティから呼び出せること,ならびに,エラー表示が以下で説明されているフォーマットに従っていることが要求される.

また,提出するSmall Cコンパイラは必ず演習室の端末で動作可能でなければいけない.次節では演習室にインストールされているRacket等について説明する.Racket以外の言語で演習を行っている場合も,選択した言語に応じ必要なライブラリがあれば前もって設定しておく等,自己責任で動作可能にしておくこと.

9.1 演習室の計算機環境

演習室の計算機にはRacket(GUI版: drracket,CUI版: racketコマンド)とSPIMシミュレータ(GUI版: qtspimコマンド,CUI版: spimコマンド)がインストールされている.CUI版のspimコマンドは,シェル端末やEmacsの上で実行したい場合に便利である.使い方は簡単で,たとえばアセンブリプログラム"test.s"を実行するには:

$ spim -f test.s

Loaded: ...

1

$

とする.spimコマンドのより詳しい使い方は,spimを起動後,helpと打ったり,無効なコマンドラインオプション(たとえば-h)をつけてspimコマンドを起動すると表示されるヘルプメッセージに書かれている.

【2016/05/13追記】 実行したMIPS命令の回数をカウントしてくれるCUI版spimコマンドを,TAの宮崎君がつくってくれました.生成コードの実行効率・最適化の効果等を測るのに有効活用してください.演習室の端末では/home/lab4/umatani/spim/bin/spimとしてインストールされています.また,ソースファイル一式がGitHubにありますので,自分のPCにインストールしたい方はそちらを参照してください.実行命令回数を測るためのコマンドラインオプションなどの簡単な説明もそちらに書かれています.

9.2 要求仕様

提出するSmall Cコンパイラは,実装言語がRacketかどうかに従い,それぞれ以下の仕様を満たしていなければいけない.

9.2.1 コンパイラ実装言語がRacketの場合

使用例(コンパイラは"compiler.rkt"ファイル中のcompile関数とする)

> (require "compiler.rkt")

> (compile "test.sc")   ;; 正常なプログラム

    .text

    .globl main

f:

    subu    $sp, $sp, 24

...

> (compile "error.sc")  ;; 23行4列のところにエラー

23:4: name resolve error: unknown identifier hoge

>

参考: spimコマンドを使ってアセンブリコードを実行するには,一旦ファイルへ保存する必要がある.Racketから標準出力への出力をファイルへ保存するには,たとえば,racketコマンドとシェルのリダイレクト機能を使って:

$ racket -e '(require "compiler.rkt") (compile "test.sc")' > test.s

とする(ただし,次節のユーティリティがその辺りの面倒は見てくれる).

9.2.2 コンパイラ実装言語がRacket以外の場合

使用例(コマンド名はcompilerとする)

$ ./compiler test.sc    # 正常なプログラム

    .text

    .globl main

f:

    subu    $sp, $sp, 24

...

$ ./compiler error.sc    # 23行4列のところにエラー

23:4: name resolve error: unknown identifier hoge

$

参考: spimコマンドを使ってアセンブリコードを実行するには,一旦ファイルへ保存する必要がある.Unixシェルのリダイレクト機能を使って:

$ ./compiler test.sc > test.s

とすることでファイルに保存できる(ただし,次節のユーティリティがその辺りの面倒は見てくれる).

9.3 Small Cコンパイラ起動ユーティリティ

コンパイラの実装言語の違いを吸収し,複数のソースファイルを一度にコンパイル・実行するための簡単なユーティリティscc66 Racketにおける入出力,例外処理,コマンドライン引数の使い方の参考になるので,興味があれば一度目を通してみるのも良い.が用意されている.

こちらのリンクを辿ってダウンロードし,実行可能属性をセット(シェルコマンドchmod +x sccを実行)して使用すること.

以下に,いくつかの使用例を挙げる.

使用例1: "compiler.rkt"ファイル中のcompile関数を用いて"test.sc"をコンパイルし,アセンブリファイル"test.s"を出力.

$ ./scc test.sc

使用例2: "compiler.rkt"ファイル中のcompile関数を用いて"test.sc"をコンパイルし,アセンブリファイル"test.s"を出力.さらに,SPIMを使って"test.s"を実行.

$ ./scc -e test.sc

使用例3: "compiler.rkt"ファイル中のcompile関数を用いてカレントディレクトリにある全てのSmall Cプログラムをコンパイルし,それぞれのアセンブリファイルを出力.さらに,SPIMを使って順に実行.

$ ./scc -e *.sc

使用例4: "main.rkt"ファイル中のcompile-file関数を用いてカレントディレクトリにある全てのSmall Cプログラムをコンパイルし,それぞれのアセンブリファイルを出力.さらに,SPIMを使って順に実行.

$ ./scc -e -r main:compile-file *.sc

使用例5: 実行可能ファイル./compilerを用いてカレントディレクトリにある全てのSmall Cプログラムをコンパイルし,それぞれのアセンブリファイルを出力.さらに,SPIMを使って順に実行.

$ ./scc -e -c ./compiler *.sc

また,-nオプションをつけると,生成したアセンブリコード中の命令数,メモリアクセス命令数をカウントする.最適化などの効果を測るのに便利に使用できる.

注意: sccは命令数をカウントするために自前のアセンブリコードパーサを使っているが,MIPSアセンブリ言語に完全に準拠していない.正しいアセンブリコードのはずなのに-nオプションで正しくカウントしてくれない,ということがあれば申し出ること.また,-nオプションを通ったからといって正しいアセンブリコードだという保証は全くない.SPIMコマンドを使って動作確認すること.

また,

$ ./scc -h

で表示されるヘルプメッセージにもコマンドの簡単な説明が書かれている.