プログラミング言語処理

構文解析の実際：yaccの使い方

これまで、yaccの基本的な使い方について解説した。さて、これからyaccを使って tiny Cのインタプリターを作ることにする。yaccのクローンであるbisonのマニュアルは、

http://www.gnu.org/manual/bison/

に解説してあるために、参考にするとよい。 (残念ながら、日本語訳は以前はありましたがみつかりませんでした)

yaccの動作

yaccは、以下のように動作する。

yylexを呼び出して、tokenを読み込み、そのtokenから始まる文法規則を探す。
その文法規則が終るまで、tokenを読み、遷移(shift)を続ける。
文法に非終端記号がある場合は、その文法規則をスタックに積み、1からやり直す。
文法規則の最後まで遷移したら、その規則を還元(reduce)する。
スタックから一つ前に処理していた規則に戻り、3.で還元した非終端記号をつかって、さらにshiftする。
2に戻る。

実際にyaccが出力するparserのコードを解読するのは無理であるが、参考として、-vを付けてyaccを起動することによって、y.outputというファイルができるので、これを見るとどのようにshift、reduceしているかを見ることができる。

yaccのactionと意味値(semantic value)

以前、つくった式のyaccのプログラムでは、単に構文が定義した文法にあっているかをチェックするものであったが、構文解析の仕事は定義した構文にあっているかとチェックするとともに、構文を表現する構文木(抽象構文木： abstract syntax tree, AST)を作ることである。構文木は意味解析でその意味に従った処理が行われる。

yaccでは、構文解析の途中で、何らかの動作を行うactionの指定ができる。構文木を作る作業はこのactionの中で行う。actionは構文規則の中に{ } で囲んで, C言語で記述する。例えば、

term:  factor { printf("factor is coming"); }
     | term '*' factor { printf("factor is added"); }
    ;

この例では、termの各規則がreduceされたときに、{}の中のactionが実行される。通常、actionは各構文規則の最後に書き、reduceされた時に実行されるようにするが、途中に書いてもよい。その場合には、そこまで、shiftされたときにactionが実行されるようになる。

構文規則の主な仕事は、構文木を作ることである。yaccでは各構文規則で生成される値を意味値(semantic value)を持つことができ、その構文で認識された構文木を意味値として、actionでその意味値を生成（計算）する。例えば、上の例では

term: factor { $$ = $1; }
     | term '*' factor { $$ = makeAST(PLUS_OP,$1,$2); }
     ;

$1,$2,...は、右に現れる非終端記号の意味値であり、これを使って、$$は右の記号termの意味値を計算する。この値のデータ型は構文木すなわちASTへのポインタ型にする。なお、makeASTは２つのASTから新しいASTを作る関数である。

宣言部に、以下の記号のデータ型を定義する。

%union {
  AST *val;
}
%type <val> term factor

%unionは、意味値に使うデータ型を定義するもので、この中のデータ型は複数でもよい。このunionのメンバーを使って、%typeで構文規則の記号の意味値を定義する。

さて、factorの定義では、終端記号の意味値を使う。

%type <val> NUM SYM
 ...
factor: NUM  | SYM ;

{ $$ = $1; }の場合は省略してもよい。終端記号に対しては、字句解析ルーチンyylexからは、yylexの値をNUM,SYMを返すとともに、意味値をyylvalという変数（これはyaccから生成されるルーチンの中で定義されている）を介して、意味値を返す。

int yylex(){
   .... /* NUMの時　*/
   yylval.val = makeNum(n);
   return NUM;
  .... /* SYMの時*/
  yylval.val = makeSymbol(yytext);
  return SYM;
  .... 
}

なお、意味値のデータ型は、yaccの中ではYYSTYPEという名前になっており、

#define YYSTYPE ...

として、直接定義する方法もある。

優先度の定義

yaccはLALR parserであり、一文字先読みをしているため、演算子の結合規則と、優先度を定義できる。%leftは左結合規則を持つ演算子であることを指定する。例えば

%left '+'

と指定すると、

expr: expr '+' expr { ...} ;

