from ボトムアップ構文解析

単純LR法ともいう

閉包

わかりにくいが、冷静に見ると簡単。再帰的な定義

Iを文法G'の項の集合とするとき、Iの閉包closure(I)は次のように得られるもの

1. I中の全ての項はclosure(I)に含まれる

2. closure(I)に含まれるものの中で、

ドットの次が非終端記号であるような項A\rightarrow\alpha\cdot B\betaがあるなら

Bを左辺にする生成規則B\rightarrow yを見て、その項でドットが左端にあるものB\rightarrow\cdot yをclosure(I)に含める

↑はもともとclosure(I)に含まれていなかった場合のみ含める

つまり、重複はない

3. この操作(1,2,3)をこれ以上追加できなくなるまで繰り返す