日記/2009/11/23/yaccの練習

プログラミング言語を作る
勉強を始めたのだけれど、速攻でyaccとlexのところで躓いてしまいました。トークンがスタックにshiftされ(=積まれ)、条件にマッチするとreduce(=設定したイベントが走り一つ上位の非終端子にランクアップ)されるのは良いのだけれど、conflictの所が良く理解できないっす。

というわけで、同書の電卓プログラムをベースに単純なものから試行錯誤でグレードアップしていき、最終的に同書と同じレベルに戻してみるというすごい無駄な事をしてみました。。スミマセン、こういうやり方でないと上手く頭に入ってこないんです・・・。つくづく技術書の読み方というか勉強の仕方が下手くそだと思う今日この頃。

※CentOS 5.2 上の byacc-1.9, flex-2.5.4a で動作確認しています。特に "y.output" ファイルのフォーマットなどはバージョンにより異なる可能性がある為注意して下さい。

• 準備と、足し算引き算しか出来ない電卓の作成（第１世代）
• 第２世代：数字だけ、あるいは3つ以上の足し算・引き算対応版
  • まず「数字だけ」に対応
  • 3つ以上の足し算・引き算に対応
  • YYDEBUGとy.outputを見比べながらshift/reduceの挙動を確認してみる
    • トークンのスタックと、状態のスタック
    • トークンのスタックと、状態のスタック（"1 + 2"入力時)
    • トークンのスタックと、状態のスタック（"1 + 2 + 3"入力時)
• 第２世代：かけ算・割り算対応版（不完全版）
  • とにかく左から順に計算させる
  • かけ算・割り算を優先させてみる（不完全版）
• 第３世代：かけ算・割り算対応の完全版
  • トークンスタック・状態スタック詳解
    • 少し気になったところ
• まとめと感想

準備と、足し算引き算しか出来ない電卓の作成（第１世代）

サポートページからソースを入手して展開します。"calc/mycalc" ディレクトリに入り、"mycalc.y" を "mycalc2.y" にコピー。
そして "mycalc2.y"の構文規則を次のように書き換えます。

...
%type <double_value> expression
%%
line_list
    : line
    | line_list line
    ;
line
    : expression CR
    {
        printf(">>%lf\n", $1);
    }
expression
    : DOUBLE_LITERAL ADD DOUBLE_LITERAL
    {
        printf("reduction (ADD) occurr!!\n");
        printf("[%f ADD %f]\n", $1, $3);
        $$ = $1 + $3;
    }
    | DOUBLE_LITERAL SUB DOUBLE_LITERAL
    {
        printf("reduction (SUB) occurr!!\n");
        printf("[%f SUB %f]\n", $1, $3);
        $$ = $1 - $3;
    }
    ;
%%

mycalc.lの方はそのまま使い回せます。で、コンパイル。

$ yacc -dv mycalc2.y
$ lex mycalc.l
$ gcc -o mycalc2 y.tab.c lex.yy.c

