次: , 上: Algorithm


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