Compiler Construction Lecture 12/21

先週の復習

先週は、

分割コンパイル
変数のscopeと型

について勉強したのであった。これを思い出しながら、今日は構文解析の実際について勉強しよう。

YACCによる構文解析

今までは、再帰下降法(Recursive Decent)という構文解析方法を使ってきた。この方法は十分に高速だし、十分に一般的である。また、プログラマにとって、コンパイラの処理状況が直接的に見えるという利点もある。しかし再帰下降法では、文法規則そのものを、そのままプログラムの構造とすることが必ずできるわけではない。例えば、左再帰は、while などを使わなくてはいけなかった。

文法規則は、一般的に以下のような形で表される。

aexpr  :   aexpr '-'  mexpr 
       |   aexpr '+'  mexpr ;

このように、: の左が一つのシンボル(non-terminal symbolという)しかない文法は、Conext Free Grammar(CFG, 文脈自由文法)と呼ばれる。これは構文解析のアルゴリズムがあることが知られている。左のシンボルが複数あるようなものは、Contex Dependent Grammar(文脈依存文法) と呼ばれる。Context Dependent Grammarを一般的に構文解析することは決定不能(undecidable)であることもわかっている。もし、文脈自由文法で、再帰呼び出しが再後尾にしかないのならば、それはFinite State(有限状態遷移) であり、その場でただちに構文解析される。高度な文法を使用したから、構文が読みやすくなるわけでもないが、有限状態遷移で表現されるような文法では、例えば、「()の対応」などを記述することはできない。これは若干不便だといわれても仕方がない。

したがって、ここで扱うコンパイラは基本的には、CFG(のsubset)を対象とすることになる。CFGのsubsetを自動的に構文解析するプログラムを生成することは可能であり、 Unixのyacc、GNU projectのbisonなどが知られている。yacc では、shift-reduce によるLR grammarの構文解析プログラムを生成することができる。再帰下降法を思い出そう。前出の文法は以下のようなプログラムで構文木の生成を実現できるのだった。

node *
aexpr()
{
    node *d;

    d = mexpr();
    while(last_token!=EOF) {
	switch(last_token) {
	case '-': 
	    d = new_node('-',0,d,mexpr());
	    break;
	case '+': 
	    d = new_node('+',0,d,mexpr());
	    break;
	default:
	    return d;
	}
    }
    return d;
}

ここでは、以下のことに注目して欲しい。

文法規則一つについて、一つの木が返される
この手続きからreturnする場合と、他の手続きを呼び出す場合がある

この手続きからreturnする場合は、文法要素が確定した時であり還元(reduce)と呼ばれる。他の手続きを呼び出す場合は、遷移 shift と呼ばれる。

reduece 文法要素が確定し、スタックが減る
shift 新しい文法要素を試す。スタックが増す。

CFGのあるsubsetでは、このshift, reduce の組を状態遷移で表すことができる。すると、構文解析プログラムは、その状態遷移を行う機械となる。そして、reduce をおこなう部分に木を返す手続きを記述すれば良い。これが、yacc の原理である。例えば、この構文解析を yacc で記述すると以下のようになる。

aexpr :  aexpr '+' mexpr { $$ = new_node('+',0,$1,$3); }
    |    aexpr '-' mexpr { $$ = new_node('-',0,$1,$3); }
    |    mexpr {$$ = $1; }
    ;

$$ が返す木を表し、$1,$2,$3... などが文法規則中に現われた要素の木を表す。返す木の型(ここではnode *)は、YYSTYPEを#defineすることによって定義できる。実際には、木以外のものでも構わない。C の union などを使ってより自由度をあげることもできる。構文解析部分以外は、 s-tree-compile.c と、まったく同じものを使うことができる。例えば、 s-yacc.y のように記述することができる。yacc に -v option を付けてコンパイルすることにより、生成された状態遷移を見ることができる。

曖昧な文法

それでは、これで yacc を使えば、構文解析はすべてOkなのだろうか? 実際のコンパイラでは、さまざまな問題がある。例えば、

statement :  if ( expr ) statement
          |  if ( expr ) statement else statement
          |  a | b | c
          ;

という文法を考えて見よう。if (x==y) if (z==w) a else b は、どのように解釈されるべきだろうか?

if (x==y) { if (z==w) a else b  }
if (x==y) { if (z==w) a } else b

の2種類の解釈が可能である。(これは、間違いやすい部分でもある。僕だったら、 {}は省略しない。) これは、曖昧な文法と呼ばれる。CFGは、曖昧さを許す文法であり、実は人間は曖昧な文法の方が読みやすいし書きやすいと感じるようである。

問題

前の二通りの解釈が出てくる時の文法の適用順序を図を用いて示せ。

