5. Bison構文解析器のアルゴリズム

Bison構文解析器は、トークンを読むと、トークンの意味値とともにスタックに積みます。 このスタックを構文解析器スタック（parser stack）と呼びます。 トークンをスタックに積むことを、伝統的に シフト（shifting）と呼びます。

たとえば、中間記法電卓が、`1 + 5 *'をすでに読んでいて、 `3'を受け取ったと仮定します。 スタックには4個の要素があり、トークンそれぞれがシフトされています。

しかし、スタックに常に読み込まれたトークンそれぞれに対する 要素があるわけではありません。 最後のn個のトークンとグループが文法規則に当てはまる場合には、 それらは規則に従って組み合わされます。 これを、還元（reduction）と呼びます。 スタックにあったトークンとグループは、 規則の結果、つまり左側にある記号である、1個のグループに置き換えられます。 規則のアクションの実行は、結果のグループの意味値を計算するので、 還元の手順の1つです。

たとえば、中間記法電卓の構文解析器スタックの内容は次のようになります。

1 + 5 * 3

そして、入力された次のトークンが改行符号ならば、 次の規則に従って、最後の3個の要素が15に還元されます。

expr: expr '*' expr;

そして、スタックは3個の要素を持ちます。

1 + 15

この時点で、別の還元が可能になり、1個の値16を得ます。 そして、改行符号がシフトされます。

構文解析器は、シフトと還元によって、入力全体を 文法の開始記号である1個のグループに還元しようとします （see 節 Languages and Context-Free Grammars）。

この種類の構文解析器は、ボトムアップ構文解析器として知られています。

5.1 先読みトークン

Bison構文解析器は、必ずしも文法規則に適合する最後のn個のトークン またはグループが見つかるとすぐに還元を行うわけではありません。 そのような単純な方法は、多くの言語の処理に適さないからです。 その代わりに、還元が可能な場合に、構文解析器は次のトークンを 「先読み」し、次に何をするべきかを決定します。

トークンが読まれると、それはすぐにシフトされるのではなく、 まず、先読みトークン（look-ahead token）になり、 スタックには置かれません。 先読みトークンを残したまま、構文解析器が、スタック上のトークンまたは グループに対して1個以上の還元を実行します。 それ以上の還元が起こりえない場合に、 先読みトークンはスタックにシフトされます。 これは、すべての可能な還元が実行されたことを意味しません。 先読みトークンのトークン型に応じて、 いくつかの規則は適用を遅らされているかもしれません。

先読みが必要な簡単な例を示します。 下記の3個の規則は、2項加算演算子、単項階乗演算子（`!'）、 グループのためのかっこを含みます。

expr:     term '+' expr
        | term
        ;

term:     '(' expr ')'
        | term '!'
        | NUMBER
        ;

トークン`1 + 2'が読み込まれてシフトされているときに、 何が起きるでしょうか。もし、続くトークンが`)'ならば、 最初の3個のトークンはexprの形式に還元される必要があります。 これが、唯一有効な道です。 なぜならば、`)'をシフトして、term ')'という記号列も 生成可能ですが、どの規則もそのような記号列を許していないからです。

もし、続くトークンが`!'ならば、それはただちにシフトされる必要があり、 `2 !'からtermが還元されます。 そうではなく、構文解析器がシフトの前に還元していれば、 `1 + 2'がexprに還元されます。 しかし、そのような還元をしようとするとexpr '!'という記号列を スタックに生成しようとするので、`!'をシフトするのは不可能です。 そのような記号列は許されません。

現在の先読みトークンは、変数yycharに記憶されています See 節 Special Features for Use in Actions。

5.2 シフト還元衝突

次の2個の規則で定められる、"if-then"と"if-then-else"文を持つ 言語の構文解析について考えます。

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

ここで、IF、THEN、ELSEは、 キーワードトークンを表す終端記号であると仮定します。

ELSEトークンが読まれて先読みトークンになったときに、 入力が正しいと仮定して、スタックの内容はちょうど 最初の規則で還元される右辺になっています。 しかし、いずれ起こるはずの第2の規則の還元のために、 ELSEトークンをシフトすることも有効です。

