C言語は文脈依存性をもっています。 すなわち、識別子の使われ方は、それの現在の意味に依存します。 次の例を考えてみてください。
foo (x);
これは、関数を呼び出す文のように見えます。
しかし、もし、fooがtypedefされた型名ならば、
この文はxの宣言になります。
C言語に対するBison構文解析器は、この入力を構文解析する方法を
どのように決定できるでしょうか。
GNU Cで使っている方法は、IDENTIFIERとTYPENAMEという、
2種類の異なるトークン型を使うことです。
yylexが識別子を見つけると、どちらのトークン型を返すか決めるために、
識別子の現在の宣言を検索し、typedefとして宣言されていれば
TYPENAMEを返し、そうでなければIDENTIFIERを返します。
そして、認識するトークン型を選ぶことによって、
文法規則は文脈依存性を表現できます。
IDENTIFIERは、式として受け入れられますが、
TYPENAMEは受け入れられません。
TYPENAMEは、宣言の始まりとして受け入れられますが、
IDENTIFIERは受け入れられません。
識別子の意味の区別が必要のない文脈、
たとえばtypedef名を隠す宣言の中では、
TYPENAMEとIDENTIFIERの両方が受け入れられます。
すなわち、2個のトークン型に対してそれぞれ1個の規則を書くことが可能です。
この方法は、どの種類の識別子が許されるかの判断が、
その識別子が構文解析される場所の近くで行われるならば、
単純に使えます。
しかし、C言語で、いつもそうであるとは限りません。
次の例のように、以前に指定された明示的な型に規定されたtypedef名の
再宣言が許されているからです。
typedef int foo, bar, lose;
static foo (bar); /* barを静的変数として再宣言する。 */
static int foo (lose); /* fooを関数として再宣言する。 */
不幸にも、込み入った文法構造「宣言子(declarator)」によって、 宣言された名前は、その宣言の構造自身から切り離されます。
結果として、C言語に対するBison構文解析器は、
すべての非終端記号の名前を変えて、二重化されました。
第1は、typedef名が再定義されているかもしれない宣言を構文解析し、
第2は、再定義が起こりえない宣言を構文解析します。
二重化したものの一部分を、簡単にするためにアクションを省略して、示します。
initdcl:
declarator maybeasm '='
init
| declarator maybeasm
;
notype_initdcl:
notype_declarator maybeasm '='
init
| notype_declarator maybeasm
;
ここで、initdclはtypedef名を再宣言できますが、
notype_initdclは再宣言できません。
declaratorとnotype_declaratorの違いも同様です。
前述の技術と、後述の字句解析結び付きには、 字句解析に影響する情報が入力の別の部分を構文解析しているときに 変化させられるという、共通点があります。 前者では、情報が広域的で、プログラム1の別の目的に 使われることが異なります。 本当の字句解析結び付きは、文脈によって制御される、 特別の目的のフラグを持ちます。