この時点でパニック。「え、lexが字句解析で、yaccが構文解析でしょ？なんで先にyaccを実行して、後にlexを実行するの？」
一般的な説明としては「lexの方でy.tab.hを必要としていて(#includeしてる)、y.tab.hを作るにはyaccを実行しないといけない」からなのですが、そうなると「y.tab.hって何？」となるわけです。で、覗いてみるとこんな感じ。

#ifndef YYERRCODE
#define YYERRCODE 256
#endif
 
#define DOUBLE_LITERAL 257
#define ADD 258
#define SUB 259
#define MUL 260
#define DIV 261
#define CR 262
typedef union {
    int          int_value;
    double       double_value;
} YYSTYPE;
extern YYSTYPE yylval;

うーん、mycalc2.yファイル中で "%token"指定したシンボルのdefine値、あとは%union指定した構造のC言語表現ですが・・・シンボルのdefineとか、何か適当な数値がdefineされてて訳分かりません。
ただしmycalc.lの方では、各トークンの正規表現に対して "return ADD"とか"return DOUBLE_LIETRAL"とかしてて、これがC言語のコード、つまりy.tab.hというのはlex側で「return ほげほげ」するための定義ファイルになるわけです。他にもlex側でunionに値をセットする所もあります。

だったらlexファイルの方で定義して、それをyacc側で読むようにすればいいじゃん・・・とも思いますが、結局 ADD とか SUB とかのトークンは構文定義と一体ですので、一箇所にまとめておいた方がメンテナンスは楽です。であれば、yacc側で生成したのを逆にlex側で取り込んだ方が良い。みたいな理由でこうなったのだろうな・・・と理解しました。本当は違うかも知れませんが。

とまれ、実行時の処理の流れとしては「字句解析→構文解析」なのですが、字句解析の結果をどう構文解析に橋渡しすればよいのか、となりますとやっぱり「字句解析から何を貰えば良いのか」は構文解析側が一番良く分かっているはずです。なので、主従関係は「構文解析（主）→字句解析（従）」となるわけです。y.tab.hというのは構文解析側が「こういう結果が欲しい」と字句解析側に提示する為のインターフェイス、と考えると、自分の場合はすんなりと理解できました。

寄り道しましたが実行してみます。

$ ./mycalc2
1 + 2
reduction (ADD) occurr!!
[1.000000 ADD 2.000000]
>>3.000000
3 - 1
reduction (SUB) occurr!!
[3.000000 SUB 1.000000]
>>2.000000

ここまではちゃんと動いてます。いつ"reduce"されるのかも分かって良いですね。ところが3つ以上を足し算させるとエラーになってしまいます。

1 + 2 + 3
reduction (ADD) occurr!!
[1.000000 ADD 2.000000]
parser error near +
Error ! Error ! Error !

これは当然で、まだそんな構文は定義してません。あと、"123"みたいな数字だけのもNGです。

$ ./mycalc2
123
parser error near

Error ! Error ! Error !

ということで、まずは"123"みたいな只の数字だけのにも対応させてみます。

第２世代：数字だけ、あるいは3つ以上の足し算・引き算対応版

まず「数字だけ」に対応

mycalc2.yのexpressionにパターンを一つ追加します。

...
expression
    : DOUBLE_LITERAL
    | DOUBLE_LITERAL ADD DOUBLE_LITERAL
    {
...

でコンパイル、実行。

$ ./mycalc2
123
>>123.000000

はいOK。

3つ以上の足し算・引き算に対応

これは本にならって、

expression = expression ADD DOUBLE_LITERAL
expression = expression SUB DOUBLE_LITERAL

みたいにすればよさそうです。

expression
    : DOUBLE_LITERAL
    | expression ADD DOUBLE_LITERAL
    {
        printf("reduction (ADD) occurr!!\n");
        printf("[%f ADD %f]\n", $1, $3);
        $$ = $1 + $3;
    }
    | expression SUB DOUBLE_LITERAL
    {
        printf("reduction (SUB) occurr!!\n");
        printf("[%f SUB %f]\n", $1, $3);
        $$ = $1 - $3;
    }
    ;

コンパイルして実行してみます。

$ yacc -dv mycalc2.y
$ gcc -o mycalc2 y.tab.c lex.yy.c
$ ./mycalc2
1 + 2
reduction (ADD) occurr!!
[1.000000 ADD 2.000000]
>>3.000000
1
>>1.000000

ここから3つ以上の足し算引き算をさせてみます。

1 + 2 + 3
reduction (ADD) occurr!!
[1.000000 ADD 2.000000]
reduction (ADD) occurr!!
[3.000000 ADD 3.000000]
>>6.000000
3 - 2 + 1
reduction (SUB) occurr!!
[3.000000 SUB 2.000000]
reduction (ADD) occurr!!
[1.000000 ADD 1.000000]
>>2.000000

OKぽいです。

YYDEBUGとy.outputを見比べながらshift/reduceの挙動を確認してみる

mycalc.yでは、ヘッダー部に

#define YYDEBUG 1

というのが定義されています。しかしこれだけではデバッグメッセージは表示されません。生成されたy.tab.cを"YYDEBUG"でgrepすれば分かりますが、YYDEBUG環境変数が"1"以上に設定されている必要があります。
というわけで、以下のようにするとデバッグメッセージが表示されます(bashの場合)。

$ YYDEBUG=1 ./mycalc2

ここから、説明がもの凄い細かくて冗長になってくるので「大体把握してるからオッケー。」な人は読み飛ばして下さい。

さてデバッグメッセージを元にyaccのshift/reduceの流れを追っていきたいと思います。先ほどからyacc実行時に"-dv"をつけていますが、"-v"オプションが、y.outputファイルでパーサの詳細を人間で読める形に出力してくれます。ということで、y.outputも見つつ追っていきます。
下準備として y.output の構成だけざっくりと見ておきます。
y.output:

   0  $accept : line_list $end

   1  line_list : line
   2            | line_list line

   3  line : expression CR

   4  expression : DOUBLE_LITERAL
   5             | expression ADD DOUBLE_LITERAL
   6             | expression SUB DOUBLE_LITERAL
^L
state 0
        $accept : . line_list $end  (0)

        DOUBLE_LITERAL  shift 1
        .  error

        line_list  goto 2
        expression  goto 3
        line  goto 4


state 1
        expression : DOUBLE_LITERAL .  (4)

        .  reduce 4
...

"^L"までが構文規則そのもののようです。"|"も番号を振って、別ものとして分かるようにしてくれています。
"state 0"以降がパーサ処理の状態遷移を表しているようです。パース処理を行う場合は、次々と字句解析からやってくるトークンに対して、「今はこの状態で、次のトークンがこれだったら、あの処理を行ってあっちの状態に移る」みたいな状態遷移でぐるぐるまわしているようです。読み方ですが、

state 番号
    reduceルール (ルール番号)

    終端子(トークン) shift (shift先のstate番号)
    終端子(トークン) reduce (reduceで使うルール番号)
    . error # 想定外のトークンなのでパースエラーにしたい時
    . reduce (reduceで使うルール番号) # この状態に来た段階でreduceかけたい時

    非終端子 goto (shift先のstate番号)

ポイントとしては以下の2点。

• ルール定義, 字句解析からのトークンに応じたアクション, 非終端子があった時のアクションの順で定義
• "."が、トークンアクションと非終端子アクションの境目

では実際に、まず数字だけを入力してみた場合です。

123

このデバッグメッセージは以下になります。

123
yydebug: state 0, reading 257 (DOUBLE_LITERAL)
yydebug: state 0, shifting to state 1
yydebug: state 1, reducing by rule 4 (expression : DOUBLE_LITERAL)
yydebug: after reduction, shifting from state 0 to state 3
yydebug: state 3, reading 262 (CR)
yydebug: state 3, shifting to state 8
yydebug: state 8, reducing by rule 3 (line : expression CR)
>>123.000000
yydebug: after reduction, shifting from state 0 to state 4
yydebug: state 4, reducing by rule 1 (line_list : line)
yydebug: after reduction, shifting from state 0 to state 2

まず"state 0"で始まり、字句解析から DOUBLE_LITERAL がやってきます。

yydebug: state 0, reading 257 (DOUBLE_LITERAL)

すると・・・

state 0
        $accept : . line_list $end  (0)
                  ↑ "."というのは、「今ここにいるよ」という印みたいです。

        DOUBLE_LITERAL  shift 1
        ↑で、こに引っ掛かります。

というわけで、字句解析が読み込んだ値がスタックに積まれ、状態は"state 1"に遷移します。

yydebug: state 0, shifting to state 1

"state 1"を見てみましょう。

state 1
        expression : DOUBLE_LITERAL .  (4)

        .  reduce 4

デバッグメッセージを見ると・・・

yydebug: state 1, reducing by rule 4 (expression : DOUBLE_LITERAL)

ルール"4"により"reduce"される、と言っています。つまり"expression : DOUBLE_LITERAL"に引っ掛かったのでreduceされます。この時は何もイベントを定義していないので、暗黙の"$$ = $1"が実行されるだけです。

次のデバッグログですが・・・

yydebug: after reduction, shifting from state 0 to state 3

reduceが終わった後、"state 0"から"state 3"へ移動するとあります。先ほどまで "state 1" にいた筈なのに、何時の間に "state 0" になったんだ！？という感じです。ほかにも、なぜ次の状態が "state 3" なのか？何時の間に決められたのか？
何となく、先ほどのreduceで "DOUBLE_LITERAL" が "expression" になり、state 0 の方では

state 0
...
       expression  goto 3

とあるから・・・かなぁ？という雰囲気ではあります。

トークンのスタックと、状態のスタック

結論から先に書くと、yaccはトークンのスタックの他に「状態」もスタックさせています。「状態」のスタックには最初は"state 0"がスタックされていて、一方初期状態ではトークンは勿論空っぽです。

state stack       |-> [state 0]
------------------+--------------
token/value stack |-> (empty)

ではこのスタックを、デバッグメッセージを元に最初から手で操作していきましょう。

123(リターン)
yydebug: state 0, reading 257 (DOUBLE_LITERAL)

→

state stack       |-> [state 0]
------------------+--------------
token/value stack |-> DOUBLE_LITERAL(=123)

と言う風に値が積まれます。すると、"y.output"で書かれているように

state 0
        DOUBLE_LITERAL  shift 1

として"state 1"に遷移します。内部的には、状態スタックの方に"state 1"が積まれます。

yydebug: state 0, shifting to state 1

→

state stack       |-> [state 0], [state 1]
------------------+--------------
token/value stack |-> DOUBLE_LITERAL(=123)

するとここで、"y.output"にあるとおり構文解析のルール4番が適用できます。

state 1
        expression : DOUBLE_LITERAL .  (4)
        .  reduce 4

このデバッグログにあたります。

yydebug: state 1, reducing by rule 4 (expression : DOUBLE_LITERAL)

ここで暗黙の "$$ = $1" が実行されます。すると、"DOUBLE_LITERAL"が"expression"にreduceされます。
さらに、状態スタックがreduceされた要素数分、ポップアップされます。reduceされたのは"DOUBLE_LITERAL"一つ分なので、最後にpushされた1つ分の[state 1] が削られます。

state stack       |-> [state 0]
------------------+--------------
token/value stack |-> expression(=123)

そして現在のステータスは、状態スタックに積まれているlast要素になります。つまり今の状態なら"state 0"になります。
ここで、"y.output"では "state 0" で非終端子がexpressionなら"state 3"に遷移するよう指示されています。

state 0
       ...
       expression  goto 3

これによる状態遷移が、次のデバッグログにあたります。

yydebug: after reduction, shifting from state 0 to state 3

"state 3"ですが、非終端子アクションは未定義です。

state 3
        line : expression . CR  (3)
        expression : expression . ADD DOUBLE_LITERAL  (5)
        expression : expression . SUB DOUBLE_LITERAL  (6)

        ADD  shift 6
        SUB  shift 7
        CR  shift 8
        .  error

よってここでは字句解析からのトークンを待つ事になりますが、既に"CR"(改行)が入力に入っています。

yydebug: state 3, reading 262 (CR)

すると

        CR  shift 8

が反応して、"state 8"に遷移します。

yydebug: state 3, shifting to state 8

この状態のスタックを見ると、次のようになっています。

state stack       |-> [state 0], [state 3], [state 8]
------------------+--------------
token/value stack |-> expression(=123), CR

さて、"state 8"の状態遷移定義を"y.output"で見てみるとトークンアクションも非終端子アクションも未定義で、すぐreduceに入るようになっています。

state 8
        line : expression CR .  (3)

        .  reduce 3

このデバッグログです。

yydebug: state 8, reducing by rule 3 (line : expression CR)

ここはmycalc2.yの

line
    : expression CR
    {
        printf(">>%lf\n", $1);
    }

にあたりますので、値を表示しています。

>>123.000000

reduceアクションが終わりましたが、ここでルール定義をもう一度見てみるとreduceされる要素は2つです。

line : expression CR .  (3)

すると状態スタックも2つ分popされますので、

reduce前：
state stack       |-> [state 0], [state 3], [state 8]
------------------+--------------
token/value stack |-> expression(=123), CR
↓
reduce後：
state stack       |-> [state 0]
------------------+--------------
token/value stack |-> line

となります。これが次のデバッグログで "from state 0" となる理由です。

yydebug: after reduction, shifting from state 0 to state 4

さて、reduce→状態スタックpop完了後の最終状態は "state 0" です。トークンスタックには "line" が載っています。すると、"y.output"中の

state 0
       ...
       line  goto 4

この定義により、"state 4" に遷移します。

state stack       |-> [state 0], [state 4]
------------------+--------------
token/value stack |-> line

さらに "state 4" を見てみると

state 4
        line_list : line .  (1)

        .  reduce 1

としてルール1番、"line_list : line"を使ってreduceせよ、となっています。

yydebug: state 4, reducing by rule 1 (line_list : line)

スタックの動きを見ると、reduceされる要素は1なので、次のように動きます。

reduce前：
state stack       |-> [state 0], [state 4]
------------------+--------------
token/value stack |-> line
↓
reduce後（途中）：
state stack       |-> [state 0]
------------------+--------------
token/value stack |-> line_list

また "state 0" に戻ってくると、今度は次の定義が発動して・・・

state 0
       ...
       line_list  goto 2

"state 2" に遷移します。

yydebug: after reduction, shifting from state 0 to state 2
↓
reduce後：
state stack       |-> [state 0], [state 2]
------------------+--------------
token/value stack |-> line_list

"state 2"の定義を見ると、"line_list"非終端子のアクションは定義されていないので、ここで再び字句解析からのトークン待ちになります。

トークンのスタックと、状態のスタック（"1 + 2"入力時)

ここまでの状態で、"1 + 2(改行)"と入力した時のデバッグログを見てみましょう。

1 + 2

yydebug: state 2, reading 257 (DOUBLE_LITERAL)
yydebug: state 2, shifting to state 1
yydebug: state 1, reducing by rule 4 (expression : DOUBLE_LITERAL)
yydebug: after reduction, shifting from state 2 to state 3
yydebug: state 3, reading 258 (ADD)
yydebug: state 3, shifting to state 6
yydebug: state 6, reading 257 (DOUBLE_LITERAL)
yydebug: state 6, shifting to state 9
yydebug: state 9, reducing by rule 5 (expression : expression ADD DOUBLE_LITERAL)
reduction (ADD) occurr!!
[1.000000 ADD 2.000000]
yydebug: after reduction, shifting from state 2 to state 3
yydebug: state 3, reading 262 (CR)
yydebug: state 3, shifting to state 8
yydebug: state 8, reducing by rule 3 (line : expression CR)
>>3.000000
yydebug: after reduction, shifting from state 2 to state 5
yydebug: state 5, reducing by rule 2 (line_list : line_list line)
yydebug: after reduction, shifting from state 0 to state 2

ざっくりとした単位で動きを見ていきます。

yydebug: state 2, reading 257 (DOUBLE_LITERAL)
yydebug: state 2, shifting to state 1
yydebug: state 1, reducing by rule 4 (expression : DOUBLE_LITERAL)
yydebug: after reduction, shifting from state 2 to state 3

ここまでは先ほどと一緒です。

state stack       |-> [state 0], [state 2]
------------------+--------------
token/value stack |-> line_list, DOUBLE_LITERAL
↓
state stack       |-> [state 0], [state 2], [state 1]
------------------+--------------
token/value stack |-> line_list, DOUBLE_LITERAL

ここでstate 1に定義されているreduceが走り、DOUBLE_LITERALがexpressionになります。reduceされる要素は1ですので、状態スタックからも1つ分popされます。

state stack       |-> [state 0], [state 2]
------------------+--------------
token/value stack |-> line_list, expression

"state 2"では "expression" での状態遷移が "state 3" へ行くよう指示されていますので、以下のスタック状態になります。

state stack       |-> [state 0], [state 2], [state 3]
------------------+--------------
token/value stack |-> line_list, expression

では次のデバッグメッセージです。

yydebug: state 3, reading 258 (ADD)
yydebug: state 3, shifting to state 6
yydebug: state 6, reading 257 (DOUBLE_LITERAL)
yydebug: state 6, shifting to state 9

まず字句解析から ADD トークンがやってきます。

state stack       |-> [state 0], [state 2], [state 3]
------------------+--------------
token/value stack |-> line_list, expression, ADD

ここで"y.output"の "state 3" では

state 3
       ADD  shift 6

となっていますので、"state 6" へ遷移します。

state stack       |-> [state 0], [state 2], [state 3], [state 6]
------------------+--------------
token/value stack |-> line_list, expression(=1), ADD

続けてDOUBLE_LITERALがやってきます。同様に "state 6"の定義に従い、"state 9"へ遷移します。

state stack       |-> [state 0], [state 2], [state 3], [state 6], [state 9]
------------------+--------------
token/value stack |-> line_list, expression(=1), ADD(=+), DOUBLE_LITERAL(=2)

ここで "state 9" の次のルールに従い、reduceされます。

state 9
        expression : expression ADD DOUBLE_LITERAL .  (5)

        .  reduce 5

次のデバッグログに相当します。

yydebug: state 9, reducing by rule 5 (expression : expression ADD DOUBLE_LITERAL)
reduction (ADD) occurr!!
[1.000000 ADD 2.000000]
yydebug: after reduction, shifting from state 2 to state 3

ここでreduceされるトークンは3つですので、状態スタックからも3つ分popされます。

state stack       |-> [state 0], [state 2]
------------------+--------------
token/value stack |-> line_list, expression(3)

後は前のパターン同様、"state 2"でexpressionが値スタックの先頭ですのでそのまま "state 3" に遷移し、改行が来たので "state 8" に遷移、reduceされて"state 2"へ戻ります。

yydebug: state 3, reading 262 (CR)
yydebug: state 3, shifting to state 8
yydebug: state 8, reducing by rule 3 (line : expression CR)
>>3.000000
yydebug: after reduction, shifting from state 2 to state 5

state stack       |-> [state 0], [state 2], [state 3]
------------------+--------------
token/value stack |-> line_list, expression(3)
↓("CR"入力)
state stack       |-> [state 0], [state 2], [state 3]
------------------+--------------
token/value stack |-> line_list, expression(3), CR
↓("state 8"へ遷移)
state stack       |-> [state 0], [state 2], [state 3], [state 8]
------------------+--------------
token/value stack |-> line_list, expression(3), CR
↓(reduce: "line : expression CR")
state stack       |-> [state 0], [state 2]
------------------+--------------
token/value stack |-> line_list, line

前のパターンと異なるのは、ここで "state 2" に戻ってきたところで "line_list: line_list line" のreduceルールが適用され、"state 5" に遷移する点です。

yydebug: state 5, reducing by rule 2 (line_list : line_list line)

スタックの動き：

state stack       |-> [state 0], [state 2]
------------------+--------------
token/value stack |-> line_list, line
↓
state stack       |-> [state 0]
------------------+--------------
token/value stack |-> line_list

"state 0"で"line_list"非終端子の場合は、結局 "state 2" へ遷移します。

yydebug: after reduction, shifting from state 0 to state 2

スタック：

state stack       |-> [state 0], [state 2]
------------------+--------------
token/value stack |-> line_list

"1 + 2(改行)" が入力される直前と同じ状態になりました。

トークンのスタックと、状態のスタック（"1 + 2 + 3"入力時)

