Compiler Construction Lecture 12/09

# Compiler Construction Lecture 12/09

# 先週の復習

先週は、Makefileの使い方について簡単な勉強をした。その後、simple compiler
の変更方法について考察した。いったん compiler を作ってしまえば、その
変更はたやすい。これは先々週の宿題の解答例でもある。

その後、register を使った compiler の作成方法を
勉強した。最適化を考えなければ、コード生成自身はstack versionと
ほとんど変わらない。これは、registerの番号の上にstackのコードを
部分計算することに相当する。先週解いた問題は、このような方法で
どのようなコードが生成されるかを問うものだった。もちろん、これよりも、
賢いコード生成をおこなうことは簡単だが、それを問題の答えとするならば、
同時にコード生成のアルゴリズムを示さなければ完結した解答とはいえない。

あと、Micro-C の全体構成について関数の呼出表を見ながら簡単に考察した。
全体構成をつかみ、Cの文法を思い出しながら、個々の関数を読んでいくことに
より、実際的なcompilerの詳細を理解して欲しい。自分で、すべてを理解
しなくては、どんなプログラムでも完成させることはできない。
あてずっぽうにコードを書いても、それは絶対に動くことはないし、それは、
他のコードに影響を与え、正しい部分まで汚染してしまう。バグは避けられない
ものではあるが、自分で書いたコードを完全に理解していれば、どのような
バグにも対処できる。

# 分割コンパイルとモジュールまたはオブジェクト

複雑なプログラムになると、プログラムを一つのファイルにまとめる
こともできなくなる。また、そうしなければ、複数の人間でプログラムを
書くということもできない。そこで、プログラムを分割してcompileする
ということが必要になる。

分割した時に、分割した部分のどこを外に見せて、どこを隠すかという
のが問題になる。この場合の単位は module と呼ばれる。
すべてを見せてしまっては、分割した意味がないとも
いえる。しかし、見る方が悪いのであって、すべてはdefaultで見えている
方が良いという考え方も存在する。実際には、見せるためには、分割した
もの同士の情報のやり取りが必要なので、import, export や
、public, privateなどのkeywordで情報のやり取りを制御するように
することが多い。Cでは、extern と static がそれに相当する。C++では、
publicとprivateを使う。

このような情報の制御と、ファイルの分割は本来は独立な問題である。
しかし、Cではファイルの分割でしか module を定義できない。C++の
場合には class がその役割を果たしている。

# Symbol Table

Tokenizerでは、記号の切り出しとkeywordの切り出しをおこなう。同時に、
名前の登録をおこなう必要がある。実際、Tokenizerが、普通の名前、
(例えば英字で始まる英数字の列などだが)に出会ったとしよう。それは、
名前(name)、つまり、予約語(reserved word)か、変数名か関数名である。
Micor-C では、getsym() という関数がTokenizerである。

これらは compiler 内部の
表に登録されなければならない。この表を Symbol Tableという。Interpreter
の場合でもSymbol Tableは必要である。Compilerが出力したコードでは、
Symbol Tableは不要である。しかし、分割compile (Separate compilation)
の場合は、相互のSymbol Tableを接続する必要があるので、Symbol Table
そのものも出力しなくてはならない。この問題は、異なるcomputer上で
分散計算を行う場合にも出て来る。

名前には様々な属性がある。例えば、ある名前はlocalであり、ある関数や、
関数の一部でしか有効でない。ある名前で指し示される(実体/objectゥ)ものは、名前で
呼ばれなくなった後も存在し続ける場合がある。あるいは、そのような
ものを別な名前で呼びたい時もある。このような属性には以下のようなものが
ある。

名前の有効範囲 (scope)
objectの寿命 (extent)
objectの型 (type)

例えば、Cだったら、scopeとextentには以下のようなものがある。

local

