5.6 還元/還元衝突

同一の入力列に対して2個以上の規則が適用可能であると、 還元/還元衝突が起きます。 これは、通常、文法の重大なエラーを意味します。

0個以上のwordの並びをグループ化する、 誤った試みの例を示します。

     sequence: /* 空 */
                     { printf ("empty sequence\n"); }
             | maybeword
             | sequence word
                     { printf ("added word %s\n", $2); }
             ;
     
     maybeword: /* 空 */
                     { printf ("empty maybeword\n"); }
             | word
                     { printf ("single word %s\n", $1); }
             ;

エラーは、あいまいさにあります。 つまり、1個のwordをsequenceに構文解析する、 2個以上の方法があります。 wordは、maybewordに還元され、 第2の規則によってsequenceになりえます。 また、最初の規則で、空データがsequenceに還元され、 それが第3の規則によってwordと組み合わされて sequenceになりえます。

さらに、空データがsequenceに還元される方法が2つ以上あります。 第1の規則で直接還元される方法と、 maybewordを経由して第2の規則で還元される方法です。

この違いは、特定の入力が正当であるかどうかに関係ないので、 ささいなことに思えるかもしれません。 しかし、これは、どのアクションが実行されるかに影響します。 ある構文解析手順では第2の規則のアクションが実行され、 別の構文解析手順では第1の規則のアクションと第3の規則のアクションが 実行されます。 この例では、プログラムの出力が異なります。

Bisonは、最初に現れた文法を選ぶことで、還元/還元衝突を解決しますが、 これに頼ることは非常に危険です。 還元/還元衝突のそれぞれは、人間によって解析され、 通常は取り除かれるべきです。 sequenceを定義する正しい方法を示します。

     sequence: /* 空 */
                     { printf ("empty sequence\n"); }
             | sequence word
                     { printf ("added word %s\n", $2); }
             ;

還元/還元衝突を起こす、別のありがちなエラーの例を示します。

     sequence: /* 空 */
             | sequence words
             | sequence redirects
             ;
     
     words:    /* 空 */
             | words word
             ;
     
     redirects:/* 空 */
             | redirects redirect
             ;

ここは、wordまたはredirectグループのどちらかを含む 列の定義が目的です。 sequence、words、redirectsそれぞれ個別の 定義にエラーはありません。しかし、3個を合わせると、あいまいになります。 空の入力には、無限個の構文解析方法があります。

空データがwordsになったと仮定しましょう。 それは、2個のwordsにも、3個のwordsにも、 何個のwordsにもなりえます。 あるいは、1個のwordsに3個のredirectsともう1個のwordが 続くことも考えられます。同様に、無限の解釈が可能です。

これらの規則を直す方法が2つあります。 第1に、1段階の列にする方法です。

     sequence: /* 空 */
             | sequence word
             | sequence redirect
             ;

第2に、wordsとredirectsが空になるのを防ぐ方法です。

     sequence: /* 空 */
             | sequence words
             | sequence redirects
             ;
     
     words:    word
             | words word
             ;
     
     redirects:redirect
             | redirects redirect
             ;