ここまでの状態で、いよいよ"1 + 2 + 3(改行)"と入力した時のデバッグログを見てみましょう。

1 + 2 + 3

yydebug: state 2, reading 257 (DOUBLE_LITERAL)
yydebug: state 2, shifting to state 1
yydebug: state 1, reducing by rule 4 (expression : DOUBLE_LITERAL)
yydebug: after reduction, shifting from state 2 to state 3
yydebug: state 3, reading 258 (ADD)
yydebug: state 3, shifting to state 6
yydebug: state 6, reading 257 (DOUBLE_LITERAL)
yydebug: state 6, shifting to state 9
yydebug: state 9, reducing by rule 5 (expression : expression ADD DOUBLE_LITERAL)
reduction (ADD) occurr!!
[1.000000 ADD 2.000000]
yydebug: after reduction, shifting from state 2 to state 3
yydebug: state 3, reading 258 (ADD)
yydebug: state 3, shifting to state 6
yydebug: state 6, reading 257 (DOUBLE_LITERAL)
yydebug: state 6, shifting to state 9
yydebug: state 9, reducing by rule 5 (expression : expression ADD DOUBLE_LITERAL)
reduction (ADD) occurr!!
[3.000000 ADD 3.000000]
yydebug: after reduction, shifting from state 2 to state 3
yydebug: state 3, reading 262 (CR)
yydebug: state 3, shifting to state 8
yydebug: state 8, reducing by rule 3 (line : expression CR)
>>6.000000
yydebug: after reduction, shifting from state 2 to state 5
yydebug: state 5, reducing by rule 2 (line_list : line_list line)
yydebug: after reduction, shifting from state 0 to state 2

