次: Shift/Reduce, 上: Algorithm
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。