この、シフトと還元の両方が有効な場合を、 シフト還元衝突（shift/reduce conflict）と呼びます。 Bisonは、演算子優先規則宣言で特に指定されていないかぎり、 シフトを選ぶことで衝突を解決するように設計されています。 この理由を理解するために、別の選択肢と比較してみましょう。

構文解析器はELSEのシフトを選ぶので、その結果、 else節はもっとも内側のif文に対応し、次の2つの入力は等価になります。

if x then if y then win (); else lose;

if x then do; if y then win (); else lose; end;

しかし、字句解析器がシフトでなく還元を選ぶと、その結果、 else節がもっとも外側のif文に対応し、次の2つの入力は等価になります。

if x then if y then win (); else lose;

if x then do; if y then win (); end; else lose;

文法があいまいに書かれているために、衝突が起きます。 つまり、入れ子になったif文について、どちらの構文解析結果も正当なのです。 確立された習慣では、else節をもっとも内側のif文に対応させて、 あいまいさを解決しています。 これが、Bisonが還元よりもシフトを選ぶ理由です （理想的には、あいまいでない文法を書くべきですが、この場合には困難です）。 この問題は、Algol 60の仕様の中に現れたのが最初で、 「ぶらさがりelse（dangling else）」問題と呼ばれています。

予測可能で正当なシフト還元衝突について、Bisonが警告を表示しないように、 %expect n宣言を使えます。 すると、ちょうどn個のシフト還元衝突があるかぎり、 警告は表示されません。 See 節 Suppressing Conflict Warnings。

上記のif_stmtの定義は、衝突をわざと発生させるために書きましたが、 追加の規則がなければ実際には衝突が起きません。 次に、実際に衝突を含む完全なBison入力ファイルの例を示します。

%token IF THEN ELSE variable
%%
stmt:     expr
        | if_stmt
        ;

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

expr:     variable
        ;

5.3 演算子の優先順位

シフト還元衝突が起きる別の可能性は、算術式の中にあります。 この場合には、シフトの選択が望ましい解決策であるとは限りません。 どのような場合にシフトしてどのような場合に還元するべきか指定するために、 演算子の優先順位についてのBison宣言を使えます。

5.3.1 優先順位が必要な場合
5.3.2 演算子の優先順位の指定		Bison文法で優先順位を指定する方法.
5.3.3 優先順位の例
5.3.4 優先順位が働く仕組み

5.3.1 優先順位が必要な場合

次のあいまいな文法の一部を見てください。 入力`1 - 2 * 3'が2通りに構文解析されうるので、 この文法はあいまいです。

expr:     expr '-' expr
        | expr '*' expr
        | expr '<' expr
        | '(' expr ')'
        ...
        ;

構文解析器が、`1'、`-'、`2'というトークンを 読み込んだと仮定します。構文解析器は、減算演算子の規則に従って、 これらのトークンを還元するべきでしょうか。 それは、次のトークンに依存します。 もちろん、次のトークンが`)'ならば、還元する必要があります。 なぜならば、もしシフトすると、`- 2 )'またはそれで始まる 記号列を還元する必要が生じ、そのような規則はないからです。 しかし、次のトークンが`*'または`<'ならば、 シフトと還元のどちらも可能です。 どちらを選んでも構文解析を完了できますが、解析の結果は異なります。

Bison字句解析器がどちらの処理をすべきか決めるために、 構文解析の結果を考慮する必要があります。 もし、次の演算子トークンopがシフトされるならば、 還元して差を求める可能性を許すために、 opは最初に還元される必要があります。 その結果は、`1 - (2 op 3)'となります。 逆に、opをシフトする前に減算を還元するならば、 結果は`(1 - 2) op 3'となります。 明らかに、シフトと還元のどちらが起こるべきかの選択は、 演算子`-'とopの相対的な優先順位に依存します。 `*'は先にシフトされるべきですが、`<'は違います。

