到達可能なアイテムの探索と遷移
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/11/21 17:57 UTC 版)
「LR法」の記事における「到達可能なアイテムの探索と遷移」の解説
構文解析表作成の第一段階は、アイテム集合クロージャ間の遷移の決定である。これはちょうど終端記号も非終端記号も読み込む有限オートマトンを検討する要領で決定できる。このオートマトンの開始状態は常に追加された規則から得られるアイテム S → • E で表される状態である。 アイテム集合 0 S → • E + E → • E * B + E → • E + B + E → • B + B → • 0 + B → • 1 アイテムの前に付与されたプラス記号は、そのアイテムがクロージャに追加されたことを意味している。'+'記号が付与されていない初期アイテムをそのアイテム集合の「核」と言う。 初期状態 (S0) から始めて、ここから到達できる全状態を決定する。まず、各アイテムの右辺でドットの次にある記号に注目する。この場合、終端記号 '0' と '1'、および非終端記号 E と B が現われている。記号 x からアイテム集合を見つけるため、次の手続きを実行する: 現在のアイテム集合内の各アイテムで何らかの記号 x の前にドットのある全アイテムの集合 S を求める。 S 内の各アイテムについて、ドットを x の次の位置に移す。 結果として生じたアイテム集合を閉じる。 終端記号 '0' について、この手続きを行うと次のようになる: アイテム集合 1 B → 0 • 終端記号 '1' については次の通り: アイテム集合 2 B → 1 • 非終端記号 E では次のようになる: アイテム集合 3 S → E • E → E • * B E → E • + B 非終端記号 B については次の通り: アイテム集合 4 E → B • これらのクロージャではドットの後に非終端記号がないため、新たなアイテムが追加されていない。この手続きを新たなアイテム集合がなくなるまで続ける。アイテム集合1, 2, 4 はドットの後に記号がないため、ここで終わりである。アイテム集合 3 についてはドットの後に終端記号 '*' と '+' がある。'*' についての遷移は次のアイテム集合で表される。 アイテム集合 5 E → E * • B + B → • 0 + B → • 1 同様に '+' については次の通り: アイテム集合 6 E → E + • B + B → • 0 + B → • 1 アイテム集合 5 では、終端記号 '0' と '1'、非終端記号 B を考慮する必要がある。終端記号については既出のアイテム集合 1 と 2 が対応する。非終端記号 B については次のような遷移が導かれる: アイテム集合 7 E → E * B • アイテム集合も同様に終端記号 '0' と '1'、非終端記号 B を考慮する必要がある。また、同様に終端記号については既出のアイテム集合 1 と 2 が対応する。非終端記号 B については次のような遷移が導かれる: アイテム集合 8 E → E + B • これらのアイテム集合もドットの後に記号がないので、アイテム集合はこれで全部である。これらから、オートマトンの状態遷移表は次の通りとなる: アイテム集合*+01EB0 1 2 3 4 1 2 35 6 4 5 1 2 7 6 1 2 8 7 8
※この「到達可能なアイテムの探索と遷移」の解説は、「LR法」の解説の一部です。
「到達可能なアイテムの探索と遷移」を含む「LR法」の記事については、「LR法」の概要を参照ください。
- 到達可能なアイテムの探索と遷移のページへのリンク
