衝突解決のアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2013/04/15 17:57 UTC 版)
「単純LR法」の記事における「衝突解決のアルゴリズム」の解説
SLR(1)は以下の方法で衝突の解決を試みる。 shift-reduce 衝突、または reduce-reduce 衝突が発生している状態を求める。 求めた状態について、reduce を含む規則の左辺、つまり A → B ... X • (ただし B および ... は空を含む)という形の LR(0) アイテムの非終端記号 A の Follow-set を求める。 求めた状態において、その Follow-set の全ての記号についてのアクションを(この LR(0) アイテムの規則で)reduce とする。 2.と3.を全ての reduce を含む規則について繰り返す。 shift を含む規則については全て、その規則において、次に読み込まれる記号についてのアクションを shift とする。 この操作を全ての状態について繰り返す。 上記の操作中に、同じ記号についてのアクションが二重に決まるような場合、その状態では SLR(1) によって解決不可能な衝突が発生している。 一般に、SLR(1) の使用する Follow-set は文脈を全く考慮しないため、余計な記号を含んでいる。そのため、文脈を考慮する Lookahead-set を使用する LALR(1) や LR(1) に比べ、衝突が発生しやすい。
※この「衝突解決のアルゴリズム」の解説は、「単純LR法」の解説の一部です。
「衝突解決のアルゴリズム」を含む「単純LR法」の記事については、「単純LR法」の概要を参照ください。
ウィキペディア小見出し辞書の「衝突解決のアルゴリズム」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 衝突解決のアルゴリズムのページへのリンク
