某大学の講義録

個人用備忘録です。間違いの可能性あり。

言語処理系のまとめ #3

構文解析 文脈自由文法 LR文法

前回まで何をやったの？

rei624.hatenablog.jp


簡単にまとめると
・字句解析のあとは構文解析を行う。
・構文解析は字句解析で切り出した単語の順番から構文規則をチェックして、ついでに内部表現にする。
・構文解析は文脈自由文法という文法を用いた。
・下向き構文解析としてLL(1)文法を学んだ。

上向き構文解析とLR(k)文法

上向き構文解析

下向き構文解析は開始記号から入力記号列になるように解析木を導出した。
上向き構文解析は入力記号列からあてはまる生成規則を適用していき最終的に開始記号になるかを確認する。
適用できるものを順次還元していくためにスタックを利用する。
例えば、入力記号列が\alpha 1 \alpha 2 \betaであり、\alpha 1 \alpha 2まで読んだ状態を考える。
スタック：\alpha 1 \alpha 2
残り　　：\beta
ここで、生成規則A\rightarrow \alpha 2が存在しているのなら、スタック上の\alpha 2をAへと"還元"する。
スタック：\alpha 1 A
残り　　：\beta
逆に、どの生成規則の右辺にも\alpha 2が存在しない場合は、還元できるものがないため、\betaを読み込む。(これを"シフト"するという。)
スタック：\alpha 1 \alpha 2 \beta
残り　　：なし

上記の還元とシフトをスタックと残りの状況にあわせて繰り返しながら上向きに構文解析する。(シフト還元構文解析)

LR(k)文法

左から右へトークンをk個先読みしつつ最右導出できる文法のこと。
入力記号列側から求めるため、左から右へトークンを読んでも最右導出となっている。(最終的に開始記号にたどり着いた時その手順を逆にたどると最右導出となっている)
LR(k)文法の例
SLR(1)、LR(1)、LALR(1)(ここではやらない)

とりあえず以下ではLR(0)構文解析を考える。(つまり、スタックの状態だけでシフトするか還元するかを決定し、先読みをしない。)

LR文法では各時点でシフトと還元どちらかが可能。
生成規則からシフトと還元の状態遷移表を作成する。

文脈自由文法の例　(い　つ　も　の)

G = {P, E}
P={
      E→E+T
      E→T
      T→T*F
      T→F
      F→(E)
      F→i
}

T→T*Fにおいて、*まで読んだとする。(T→T*.F、.は次に読む位置を表す)
生成規則からここから遷移できる状態は
{T→T*.F, F→.(E), F→.i}の3種類が存在する。このようにある語彙の読み出しで遷移できる状態の集合を作成する。

状態遷移表の作成

LR(0)項

文法G={P, S}におけるPの任意の生成規則に対して、右辺の左端、右端、終端記号または非終端記号の間のどれか1カ所に"."をつけたもの。
例：E→E+Fという生成規則のLR(0)項を考えると、以下の4つになる。
　　E→.E+F, E→E.+F, E→E+.F, E→E+F.#(#はそれ以上シフトができないため還元すべき状態を表す)

closure(I)

Iに対するclosureを以下のように構築する。(ただしIはLR(0)項の集合とする)
1. closure(I) = I
2. A→α.Bβ\inclosure(I)に対してB→γという生成規則があればB→.γをclosure(I)に加える。
3. 全て追加するまで2を繰り返す。
つまり読み込み位置の後ろの文字が左辺に来る生成規則が存在する場合、その生成規則の右辺の先頭に"."を付けたものもclosureに含める。
例：いつもの例を用いると(ここではIとしてLR(0)項の集合すべてを考えることはせず、一例としてひとつ取り上げる。)

G = {P, E}
P={
      E→E+T
      E→T
      T→T*F
      T→F
      F→(E)
      F→i
}
closure(E→E+.T)={
      E→E+.T
      T→.T*F
      T→.F
      F→.(E)
      F→.i
}

GOTO(I, X)

Iは先ほどと同様にLR(0)項の集合。X\in(V_N \cup V_T)
GOTO(I,X)=closure({A→αX.β | A→α.Xβ\inI})
Iに含まれる状態の中でXの読み込みによって遷移する状態の集合。
Xの前に読み出し位置がある状態がIに含まれているなら、読み込み位置をXの後ろにシフトした状態のclosureをGOTOとして定義する。
文法GにおけるすべてのGOTO(I, X)を求めれば状態遷移表は完成する。(するだけ)

状態を求める

