Lecture Notes

1-4 構文解析１

これまでの３回で、Lisp のインタプリタを作成した。今回からは C 言語のごく小さなサブセット Tiny C のコンパイラを作っていく。

最初の作業は構文解析である。字句解析部が返してくる token を、個々の式や文ごとにグループ化し、木構造に変換する。

文法の定義

字句解析をおこなうプログラムが lex を使うと簡単に作成できたように、構文解析をおこなうプログラムも yacc を使うと簡単に生成できる。yacc は BNF (Backus Naur Form or Backus Normal Form) で記述された文法に沿って構文解析をおこなう C プログラムを合成する。

BNF で定義した文法は次のようなものである。

program : statement | program statement

statement : VARIABLE '=' expression ';' | PRINT VARIABLE ';'

expression : NUMBER | VARIABLE | '(' expression ')' | expression '+' expression

一番上の規則は、program は statement か、または program の後に statement が続いたである、と読む。大文字で書いた名前や引用符で囲った文字は token である。小文字で書いた名前は非終端記号(non-terminal symbol)と呼ぶ。

この文法に合うプログラムは例えば次のようになる。

a = 31;
b = a + 3;
print b;

yacc が自動合成する構文解析のプログラムは、与えられたプログラム(token 列)に文法規則をどのように当てはめていくと、program に行き着くかを計算する。例えば、上のプログラムの場合、字句解析後は、

VARIABLE = NUMBER ;
VARIABLE = VARIABLE + NUMBER ;
PRINT VARIABLE ;

なので、

VARIABLE = expression ;
VARIABLE = expression + expression ;
statement

であり、

statement
VARIABLE = expression ;
statement

となり、

program
statement
statement

となり、

program
statement

となり、

program

と最後に program に行き着く。

もし規則をうまく当てはめて最後に program に行き着くなら、yacc が合成した関数 yyparse() は 1 を返し、行き着かないなら 0 を返す。つまり yyparse() は入力プログラムを検査して、文法エラーがあるかないかを判断する関数なのである。

文脈自由文法 (Context Free Grammar)

BNF で記述できる文法のクラスを文脈自由文法 (context free grammar)という。これ以外に有名な文法クラスには、文脈依存文法 (context-dependent grammar)と、正規文法 (regular grammar)がある。

文脈依存文法は、次のような形の生成規則を含む文法である。

xUy : xuy 文脈自由文法では、生成規則の左辺はひとつの非終端記号しかとれなかった。一方、文脈依存文法では、前後に一定の token か非終端記号がきたときに、U は u である、という記述ができる。

文脈自由文法である文法は、文脈依存文法でもある。これは定義から明らかである。しかし文脈依存文法である文法が、文脈自由文法であるとは限らない。したがって、文脈依存文法は、文脈自由文法より強力である。

正規文法とは、正規表現で記述できる文法のクラスである。正規表現の記法は、すべて BNF に書き換えることができる。

このため、少なくとも正規文法である文法は、文脈自由文法でもあることがわかる。それでは逆はどうであろうか。

例えば次のような文脈自由文法は正規文法でもある。

expression : NUMBER | VARIABLE | expression '+' expression これは次のような正規表現になる。

((NUMBER | VARIABLE) '+')* (NUMBER | VARIABLE) しかし、次のように () を扱えるようにすると正規表現では表せない。

expression : NUMBER
           | VARIABLE
           | expression '+' expression
           | '(' expression ')'

最後の規則は無限の入れ子構造を作るので、正規表現で扱えない。仮にこの文法を正規表現でも表わせたとしよう。すると対応する有限状態オートマトンがあるはずだが、この文法は無限の入れ子構造を作るので、途中の状態(括弧のネストが何段になっているか)は無限個なければならず、矛盾するので、この文法は正規文法ではない。

LR 構文解析

yacc が生成するプログラムは LR 構文解析(正確には LALR(1))という方法で、構文解析をおこなう。LR 構文解析は Left-to-right Rightmost derivation の意味で、上向き構文解析の一種である。上向き構文解析とは、token 列をまず下位の非終端記号に置き換え、それらを集めてさらに上位の非終端記号に置き換えていく、解析方法である。

例えば最初に定義した文法にそって、

b = a + 3; を LR 構文解析で解析してみよう。まず、token に直すと、

VARIABLE = VARIABLE + NUMBER ; となる。LR 構文解析は token を左から右に向かって、ひとつづつ読みならが解析をおこなう。

まず最初の token は VARIABLE である。これは規則

statement : VARIABLE '=' expression ';' の先頭の token である。そこで上の規則のひとつ目の token ないしは非終端記号として読み込み、次の token をまつ。この動作のことを遷移(shift)という。

次の token も '=' であるから、さらに遷移をおこなえる。ここで、もし '=' 以外の token が来たら、それ以上遷移をおこなえなくなるので、エラーとなる。

さて次の token は VARIABLE である。ここで、現在は次に expression が来るのを待っている状態なので、該当する規則を探すと、

expression : VARIABLE がある。そこでこの規則について遷移をおこなう。ところが遷移するとこの規則はおしまいであり、expression という非終端記号を見つけたことがわかる。これを expression に還元(reduce)した、という。

