構築した表内での衝突
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/11/21 17:57 UTC 版)
ところで、構築されたオートマトンは常に決定性オートマトンである。しかし、reduce アクションを表に追記しようとすると、1つのマスに shift アクションと reduce アクションが共に存在してしまう場合がある。これは shift-reduce 衝突と呼ぶ。あるいは、2つの reduce アクションが衝突する場合もある。これを reduce-reduce 衝突と呼ぶ。しかし、これが発生するということは、その文法が LR(0) では扱えないことを示している。 非常に単純な LR(0) で扱えない文法（shift-reduce衝突が発生する）の例を示す。 (1) E → 1 E (2) E → 1 ここから次のようなアイテム集合が得られる: アイテム集合 1 E → 1 • E E → 1 • + E → • 1 E + E → • 1 このアイテム集合と終端記号 '1' の交差するマスには、状態 1 への shift アクションと規則 2 の reduce アクションが対応するため、shift-reduce 衝突が発生する。 非常に単純な LR(0) で扱えない文法（reduce-reduce衝突が発生する）の例を示す。 (1) E → A 1 (2) E → B 2 (3) A → 1 (4) B → 1 この場合、次のようなアイテム集合が得られる: アイテム集合 1 A → 1 • B → 1 • この場合、各アイテムがそれぞれ文法規則 3 と 4 に対応しているため、reduce-reduce 衝突が発生する。 これらの例では、非終端記号 A の Follow-set（LL法参照）を使用して、A の還元規則を使うかどうかを決定すればよい。つまり、入力の次の記号が A の Follow-set にある場合だけ、規則 A → w を適用する。この方式を単純LR法と呼ぶ。
※この「構築した表内での衝突」の解説は、「LR法」の解説の一部です。
「構築した表内での衝突」を含む「LR法」の記事については、「LR法」の概要を参照ください。
- 構築した表内での衝突のページへのリンク
