● 上昇型構文解析 (bottom-up parsing) --- LR構文解析 * 文法の例 終端記号: ＋ ＊ （ ） id 非終端記号: Ｅ Ｔ Ｆ 開始記号: Ｅ 生成規則: Ｅ → Ｅ ＋ Ｔ Ｅ → Ｔ Ｔ → Ｔ ＊ Ｆ Ｔ → Ｆ Ｆ → （ Ｅ ） Ｆ → id * 入力文字列 id ＊ id ＋ id * 導出木 Ｅ ／｜＼ ／ ｜ Ｔ ／ ｜ ｜ Ｅ ｜ Ｆ ｜ ｜ ｜ Ｔ ｜ ｜ ／｜＼ ｜ ｜ Ｔ ｜ Ｆ ｜ ｜ ｜ ｜ ｜ ｜ ｜ Ｆ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ id ＊ id ＋ id * 上昇型構文解析の基本的な考え方 入力を読みながら導出木を少しずつ作る。 読んだ入力を使って、導出木のできる限り大きな部分を作る。 それ以上大きくできなかったら次の文字を読む。 部分木の並び 得られた文形式 残りの入力 id id ＊ id ＋ id Ｆ Ｆ ＊ id ＋ id ｜ id Ｔ Ｔ ＊ id ＋ id ｜ Ｆ ｜ id Ｔ Ｔ ＊ id ＋ id ｜ Ｆ ｜ id ＊ Ｔ Ｔ ＊ id ＋ id ｜ Ｆ ｜ id ＊ id Ｔ Ｆ Ｔ ＊ Ｆ ＋ id ｜ ｜ Ｆ ｜ ｜ ｜ id ＊ id Ｔ Ｔ ＋ id ／｜＼ Ｔ ｜ Ｆ ｜ ｜ ｜ Ｆ ｜ ｜ ｜ ｜ ｜ id ＊ id Ｅ Ｅ id ｜ Ｔ ／｜＼ Ｔ ｜ Ｆ ｜ ｜ ｜ Ｆ ｜ ｜ ｜ ｜ ｜ id ＊ id Ｅ Ｅ ＋ id ｜ Ｔ ／｜＼ Ｔ ｜ Ｆ ｜ ｜ ｜ Ｆ ｜ ｜ ｜ ｜ ｜ id ＊ id ＋ Ｅ Ｅ ＋ id ｜ Ｔ ／｜＼ Ｔ ｜ Ｆ ｜ ｜ ｜ Ｆ ｜ ｜ ｜ ｜ ｜ id ＊ id ＋ id Ｅ Ｆ Ｅ ＋ Ｆ ｜ ｜ Ｔ ｜ ／｜＼ ｜ Ｔ ｜ Ｆ ｜ ｜ ｜ ｜ ｜ Ｆ ｜ ｜ ｜ ｜ ｜ ｜ ｜ id ＊ id ＋ id Ｔ Ｅ ＋ Ｔ ｜ Ｅ Ｆ ｜ ｜ Ｔ ｜ ／｜＼ ｜ Ｔ ｜ Ｆ ｜ ｜ ｜ ｜ ｜ Ｆ ｜ ｜ ｜ ｜ ｜ ｜ ｜ id ＊ id ＋ id Ｅ Ｅ ／｜＼ ／ ｜ Ｔ ／ ｜ ｜ Ｅ ｜ Ｆ ｜ ｜ ｜ Ｔ ｜ ｜ ／｜＼ ｜ ｜ Ｔ ｜ Ｆ ｜ ｜ ｜ ｜ ｜ ｜ ｜ Ｆ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ id ＊ id ＋ id 以上の話は、既に導出木があるとしてのもの。 そのそも、parsingとは、導出木がないところで、 入力のみから導出木を作ることである。 * シフトと還元 入力文字列を、 既に読んだ部分 ｜ まだ読んでいない部分 $ と書く。 $ は end of string を示すマーカー。 シフト (shift) は次の文字を読む操作。 還元 (reduce) は生成規則を逆に適用して、 読んだ文字列を非終端記号に置き換える操作。 ｜ id ＊ id ＋ id $ ↓ シフト id ｜ ＊ id ＋ id $ ↓ Ｆ→idによる還元 Ｆ ｜ ＊ id ＋ id $ ↓ Ｔ→Ｆによる還元 Ｔ ｜ ＊ id ＋ id $ ↓ シフト Ｔ ＊ ｜ id ＋ id $ ↓ シフト Ｔ ＊ id ｜ ＋ id $ ↓ Ｆ→idによる還元 Ｔ ＊ Ｆ ｜ ＋ id $ ↓ Ｔ→Ｔ＊Ｆによる還元 Ｔ ｜ ＋ id $ ↓ Ｅ→Ｔによる還元 Ｅ ｜ ＋ id $ ↓ シフト Ｅ ＋ ｜ id $ ↓ シフト Ｅ ＋ id ｜ $ ↓ Ｆ→idによる還元 Ｅ ＋ Ｆ ｜ $ ↓ Ｔ→Ｆによる還元 Ｅ ＋ Ｔ ｜ $ ↓ Ｅ→Ｅ＋Ｔによる還元 Ｅ ｜ $ ↓ 受理 終了 シフトの操作を無視して、下から上にたどれば、 入力文字列の最右導出になっている。 ^^^^^^^^ 常に最も右の非終端記号を生成規則によって書き換える。 LR --- Left-to-right, Right-parse 以下では、文法は曖昧ではないとする。 すなわち、文字列に対して、導出木はuniqueに存在。 したがって、最右導出もunique。 * シフト α ｜ aw$ ==> αa ｜ w$ α: 終端非終端記号列 a: 終端記号 w: 終端記号列 * A→αによる還元 βα ｜ w$ ==> βA ｜ w$ A: 非終端記号 α: 終端非終端記号列 β: 終端非終端記号列 w: 終端記号列 * 受理 S ｜ $ ==> 終了 S: 開始記号 $: end of string * シフト対還元 Ｔ ｜ ＊ id ＋ id $ ↓ シフト Ｔ ＊ ｜ id ＋ id $ このとき、なぜ、還元してはならないのか? Ｔ ｜ ＊ id ＋ id $ ↓ Ｅ→Ｔによる還元 Ｅ ｜ ＊ id ＋ id $ 還元が可能なところでも、還元が行われていない。 どうしてそれがわかるのか? いかにして還元を制御するのか? * 還元対還元 Ｔ ＊ Ｆ ｜ ＋ id $ ↓ Ｔ→Ｔ＊Ｆによる還元 Ｔ ｜ ＋ id $ このとき、なぜ、Ｔ→Ｆによって還元してはならないのか? Ｔ ＊ Ｆ ｜ ＋ id $ ↓ Ｔ→Ｆによる還元 Ｔ ＊ Ｔ ｜ ＋ id $ 2種類以上の還元が可能なとき、 どの生成規則による還元を行えばよいのか? いかにして還元を制御するのか? * 可延頭部とハンドル A→αによる還元: βα ｜ w$ ==> βA ｜ w$ 対応する最右導出: * * S ⇒ βAw ⇒ βαw ⇒ 入力文字列 ハンドル (handle) とは、(生成規則A→αと) 文字列 βαw における部分文字列α (の位置) こと。 また、βを可延頭部という。 * 還元のための条件 βαw の中のαがハンドルになる (βが可延頭部になる) 条件は、 * S ⇒ βαw という最右導出が存在が存在することである。 S → β1 A1 γ1 A1 → β2 A2 γ2 A2 → β3 A3 γ3 ... An-1 → βn A γn A → α であるとき、 * S ⇒ β1 β2 β3 ... βn α γn ... γ3 γ2 γ1 * γn ... γ3 γ2 γ1 ⇒ w とすると、 * S ⇒ β1 β2 β3 ... βn α w が最右導出となる。従って、 β = β1 β2 β3 ... βn ならば、αがハンドルになる。 逆に、αがハンドルならば (βが可延頭部ならば)、 β = β1 β2 β3 ... βn と書けて、上のような生成規則が存在するはずである。 注: 以下、任意の非終端記号からは終端記号列が (一つ以上は) 導出されると仮定する。 (文法は冗長でない) * 可延頭部の特徴付け A→βBγ という生成規則に対して、 A'→βB' という生成規則を対応させる。A'とB'は新しい非終端記号。 この規則においては、もとの非終端記号を終端記号とみなす。 上の生成規則によってS'から導出される文字列が可延頭部になる。 従って、可延頭部の全体は正則言語である。 * LR(0)項 生成規則 A→αβ に対して (α=εでもβ=εでもかまわない)、 A→α.β という形の式をLR(0)項という。 LR(0)項を状態とする非決定性有限オートマトンを定義する。 X A→α.Xβ -------> A→αX.β (X:終端記号または非終端記号) ε A→α.Bβ -------> B→.γ (ε遷移, B:非終端記号) すると、次のことが成り立つ。 β α S→.γ -------> A→.α -------> A→α. iff * ∃w s.t S ⇒ βAw ⇒ βαw (最右導出) (すなわち、αはハンドルで、βは可延頭部) * まとめと例 βα｜w$ がA→αによって還元可能 Ｔ＊id｜＋id$ がＦ→idによって還元可能 ∧ ‖ ∨ * * S ⇒ βAw ⇒ βαw (最右導出) Ｅ ⇒ Ｔ＊Ｆ＋id ⇒ Ｔ＊id＋id (最右) ∧ ‖ ∨ ∃(n＝3の場合) (n＝3) * * S → β1 A1 γ1 γ1⇒w1 Ｅ → Ｅ＋Ｔ ＋Ｔ⇒＋id A1 → β2 A2 γ2 γ2⇒w2 Ｅ → Ｔ A2 → β3 A γ3 γ3⇒w3 Ｔ → Ｔ＊Ｆ A → α Ｆ → id st β＝β1 β2 β3 Ｔ＊ w ＝ w1 w2 w3 ＋id ‖ ∨ S→.β1 A1 γ1 Ｅ→.Ｅ＋Ｔ ↓β1 S→ β1.A1 γ1 ↓ε ↓ε A1→.β2 A2 γ2 Ｅ→.Ｔ ↓β2 A1→ β2.A2 γ2 ↓ε ↓ε A2→.β3 A γ3 Ｔ→.Ｔ＊Ｆ ↓β3 ↓Ｔ＊ A2→ β3.A γ3 Ｔ→ Ｔ＊.Ｆ ↓ε ↓ε A→.α Ｆ→.id ↓α ↓id A→ α. Ｆ→ id. ゆえに、 * ∃w s.t E ⇒ Ｔ＊Ｆw ⇒ Ｔ＊id w (最右導出) が成り立つ。 従って、Ｔ＊ は可延頭部で、id はハンドル。 また、上のwとしては、例えば、 ＋id をとることができる。従って、次のような還元が可能である。 Ｔ ＊ id ｜ ＋ id $ ↓ Ｆ→idによる還元 Ｔ ＊ Ｆ ｜ ＋ id $ オートマトンの遷移に従って、 次のようにして導出木を成長させることができる。 Ｅ→.Ｅ＋Ｔ Ｅ ／｜＼ .Ｅ ＋ Ｔ ↓ ε Ｅ→.Ｔ Ｅ ／｜＼ Ｅ ＋ Ｔ ｜ .Ｔ ↓ ε Ｔ→.Ｔ＊Ｆ Ｅ ／｜＼ Ｅ ＋ Ｔ ｜ Ｔ ／｜＼ .Ｔ ＊ Ｆ ↓ Ｔ Ｔ→Ｔ.＊Ｆ Ｅ ／｜＼ Ｅ ＋ Ｔ ｜ Ｔ ／｜＼ Ｔ.＊ Ｆ ↓ ＊ Ｔ→Ｔ＊.Ｆ Ｅ ／｜＼ Ｅ ＋ Ｔ ｜ Ｔ ／｜＼ Ｔ ＊.Ｆ ↓ ε Ｆ→.id Ｅ ／｜＼ Ｅ ＋ Ｔ ｜ Ｔ ／｜＼ Ｔ ＊ Ｆ ｜ .id ↓ id Ｆ→id. Ｅ ／｜＼ Ｅ ＋ Ｔ ｜ Ｔ ／｜＼ Ｔ ＊ Ｆ ｜ id. * 上昇型構文解析の一般論 拡大文法: 新しい開始記号S'を導入し、古い開始記号Sに対して、 S'→S という生成規則を付け加えてできる文法。 (開始記号S'が左辺にある規則は上のものしかない。) 拡大文法に対して先の非決定性有限オートマトンを作る。 ただし、 S'→.S を初期状態と定義する。 そして、その非決定性オートマトンを決定化する。 ｜の左の各記号にオートマトンの状態を割り当てる。 X1 ... Xn ｜ w$ s1 ... sn siは、X1...Xi までを読んだ後の状態。 siは決定性オートマトンの状態なので、 もとの非決定性オートマトンの状態の有限集合。 すなわち、LR(0)項の有限集合。 シフト: X1 ... Xn ｜ aw$ s1 ... sn ↓ シフト X1 ... Xn a ｜ w$ s1 ... sn sn+1 sn+1は、snとaより定まる(snとaに対する次の状態)。 n=0の場合は、s0として初期状態を用いる。 還元: X1 ... Xi Xi+1 ... Xn ｜ w$ s1 ... si si+1 ... sn ↓ A→Xi+1...Xnによる還元 X1 ... Xi A ｜ w$ s1 ... si s'i+1 s'i+1は、siとAより定まる(siとAに対する次の状態)。 i=0の場合は、s0として初期状態を用いる。 ただし、還元が起こるためには、 A→Xi+1...Xn. というLR(0)項がsnの元でなければならない。 * 還元の条件 例えば、次のような還元は不可能である。 Ｔ ＊ Ｆ ｜ ＋ id $ ↓ Ｔ→Ｆによる還元 Ｔ ＊ Ｔ ｜ ＋ id $ なぜならば、Ｔ＊Ｆ までを読んだときの状態に、 Ｔ→Ｆ. というLR(0)項は含まれていない。 このようにして、オートマトンの状態を用いて、 還元を制御することができる。 また、 Ｔ ｜ ＊ id ＋ id $ ↓ Ｅ→Ｔによる還元 Ｅ ｜ ＊ id ＋ id $ という還元は、次の理由により不可能である。 ＊がFOLLOW(Ｅ)に含まれていない。 この考え方がSLR構文解析のもとになっている。