長いので、ざっくりとした単位でデバッグログとスタックの状態変化を追います。

yydebug: state 2, reading 257 (DOUBLE_LITERAL)
...
yydebug: state 9, reducing by rule 5 (expression : expression ADD DOUBLE_LITERAL)
reduction (ADD) occurr!!
[1.000000 ADD 2.000000]
yydebug: after reduction, shifting from state 2 to state 3

ここまでは先ほどまでのパターンと同じです。スタックは次のようになっています。

state stack       |-> [state 0], [state 2]
------------------+--------------
token/value stack |-> line_list, expression(3)

ここで続けて ADD, DOUBLE_LITERAL と入ってきますが、あとはもう一度同じパターンになります。

ここで、続いて ADD が入力されます。

yydebug: state 3, reading 258 (ADD)
yydebug: state 3, shifting to state 6

スタックの動き：

state stack       |-> [state 0], [state 2]
------------------+--------------
token/value stack |-> line_list, expression(3), ADD
↓
state stack       |-> [state 0], [state 2], [state 6]
------------------+--------------
token/value stack |-> line_list, expression(3), ADD

さらに続けて DOUBLE_LITERAL が入力されます。

yydebug: state 6, reading 257 (DOUBLE_LITERAL)
yydebug: state 6, shifting to state 9