さて expression を見つけたのだから、途中で止めていた最初の規則についての遷移を再開するのだろうか。次の token は '+' である。残念ながら expression の次は ';' であるはずなので、この遷移はおこなえない。代わりに別な規則について遷移をおこなえる。

expression : expression '+' expression この規則の最初の expression と '+' を読み込み、遷移する。次の token は NUMBER だから、

expression : NUMBER という規則について、遷移、還元をおこない、先の規則

expression : expression '+' expression が完了して、expression に還元をおこなう。次の token は ';' であるから、一番はじめの規則

statement : VARIABLE '=' expression ';' の最後の遷移をおこなうことができ、statement に還元する。

LR 構文解析で、還元は token と非終端記号の列が、ある規則に一致していることを発見して、全体をより上位の一個の非終端記号に置き換えたことを意味する。これを繰り返してゆき、最後に最上位の非終端記号 program になれば、文法エラーなしで構文解析が終了したことになり、そうでなければ文法エラーで解析失敗ということになる。

文法のあいまいさ

文法にあいまいさがあると、LR 構文解析ができなくなるので、yacc は警告メッセージをだす。警告には2種類あって、shift/reduce conflicts と reduce/reduce conflicts がある。それぞれ同一の入力に対して、遷移(shift)と還元(reduce)の両方が可能であること、あるいは2種類の還元(reduce)が可能であること、を意味する。

shift/reduce conflict をおこす文法の例として有名なのは if 文である。

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

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

if (a > 0)
    if (b > 0)
        c = true;
else
    c = false;

else を読んだとき、この token は内側の if 文の一部であると考え、遷移すればよいのだろうか、それとも、内側の if 文は完了したと考え、還元して、読みこんだ else は外側の if 文の一部であるとして遷移すればよいのだろうか？

一般に yacc は、shift/reduce conflict がおきたときには、例外条件として、遷移(shift)を優先させる。したがって上の else は内側の if 文の一部と解釈される。この解釈は、C 言語を始めほとんどの言語の仕様と一致するので、一般に if 文にまつわる shift/reduce conflict はそのままにしておいて問題ない。

さて文法によっては、遷移と還元のどちらを優先してもかまわないこともある。

expression : NUMBER
           | Identifier
           | expression '+' expression

これは 1 + 2 + 3 のような式の場合、'+' を読んだ際に、1 + 2 を先に expression に還元するか、それとも遷移して、2 + 3 を最終的に expression として還元するか、2つの選択肢がある。意味的には (1+ 2) + 3 か 1 + (2 + 3) かの違いになるが、どちらでもかまわない。

もし文法のあいまいさを取り除きたいのなら、次のように文法を書きかえればよい。

expression : term
           | expression '+' term

term       : NUMBER
           | Identifier

一方、遷移を優先しては困ることもある。

expression : NUMBER
           | expression '+' expression
           | expression '*' expression

これは 1 * 2 + 3 のような式の場合、'+' を読んだ際に、1 * 2 を先に expression に還元するか、それとも遷移して、2 + 3 を最終的に expression として還元するか、2つの選択肢がある。演算子の優先順位としては、還元すべきだが、yacc は遷移を優先させてしまう。

これを回避するには、+ と * の間の演算子の優先順位を明示的に指定するか、あるいは次のように文法を書きかえればよい。

expression : term
           | expression '+' term

term       : NUMBER
           | term '*' NUMBER

yacc のプログラム

yacc は lex と連携して使うようになっている。yacc のプログラムは次のような構成をとる。

%{
    任意の C 言語プログラム。#include など。
%}

%token  ...

%%

    BNF による文法定義

%%

    任意の C 言語プログラム。main() など。

%token というのは文法中にでてくる token を宣言するためのものである。このプログラム sample.y を

% yacc -dv sample.y とすると y.tab.c, y.tab.h, y.output というファイルを生成する。y.tab.h の中では各 token に対応するマクロが定義される。lex プログラムの方では、y.tab.h を #include で取りこむようにすれば、yacc プログラムとマクロを共有することができる。

y.tab.c の中には、sample.y の最後のパートで定義された main() 関数などの他、yacc が生成する yyparse() という関数も含まれる。この関数は呼ばれると、yylex() を使って token をひとつづつ読みながら、構文解析をおこなう。そして解析が文法エラーなく終了すると、0 (false) を、そうでなければ 1 (true) を返す。

課題4

grammar.yは Tiny C 言語の文法定義である。これをよく読んで、if 文を追加せよ。必要なら token.l も修正せよ。

さらに

% yacc -dv grammar.y
% lex token.l
% gcc y.tab.c lex.yy.c -ll

とコンパイルし、

% ./a.out
int foo(int x, int y) {
    return x + y - 3;
}
^D

などとプログラムを入力し、正しいプログラムならエラーがでず、間違ったプログラムなら Syntax error と表示されることを確認せよ。(なお最後の ^D は入力の終了をあらわす制御文字である。)

注: yacc が使えない場合は bison コマンドを試してみよ。

さてgrammar.yはいくつかの shift/reduce conflict を発生させる。文法を書き直して、shift/reduce conflict がひとつだけになるようにせよ。残ったひとつは if 文によるものである。

目次へ戻る

Email: chiba@is.tsukuba.ac.jp