- 名前は{}の中で有効であり、その外では使えない。object も、その外では
消滅してしまうのでアクセスしてはならない。{}は入れ子(nest)することが
できるので、名前の有効範囲もnestする必要がある。しかし、C では実際には、
nest は処理されずに、local 変数は、手続の中で一意な名前でなければならない。
自動的にobjectが作られ、自動的に消滅するので、
自動変数(auto)とも呼ばれる。Cではこちらの呼び方の方が正式である。
local variableのobjectは通常はstack上に取られる。したがって、
特に、pointer を使って
local 変数を手続き呼び出しから返してはならない。Cでは、local変数の
初期化を行うことができる。Cにはlocalな手続き名は存在しない。
- global
- 名前とobjectは、プログラム全体で有効であり、存在する。C++では、
この名前の有効範囲を class 単位にすることができる。分割 compile
する場合は、この名前はコード中に出力する必要がある。分割 compile
後、さらに、link された完全なコードには symbol table は必要ない。
しかし、debug のためにわざと情報を残すこともある。(-g flag in cc)。
最近のOSでは、kernel levelで library の dynamic loadingを行う。
場合もあり、この場合もlinkのための情報を残す必要がある。
別なファイルのglobalを参照したい時には、externを使う。
- static
- objectは、プログラム全体で有効であり、存在する。しかし、名前は
ファイル内部でしか有効ではない。localなstaticという名前もあり、
この場合は、名前の有効範囲は関数または{}の内部ということになる。
- macro
- マクロ(macro)名は、通常compilerが処理する前に変換されてしまう。
したがって、compilerからも見えない名前である。しかし、Micor-C
ではマクロも1 pathで処理するために、マクロ名も自分で管理する。
この名前の有効範囲は分割compile単位である。マクロには引数が
あることがあるので、その処理も必要だが、Micro-C自身には、その
機能はない。しかし、付加することはそれほど難しくはない。
- compilerにとって問題なのは変数の有効範囲であり、大域名(global)と
局所名(local)が衝突した場合には大域名を優先する必要があり、
局所名が有効でなくなれば、その名前を再利用する必要がある。

名前には、その名前が指すもの(object)の型がある。一つの名前には
一つの型がある言語(Cはそうだ)もあるが、一つの名前を複数の型に
使うことができるもの(Perlなど)もある。前者の場合は、名前を検索することに
より型が分かる。しかし、後者の場合には、型は名前とは別に指定する
必要がある。後者の方がどちらかといえば優れているようである。Cには
以下のような型がある。

long, int, short, char

- 基本的な型。アセンブラでのword,2byte,1byteに
相当する。
- unsinged/singed
- 符号が付くかどうか。引き算などで2の補数として
扱うかどうかに相当する。Micro-Cには、signed char, unsinged char などは
存在しない。
- float, double
- Micro-Cにはない。
- * pointer
- Cを特徴づける型。直接にobjectを指すのではなく、object
のaddressを表す型である。単なるaddressではなく、足し算が定義されている。
1を加えることにより、指し示すobjectの大きさの分だけaddressが加算される。
大きさは、sizeof()という内蔵関数で取り出すことができる。
sizeof(char) == 1であるけれど、sizeof(int)==sizeof(int *)
であるとは保証されない、ということを覚えておこう。pointerのpointerという
型もある。これを理解しているかどうかでCを理解したかどうかが決まる重要な
部分である。
- array[10],array[],array[10][20]
- 配列。pointerを使ってアクセス
されることが多い。2次元配列と、pointerの配列の違いを理解しよう。
- struct, union
- ユーザ定義可能な型。レコード型などと呼ばれることもある。
複数の型を合わせて一つのobjectとして扱うことができる。
- さらに、Cには、cast という概念があり、型を変換することができる。この
時の構文はなかなか面白い。
このあたりのcompileの詳細は、また後日、追求することにしよう。

# Implementation of Symbol Table

Symbloc Table(記号表)の実装は、さまざまな方法があるが、hash tableと、
stack を組み合わせるのが容易である。

localな名前は、stack上に作られる。入れ子(nest)になったものを実現する
場合には常にstackを使う。localな名前が作れる度に名前はstackにつまれる。
そして、compileが、そのscope(手続き、または{}(statement))から抜ける
と、必要な所までstackを開放する。検索を、localな名前を格納したstack
そして、大域名を格納したhash tableという順番に探すことにより、Cの
変数の有効範囲を実現することができる。

名前にはreserved word(予約語)が取ら
れることがある。例えば、if, for, continue などは
Cの予約語である。これらの語を字句解析のレベルで切り分ける手もあるが、
ユーザの定義よりも先に表に登録してしまうという手もある。すると、
reserved wordかどうかは、一種の名前の型となる。

さて、Micro-CではSymbol tableは以下のように定義されている。

