Compiler Construction Lecture 12/03

先週の復習

先週は、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 により、記号の扱いが変わることに注意しよう。