新しいアイテム集合の作成
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/01/06 06:08 UTC 版)
「正規LR法」の記事における「新しいアイテム集合の作成」の解説
残りのアイテム集合は以下のアルゴリズムで作成できる。 既存の各アイテム集合kにおいて•の後に現れる各記号Aについて、•の直後がAであるkのすべての規則を追加することで新しいアイテム集合mを作成する。ただし、mがステップ3以降ですでに存在しているアイテム集合と同じとならない場合に限る。 新しいアイテム集合内の各規則においてすべての•を記号1つ分右にシフトする 新しいアイテム集合の閉包を作成する 新しいアイテム集合が追加されなくなるまで、追加されたすべてのアイテム集合についてステップ1から繰り返す。 今回の例では、アイテム集合0からさらに5つのアイテム集合を得られる。 アイテム集合1(非終端記号E) [S → E •, $] アイテム集合2(非終端記号T) [E → T •, $] [T → T • + n, $] [T → T • + n, +] ... アイテム集合3(終端記号n) [T → n •, $] [T → n •, +] [T → n •, )] アイテム集合4(終端記号'+') [T → + • T, $] [T → + • T, +] [T → • n, $] [T → • n, +] [T → • + T, $] [T → • + T, +] [T → • T + n, $] [T → • T + n, +] ... アイテム集合5(終端記号'(') [E → ( • E ), $] [E → • T, )] [E → • ( E ), )] [T → • n, )] [T → • n, +] [T → • + T, )] [T → • + T, +] [T → • T + n, )] [T → • T + n, +] ... アイテム集合2、4および5からさらにいくつかのアイテム集合が作成される。完全なリストはかなり長いためここでは述べない。この文法の詳細なLR(k)での扱いは例えばに示されている。
※この「新しいアイテム集合の作成」の解説は、「正規LR法」の解説の一部です。
「新しいアイテム集合の作成」を含む「正規LR法」の記事については、「正規LR法」の概要を参照ください。
- 新しいアイテム集合の作成のページへのリンク