7. 文脈依存性の処理

Bisonの枠組みは、まずトークンを読み、 次にトークンをより大きな文法的単位にグループ化することです。 多くの言語では、トークンの意味は文脈の影響を受けます。 文脈依存性によってBisonの枠組みが壊れますが、 （kludgesとして知られる）いくつかの技術を使って、 このような言語に対するBison構文解析器を書けます。

（実際に、「kludge」は、仕事を可能にしますが、 美しくも頑丈でもない技術を意味します）

7.1 トークン型の意味情報

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の違いも同様です。

前述の技術と、後述の字句解析結び付きには、 字句解析に影響する情報が入力の別の部分を構文解析しているときに 変化させられるという、共通点があります。 前者では、情報が広域的で、プログラム(15)の別の目的に 使われることが異なります。 本当の字句解析結び付きは、文脈によって制御される、 特別の目的のフラグを持ちます。

7.2 字句解析結び付き

文脈依存性を処理する1つの方法は、字句解析結び付き（lexical tie-in）で、 Bisonのアクションによって設定されるフラグが、 トークンが構文解析される方法に影響します。

たとえば、C言語によく似ていて、`hex (hex-expr)'という 特別な構造を持つ言語について、考えてみましょう。 予約語hexがきた後にかっこで囲まれた式が続いて、 そのかっこの中ではすべての整数が16進数になります。 特に、トークン`a1b'は、このような文脈に現れれば、 識別子ではなく整数として扱われる必要があります。 どのようにすればよいかを示します。

%{
int hexflag;
%}
%%
...
expr:   IDENTIFIER
        | constant
        | HEX '('
                { hexflag = 1; }
          expr ')'
                { hexflag = 0;
                   $$ = $4; }
        | expr '+' expr
                { $$ = make_sum ($1, $3); }
        ...
        ;

constant:
          INTEGER
        | STRING
        ;

yylexは、hexflagの値が0でなければ、 すべての整数が16進数であると字句解析し、 英字で始まるトークンも可能な限り整数と解釈すると、仮定します。

hexflagの宣言は、アクションから参照可能なように、 文法ファイルのC宣言部に書かれる必要があります （see 節 The C Declarations Section）。 同様に、yylexのプログラムにも、hexflagの宣言が必要です。

7.3 字句解析結び付きとエラー回復

字句解析結び付きは、厳密なエラー回復規則を要求します。 See 節 6. エラーからの回復。

その理由は、エラー回復規則の目的が、ある構成物の構文解析を中断し、 より大きな構成物の構文解析を再開することです。 前述のC言語に似ている言語の例では、次のように、 標準的なエラー回復規則は、次のセミコロンまでトークンを読み捨て、 新しい文の構文解析を再開します。

stmt:   expr ';'
        | IF '(' expr ')' stmt { ... }
        ...
        error ';'
                { hexflag = 0; }
        ;

もし、`hex (expr)'の途中で構文エラーが発生すれば、 このエラー回復規則が適用され、完了した`hex expr)'に対する アクションは決して実行されません。 すると、hexflagは、入力の残りの間ずっと設定されたままでいるか、 次のhex予約語の出現までそのままの状態でいて、 識別子が16進整数と誤解されます。

この問題を防ぐためには、エラー回復規則が hexflagを元に戻すべきです。

さらに、式の内部で働くエラー回復規則があるかもしれません。 たとえば、次の例のように、かっこの中でエラーが発生すると、 閉じかっこまで読み捨てるようなエラー回復規則が考えられます。

expr:   ...
        | '(' expr ')'
                { $$ = $2; }
        | '(' error ')'
        ...

もし、この規則がhex構造の中で働くならば、 その構造の中の内側のかっこに適用されるので、 構造を中断するべきではありません。 したがって、このアクションではフラグを戻すべきではなく、 hex構造の残りはフラグを有効にしたまま構文解析されるべきです。

状況に応じて、hex構造を中断できるかもしれないし、そうでないかもしれない エラー回復規則があれば、どうなるでしょうか。 hex構造を中断すべきかどうか決定できるアクションを書けません。 そこで、もし、字句解析結び付きを使っているならば、 あなたが書いたエラー回復規則がそのようになっていないことを確かめるべきです。 それぞれの規則は、常にフラグを戻すべきか、あるいは常にフラグを戻さないべきか、 決定できるべきです。