`1 - 2 - 5'のような例ではどうなるでしょうか。 `(1 - 2) - 5'と処理するべきでしょうか。 それとも、`1 - (2 - 5)'と処理するべきでしょうか。 ほとんどの演算子については前者が適し、これを、 左結合性（left association）と呼びます。 後者の右結合性（right association）は、代入演算子に適します。 左結合性か右結合性かの判断は、スタックに`1 - 2'が含まれ、 先読みトークンが`-'である場合の、シフトか還元かの選択です。 シフトを選ぶと、右結合的になります。

5.3.2 演算子の優先順位の指定

演算子優先順位宣言%leftと%rightによって、 演算子の優先順位と結合規則を指定できます。 どちらの宣言も、優先順位と結合規則を指定したい演算子である、 トークンの並びからなります。 %left宣言はすべての演算子を左結合的に、 %right宣言はすべての演算子を右結合的に宣言します。 第3の選択肢は%nonassoc宣言で、これで宣言した演算子が 続けて2回以上現れると、構文解析器が文法エラーを指摘します。

異なる演算子の相対的な優先順位は、それらが宣言される順序で決まります。 文法ファイルの中の最初の%left宣言または%right宣言で 宣言された演算子が、もっとも低い優先順位を持ちます。 後から宣言される演算子ほど、高い優先順位を持ちます。

5.3.3 優先順位の例

先ほどの例では、次のように宣言するべきでした。

%left '<'
%left '-'
%left '*'

もっと複雑な例では、より多くの演算子を使うだけでなく、 同じ優先順位を持つ演算子があります。 次の例では、'+'演算子と'-'演算子が同じ優先順位を持ちます。

%left '<' '>' '=' NE LE GE
%left '+' '-'
%left '*' '/'

（この例で、NEは「等しくない」演算子を表し、他も同様です。 これらのトークンは、2文字以上からなるので、 1文字リテラルではなく名前で表されると仮定しています）

5.3.4 優先順位が働く仕組み

優先順位宣言の最初の働きは、宣言された終端記号への優先順位の割り当てです。 第2の働きは、規則に含まれる最後の終端記号が優先順位を示すように、 ある規則に優先順位を割り当てることです （規則に対して、明示的に優先順位を指定することも可能です。 See 節 Context-Dependent Precedence）。

最後に、衝突の解決は、問題になっている規則の優先順位と、 先読みトークンの優先順位の比較によって行われます。 もし、先読みトークンの優先順位が高ければ、還元されます。 もし、規則の優先順位が高ければ、シフトされます。 もし、優先順位が同じならば、その優先順位での結合規則によって決定されます。 `-v'オプションを付けてBisonを実行し、冗長な出力ファイルを得ると、 どのように衝突が解決されているかがわかります （see 節 Invoking Bison）。

すべての規則とトークンが優先順位を持っているとはかぎりません。 もし、規則と先読みトークンが優先順位を持っていなければ、 シフトが行われます。

5.4 文脈依存優先順位

しばしば、演算子の優先順位は文脈に依存します。 これは、最初は奇異に感じるかもしれませんが、 実際によく起きていることなのです。 たとえば、通常、減算演算子（`-'）は、 単項演算子としては非常に高い優先順位を持ちますが、 2項演算子としては乗除算よりも低い優先順位を持ちます。

Bisonの優先順位宣言、%left、%right、%nonassocは、 あるトークンに対して1回のみ使え、この方法では、 トークンは唯一の優先順位を宣言されます。 文脈に依存する優先順位のためには、別の方法、すなわち、 %precで規則を修飾する方法が必要になります。

%prec修飾子は、ある規則で使われるべき終端記号の優先順位を指定して、 その規則の優先順位を宣言します。 その記号がその規則の中以外に現れる必要はありません。 修飾子の記法は、次のようになっています。

%prec terminal-symbol

これは、規則の構成要素の後に書かれます。 これによって、通常の方法で導かれる優先順位に代わって、 terminal-symbolの優先順位を規則に割り当てます。 規則の優先順位が変更されて、その規則が関係している衝突の解決に影響します （see 節 Operator Precedence）。

%precがどのように単項負記号を解決するかを示します。 まず、UMINUSという名前の終端記号に対する優先順位を宣言します。 この型のトークンは存在しませんが、 この記号が優先順位を表現するために使われます。

