第9章 速習yacc

概要

パーサとスキャナ

プログラム言語のパーサの書きかたは昔からしつこく研究されてきており、 かなりしっかりした定石がある。よほど変な(または曖昧な)文法でない 限り、定石にのっていけば解決できるものだ。

まず最底辺には文字列を単語(トークンとも言う)の列に切り出す部 分がある。これをスキャナ(scanner)とかレクサ(lexer)と言 う。日本語で言うと字句解析器だが、言いにくいのでスキャナと呼ぼう。

スキャナというものが出てくる根底にはそもそも「単語の区切りには空白ある でしょ」という常識がある。そして実際にたいていのプログラミング 言語はそういう仕様になっている。そのほうが楽だからだ。

例えば古いFortranでは空白が意味を持たなかった。つまり空白を入れても 単語区切りとは限らないし、変数の途中で何の前触れもなく空白を挿入したり することもできた。ところが解析が恐ろしく面倒なものでコンパイラベンダが 次々とその規格を無視しはじめ、結局Fortran 90もそれを後追いして空白が ちゃんと影響するような規格になった。

ちなみにFortran 77がなぜ空白に意味を持たせなかったかと言うと、プログラ ムをパンチカードに打つときに空白の数を間違いやすかったから、らしい。

記号列

スキャナは単語(トークン)の列を吐きだすと言ったが、正確に言うと単語で はない。スキャナが生成するのは「記号」の列である。

記号とはなんだろうか。例えば数値のことを考えてみよう。プログラム言語 なら1も2も3も99も同じ「数」だ。どれも文法的には全く同じ扱いをされる。 1と書ける場所なら2も3も書ける。だからパーサとしてみれば必ずしもこれらを 全部区別して扱う必要はない。数値なら「数値」で十分だ。

その「数値」とか「識別子」のようなものをまとめて「記号(symbol)」 と呼ぶ。 日本語になってしまうと意味がわかりづらいが、この場合の記号とは「意味」 とか「象徴」のような意味で使われている。もうちょっといい呼びかたはない ものかと考えたのだが、シンボルと言うとSymbolクラスのインスタンスと紛ら わしい。symbolと書くと変数名と紛らわしい。仕方がないのであきらめて「記 号」と呼んでおくことにする。

スキャナはまず文字列を単語に区切り、そしてその記号を割り出す。 例えば数値ならNUMBERDIGIT、 「name」のような名前(識別子)ならIDENTIFIER、 予約語のifならIF、というように。 そしてその記号を次の段階に渡す。

パーサジェネレータ

さてスキャナが吐きだした単語と記号の列を今度はツリー状に組み立てていく。 このツリーを構文木(syntax tree)と言う。

単にパーサという言葉を使うと構文木を作るところからスキャナまで全部含め ることもあるので、この構文木を作る装置を限定的に狭義のパーサと呼ぼう。 その狭義のパーサはどうやってただの記号列をツリーにするのだろうか。 言い換えると、何に注目すればツリーを発見できるだろうか。

一つは、その単語の持つ意味に注目するという手がある。例えばvarという 単語を発見したとしよう。このときまでにローカル変数varの定義が発見され ていれば、これはローカル変数の参照だな、とわかるはずである。

もう一つはひたすら見ために注目する方法である。例えば識別子の次に=が来 たら、これは代入だな、とわかる。予約語のifが登場したら、ここからは if文だな、とわかる。

後者の、見ためにだけ注目する方式が現在のトレンドだ。つまり記号列だけを 見て解析できるように言語を設計するということだ。なぜならそのほうが簡単 で単純でしかも一般化が進んでいる、従ってツールで自動化できるからである。 その自動化ツールをパーサジェネレータ(parser generator)と言う。

そしてUNIXで一番使われているパーサジェネレータがyaccだ。rubyの パーサも御多分に漏れずこのyaccを使って書かれている。parse.yがその 入力だ。つまりrubyのパーサを読むためにはyaccのことをある程度知って おかなければならない。

そこで本章はparse.y解析の前準備としてyaccの簡単な解説を行うが、あくま で読むのに必要な最小限の説明にとどめる。もっと詳しくパーサとパーサジェ ネレータについて知りたい読者には拙著 『Rubyを256倍使うための本 無道編』\footnote{『Rubyを256倍使うための本 無道編』青木峰郎著、アスキー出版局、2001}を お勧めしておく。これは別に自分で書いたから勧めているわけではなく、客 観的に見てもこの分野に関しては一番わかりやすい本だからである。それに安 いので博打にならない。