文法G={P, S}に対して
1. S'→S$という生成規則をGに加えてG'={P\cup{S'→S$}, S'}とする。
2. 上記のS→S$という生成規則に対してS→.S$という状態を考える。(つまり何もシフトしていない初期状態。)
　まず、C={closure({S'→.S$})}とする。
3. 次に以下を行えるだけ繰り返し、Cに加える。
　任意のI\inCとX\inVに対してGOTO(I, X)が空集合でなく、まだCに加えていない場合はCに加える。

いつもの例で考える
G = {P, E}
P={
      E→E+T
      E→T
      T→T*F
      T→F
      F→(E)
      F→i
}

G'={P', E'}
P'={
      E'→E$
      E→E+T
      E→T
      T→T*F
      T→F
      F→(E)
      F→i
}
C={closure({E'→.E$})}={
      E'→.E$  // そのものを入れる
      E→.E+T
      E→.T
      T→.T*F
      T→.F
      F→.(E)
      F→.i
}
上記のCの集合をとりあえずI0とすると
GOTO(I0, E)=closure({E'→E.$, E→E.+T})={
      E'→E.$
      E→E.+T
/* $はその位置で終了。+は終端記号のため生成規則は存在しない */
}
こうしてI0からEを読み込んで遷移できる状態の集合を今度はI1とする。
GOTO(I0, T)=closure({E→T.#, T→T.*F})={
      E→T.#  // #は次に還元することを表す
      T→T.*F
}
こうしてI0からTを読み込んで遷移できる状態の集合を今度はI2とする。

以下、上記を文法Gの全てのGOTOに対して繰り返すとスライド17pのような状態遷移図が得られる。ここでは各状態の集合からある記号を読み込んだ時に遷移できる状態の集合が遷移図として示されている。
状態遷移図の構築方法は下記のように全てのGOTOを書きだした後、それぞれの状態の集合と、ある文字を読みだした時の遷移先を繋げればよい。(下の画像ではGOTO(I10, *)を書き忘れています・・・ちなみにGOTO(I10, *)はI8に遷移します。)ただし、状態の名前はスライドと異なるつけ方をしているため、状態遷移図としては参照しないことをおすすめする。(どんな状態遷移図であっても受理するかどうかはわかるのだが)

f:id:rei_624:20190626221857j:plainf:id:rei_624:20190626221834j:plainf:id:rei_624:20190626221819j:plainf:id:rei_624:20190626221811j:plain

シフト還元の動き方

例えばi+j*100という式が上記の文法G'から生成できるかを考える。
ただし、スライドの状態遷移図での状態の番号を元にする。
f:id:rei_624:20190626232418p:plain

注意すべきはT→T*FやE→E+Tといった生成規則をもとに還元を行う場合は、スタック上で一気にその生成規則の直前の状態番号まで戻って、その後還元した記号をもとに遷移する点である。
また、今回の状態遷移図においてI2での動作は一意に定まっていない。(T.に対して還元もシフトも存在しうる。)この場合は、とりあえず一文字先読みしてからシフトをするか還元するかを決定することとなる。今回の例では次の文字が+であったため、還元した。(上記においてスタックがI0TI2からI0EI1へと変わっている部分。)

SLR(1)構文解析

上記のようにLR(0)構文解析では競合状態が発生する。(つまり、シフトすべきか還元すべきかが一意に定まらないということ)
競合状態は、シフト/還元での競合か、還元/還元での競合の二種類が発生しうる。
そこで、競合状態を解消する解析方法がこのSLR(1)構文解析および次のLR(1)構文解析である。(LALR(1)構文解析はとりあげない。)
SLR(1)構文解析では、SLR(1)構文解析表が矛盾なく作れれば、Follow集合を用いるだけで競合状態を解決できる。
SLR(1)構文解析表の作成方法は以下の通りである。
1. まず、LR(0)状態の集合をC={I0, I1, ... , In}とし、A[Ii, a]をスタックの先頭の状態がI1で次の読み込む記号がaであった時の動作を定義しているものとする。ここでa=sjであった時は、シフトして状態jへ遷移することを表しているものとする。
2. 初期状態をS'→.S$の存在している状態とする。(上記の例でいえばE'→.E$のあるI0)
3. GOTO(Ii, a)=Ijであれば、A[Ii, a] = sjとする。
4. A→α.#\inIiでainFollow(A)ならばA[li, a]="A→αで還元"とする。
5. S'→S.$\inIiであればA[Ii, $]="受理"とする。

上記の手順でSLR(1)構文解析表を作成する際に、A[Ii, a]が二つ以上の動作になる等の矛盾が生じた時はSLR(1)構文解析を行えないということである。

結局上記は何をしているのか？
2：初期状態の設定
3：GOTOが遷移する場合は該当のAに対して遷移を定義
4：A→α.#に対して、次の文字を見てその文字がFollow(A)に含まれているということは、αをAに還元しても正しいということになるため(Aの後ろにaが存在することに矛盾が発生しない)、Aに対して還元を定義する。
5：受理状態の設定

LR(1)構文解析

上記のSLR(1)構文解析ではFollow集合を使うだけで競合を回避しようとした。しかしFollow集合はある記号とその後ろに来る記号のみに注目しているため、それまでのスタックの中身を考慮することができない。
しかし、それまでのスタックの中身も考慮したうえで動作を定義することができれば文法の範囲を広げることができる。
・LR(1)項
　[A→x.y,z]：LR(0)項に対して、生成規則の直後にくる一つの終端記号を付加する。
例えば、A→xByとB→βという生成規則を考える。読み込み位置がA→x.Byであった時にB→.βという状態からβを読み込むとB→β.#となる。ここで、βをBに還元すると、A→xByという生成規則からBを読んだ後の記号はyであることがわかるため、先のB→β.#においてB→β.#, yというように次の入力を先読みして表記することを表している。
そしてLR(0)項で作成したclosureと同様にLR(1)項でもclosureを作成することを考える。
・LR(1)項からなる集合Iのclosure(I)
1. closure(I)=I
2. [A→α.Bβ, a]\in closure(I)に対してB→γという生成規則があれば、b\inFirst(βa)を満たす全てのbについて、[B→.γ, b]もclosure(I)に追加する。
つまり、LR(0)と異なる点は、生成規則だけでなくFirst集合も考慮する点である。(この時、ある生成規則に対して、bが例えば+, *, $のように複数存在する場合は[T→.T*F, +/*/$]のようにまとめて表記する。)
ここで、First(βa)を考えるときに、β=εであればFirst(βa)=First(a)={a}であるから、A→α.Bという生成規則に対しては[B→γ, a]をclosure(I)に追加できることになる。
3. 上記の2をclosure(I)に追加するものがなくなるまで繰り返す。
・LR(1)項のGOTO(I, X)
LR(0)の時と同様に、GOTOは以下のように求めることができる。
GOTO(I, X) = closure({[A→αX.β, a] | [A→α.Xβ, a]\inI})

言葉だけでは実際に理解することは難しいため、実際に手を動かして自分で求めると理解が深まる。以下では例としていつもの文法をもとにLR(1)項の集合Iでのclosure(I)を考える。

G'={P', E'}
P'={
      E'→E
      E→E+T
      E→T
      T→T*F
      T→F
      F→(E)
      F→i
}

上記の文法において初期状態のclosure({[E'→.E, $]})を考える。
まず、定義通り考えて[E'→.E, $]そのものと.Eの後ろがεであることから左辺がEの生成規則に対して$を先読みしたものをclosure({[E'→.E, $]})に追加する。

closure({[E'→.E, $]})={
      [E'→.E, $]
      [E→.E+T, $]
      [E→.T, $]
}

次に、今追加した生成規則から求められるものをclosure({[E'→.E, $]})に追加する。
まず、E→.Tから上記で左辺がEの生成規則を追加したのと同様の方法で左辺がTの物を追加する。次に、E→.E+TにおいてEの後ろは+であるから、左辺がEの生成規則に対して+を先読みできることがわかる。そこで、先ほどの$に加えaも先読みできるようにclosure({[E'→.E, $]})を更新する。

closure({[E'→.E, $]})={
      [E'→.E, $]
      [E→.E+T, $/+]
      [E→.T, $/+]
      [T→.T*F, $]
      [T→.F, $]
}

先ほどのE→E+Tと同様の考えでT→T*Fという生成規則から、左辺がTの生成規則で*を先読みできることがわかる。また、E→.Tという生成規則は先に述べたA→αBβにおいてβがεであるパターンなので、左辺がEの生成規則において先読みできる記号は左辺がTの生成規則においても先読みできることがわかる。この結果closure({[E'→.E, $]})は以下のように更新できる。

closure({[E'→.E, $]})={
      [E'→.E, $]
      [E→.E+T, $/+]
      [E→.T, $/+]
      [T→.T*F, $/+/*]
      [T→.F, $/+/*]
      [F→.(E), $]
      [F→.i, $]
}

そしてT→Fという生成規則をもとに考えれば、Fが左辺にある生成規則に対しても上記と同様に考えれば先読みできる記号が求まる。この結果新たにclosure({[E'→.E, $]})に追加するものがなくなり、最終的にclosure({[E'→.E, $]})は以下のようになる。

closure({[E'→.E, $]})={
      [E'→.E, $]
      [E→.E+T, $/+]
      [E→.T, $/+]
      [T→.T*F, $/+/*]
      [T→.F, $/+/*]
      [F→.(E), $/+/*]
      [F→.i, $/+/*]
}

こうして出来上がったclosure({[E'→.E, $]})を状態J0として、LR(0)項の時と同様に全てのGOTOを求めることでLR(1)項での状態遷移図を作成することができる。
ちなみにLR(1)項で状態遷移図を作成すると以下のようになる。(J9が2つ存在してしまっているがあまり気にしないように。)
f:id:rei_624:20190627212450j:plain
こうして先読みできる記号を示したことによって、LR(0)構文解析ではシフトするか還元するか不明であった状態I2が状態J2のように次の記号が$または+なら還元すればいいことが先読みでわかる。

まとめ

上向き構文解析→解析木を入力記号列から開始記号の方向へ構築していく解析方法。状態遷移図を元にシフトと還元により解析していく。
LR(0)構文解析→現在のスタックの状態だけでシフトするか還元するかを決定する。
SLR(1)構文解析→Follow集合をもとに還元を定義することで競合を回避できるようにする。回避できない時もある。
LR(1)構文解析→1文字先読みすることでシフトするべきか還元するべきかを一意に決定する。