...
%left '+' '-'
%left '*'
%left UMINUS

さて、UNIMISの優先順位を、規則の中で使えます。

exp:    ...
        | exp '-' exp
        ...
        | '-' exp %prec UMINUS

5.5 構文解析器の状態

関数yyparseは、有限状態機械を使って実装されています。 構文解析器のスタックに積まれる値は、トークン型番号だけでなく、 スタックの先頭またはその近くにある終端記号と非終端記号の列を 表現しています。現在の状態は、次にすべきことに関連する、 今までの入力の情報全体の集まりです。

先読みトークンが読まれるたびに、先読みトークンの型と 現在の構文解析器の状態によって、表が引かれます。 この表の項目には、「先読みトークンをシフトしなさい」というような ことが書かれています。この場合、その表の項目は、 先読みトークンが構文解析器スタックのトップに置かれた、 構文解析器の新しい状態をも示しています。 「n番目の規則を使って還元しなさい」というような項目もあります。 これによって、決められた数のトークンまたはグループがスタックのトップから 取り除かれ、1個のグループがスタックのトップに置かれます。 言い換えると、その数の状態がスタックからポップされ、 新しい1個の状態がスタックにプッシュされます。

これには、1つの例外があります。 先読みトークンが現在の状態に対してエラーであるという項目もあります。 この場合には、エラー処理が起こります （see 節 6. エラーからの回復）。

5.6 還元/還元衝突

同一の入力列に対して2個以上の規則が適用可能であると、 還元/還元衝突が起きます。 これは、通常、文法の重大なエラーを意味します。

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); }
        ;

エラーは、あいまいさにあります。 つまり、1個のwordをsequenceに構文解析する、 2個以上の方法があります。 wordは、maybewordに還元され、 第2の規則によってsequenceになりえます。 また、最初の規則で、空データがsequenceに還元され、 それが第3の規則によってwordと組み合わされて sequenceになりえます。

さらに、空データがsequenceに還元される方法が2つ以上あります。 第1の規則で直接還元される方法と、 maybewordを経由して第2の規則で還元される方法です。

この違いは、特定の入力が正当であるかどうかに関係ないので、 ささいなことに思えるかもしれません。 しかし、これは、どのアクションが実行されるかに影響します。 ある構文解析手順では第2の規則のアクションが実行され、 別の構文解析手順では第1の規則のアクションと第3の規則のアクションが 実行されます。 この例では、プログラムの出力が異なります。

Bisonは、最初に現れた文法を選ぶことで、還元/還元衝突を解決しますが、 これに頼ることは非常に危険です。 還元/還元衝突のそれぞれは、人間によって解析され、 通常は取り除かれるべきです。 sequenceを定義する正しい方法を示します。

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

還元/還元衝突を起こす、別のありがちなエラーの例を示します。

sequence: /* 空 */
        | sequence words
        | sequence redirects
        ;

words:    /* 空 */
        | words word
        ;

redirects:/* 空 */
        | redirects redirect
        ;

ここは、wordまたはredirectグループのどちらかを含む 列の定義が目的です。 sequence、words、redirectsそれぞれ個別の 定義にエラーはありません。しかし、3個を合わせると、あいまいになります。 空の入力には、無限個の構文解析方法があります。

空データがwordsになったと仮定しましょう。 それは、2個のwordsにも、3個のwordsにも、 何個のwordsにもなりえます。 あるいは、1個のwordsに3個のredirectsともう1個のwordが 続くことも考えられます。同様に、無限の解釈が可能です。

これらの規則を直す方法が2つあります。 第1に、1段階の列にする方法です。

sequence: /* 空 */
        | sequence word
        | sequence redirect
        ;

第2に、wordsとredirectsが空になるのを防ぐ方法です。

sequence: /* 空 */
        | sequence words
        | sequence redirects
        ;

words:    word
        | words word
        ;

redirects:redirect
        | redirects redirect
        ;

5.7 不可解な還元/還元衝突

そうなるはずがないように見えるのに、ときどき 還元/還元衝突が起きることがあります。 例を示します。

%token ID

%%
def:    param_spec return_spec ','
        ;