それでもやっぱり別の人のがいい、ということなら オライリーの『lex&yaccプログラミング』 \footnote{『lex&yaccプログラミング』John R. Levine, Tony Mason, Doug Brown著、村上列訳、アスキー出版局、1994} をお勧めする。 それでもまだ満足できなければあとはAhoの 『コンパイラ』 \footnote{『コンパイラ』Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman共著、原田賢一訳、サイエンス社、1990} でも読んでもらうほかない。

文法

文法ファイル

yaccへの入力は文法ファイルと言う。文法を書いたファイルだから文法ファイ ルだ。文法ファイルは*.yというファイル名にするのが慣例である。 これをyaccにかけるとCのソースコードができるので、 あとは普段通りそれをコンパイルすればよい(全体図は図1)。

(build)
図1: ファイル関係図

なお、出力ファイル名は常にy.tab.cで、変更できない。 新しいyaccだとたいていコマンドラインオプションで変更できるが、 互換性を考えるとy.tab.cにしておいたほうが無難である。 ちなみにy.tab.ctabtabletabらしい。巨大なテーブルがたくさん 定義されているからだ。一度ファイルを覗いてみるといい。

さて、文法ファイルの中身は次のような形になっている。

▼文法ファイル概形

%{
ヘッダ
%}
%union ....
%token ....
%type ....

%%
規則部
%%
ユーザ定義部

yaccの入力はまず%%で大きく三つに区分される。最初の一つ は定義部と言い、いろいろな定義をしたり前準備を書く。特に%{から %}まではC言語で好きなことが書ける場所である。ここには例えば必要なマ クロを書いたりする。その外では%を使ったyacc特有の命令が続く。ここで使 う命令についてはその都度説明しよう。

真ん中は規則部と言う。yaccの一番肝心なところで、ここに「こういう文法を パースしたいんだ」と書いておくとパーサができる。詳しくは次の項で話す。

最後の一つ、ユーザ定義部はユーザが自由に使ってよい。yaccはここの内容に は全く関知せず、一字一句そのまま出力ファイルにコピーしてくれる。 例えばパースのときに必要になる補助ルーチンを書いたりするのに使う。

yaccのすること

yaccが面倒を見てくれるのは主にその真ん中のところ、規則部に書いたものだ。 ここに文法を書くとyaccがそれをyyparse()という関数に変換してくれる。 これがつまり狭義のパーサである。

狭義の、なので、その他にスキャナが必要である。しかしyaccはスキャナまで は面倒を見てくれないのでユーザが用意しなければならない。 スキャナはyylex()という関数である。

それから、yyparse()にしてもyaccが生成してくれるのはその中のさらに肝心 な部分だけで、後述する「アクション」というところはほとんどyaccの範囲外 になる。それではyaccの活躍する部分が少なすぎないか、と思うかもしれない が、さにあらず。その「肝心な部分」というのがあまりにも 肝心すぎるからこそ、なんだかんだと文句を言われつつもyaccがい まだに生き残っているのである。ではその肝心な部分とはいったい何なのか、 という話になるわけだ。

BNF

Cでパーサを書くとすると、そのコードは「文字列のここをこう切って、これ をif文にして……」となる。パーサジェネレータを使う場合はその逆で、「こ ういう文法をパースしたいんだ」と言えばいい。そうするとその文法を扱うパー サを生成してくれる。つまり仕様を伝えると実装ができるわけだ。それが yaccの便利なところである。

ではどうやって仕様を伝えるのだろうか。 yaccの場合はBNF(Backus-Naur Form) という記述方法を使う。ごくごく簡単な例を見てみよう。

if_stmt: IF expr THEN stmt END

:」の左右で分けて見る。左側のもの、つまりif_stmtは、右側の並びに等し い……というのが、ここで言っていることだ。つまり

if_stmtはIF expr THEN stmt ENDという並びと等しい

と言っているのだ。ここでif_stmtIFexprや……は全て「記号」である。 exprexpression(式)、stmtstatement(文)の略のつもりだ。これは きっとif文の定義なんだろう。

この定義一つのことを規則と言う。そして「:」の左側を「左辺」、 右側を「右辺」と呼ぶ。実にストレートで覚えやすいネーミングだ。