スタックの動き：

state stack       |-> [state 0], [state 2], [state 6]
------------------+--------------
token/value stack |-> line_list, expression(3), ADD, DOUBLE_LITERAL(3)
↓
state stack       |-> [state 0], [state 2], [state 6], [state 9]
------------------+--------------
token/value stack |-> line_list, expression(3), ADD, DOUBLE_LITERAL(3)

ここでまたreduceです。

yydebug: state 9, reducing by rule 5 (expression : expression ADD DOUBLE_LITERAL)
reduction (ADD) occurr!!
[3.000000 ADD 3.000000]
yydebug: after reduction, shifting from state 2 to state 3
state stack       |-> [state 0], [state 2], [state 6], [state 9]
------------------+--------------
token/value stack |-> line_list, expression(3), ADD, DOUBLE_LITERAL(3)
↓
state stack       |-> [state 0], [state 2], [state 3]
------------------+--------------
token/value stack |-> line_list, expression(6)

以降はこれまでのパターン同様ですので、省略します。

第２世代：かけ算・割り算対応版（不完全版）

とりあえずかけ算・割り算を行わせてみます。

とにかく左から順に計算させる

とりあえずmycalc2.yのexpressionの構文を次のようにすれば左から右へ計算していきます。

expression
    : DOUBLE_LITERAL
    | expression ADD DOUBLE_LITERAL
    {
        printf("reduction (ADD) occurr!!\n");
        printf("[%f ADD %f]\n", $1, $3);
        $$ = $1 + $3;
    }
    | expression SUB DOUBLE_LITERAL
    {
        printf("reduction (SUB) occurr!!\n");
        printf("[%f SUB %f]\n", $1, $3);
        $$ = $1 - $3;
    }
    | expression MUL DOUBLE_LITERAL
    {
        printf("reduction (MUL) occurr!!\n");
        printf("[%f MUL %f]\n", $1, $3);
        $$ = $1 * $3;
    }
    | expression DIV DOUBLE_LITERAL
    {
        printf("reduction (DIV) occurr!!\n");
        printf("[%f DIV %f]\n", $1, $3);
        $$ = $1 / $3;
    }
    ;