param_spec:
             type
        |    name_list ':' type
        ;
return_spec:
             type
        |    name ':' type
        ;
type:        ID
        ;
name:        ID
        ;
name_list:
             name
        |    name ',' name_list
        ;

この文法は、1個のトークンの先読みによって、構文解析できるように見えます。 たとえば、pram_specが読まれた後で、 IDはカンマかセミコロンが続くならばname、 そうでなければtypeとなります。 言い換えれば、この文法はLR(1)です。

しかし、Bisonは、多くの構文解析器生成器と同様に、 すべてのLR(1)文法を扱えるわけではありません。 前述の例では、IDの後で、そこがparam_specの先頭であるという 文脈と、そこがreturn_specの先頭であるという文脈は、 Bisonが同一であるとみなしてしまうほど似ています。 これらの文脈が似てしまう原因は、同じ規則の集合が有効になる、つまり、 nameへ還元するための規則と、typeへ還元するための規則の 両方が有効なことです。 Bisonは、その規則が2つの文脈で異なる先読みトークンを要求するような、 処理の段階を決定できず、両者から1つの構文解析器状態ができてしまいます。 2個の文脈の組み合わせは、後で衝突を起こします。 構文解析器の用語でいえば、この問題の発生は、 文法がLALR(1)でないことを意味します。

一般に、このような欠点は解決して、文書化するべきです。 しかし、この問題は本質的に解決困難です。 LR(1)文法を扱える構文解析器生成器は、作成困難で、 生成される構文解析器が巨大になってしまいます。 実用上、Bisonは今のままでも有用です。

このような問題が現れた場合に、混乱の元になっている2種類の構文解析器の 状態を区別し、それらが違うという目印か何かを追加することによって、 しばしば問題を解決できます。 前述の例では、次のようにreturn_specに規則を追加して、 問題を解決できます。

%token BOGUS
...
%%
...
return_spec:
             type
        |    name ':' type
         /* この規則は決して使われない。  */
        |    ID BOGUS
        ;

IDの次でreturn_specの先頭である文脈で、 追加の規則が有効になる可能性を導入して、問題を解決しています。 この規則は、param_specに関連する文脈では有効にならないので、 2個の文脈は、異なる構文解析器状態を持ちます。 BOGUSはyylexによっては決して生成されないので、 追加された規則は入力が実際に構文解析される方法には影響しません。

この具体例では、問題を解決する別の方法があります。 つまり、return_specの規則を、name経由ではなく IDを直接使うように書き換えるのです。 return_specに対する規則は、nameに対する規則ではなく、 return_specに対する規則を有効にするので、 2つの混乱していた文脈は異なる有効な規則の集まりを持ちます。

param_spec:
             type
        |    name_list ':' type
        ;
return_spec:
             type
        |    ID ':' type
        ;

5.8 スタックオーバーフローと防ぎ方

Bison構文解析器のスタックは、あまりにも多くのトークンがシフトされて 還元されないでいると、オーバーフローする可能性があります。 スタックがオーバーフローすると、オーバーフローを報告するためにyyerror を呼び出して、関数yyparseは0でない値を返します。

マクロYYMAXDEPTHを定義して、スタックオーバーフローが起こらないように、 構文解析器のスタックの深さを調節できます。 マクロの値として、整数値を定義してください。 この値は、オーバーフローする前に、シフトされたが還元されていないトークンの 最大数になります。 マクロの値として、コンパイル時に決定可能な定数式を指定してください。

指定されたスタック領域は、割り当てられる必要はありません。 大きなYYMAXDEPTHを指定すると、 構文解析器はまず小さなスタック領域を割り当て、 必要に応じてより大きなスタック領域を割り当てます。 この割り当ての増加は、何も表示せずに、自動的に行われます。 したがって、スタックをあまり必要としない通常の入力に対して メモリを節約するために、YYMAXDEPTHを小さくする必要はありません。

特に指定しないと、YYMAXDEPTHの値は10000になります。

マクロYYINIDEPTHを指定して、最初に割り当てられるスタックの量を 調節できます。この値は、コンパイル時に決定可能な整定数の必要があります。 特に指定しないと、200になります。