の文法規則を使って、x + y + z に対して((x + y) + z)のように処理される。 %rightは右結合規則を持つもので、例えば代入の'='は右結合規則を持つものである。%left、%rightは同時に演算子の優先度も指定する。後から、指定したほうが高い優先度を持つものと解釈される。これを使うと優先度をもつような規則を簡単に書くことができる。

%left '+' '-'
%left '*'
%left UMINUS
...
expr:   factor
       |  expr '+' expr { $$=addSymbol(plusSym,makeList2($1,$3)); }
       | exp '-' exp { $$=addSymbol(minusSym,makeList2($1,$3)); }
       | exp '*' exp { $$=addSymbol(mulSym,makeList2($1,$3)); }
       | '-' exp %prec UMINUS { .... }
　　　 ;

なお、最後の%precは単項演算子を最も優先度の高い処理をするための指定である。

あいまいな文法とshift/reduce conflict, reduce/reduce conflict

文法にあいまいさがあると、LR 構文解析ができなくなるので、yacc は警告メッセージをだす。メッセージには２種類あり、 shift/reduce conflict, reduce/reduce conflictがある。shift/reduce conflictとは、文法規則が shift（つまり、さらに長い非終端記号にreduceできる）なのか、reduce(そこで打ち切って、非終端記号にしてしまう)か、解釈ができることを示す。この conflictは一概に文法定義が間違っているということではない場合がある。有名な例として、IF文の定義がある。

statement : IF '(' expression ')' statement
          | IF '(' expression ')' statement ELSE statement
           ....;

これは次の場合にあいまいになる。

if (a > 0)
 if (b > 0) c = 100;
  else
 c = 2000;

else を読んだとき、この token は内側の if 文の一部であると考え、遷移すればよいのだろうか、それとも、内側のif 文は完了したと考え、還元して、読みこんだ else は外側の if 文の一部であるとして遷移すればよいのだろうか？一般に yacc は、shift/reduce conflict がおきたときには、例外条件として、遷移(shift)を優先させる。したがって上のelse は内側の if 文の一部と解釈される。この解釈は、C 言語を始めほとんどの言語の仕様と一致するので、一般にif 文にまつわる shift/reduce conflict はそのままにしておいて問題ない。

他方、reduce/reduce conflictは、同時に還元できる文法規則が複数あることを意味する。便宜上、yaccでははじめに現れた文法規則を優先させるが、これは望ましいことではないので、このconflictがないように文法を作る必要がある。例えば、良くある例として0個以上のword列を読む場合を考えてみる。

sequence: /*  */　{ printf ("empty sequence\n"); }
        | maybeword
        | sequence word　{ printf ("added word %s\n", $2); }
        ;
maybeword: /*  */　{ printf ("empty maybeword\n"); }
        | word　{ printf ("single word %s\n", $1); }
        ;

この場合は、wordはmaywordにreduceでき,sequenceでもreduceできてしまう。この場合は単に、以下のように定義してやればよい。

sequence: /*  */　{ printf ("empty sequence\n"); }
        | sequence word　{ printf ("added word %s\n", $2); }
        ;

もう一つの注意点として、再帰的な定義がある。例えば、','で区切られた列を表現する場合に次の２つの方法がある。

seq:  item |  seq ',' term ;　/* left recursion */
seq:  item | term ',' seq ;   /* right recursion */

yaccでは、right recursionでは、途中の状態をスタックにとっておく必要があるため、なるべく、left recursionで書いておくべきである。

エラー回復処理

通常使っているコンパイラでは、途中で文法エラーを見つけたとしてもなるべく、他の部分もparseして一度に多くの文法エラーを見つけることができるようにしてある。文法エラーを見つけたときに、次にどこから構文解析を再開するかの処理をエラーからの回復処理という。どこから処理を再開するか、どうやって再開するかについてはコンパイラの使いやすさの要素の一つにもなり、結構むずかしい問題である。ここでは、yaccでの簡単なエラー処理だけについて述べておく。

yaccでは、予約の非終端記号として、errorという予約語があり、yyerrorが呼び出されて、これが終了(retrun)すると、errorという記号にreduceされるように処理してある。例えば、

statement: ....
          | error ';'
          ;

とすることによって、statementの構文解析で文法エラーが起きた場合には、';' がくるまで読みとばす処理をすることになる。