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();

• 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;

  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  }

  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          }