$ ./mycalc2
1 + 2 * 3 - 3 / 2
reduction (ADD) occurr!!
[1.000000 ADD 2.000000] # 1 + 2 = 3
reduction (MUL) occurr!!
[3.000000 MUL 3.000000] # 3 * 3 = 9
reduction (SUB) occurr!!
[9.000000 SUB 3.000000] # 9 - 3 = 6
reduction (DIV) occurr!!
[6.000000 DIV 2.000000] # 6 / 2 = 3
>>3.000000

良さそうです。

かけ算・割り算を優先させてみる（不完全版）

続けて、かけ算・割り算を優先させてみます。とりあえず、MUL, DIV処理だけを抜き出してみます。

expression
    : DOUBLE_LITERAL
    | expression ADD DOUBLE_LITERAL
    {
        printf("reduction (ADD) occurr!!\n");
        printf("[%f ADD %f]\n", $1, $3);
        $$ = $1 + $3;
    }
    | expression SUB DOUBLE_LITERAL
    {
        printf("reduction (SUB) occurr!!\n");
        printf("[%f SUB %f]\n", $1, $3);
        $$ = $1 - $3;
    }
    ;
expression_muldiv
    : DOUBLE_LITERAL
    | expression_muldiv MUL DOUBLE_LITERAL
    {
        printf("reduction (MUL) occurr!!\n");
        printf("[%f MUL %f]\n", $1, $3);
        $$ = $1 * $3;
    }
    | expression_muldiv DIV DOUBLE_LITERAL
    {
        printf("reduction (DIV) occurr!!\n");
        printf("[%f DIV %f]\n", $1, $3);
        $$ = $1 / $3;
    }
    ;

ところが、"expression_muldivは型が指定されてない"旨のエラーが出てしまいます。

$ yacc -dv mycalc2.y
yacc: e - line 44 of "mycalc2.y", $1 (expression_muldiv) is untyped

というわけで、"%type"にexpression_muldivを追加します。

%type <double_value> expression
↓
%type <double_value> expression expression_muldiv

すると今度は、"3つのルールが使われないままですよ"となります。確かにexpression_muldivは何処にも組み込んでなかったです。

$ yacc -dv mycalc2.y
yacc: 3 rules never reduced

というわけで、expressionに組み込んでみます。どうせexpression_muldiv : DOUBLE_LITERALを設定してますので、

expression
   : DOUBLE_LITERAL

これを置き換えちゃいましょう。

expression
   : expression_muldiv

$ yacc -dv mycalc2.y
$ gcc -o mycalc2 y.tab.c lex.yy.c
$ ./mycalc2
2 * 3 + 2
reduction (MUL) occurr!!
[2.000000 MUL 3.000000]
reduction (ADD) occurr!!
[6.000000 ADD 2.000000]
>>8.000000
4 / 2 -1
reduction (DIV) occurr!!
[4.000000 DIV 2.000000]
reduction (SUB) occurr!!
[2.000000 SUB 1.000000]
>>1.000000
1 + 2 * 3
reduction (ADD) occurr!!
[1.000000 ADD 2.000000]
parser error near *
Error ! Error ! Error !

このように、かけ算・割り算を "+"/"-" の次に持ってくると、未定義の構文の為エラーになります。

ここまでくれば、本に載っている電卓プログラムまであと一歩です。

第３世代：かけ算・割り算対応の完全版

あとはexpression中のDOUBLE_LITERALを、expression_muldivに返ればOKです。

expression
    : expression_muldiv
    | expression ADD expression_muldiv
    {
        printf("reduction (ADD) occurr!!\n");
        printf("[%f ADD %f]\n", $1, $3);
        $$ = $1 + $3;
    }
    | expression SUB expression_muldiv
    {
        printf("reduction (SUB) occurr!!\n");
        printf("[%f SUB %f]\n", $1, $3);
        $$ = $1 - $3;
    }
    ;

$ yacc -dv mycalc2.y
$ gcc -o mycalc2 y.tab.c lex.yy.c
$ ./mycalc2
2 * 3 + 2
reduction (MUL) occurr!!
[2.000000 MUL 3.000000]
reduction (ADD) occurr!!
[6.000000 ADD 2.000000]
>>8.000000
1 + 2 * 3
reduction (MUL) occurr!!
[2.000000 MUL 3.000000]
reduction (ADD) occurr!!
[1.000000 ADD 6.000000]
>>7.000000

この時点で、足し算・引き算・かけ算・割り算の電卓機能としては本と同じものになりました。expression_muldivをtermに置換して、あとterm中のDOUBLE_LITERALをprimary_expressionにまとめれば本の "mycalc.y" と同じになります。

トークンスタック・状態スタック詳解

では最後に優先順位付けされた時のスタック挙動を確認してみます。まずデバッグログの全貌：