実際には、このような文は、適当な規則により適当な解釈に固定される。逆にいえば、yacc がこのような曖昧な文法にであった時には、それを解決しなければならない。(状態遷移には曖昧さは許されない) このような曖昧さに出会った時に yacc は、shift reduce conflict とか、reduce reduce conflict という文句をいう。

yacc では、この場合は先に書いてある文法規則が優先される。つまり、二つ目の解釈になる。しかし、それが常に望ましいとは限らない。このためのいろいろなオプションがyaccには用意されている。

例えば、演算子の順位を指定することにより曖昧さを解決することもできる。例えば、四則演算だったら、

%left '+' '-'
%left '*' '/'
expr :  expr '+' expr { $$ = new_node('+',0,$1,$3); }
    |   expr '-' expr { $$ = new_node('-',0,$1,$3); }
    |   expr '*' expr { $$ = new_node('-',0,$1,$3); }
    |   expr '/' expr { $$ = new_node('-',0,$1,$3); }
    |   term   /* $$=$1 は省略可能 */
    ;

と記述することもできる。%leftが、左再帰を表し、その出現順序が演算子の優先順位を表している。

ここでは、yaccの実現や他の機能にはあまり深入りしないことにしよう。ただ、yacc の conflict はエラーではなく、曖昧な文法を表していて、yacc が勝手にそれを解決しているということは覚えておこう。conflict は文法の間違いを表していることも多いが、特に直す必要がない場合も多い。

モードに依存する文法

文法規則だけでは解釈する情報が足りない場合がある。例えば、

Cのtypedefのように、文法要素をプログラム中で定義する場合
演算子と、その順位をプログラム中で決める場合
global変数とlocal変数のように、同じ文法要素でも、出て来る位置により意味が違う場合

このような場合は、文法解釈の途中で、さらに文法構造とは別のモード(mode)を用意する。あるいは、いったん曖昧なまま構文木を作ってしまい、その後に解釈を行う方法もある。しかし、いったん木を作った後、木の構造を操作すると見通しが悪く間違いを起こしやすい。構文解析の途中で、mode を設定する方法が直観的で分かりやすいことも多い。例えば、 Cの文法は、かなり複雑であるが、modeを使うと簡単になる部分がある。

例えば、Micro-C では、Cの以下の宣言を一つの文法で済ましている。

global変数/関数の宣言
関数の引数の宣言
local変数の宣言
構造体の中の宣言

これらは、mode 変数の、

    45	#define TOP	0
    46	#define GDECL	1    /* global 変数 */
    47	#define GSDECL	2    /* global struct */
    48	#define GUDECL	3    /* global union */
    49	#define ADECL	4    /* argument 変数 */
    50	#define LDECL	5    /* local 変数 */
    51	#define LSDECL	6    /* local struct */
    52	#define LUDECL	7    /* local union */
    53	#define STADECL 8    /* static */
    54	#define STAT	9    /* function の最初 */
    55	#define GTDECL	10   /* global typedef */
    56	#define LTDECL	11   /* local typedef */

によって区別されている。getsym() では、このmodeを見ながら、どの処理を変えている。ただし、このmodeによる区別はプログラムの見通し悪くするので使い方には気を付けよう。

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

型のコンパイル

C では、変数の宣言は以下のように行われる。

     int i,*ptr;

これが、表れる場所によって、global変数やlocal変数となる。シンボル表の登録は、getsym()によってglobalとlocalに分けて、行われるので、getsym() が呼ばれる前に、 mode が決まっていなければならない。シンボルのsymbol classやdispの設定は、def() でやはりmodeを見て行われる。def() では、初期値の設定もおこなわれる。

ここで型名には、いろいろなものがくる。

前もって定義されている型 char,int,short,long,unsigned
* pointer 型
[]配列、()手続。これらは()でくくられる場合が多い
struct, unicon さらに中身の定義がある場合とない場合がある
typedef で定義された型名

しかも、この型名の構文は、通常の関数の定義と、cast (型変換の場合で異なる。例えば、関数へのポインタの宣言と、関数へのポインタの大きさを取る場合では以下のようになる。

int (*func)();
j  = sizeof(int (*)());

前者は typespec()とdecl0()で処理され、後者は、typename()とndecl0() で処理される。これを例えば以下のように使うことができる。(まるでアセンブラのようだ...)

func  = (int (*)())i;
return (*func)(j);

宿題

(1)
```
    int j;
    j  = sizeof(int (*)());
```
が、どのようにコンパイルされるかを、文字列と手続名と行番号の対応で示せ。 (ヒント、sizeof は、expr13()にあります。gdb とかを有効に使うと楽勝) 単なるtraceだと何が何だか分からないと思います。