さてしかし、これだけではちょっとものたりない。if文ならelseも付けられな いと嫌だ。それも、いつもelseを書くのは面倒なのでelseが必要ないときは 省略できるようにしたい。そういうときは次のようにすればいい。

if_stmt: IF expr THEN stmt END
       | IF expr THEN stmt ELSE stmt END

|」は「or(または)」の意味である。

if_stmtは、「IF expr THEN stmt END」という並びか または「IF expr THEN stmt ELSE stmt END」という並びである。

ということだ。

ここで注意してほしいのは、|で区切るとそれだけで規則は一つ増えてい るということだ。実は|で区切るというのは左辺の記述を省略しているだけで あり、論理的には先程の例は次の文法と全く同じ意味なのである。

if_stmt: IF expr THEN stmt END
if_stmt: IF expr THEN stmt ELSE stmt END

つまり先程の例で定義した規則は二つである。

これだけでif文の定義が完結したわけではない。exprstmtなんて記号 はスキャナから送られてくるはずがないから、それがどういう並びなのかをちゃ んと定義しないといけない。Rubyに近付けるべく、大胆に規則を足してみよう。

stmt   : if_stmt
       | IDENTIFIER '=' expr   /* 代入 */
       | expr

if_stmt: IF expr THEN stmt END
       | IF expr THEN stmt ELSE stmt END

expr   : IDENTIFIER       /* 変数参照 */
       | NUMBER           /* 整数定数 */
       | funcall          /* 関数呼び出し(FUNction CALL) */

funcall: IDENTIFIER '(' args ')'

args   : expr             /* とりあえず引数は一つだけ */

新しい要素を二つ使った。まずC言語と同じ形式のコメント、それから'='のよ うな文字の表現だ。この'='もやはり記号である。 「=」のような記号は数などと違ってただ一種類しか ないので、記号もそのまま'='でいいのだ。と来れば予約語などにも文字列を そのまま使いたくなるが、C言語の制約のためそれはできない。

こういうふうに規則を増やしていって、従うべき規則全体が書ければ文法ので きあがりだ。yaccでは一番上に書いた規則の左辺が「表現したい文法全体」を 表すことになっているので、この例ならstmtがプログラム全体を表すことにな る。

ちょっと抽象的にすぎた。もう少し具体的に説明しよう。「stmtがプログラム 全体を表す」というのは、stmtと規則上「等しい」記号の並び全てが文法とし て認められる、ということである。例えばまず、stmtstmtと等しい。あたり まえだ。次に、exprstmtと等しい。これは規則そのままだ。そして次に、 NUMBERstmtと等しい。なぜならNUMBERexprexprstmtだからだ。

もちろんもっと複雑なものも等しいと言える。

              stmt
               ↓
             if_stmt
               ↓
      IF expr THEN stmt END
          ↓        ↓
IF IDENTIFIER THEN expr END
                    ↓
IF IDENTIFIER THEN NUMBER END

ここまで展開したところで全部スキャナから送られてくる記号になったようだ。 つまりこういう記号の並びはプログラムとして正しいということである。逆に 言えば、こういう記号の並びがスキャナから送られてくるとパーサは展開の逆 の順序で入力を理解していける。

IF IDENTIFIER THEN NUMBER END
                    ↓
IF IDENTIFIER THEN expr END
          ↓        ↓
      IF expr THEN stmt END
               ↓
             if_stmt
               ↓
              stmt

そしてstmtはプログラム全体を表す記号だ。だからこの記号列はプログラムと して正しい。と、パーサは思うことだろう。そうなるとパースルーチン yyparse()は成功したという印に0を返して終了する。

ちなみに専門用語だとパース成功のことを受理(accept)と言う。 パーサはお役所みたいなもんで、自分の指定した枠にカッチリはめた 書類を提出してくれないと即つっぱねるわけだ。acceptされる記号列とい うのはその枠にちゃんとはまっているのである。妙に指定が細かいところとか、 わざわざ難解な用語を使うあたり、パーサとお役所はかなり似ている。

終端記号と非終端記号

さて、どさくさに紛れて「スキャナから来る記号」なんて言葉を説明なしで入 れてみたわけだが、改めて説明しよう。実は一口に記号と言っても二種類ある。