$ YYDEBUG=1 ./mycalc2
1 + 2 * 3 + 4
yydebug: state 0, reading 257 (DOUBLE_LITERAL)
yydebug: state 0, shifting to state 1
yydebug: state 1, reducing by rule 7 (expression_muldiv : DOUBLE_LITERAL)
yydebug: after reduction, shifting from state 0 to state 4
yydebug: state 4, reading 258 (ADD)
yydebug: state 4, reducing by rule 4 (expression : expression_muldiv)
yydebug: after reduction, shifting from state 0 to state 3
yydebug: state 3, shifting to state 7
yydebug: state 7, reading 257 (DOUBLE_LITERAL)
yydebug: state 7, shifting to state 1
yydebug: state 1, reducing by rule 7 (expression_muldiv : DOUBLE_LITERAL)
yydebug: after reduction, shifting from state 7 to state 12
yydebug: state 12, reading 260 (MUL)
yydebug: state 12, shifting to state 10
yydebug: state 10, reading 257 (DOUBLE_LITERAL)
yydebug: state 10, shifting to state 14
yydebug: state 14, reducing by rule 8 (expression_muldiv : expression_muldiv MUL DOUBLE_LITERAL)
reduction (MUL) occurr!!
[2.000000 MUL 3.000000]
yydebug: after reduction, shifting from state 7 to state 12
yydebug: state 12, reading 258 (ADD)
yydebug: state 12, reducing by rule 5 (expression : expression ADD expression_muldiv)
reduction (ADD) occurr!!
[1.000000 ADD 6.000000]
yydebug: after reduction, shifting from state 0 to state 3
yydebug: state 3, shifting to state 7
yydebug: state 7, reading 257 (DOUBLE_LITERAL)
yydebug: state 7, shifting to state 1
yydebug: state 1, reducing by rule 7 (expression_muldiv : DOUBLE_LITERAL)
yydebug: after reduction, shifting from state 7 to state 12
yydebug: state 12, reading 262 (CR)
yydebug: state 12, reducing by rule 5 (expression : expression ADD expression_muldiv)
reduction (ADD) occurr!!
[7.000000 ADD 4.000000]
yydebug: after reduction, shifting from state 0 to state 3
yydebug: state 3, shifting to state 9
yydebug: state 9, reducing by rule 3 (line : expression CR)
>>11.000000
yydebug: after reduction, shifting from state 0 to state 5
yydebug: state 5, reducing by rule 1 (line_list : line)
yydebug: after reduction, shifting from state 0 to state 2

順に追っていきます。"y.output"中の定義については、必要最低記載します。

yydebug: state 0, reading 257 (DOUBLE_LITERAL)
yydebug: state 0, shifting to state 1

↓

state stack       |-> [state 0], [state 1]
------------------+--------------
token/value stack |-> DOUBLE_LITERAL

yydebug: state 1, reducing by rule 7 (expression_muldiv : DOUBLE_LITERAL)
yydebug: after reduction, shifting from state 0 to state 4

↓ reduce発生, "state 0" with expression_muldiv は "goto 4"と定義。

state stack       |-> [state 0], [state 4]
------------------+--------------
token/value stack |-> expression_muldiv(=1)

yydebug: state 4, reading 258 (ADD)

↓

state stack       |-> [state 0], [state 4]
------------------+--------------
token/value stack |-> expression_muldiv(=1), ADD

yydebug: state 4, reducing by rule 4 (expression : expression_muldiv)

↓ reduce発生

state stack       |-> [state 0]
------------------+--------------
token/value stack |-> expression(=1), ADD

↓

yydebug: after reduction, shifting from state 0 to state 3
state stack       |-> [state 0], [state 3]
------------------+--------------
token/value stack |-> expression(=1), ADD

↓さらに"state 3" で ADD だと "state 7" へ遷移と定義。

yydebug: state 3, shifting to state 7

↓

state stack       |-> [state 0], [state 3], [state 7]
------------------+--------------
token/value stack |-> expression(=1), ADD

yydebug: state 7, reading 257 (DOUBLE_LITERAL)
yydebug: state 7, shifting to state 1

↓

state stack       |-> [state 0], [state 3], [state 7], [state 1]
------------------+--------------
token/value stack |-> expression(=1), ADD, DOUBLE_LITERAL(=2)

↓

yydebug: state 1, reducing by rule 7 (expression_muldiv : DOUBLE_LITERAL)

↓

state stack       |-> [state 0], [state 3], [state 7]
------------------+--------------
token/value stack |-> expression(=1), ADD, expression_muldiv(=2)

↓

yydebug: after reduction, shifting from state 7 to state 12

↓

state stack       |-> [state 0], [state 3], [state 7], [state 12]
------------------+--------------
token/value stack |-> expression(=1), ADD, expression_muldiv(=2)

↓

yydebug: state 12, reading 260 (MUL)

↓

state stack       |-> [state 0], [state 3], [state 7], [state 12]
------------------+--------------
token/value stack |-> expression(=1), ADD, expression_muldiv(=2), MUL

↓

yydebug: state 12, shifting to state 10

↓

state stack       |-> [state 0], [state 3], [state 7], [state 12], [state 10]
------------------+--------------
token/value stack |-> expression(=1), ADD, expression_muldiv(=2), MUL

↓

yydebug: state 10, reading 257 (DOUBLE_LITERAL)
yydebug: state 10, shifting to state 14

↓

state stack       |-> [state 0], [state 3], [state 7], [state 12], [state 10], [state 14]
------------------+--------------
token/value stack |-> expression(=1), ADD, expression_muldiv(=2), MUL, DOUBLE_LITERAL(3)

↓

yydebug: state 14, reducing by rule 8 (expression_muldiv : expression_muldiv MUL DOUBLE_LITERAL)
reduction (MUL) occurr!!
[2.000000 MUL 3.000000]

↓reduce, ３つ分状態スタックからpop

state stack       |-> [state 0], [state 3], [state 7]
------------------+--------------
token/value stack |-> expression(=1), ADD, expression_muldiv(=6)

↓

yydebug: after reduction, shifting from state 7 to state 12

↓

state stack       |-> [state 0], [state 3], [state 7], [state 12]
------------------+--------------
token/value stack |-> expression(=1), ADD, expression_muldiv(=6)

