次: Mystery Conflicts, 前: Parser States, 上: Algorithm
同一の入力列に対して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 ;