一つはスキャナから送られてくる記号、例えばIFTHENEND'='など である。これを終端記号(terminal symbol)と言う。先程のようにどんどん 展開したときに一番端っこに並ぶからだ。本章では終端記号は常に全て大文字 で記述する。ただし'='のようにクオートでくくってあるものは特別だ。この 類の記号は例外なく終端記号である。

もう一つはスキャナからは絶対に来ない記号、例えばif_stmtexprstmtである。こういう記号を非終端記号(nonterminal symbol)と 言う。非終端記号はスキャナから来ないわけだから、パーサの中だけの存在だ。 そして非終端記号はいつか必ず規則の左辺に現れる。本章では非終端記号は全 て小文字で記述する。

テストの方法

ここらで文法ファイルをyaccで実際に処理する方法を教えておこう。

%token A B C D E
%%
list: A B C
    | de

de  : D E

まず使っている終端記号を%tokenのあとに全て並べる。 ただしクオートを使った記号('='など)は書かなくてよい。 そして%%で区切って文法を書く。これだけだ。

では処理してみよう。

% yacc first.y
% ls
first.y  y.tab.c
%

UNIXツールの常として「沈黙は成功の意」である。

それから、規則(群)の最後にセミコロンが必要なyaccも存在する。 そのときは次のようにしよう。

%token A B C D E
%%
list: A B C
    | de
    ;

de  : D E
    ;

筆者はこのセミコロンが嫌いなので本書では常に省略する。

空規則

ではもう少しyaccの文法記述の定石をいくつか見ておくことにする。 まずは空規則から紹介しよう。

void:

右辺に何もない。ということは、記号voidは「無」と等しいということであ る。例えば次の二つのtargetは全く同じ意味になる。

target: A B C

target: A void B void C
void  :

こんなものが何の役に立つのだろうか。それがとても役に立つのだ。 例えば次のように。

if_stmt : IF expr THEN stmts opt_else END

opt_else:
        | ELSE stmts

空規則を使うことで「else節は省略される(無)かもしれない」ことを うまく表現できた。先程のように同じような規則を二つ並べて書くよりも こちらのほうが簡潔だし、責任が分散しなくてよい。

再帰定義

次の例はもう少しわかりにくい。

list: ITEM         /*  規則1  */
    | list ITEM    /*  規則2  */

これは一個以上のITEMを並べたリストを表現している。 つまり以下の記号列のいずれかを示す。

ITEM
ITEM ITEM
ITEM ITEM ITEM
ITEM ITEM ITEM ITEM
      :

どうしてかわかるだろうか。まず規則1により listITEMと読み換えることができる。 すると今度は規則2からlistITEM ITEMだと言えるようになる。

list: list ITEM
    = ITEM ITEM

これでITEM ITEMという記号列もlistと等しいとわかる。 これをまたさらに規則2のlistにあてはめればITEM三つもlistに等しいと言え…… これをどんどん続ければITEMをいくらでも増やしていける。 数学的帰納法みたいなものだ。

次の例を示す。以下はITEMをゼロ個以上並べたリストを表す。

list:
    | list ITEM

まず一行目は「listは(無)と等しい」という意味である。 無とは即ちITEMゼロ個のリストである。 次に二つめの規則を見ると、「list ITEM」はITEM一個と等しいと言える。 なぜならlistは無と等しいからだ。

list: list ITEM
    =(無)ITEM
    =      ITEM

先程と同じようにこの置き換え作業を何度も続ければ、listはゼロ個以上 のITEMのリストの表現であるとわかる。

この知識を応用すれば「ITEMが二個以上のリスト」とか「ITEMが三個以上のリスト」 は簡単だし、「ITEMが偶数個のリスト」なんてものも作れる。

list:
    | list ITEM ITEM

値の構築

抽象的な話が続いたのでこの節は思いきり物理的に話を進めたいと思う。

シフトと還元

ここまででは文法の書きかたをいろいろ説明してきたが、我々がやりたいのは あくまで構文木を作ることだ。しかし残念ながら規則を伝えるだけで構文木ま で作ってくれるわけでは、さすがにない。そこで今度は規則にプラスアルファ して構文木を作る方法を教えよう。

まずパーサが現実に実行時にやることを説明する。 次のような単純な文法を例に取ろう。

%token A B C
%%
program: A B C

パーサの中にはセマンティックスタック(semantic stack)と呼ばれるスタッ クが一つある。そしてこれにスキャナから来る記号をどんどんプッシュしてい く。この動作のことを指して「記号をシフト(shift)する」と言う。

