第9章速習`yacc`

概要

パーサとスキャナ

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

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

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

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

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

記号列

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

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

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

スキャナはまず文字列を単語に区切り、そしてその記号を割り出す。例えば数値ならNUMBERやDIGIT、「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.cのtabはtableのtabらしい。巨大なテーブルがたくさん定義されているからだ。一度ファイルを覗いてみるといい。

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

▼文法ファイル概形

%{
ヘッダ
%}
%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_stmtやIFやexprや……は全て「記号」である。 exprはexpression（式）、stmtはstatement（文）の略のつもりだ。これはきっと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文の定義が完結したわけではない。exprやstmtなんて記号はスキャナから送られてくるはずがないから、それがどういう並びなのかをちゃんと定義しないといけない。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と規則上「等しい」記号の並び全てが文法として認められる、ということである。例えばまず、stmtはstmtと等しい。あたりまえだ。次に、exprはstmtと等しい。これは規則そのままだ。そして次に、 NUMBERはstmtと等しい。なぜならNUMBERはexprでexprはstmtだからだ。

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

              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される記号列というのはその枠にちゃんとはまっているのである。妙に指定が細かいところとか、わざわざ難解な用語を使うあたり、パーサとお役所はかなり似ている。

終端記号と非終端記号

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

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

もう一つはスキャナからは絶対に来ない記号、例えばif_stmt、expr、 stmtである。こういう記号を非終端記号（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により listはITEMと読み換えることができる。すると今度は規則2からlistはITEM 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 Cをprogramに還元（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

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

スタック		動作
		最初は空
`IF`		`IF`をシフト
`IF E`		`E`をシフト
`IF expr`		`E`→`expr`で還元
`IF expr THEN`		`THEN`をシフト
`IF expr THEN S`		`S`をシフト
`IF expr THEN stmts`		`S`→`stmts`で還元
`IF expr THEN stmts S`		`S`をシフト
`IF expr THEN stmts`		`stmts S`→`stmts`で還元
`IF expr THEN stmts S`		`S`をシフト
`IF expr THEN stmts`		`stmts S`→`stmts`で還元
`IF expr THEN stmts END`		`END`をシフト
`if`		`IF expr THEN stmts END`→`if`で還元
`program`		`if`→`program`で還元
		accept.

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

アクション

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

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

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

記号の値

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

IF    expr   THEN   stmts   S
値    値     値     値     値

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

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一つを選ぶべきかabとCの組み合わせにすべきかわからない。こういうとき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;
}

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

ただし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ソースコード完全解説』はインプレスダイレクトで御予約・御購入いただけます (書籍紹介ページへ飛びます)。

第9章 速習yacc

概要