アイテム集合のクロージャ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/11/21 17:57 UTC 版)
E → E + • B のように非終端記号の前にドットのあるアイテムは、構文解析器が次に非終端記号 B を構文解析すべきであることを示している。構文解析中に適用が可能な全ての規則をアイテム集合に含めるため、ここでは B 自体の構文解析を表すアイテム集合も含めなければならない。すなわち B → 1 や B → 0 といった規則がある場合、アイテム B → • 1 や B → • 0 をアイテム集合に含めるということである。これを一般化して定式化すると次のようになる: A → v•Bw という形式のアイテムがアイテム集合内にあり、文法に B → w' という規則がある場合、アイテム B → • w' をアイテム集合に含めなければならない。 これをアイテム集合全体に適用して、全ての非終端記号の前のドットに関して同様の処置を施してアイテム集合を特定する。ここで、構文解析のある特定の状態を与えるアイテム集合を「クロージャ」と呼び、clos(I) と表記する。ここで、I はアイテム集合である。ただし、構文解析表では初期状態から到達可能な状態に関するものしか考慮されない。
※この「アイテム集合のクロージャ」の解説は、「LR法」の解説の一部です。
「アイテム集合のクロージャ」を含む「LR法」の記事については、「LR法」の概要を参照ください。
ウィキペディア小見出し辞書の「アイテム集合のクロージャ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- アイテム集合のクロージャのページへのリンク