[ A B ] ← C   シフト

そして文法のいずれかの右辺にある並びがスタックの先端に揃うと、 これを「理解」する。「理解」すると右辺の並びが左辺の記号に変わる。

[ A B C ]
    ↓         還元
[ program ]

この動作を「A B Cprogramに還元(reduce)する」と言う。 言葉は偉そうだがようするに白發中が揃うと大三元になるようなものだ。 ……それは違うか。

そしてprogramはプログラム全体を表すから、スタックにprogramだけがあると いうことはプログラム全体を見付けたのかもしれない。だからここでちょうど 入力が終われば受理される。

もう少しだけ複雑な文法で試してみよう。

%token IF E S THEN END
%%
program : if

if      : IF expr THEN stmts END

expr    : E

stmts   : S
        | stmts S

スキャナからの入力はこうだ。

IF  E  THEN  S  S  S  END

このときのセマンティックスタックの遷移を以下に示す。

スタック動作
最初は空
IFIFをシフト
IF EEをシフト
IF exprEexprで還元
IF expr THENTHENをシフト
IF expr THEN SSをシフト
IF expr THEN stmtsSstmtsで還元
IF expr THEN stmts SSをシフト
IF expr THEN stmtsstmts Sstmtsで還元
IF expr THEN stmts SSをシフト
IF expr THEN stmtsstmts Sstmtsで還元
IF expr THEN stmts ENDENDをシフト
ifIF expr THEN stmts ENDifで還元
programifprogramで還元
accept.

最後に一つだけ注意。還元では記号が減るとは限らない。 空規則があると「無」から記号が生成される場合もある。

アクション

さて、ここからが重要なところだ。シフトだろうが還元だろうが、セマンティッ クスタックの中でウダウダやっているだけでは何の意味もない。我々の最終目 標は構文木を生成することだったから、それにつながってくれないと困るのだ。 yaccはどう落としまえを付けるつもりなのか。「パーサが還元する瞬間をフッ クできるようにしましょう」というのがyaccの出した答えだ。そのフックを パーサのアクション(action)と言う。アクションは次のように規則の 最後に書く。

program: A B C { /* ここがアクション */ }

{}で囲んだ部分がアクションだ。こう書いておくとA B Cprogramに 還元する瞬間にこのアクションを実行してくれる。アクションでは何をしようと 自由だ。Cのコードならだいたいなんでも書ける。

記号の値

そしてここからがさらに重要なのだが、全ての記号には「その値」というもの がある。終端記号も非終端記号もだ。終端記号はスキャナから来るからその値 もスキャナからもらう。それは例えば記号NUMBERに対しては1とか9とか 108かもしれない。記号IDENTIFIERに対しては"attr"とか"name"とか "sym"かもしれない。なんでもいいのだ。その値は記号といっしょにセマン ティックスタックに積まれる。次の図は今ちょうどSを値と一緒にシフトし たところだ。

IF    expr   THEN   stmts   S
値    値     値     値     値

先程の規則によればstmts Sstmtsに還元できる。もしその規則にアクション が書いてあればそれが実行されるわけだが、その時、右辺に対応する分の記号 の値をアクションに渡すのだ。

IF    expr   THEN   stmts  S      /* スタック */
値1   値2    値3    値4    値5
                    ↓     ↓
            stmts:  stmts  S      /* 規則 */
                    ↓     ↓
                  { $1  +  $2; }  /* アクション */

と、このようにアクションでは$1$2$3…… で規則右辺に相当する記号の値を取ることができる。 $1とか$2はスタックを指す表現にyaccが書き換えてくれるわけだ。 もっともC言語なら本当は型のこととかいろいろあるのだけれど、 面倒なので当面intと仮定しておこう。

そして次は代わりに左辺の記号を積むのだが、記号はどれも値があるのだか らその左辺の記号にもやはり値がなくてはいけない。それはアクション中では $$と表現され、アクションを抜けたときの$$の値が左辺の記号の値となる。

IF    expr   THEN   stmts  S      /* 還元直前のスタック */
値1   値2    値3    値4    値5
                    ↓     ↓
            stmts:  stmts  S      /* 右辺が末尾にマッチした規則 */
              ↑    ↓     ↓
            { $$  = $1  +  $2; }  /* そのアクション */


IF    expr   THEN   stmts         /* 還元後のスタック */
値1   値2    値3    (値4+値5)

