私は LR(k) 解析テーブルの構築について読み始めました。k > 0 のアルゴリズムを説明するすべてのテキストは、アイテム セットを生成する前にすべてのシンボルに対して先読みを計算する必要があることを示唆しています。冗長なものをマージして、最小限の解析テーブルを生成する必要があります。
次の疑似状態/アイテムセット構築ルーチンを検討してください。
- 先読みなしで状態遷移を決定できると仮定することから始めます (k = 0)
- 現在の状態のアイテムセット全体を計算する
- 現在の状態のアクションを決定してみてください。
- セット内にアイテムが 1 つしかなく、それがすべての入力を消費した場合 (rhs の右側にあるマーカー、アクションはアイテムの lhs に縮小されます。
- セット内のすべてのアイテムが入力を期待している場合、アクションはシフトして次の状態に進むことです
- 入力を期待する項目と入力を期待しない項目がある場合、これは shift/reduce 競合です
- lhs が異なる 2 つ以上のアイテムが入力の最後に達した場合、これは reduce /reduce の競合です。最後の 2 つのケースのいずれかが発生した場合は、状態のアクションを決定する前に先を見据える必要があることを意味します。k を 1 増やして、ステップ 2 に戻ります。
- アクションがシフトする場合は、入力の組み合わせ (および k > 0 の場合は先読み) をシミュレートしてフォローアップ状態を作成し、新しい状態ごとにステップ 1 に戻ります。
上記の手順を使用して、任意の LR(k) 文法のテーブルを構築することは可能/実行可能でしょうか? そうでない場合、何が欠けていますか？