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)。
この種類の構文解析器は、ボトムアップ構文解析器として知られています。