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ゥ)ものは、名前で 呼ばれなくなった後も存在し続ける場合がある。あるいは、そのような ものを別な名前で呼びたい時もある。このような属性には以下のようなものが ある。

例えば、Cだったら、scopeとextentには以下のようなものがある。 compilerにとって問題なのは変数の有効範囲であり、大域名(global)と 局所名(local)が衝突した場合には大域名を優先する必要があり、 局所名が有効でなくなれば、その名前を再利用する必要がある。

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

さらに、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 が入る。

さて、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