168 typedef struct nametable {
169 char nm[9];
170 int sc,ty,dsp; } NMTBL;
171
172 NMTBL ntable[GSYMS+LSYMS],*nptr,*gnptr,*decl0(),*decl1(),*lsearch(),*gse
arch();

9文字しか変数名は見ないらしい。逆に言えば、iという変数に対しても9文字分の
データが取られている。実用的にはこんなものかも知れない。GSYMS,LSYMSは、
global, local の記号の最大値である。定数は、このように大文字のマクロで
書くのが C 流である。sc は、たぶん、symbol class の意味で、以下のどれか
である。これと ty との値で型が決まる。ty には、struct, unioon を表す
木構造(tree)か INT が入る。

EMPTY

- なんだか分からないもの
- RESERVE
- 予約語
- FUNCTION
- 手続名
- LVAR
- local variable
- TYPE
- 型名
- TAG
- struct, unicon のfieldの定義
- FIELD
- struct, unicon のfieldの参照
- FLABEL,BLABEL
- label (未定義=forward label)
- MACRO
- macro で定義された名前

さて、getsym()を見てみよう。

2520 getsym()
2521 {NMTBL *nptr0,*nptr1;
2522 int i;
2523 char c;
2524 if (alpha(skipspc()))
2525 { i = hash = 0;
2526 while (alpha(ch) || digit(ch))
2527 { if (i <= 7) hash=7*(hash+(name[i++]=ch));
2528 getch();
2529 }
2530 name[i] = '\0';
2531 nptr0 = gsearch();
2532 if (nptr0->sc == RESERVE) return sym = nptr0->dsp;

ここでは、
hash table という技術を使っている。名前によって決まったrandamな値により、
表を引く。このようにすることにより、randamな値が重ならなければ一度だけで
記号に対応する値を取りだすことができる。2527ではhashを計算するだけで、
実際の検索は、gsearch(),lsearch() でおこなう。

2661 NMTBL *gsearch()
2662 {NMTBL *nptr,*iptr;
2663 iptr=nptr= &ntable[hash % GSYMS];
2664 while(nptr->sc!=EMPTY && neqname(nptr->nm))
2665 { if (++nptr== &ntable[GSYMS]) nptr=ntable;
2666 if (nptr==iptr) error(GSERR);
2667 }
2668 if (nptr->sc == EMPTY) copy(nptr->nm);
2669 return nptr;
2670 }
2671 NMTBL *lsearch()
2672 {NMTBL *nptr,*iptr;
2673 iptr=nptr= &ntable[hash%LSYMS+GSYMS];
2674 while(nptr->sc!=EMPTY && neqname(nptr->nm))
2675 { if (++nptr== &ntable[LSYMS+GSYMS]) nptr= &ntable[GSYMS];
2676 if (nptr==iptr) error(LSERR);
2677 }
2678 if (nptr->sc == EMPTY) copy(nptr->nm);
2679 return nptr;
2680 }

このsearchは、もし表になかった場合には登録も行う。これは標準的な実装である。
lsearch()とgsearch()の差はどこにあるか考えてみよう。

2532 if (nptr0->sc == RESERVE) return sym = nptr0->dsp;
2533 if (nptr0->sc == MACRO && !mflag)
2534 { mflag++;
2535 chsave = ch;
2536 chptrsave = chptr;
2537 chptr = (char *)nptr0->dsp;
2538 getch();
2539 return getsym();
2540 }
2541 sym = IDENT;
2542 gnptr=nptr=nptr0;
2543 if (mode==GDECL || mode==GSDECL || mode==GUDECL ||
2544 mode==GTDECL || mode==TOP)
2545 return sym;
2546 nptr1=lsearch();
2547 if (mode==STAT)
2548 if (nptr1->sc == EMPTY) return sym;
2549 else { nptr=nptr1; return sym;}
2550 nptr=nptr1;
2551 return sym;
2552 }

検索が修了すると、その後で予約語とマクロの処理を行う。どちらでもなければ
globalかlocalかどちらかである。この後、その記号のscとtyが決まることに
なる。これらは、構文解析の途中で決定するので、そこで代入される。mode
により、記号の扱いが変わることに注意しよう。

## あと以下のアンケートに答えてください

## アンケート用紙

prev
next

top
lecture top
absolute top