↓

yydebug: state 12, reading 258 (ADD)

↓

state stack       |-> [state 0], [state 3], [state 7], [state 12]
------------------+--------------
token/value stack |-> expression(=1), ADD, expression_muldiv(=6), ADD

↓
yydebug: state 12, reducing by rule 5 (expression : expression ADD expression_muldiv)
reduction (ADD) occurr!!
[1.000000 ADD 6.000000]
↓

state stack       |-> [state 0]
------------------+--------------
token/value stack |-> expression(=7), ADD

↓

yydebug: after reduction, shifting from state 0 to state 3

↓

state stack       |-> [state 0], [state 3]
------------------+--------------
token/value stack |-> expression(=7), ADD

↓

yydebug: state 3, shifting to state 7

↓

state stack       |-> [state 0], [state 3], [state 7]
------------------+--------------
token/value stack |-> expression(=7), ADD

↓

yydebug: state 7, reading 257 (DOUBLE_LITERAL)
yydebug: state 7, shifting to state 1

↓

state stack       |-> [state 0], [state 3], [state 7], [state 1]
------------------+--------------
token/value stack |-> expression(=7), ADD, DOUBE_LITERAL(=4)

↓

yydebug: state 1, reducing by rule 7 (expression_muldiv : DOUBLE_LITERAL)

↓

state stack       |-> [state 0], [state 3], [state 7]
------------------+--------------
token/value stack |-> expression(=7), ADD, expression_muldiv(=4)

↓

yydebug: after reduction, shifting from state 7 to state 12

↓

state stack       |-> [state 0], [state 3], [state 7], [state 12]
------------------+--------------
token/value stack |-> expression(=7), ADD, expression_muldiv(=4)

↓

yydebug: state 12, reading 262 (CR)

↓

state stack       |-> [state 0], [state 3], [state 7], [state 12]
------------------+--------------
token/value stack |-> expression(=7), ADD, expression_muldiv(=4), CR

↓

yydebug: state 12, reducing by rule 5 (expression : expression ADD expression_muldiv)
reduction (ADD) occurr!!
[7.000000 ADD 4.000000]

↓

state stack       |-> [state 0]
------------------+--------------
token/value stack |-> expression(=11), CR

↓

yydebug: after reduction, shifting from state 0 to state 3

↓

state stack       |-> [state 0], [state 3]
------------------+--------------
token/value stack |-> expression(=11), CR

↓

yydebug: state 3, shifting to state 9

↓

state stack       |-> [state 0], [state 3], [state 9]
------------------+--------------
token/value stack |-> expression(=11), CR

↓

yydebug: state 9, reducing by rule 3 (line : expression CR)
>>11.000000

↓

state stack       |-> [state 0]
------------------+--------------
token/value stack |-> line

↓

yydebug: after reduction, shifting from state 0 to state 5

↓

state stack       |-> [state 0], [state 5]
------------------+--------------
token/value stack |-> line

↓

yydebug: state 5, reducing by rule 1 (line_list : line)

↓

state stack       |-> [state 0]
------------------+--------------
token/value stack |-> line_list

↓

yydebug: after reduction, shifting from state 0 to state 2

↓

state stack       |-> [state 0], [state 2]
------------------+--------------
token/value stack |-> line_list

少し気になったところ

yydebug: state 4, reducing by rule 4 (expression : expression_muldiv)
yydebug: after reduction, shifting from state 0 to state 3
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
yydebug: state 3, shifting to state 7
...
yydebug: state 12, reducing by rule 5 (expression : expression ADD expression_muldiv)
reduction (ADD) occurr!!
[1.000000 ADD 6.000000]
yydebug: after reduction, shifting from state 0 to state 3
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
yydebug: state 3, shifting to state 7
...
yydebug: state 12, reducing by rule 5 (expression : expression ADD expression_muldiv)
reduction (ADD) occurr!!
[7.000000 ADD 4.000000]
yydebug: after reduction, shifting from state 0 to state 3
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
yydebug: state 3, shifting to state 9
...

この３箇所、reduceして状態遷移した後に、さらにもう一度状態遷移している。このパターンは初めてみた。
三つ目のスタック挙動を見てみる。

state stack       |-> [state 0], [state 3], [state 7], [state 12]
------------------+--------------
token/value stack |-> expression(=7), ADD, expression_muldiv(=4), CR

↓

yydebug: state 12, reducing by rule 5 (expression : expression ADD expression_muldiv)
reduction (ADD) occurr!!
[7.000000 ADD 4.000000]

↓

state stack       |-> [state 0]
------------------+--------------
token/value stack |-> expression(=11), CR

ここまでは特に気にならないのだけれど、次：

yydebug: after reduction, shifting from state 0 to state 3

↓

state stack       |-> [state 0], [state 3]
------------------+--------------
token/value stack |-> expression(=11), CR

これが分からない・・・。"state 0" で "state 3"に遷移する定義は、

state 0
       ...
       expression  goto 3

これだけなのだけど、今値のスタックに積まれている末尾要素は "CR" なのだが・・・。
それとも、CRは終端子なので無視して、次が非終端子の"expression"だから引っ掛かったのだろうか。

まとめと感想

YYDEBUG有効化の方法、およびYYDEBUGによるデバッグ出力と、yacc内部の値・状態のスタック挙動を突き合わせた事で、yacc構文解析の挙動や仕組みを理解する事が出来た。

実際は y.tab.c に生成されたコードまで一通り目を通しているが、書き出すと長くなるので省略した。

感想としては、状態までスタックに保存されていて、しかもreduceされるトークンの数に合わせて状態スタックからもpopされる事に気づくまでが大変だった。