5.7 不可解な還元/還元衝突

そうなるはずがないように見えるのに、ときどき 還元/還元衝突が起きることがあります。 例を示します。

     %token ID
     
     %%
     def:    param_spec return_spec ','
             ;
     param_spec:
                  type
             |    name_list ':' type
             ;
     return_spec:
                  type
             |    name ':' type
             ;
     type:        ID
             ;
     name:        ID
             ;
     name_list:
                  name
             |    name ',' name_list
             ;

この文法は、1個のトークンの先読みによって、構文解析できるように見えます。 たとえば、pram_specが読まれた後で、 IDはカンマかセミコロンが続くならばname、 そうでなければtypeとなります。 言い換えれば、この文法はLR(1)です。

しかし、Bisonは、多くの構文解析器生成器と同様に、 すべてのLR(1)文法を扱えるわけではありません。 前述の例では、IDの後で、そこがparam_specの先頭であるという 文脈と、そこがreturn_specの先頭であるという文脈は、 Bisonが同一であるとみなしてしまうほど似ています。 これらの文脈が似てしまう原因は、同じ規則の集合が有効になる、つまり、 nameへ還元するための規則と、typeへ還元するための規則の 両方が有効なことです。 Bisonは、その規則が2つの文脈で異なる先読みトークンを要求するような、 処理の段階を決定できず、両者から1つの構文解析器状態ができてしまいます。 2個の文脈の組み合わせは、後で衝突を起こします。 構文解析器の用語でいえば、この問題の発生は、 文法がLALR(1)でないことを意味します。

一般に、このような欠点は解決して、文書化するべきです。 しかし、この問題は本質的に解決困難です。 LR(1)文法を扱える構文解析器生成器は、作成困難で、 生成される構文解析器が巨大になってしまいます。 実用上、Bisonは今のままでも有用です。

このような問題が現れた場合に、混乱の元になっている2種類の構文解析器の 状態を区別し、それらが違うという目印か何かを追加することによって、 しばしば問題を解決できます。 前述の例では、次のようにreturn_specに規則を追加して、 問題を解決できます。

     %token BOGUS
     ...
     %%
     ...
     return_spec:
                  type
             |    name ':' type
              /* この規則は決して使われない。  */
             |    ID BOGUS
             ;

IDの次でreturn_specの先頭である文脈で、 追加の規則が有効になる可能性を導入して、問題を解決しています。 この規則は、param_specに関連する文脈では有効にならないので、 2個の文脈は、異なる構文解析器状態を持ちます。 BOGUSはyylexによっては決して生成されないので、 追加された規則は入力が実際に構文解析される方法には影響しません。

この具体例では、問題を解決する別の方法があります。 つまり、return_specの規則を、name経由ではなく IDを直接使うように書き換えるのです。 return_specに対する規則は、nameに対する規則ではなく、 return_specに対する規則を有効にするので、 2つの混乱していた文脈は異なる有効な規則の集まりを持ちます。

     param_spec:
                  type
             |    name_list ':' type
             ;
     return_spec:
                  type
             |    ID ':' type
             ;