最後に蛇足。記号の値は意味値、semantic valueと呼ばれることもある。 だからそれを入れるスタックはsemantic value stackで、 略してsemantic stackと呼ぶわけだ。

yaccと型

さて実に面倒だが、型の話をしなければ話が収まらない。記号の値の型はいっ たいなんだろう。結論から言うとYYSTYPEという型になる。きっとこれは YY Stack TYPEか、はたまたSemantic value TYPEか、どちらかの略に違いない。 そしてYYSTYPEは当然何か別の型のtypedefである。その型とは、定義部で %unionという命令で指定した共用体だ。

だが今までは%unionなんて書いていなかった。それなのにエラーにならなかっ たのはどういうわけだろう。それはyaccが気をきかせて勝手にデフォルトでもっ て処理してくれたからだ。Cでデフォルトと言えば当然intだ。ということ でYYSTYPEのデフォルトはintである。

yaccの本に出す例や電卓プログラムくらいならintのままでも構わないのだが、 構文木を作るには構造体やポインタやその他いろいろを使いたい。そこで例え ば次のように%unionを使う。

%union {
    struct node {
        int type;
        struct node *left;
        struct node *right;
    } *node;
    int num;
    char *str;
}

今は実際に使うわけではないので型やメンバ名は適当だ。普通のCと違って %unionのブロックの最後にはセミコロンが必要ないので注意。

それで、こう書くとy.tab.cでは次のようになるわけだ。

typedef union {
    struct node {
        int type;
        struct node *left;
        struct node *right;
    } *node;
    int num;
    char *str;
} YYSTYPE;

そうするとセマンティックスタックは

YYSTYPE yyvs[256];       /* スタックの実体(yyvs = YY Value Stack) */
YYSTYPE *yyvsp = yyvs;   /* スタックの先端を指すポインタ */

という感じだろうな、と予想が付く。 それならアクションに出てくる記号の値も……

/* yacc処理前のアクション */
target: A B C { func($1, $2, $3); }

/* 変換後、y.tab.cでの様子 */
{ func(yyvsp[-2], yyvsp[-1], yyvsp[0]); ;

当然こうなる。

この場合はデフォルトのintを使ったのでスタックを参照するだけでよいが、 YYSTYPEが共用体の場合は同時にそのメンバも指定しなければアクセスでき ないはずである。それには記号単位で結び付ける方法とその都度指定する 方法の二通りがある。

まずは一般的な、記号単位で指定する方法から。終端記号の場合は %tokenを、非終端記号の場合は%typeを使って次のように書く。

%token<num> A B C    /* 全てのA B Cの値はint型 */
%type<str> target    /* 全てのtargetの値はchar*型 */

一方、毎回指定する場合は次のように$の次にメンバ名を割り込ませる。

%union { char *str; }
%%
target: { $<str>$ = "ようするにキャストみたいなものさ"; }

こちらの方法はできるだけ使わないほうがいい。 記号単位でメンバを決めるのが基本だ。

パーサとスキャナの連結

これでパーサの中の値のアレコレについては全て話した。あとはスキャナ との連結プロトコルを話せば核となる事項は全ておしまいだ。

まず確認すると、スキャナは関数yylex()であった。 (終端)記号そのものは関数の返り値として(intで)返す。yaccが記 号と同じ名前で定数を#defineしてくれているので、記号NUMBERならNUMBERと 書くだけでいい。そしてその値はyylvalというグローバル変数に入れて渡す。 このyylvalもまたYYSTYPE型で、パーサのときと全く同じことが言える。つま り%unionで定義すると共用体になる。しかし今回はメンバを勝手に選んだりは してくれないので自分でメンバ名を書かないとだめだ。つまり非常に簡単な 例だと次のようになる。

static int
yylex()
{
    yylval.str = next_token();
    return STRING;
}

ここまでの関係を図2にまとめたので一つ一つ確認してみてほしい。 yylval$$$1$2……など、インターフェイスとなる変数は全て YYSTYPE型である。

(yaccvars)
図2: yacc関連の変数・関数の関係

埋め込みアクション

アクションは規則の最後に書くもの、と説明したが、実は規則の途中で 書いてしまうこともできる。

target: A B { puts("embedded action"); } C D

これを埋め込みアクションと言う。 埋め込みアクションは次のような記述の 単なるシンタックスシュガーだ。

target: A B dummy C D

dummy :     /* 空規則 */
        {
            puts("embedded action");
        }

実行されるタイミングなどはこれで全てわかるだろう。記号の値も普通に取れ る。つまりこの例なら埋め込みアクションの値は$3として出てくる。

現実的な話題

衝突

もうこれでyaccなんて恐くない。

と思ったとしたらそれはかなり甘い。なぜyaccがこれほどまでに 恐れられるのか、その理由はこの後にあるのだ。

これまでは「規則の右辺がスタック先端にマッチしたら」と何気なく書いて きたが、次のような規則があったらどうなるのだろうか。

target  : A B C
        | A B C

実際にA B Cという記号列が出てきたとき、どちらの規則がマッチするのか わからなくなるはずである。こんなものは人間にだって理解できない。 従ってyaccもわからない。こういう変な文法を発見するとyaccは reduce/reduce conflict(還元・還元衝突)が起きた、と文句を 言ってくる。複数の規則が同時に還元可能であるという意味だ。

% yacc rrconf.y
conflicts:  1 reduce/reduce

とはいえ普通ならば事故以外にこんなことはしないと思うが、 次の例はどうだろうか。記述している記号列は全く同じである。

target  : abc
        | A bc

abc     : A B C

bc      :   B C

これならば比較的ありうる。特に規則を考えながらグチャグチャ移 動していると知らず知らずのうちにこんな規則ができてしまうものだ。

似たパターンで次のようなものもある。

target  : abc
        | ab C

abc     : A B C

ab      : A B

A B Cという記号列が現れた場合、abc一つを選ぶべきかabCの組み 合わせにすべきかわからない。こういうときyaccは shift/reduce conflict(シフト・還元衝突)が起きたぞ、と文句を垂れる。 こちらは、同時にシフトできる規則と還元できる規則があるという意味だ。

% yacc srconf.y
conflicts:  1 shift/reduce

shift/reduce conflictの有名な例が「ぶらさがりelse問題」である。 例えばC言語のif文でこの問題が起こる。話を単純化して書いてみよう。

stmt     : expr ';'
         | if

expr     : IDENTIFIER

if       : IF '(' expr ')' stmt
         | IF '(' expr ')' stmt  ELSE stmt

式はIDENTIFIER(変数)だけ、ifの本体は文一つだけとして規則を作ってみた。 さて、この文法で次のプログラムをパースするとどういうことになるだろう。

if (cond)
    if (cond)
        true_stmt;
    else
        false_stmt;

こう書いてしまうとなんとなく一目瞭然に見えるのだが、 実は次のようにも解釈できる。

if (cond) {
    if (cond)
        true_stmt;
}
else {
    false_stmt;
}

つまり外側と内側どちらのifelseを付けるかという問題だ。

ただしshift/reduce conflictはreduce/reduce conflictに比べれば比較的無 害な衝突である。なぜかというと、たいていの場合はシフトを選べばうまくい くからだ。シフトを選ぶというのは「できるだけ近い要素同士を連結する」と だいたい同義語であり、人間の直感にマッチしやすい。実際、ぶらさがり elseもシフトしておけばうまくいく。そういうわけでyaccもその流れに従い shift/reduce conflictが起きたときにはデフォルトでシフトを選ぶようになっ ている。

先読み

試しに次の文法をyaccにかけてみてほしい。

%token A B C
%%
target  : A B C   /* 規則1 */
        | A B     /* 規則2 */

どう考えても衝突しそうではないだろうか。A Bまで読んだ時点で 規則1はシフトしたがるし、規則2は還元したがる。 つまりこれはshift/reduce conflictになるはずだ。ところが……

% yacc conf.y
%

おかしい、衝突しない。どうしてだろう。

実を言うとyaccで作ったパーサは記号を一つだけ 「先読み(look ahead)」できる。 本当にシフトや還元をする前に次の記号を盗み見て、どうするか判断 できるのだ。

だからパーサ生成時にもそれを考慮してくれて、一つの先読みで区別 できるなら衝突させない。例えば先程の規則ならA Bの次にCが来れば 規則1しか可能性はないので規則1を選ぶ(シフトする)。入力が終わっ たら規則2を選ぶ(還元する)。

注意してほしいのは「先読み」という単語には二通りの意味があることだ。 一つはyacc*.yを処理するときの先読み。もう一つは生成したパーサを 実際に動かすときの先読み。実行時の先読みはたいして難しくないがyacc自身 の先読みは非常にややこしい。なぜなら文法規則だけから実行時のあらゆる 入力パターンを予測して挙動を決めないといけないからだ。

もっとも、実際には「あらゆる」は無理なので「かなりの」パターンに対処す ることになる。そして全パターンのうちどのくらいの範囲に対処できるかどう かが先読みアルゴリズムの強さになるわけだ。yaccが文法ファイル処理時に 使っている先読みアルゴリズムはLALR(1)と言い、現存する衝突解決アルゴリ ズムの中ではわりと強力なものである。

いろいろ言ったが、本書でやるのは規則を読むだけで書くことではないので、 あまり心配することはない。ここで説明したかったのは文法を使った先読みで はなく実行時の先読みのほうだ。

演算子優先順位

しばらく抽象的な話が続いたのでここらでもう少し具体的な話をする。+*などの二項演算子(インフィックス型演算子)の規則を定義してみること にしよう。これにも定石があるので、おとなしくそれに従っておけばいい。以 下に四則演算が使える電卓のようなものを定義した。

expr    : expr '+' expr
        | expr '-' expr
        | expr '*' expr
        | expr '/' expr
        | primary

primary : NUMBER
        | '(' expr ')'

primaryは「項」とか訳される。一番小さな文法単位のことである。 exprを括弧でくくるとprimaryになるというところがポイントだ。

さて、この文法を適当にファイルに書いてコンパイルすると、こうなる。

% yacc infix.y
16 shift/reduce conflicts

激しく衝突してしまった。五分ばかり考えていればわかると思うが、 この規則では次のような場合に困るのである。

1 - 1 - 1

これは次の二通りのどちらにも解釈できてしまう。

(1 - 1) - 1
1 - (1 - 1)

数式として自然なのはもちろん前者だ。しかしyaccがやるのはあくまで見ため の処理であって、そこに意味は全く入らない。-という記号の持つ意味なんてこれっ ぽちも考慮してはくれないのだ。人間の意図を正しく反映させるには、やりた いことを地道に指示してやらないといけない。

ではどうしたらいいかと言うと、定義部にこう書けばよい。

%left '+' '-'
%left '*' '/'

この命令は演算子の優先順位と結合性の二つを同時に指定する。 順番に説明していこう。

優先順位という言葉はプログラム言語の文法の話をするときにはよく出てくる と思う。理論的に話すとややこしいので直感的に言うと、次のような場合にど ちらの演算子に括弧が付くかという話だ。

1 + 2 * 3

*のほうが優先順位が高ければ、こうなる。

1 + (2 * 3)

+のほうが優先順位が高ければ、こうなる。

(1 + 2) * 3

このように、演算子に強いものと弱いものを設定して shift/reduce conflictを解決するのが演算子優先順位だ。

だがしかし、同じ状況に陥っても優先順位が同じだったらどうすればいい だろうか。例えばこのように。

1 - 2 - 3

今度はどちらも-なので優先順位は全く同じだ。こういうときには結合性 を使って解決する。結合性にはleft right nonassocの三種類があり、 それぞれ次のように解釈される。

結合性解釈
left(左結合)(1 - 2) - 3
right(右結合)1 - (2 - 3)
nonassoc(非結合)パースエラー

数式用演算子だとほとんど左結合である。右結合は主に代入の=や 否定のnotで使う。

a = b = 1    # (a = (b = 1))
not not a    # (not (not a))

nonassocの代表格は比較演算子だろう。

a == b == c   # パースエラー
a <= b <= c   # パースエラー

もっともPythonなどでは三項の比較が可能なのでこの限りではない。

それで先程の%left%right%nonassocという命令は、 名前通りの結合性を示すために使われる。そして優先順位は並べる順で示す。 下にある演算子ほど優先順位が高い。同じ列にあれば同じ順位である。

%left  '+' '-'    /* 左結合で優先順位3 */
%left  '*' '/'    /* 左結合で優先順位2 */
%right '!'        /* 右結合で優先順位1 */

御意見・御感想・誤殖の指摘などは 青木峰郎 <aamine@loveruby.net> までお願いします。

『Rubyソースコード完全解説』 はインプレスダイレクトで御予約・御購入いただけます (書籍紹介ページへ飛びます)。

Copyright (c) 2002-2004 Minero Aoki, All rights reserved.