2018-10-20

はじめに

りーどみー的な

2019-06-26

言語処理系のまとめ #3

前回まで何をやったの？

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β $\in$ closure(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β $\in$ I})
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 $\in$ CとX $\in$ Vに対して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に遷移します。)ただし、状態の名前はスライドと異なるつけ方をしているため、状態遷移図としては参照しないことをおすすめする。(どんな状態遷移図であっても受理するかどうかはわかるのだが)

シフト還元の動き方

例えば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→α.# $\in$ Iiでa $in$ Follow(A)ならばA[li, a]="A→αで還元"とする。
5. S'→S.$ $\in$ Iiであれば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 $\in$ First(β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] $\in$ I})

言葉だけでは実際に理解することは難しいため、実際に手を動かして自分で求めると理解が深まる。以下では例としていつもの文法をもとに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文字先読みすることでシフトするべきか還元するべきかを一意に決定する。

2019-06-24

言語処理系のまとめ #2

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

前回まで何やったの？

rei624.hatenablog.jp

簡単にまとめると
・コンパイラのフロントエンドでは字句解析と構文解析を行っている。
・字句解析には正規表現を用いた。

構文解析

字句解析では生成規則に従ってソースコードから単語を取り出すことができるようになった。しかし、それだけではまだ単語の意味まではわからず、ただのアルファベットの単語の集合のまま。
そこで、単語の順番や予約語のように決まった単語から構文規則をチェックし、内部表現へ変換する。
　→構文解析

文脈自由文法

言語は記号列の組み合わせ規則と考える。
例：<加算式>→<式>+<式>

文脈自由文法は上記のような生成規則の集合Pと開始記号Sの組で定義される。→構文の意味は関係ない。
生成規則の左辺に表れる記号を非終端記号、右辺だけに現れる記号を終端記号という。

非終端記号が残っている：まだなんらかの生成規則を適用できる。
終端記号のみになった：それ以上生成規則は適用できない。

生成規則に出現する記号の集合→語彙

文脈自由文法の例

G = {P, E}
/* Pは生成規則の集合。開始記号は"E"。 */
P={
      E→E+T
      E→T
      T→T*F
      T→F
      F→(E)
      F→<名前>
      F→<数字>
}
/* E,T,Fは右辺にも左辺にも出現→非終端記号 */
/* +,*,(,),<名前>,<数字>は右辺のみに出現→終端記号 */

導出と還元

U→uという生成規則があったとき、v,w,x,yをV*(語彙の任意の並び)として、
v=xUy，w=xuyならばvはwを"直接"導出する(v⇒w)。wはvに直接還元される。

つまり：U→uという生成規則を用いれば一発でv⇒wとなる。

同様に、複数の生成規則を適用してvからwが得られるなら、vはwを導出し、wはvに還元されるという。

解析木

先の文脈自由文法の例に示した生成規則を用いて<数字>+<名前>*<数字>を導出することを考える。

f:id:rei_624:20190623170612p:plain

実際にどう変わっていくのかを文字で示せば、
E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ <数字> + T ⇒ <数字> + T * F
⇒ <数字> + F * F ⇒ <数字> + <名前> * F ⇒ <数字> + <名前> * <数字>
となる。ここで生成規則の適用順序は定めていないことから右端の<数字>を最初に導出しても問題ない。結果として解析木の形は変わらない。

曖昧な文法

上記の<数字>+<名前>*<数字>の例では生成規則の適用順序を変えても解析木は変わらなかったが、生成規則の種類によっては解析木が複数種類存在してしまう。→曖昧な文法という
その場合は、生成規則の優先順位や付帯規則で対処する。

最左導出と最右導出

最左導出 := 最も左の非終端記号に生成規則を適用していく。
　入力記号列と比較していきながら順に生成規則を当てはめていく。
最右導出 := 最も右の非終端記号に生成規則を適用していく。
　入力記号列に対して当てはまるであろう生成規則を試していき、
　最後にそれらの生成規則が文法に適合するかどうかを確認する。

下向き構文解析

下向き構文解析：開始記号列から入力記号列になるように解析木を上から下向きに構築する。
最左導出によるアルゴリズム：LL(1)文法

LL(1)文法

LL(k)文法 := 左から右へトークンをk個先読みしつつ最左導出できる文法のこと
LL(1)文法 := トークンを1つ先読みしつつ最左導出できる文法。
複数の生成規則に対して先読みしたトークンによってどの規則を適用するかを決定できる。

LL(1)文法の定義(形式的)

$G = \{V_N , V_T, P, S\}$ 及び記号列 $\alpha \in (V_N \cup V_T)^*$ と $A \in V_N$ に対して $First(\alpha)$ , $Follow(A)$ を以下のように定義する。
ただし、 $V_N$ は非終端記号の集合、 $V_T$ は終端記号の集合とする。
$First(\alpha)=\{a|a\in V_T, \alpha \overset{*}{\Rightarrow} a \cdots \}$
ただし、 $\alpha\overset{*}{\Rightarrow}ε$ なら $ε \in First(\alpha)$ であり、 $\alpha$ が終端記号なら $First( \alpha )= \alpha$ である。
$Follow(A)=\{a|a \in V_T,S\overset{*}{\Rightarrow} \cdots Aa \cdots \}$ (ただし $ε$ は含めない。(= $ε$ ではなく後述の終端記号$を入れるため。))
さらに $A \rightarrow \alpha$ があるときに $Director(A, \alpha)$ を以下のように定義する。
$Director(A, \alpha) = \{a|a \in V_T, a \in First( \alpha ) \vee ( \alpha \overset{*}{\Rightarrow} ε \land a \in Follow(A))\}$

上記の定義を踏まえて文法Gにおいて任意の $A \in V_N$ と $A$ を左辺に持つ生成規則 $A \rightarrow \alpha_1 | \alpha_2 | \cdots | \alpha_n$ に対して以下の条件が成り立っていれば文法GはLL(1)文法となる。
$Director(A, \alpha_i) \cap Director(A, \alpha_j) = \varnothing , i\not= j$

LL(1)文法の解釈

Firstについて

任意の記号列 $\alpha$ に対して、 $\alpha$ から生成規則を適用することで導出される記号列の中で、先頭に現れる終端記号の集合。このとき、何回生成規則を適用してもよい。 $(=" \overset{*}{\Rightarrow}"$ の定義)そして $\alpha$ から $ε$ が導出できるなら、 $ε$ も $First(\alpha)$ に含める。

Followについて

非終端記号 $A$ に対して、生成規則を適用していった結果 $A$ のすぐ後ろに現れる可能性のある終端記号の集合。ここで、もし $A$ が文の一番後ろに来る可能性がある場合は、文の終了を表す終端記号 $"$"$ も $Follow$ に含める。

Directorについて

生成規則 $A\rightarrow \alpha$ を適用した時に、先頭に現れる可能性のある終端記号の集合。 $\Leftrightarrow$ 基本的には上記の $First(\alpha)$ だが、 $\alpha \overset{*}{\Rightarrow}ε$ の場合は、Aのすぐ後ろに現れる可能性のある終端記号、つまり $Follow(A)$ も含む。
$\beta$ を非終端記号として、
$A \beta \cdots \rightarrow \alpha \beta \cdots \rightarrow \beta \cdots$ を考えれば明らか。

文脈自由文法の例(再掲)

G = {P, E}
P={
      E→E+T
      E→T
      T→T*F
      T→F
      F→(E)
      F→<名前>
      F→<数字>
}

上記の文法の生成規則のE→E+Tのように右辺に複数の文字がある場合は、その一番左の文字だけに注目すればよい(Directorは先頭に来る終端記号の集合であり、またEからεが仮に導出されたとしても+はFollow(E)に含まれているから。)

そして、各生成規則において左辺が同じ記号の生成規則でDirector同士の積集合が= $\varnothing$ )ということは、最初の終端記号だけでどの生成規則を適用すればいいのかが一意に決まるということであり、LL(1)文法であることとなる。

実際にやってみると

上記の文法の例で実際にFirst, Follow, Directorを求めることとする。先に言ってしまうと上記の例は左再帰性を持ち、あいまいな文法であるが今回は気にしない。(あとで左再帰性を持たない方法を述べる)
まずFirstを定義に従って求めてみる。

First(E)={(,<名前>,<数字>}
First(E+T)=First(E)={(,<名前>,<数字>} //Eからεを導出することがないため
First(T)={(,<名前>,<数字>}
First(T*F)=First(T)={(,<名前>,<数字>} //Tからεを導出することがないため
First(F)={(,<名前>,<数字>}
First((E))=First(()={(}
First(<名前>)={<名前>}
First(<数字>)={<数字>}
First(+)={+}
First(*)={*}

次にFollowを定義に従って求めてみる。

Follow(E)={+,),$} //開始記号のFollowには$を入れる。(=一番最初に$が右にある)
Follow(T)={+,*,),$} //生成規則を見るとTが右端のものがあるため$を入れる
Follow(F)={+,*,),$} //生成規則を見るとFが右端のものがあるため$を入れる

求めたFirstとFollowの集合をもとにDirectorを求める。

Director(E,E+T)=First(E+T)={(,<名前>,<数字>}
Director(E,T)=First(T)={(,<名前>,<数字>}
Director(T,T*F)=First(T*F)={(,<名前>,<数字>}
Director(T,F)=First(F)={(,<名前>,<数字>}
Director(F,(E))={(}
Director(F,<名前>)={<名前>}
Director(F,<数字>)={<数字>}

今回はどの記号もεを導出しないため、生成規則の右辺のFirstを考えればよいということになる。
ここで、Director(E,E+T) $\cap$ Director(E,T)={(,<名前>,<数字>}、Director(T,T*F) $\cap$ Director(T,F)={(,<名前>,<数字>}から明らかにこの文法の例はLL(1)文法ではない。

文法を変える

ある生成規則の右辺の先頭がその生成規則の左辺と同じ記号だと困る。
$A\rightarrow A \alpha | \beta$ において、なんとか右辺のAをなくしたい。(ただし、 $\beta$ は $A$ から始まらないものとする)
今回の文法の例でいうと、
$E\rightarrow E+T|T \Leftrightarrow \alpha = +T, \beta = T$
$T\rightarrow T*F|F \Leftrightarrow \alpha = *F, \beta = F$
いつか $A \rightarrow \beta$ を適用すると考えると、 $\beta$ の後ろに $A \rightarrow A\alpha$ を適用した回数だけ $\beta$ の後ろに $\alpha$ が並ぶこととなる。ということはまず先頭に $\beta$ を配置してから $\alpha$ を繰り返すようにしても同じこと。
よって以下の規則で $A\rightarrow A \alpha | \beta$ を書き換えることが可能。
$A\rightarrow A \alpha | \beta$ に対して $A\rightarrow \beta A', A' \rightarrow \alpha A'|ε$
$A$ からはとりあえず $\beta$ のみを出力するように決め、代わりとなる $A'$ から $ε$ が導出されるまで $\alpha$ と $A'$ を導出し続ける。

よって上記の文法を書き換えれば、

G'={P,E}
P={
      E→TE'
      E'→+TE'|ε
      T→FT'
      T'→*FT'|ε
      F→(E)
      F→i /* 以降iは<名前>と<数字>を表していることとする */
}

こうしてできた文法G'で再度First,Follow,Directorを求めてみる。
まずはFirstを求めると、

First(E)={(,i}
First(TE')=First(T)={(,i}
First(E')={+,ε}
First(+TE')=First(+)={+}
First(T)={(,i}
First(FT')=First(F)={(,i}
First(T')={*,ε}
First(*FT')=First(*)={*}
First(F)={(,i}
First((E))=First(()={(}
First(+)={+}
First(*)={*}
First(i)={i}
First(ε)={ε}

となる。そしてFollowは以下のようになる。

Follow(E)={),$}
Follow(E')={),$}
Follow(T)={),+,$}
Follow(T')={),+,$}
Follow(F)={),+,*,$}

上記のFirstとFollowからDirectorは以下のようになる。

Director(E,TE')=First(TE')=First(T)={(,i}
Director(E',+TE')=First(+TE')=First(+)={+}
Director(E',ε)=Follow(E')={),$}
Director(T,FT')=First(FT')=First(F)={(,i}
Director(T',*FT')=First(*FT')=First(*)={*}
Director(T',ε)=Follow(T')={),+,$}
Director(F,(E))=First((E))=First(()={(}
Director(F,i)=First(i)={i}

やるだけ

得られたDirectorを見てみると、
Director(E',+TE') $\cap$ Director(E',ε)= $\varnothing$
Director(T',*FT') $\cap$ Director(T',ε)= $\varnothing$
Director(F,(E)) $\cap$ Director(F,i)= $\varnothing$
であるから、上記の文法G'はLL(1)文法である。

Followを求める際の工夫(メモ)

Followを求めようとすると大抵どこか忘れる。しかし、実際のFollowを求める動作は以下の2種類しかないため、あらかじめFollow同士の関係とFirst、Follow同士の関係をメモしておくことで、間違いを減らすことが可能である(はず)。
1. とりあえず開始記号のFollowに$を入れる
2. $A \rightarrow \alpha B \beta$ という形の生成規則を考える。
　とりあえずFirst( $\beta$ )をFollow(B)に加える。(厳密にはFirst( $beta$ )-{ $ε$ }
　 $\beta \overset{*}{\Rightarrow}ε$ ならFollow(A)をFollow(B)に加える。( $\beta=ε$ も含んでいる)
上記の2種類を全ての生成規則に対して考えればそれ以上Followの値が増えることはなくなるため、あとは実際にその値を満たすようにFollowの集合を求めるだけである。

もちろんそれで間違えることもあるけど・・・その時は諦めよう。

まとめ

構文解析って？→字句解析で切り出した単語をもとに構文規則をチェックし、内部表現に落とし込む。
文脈自由文法→生成規則と開始記号をもった文法。
下向き構文解析→解析木を上から(つまり文脈自由文法の開始記号から)入力記号列になるように構築する。
LL(1)文法→生成規則をもとに、入力記号列を一文字読めばどの生成規則を適用すればいいかがわかる文法。First、Follow、Directorを求めることでその文脈自由文法がLL(1)文法かどうかを判断することができる。

2019-06-06

言語処理系のまとめ #1

正規表現字句解析構文解析

そもそも何を勉強させられているのか

今のところは(5/21現在)
字句解析および構文解析
→コンパイラのフロントエンド部分の処理に使われている。

自分たちの書いたソースコードは機械や機械語に落とし込むコンパイラにしてみればただの文字列に過ぎない。それを適切に切り分けて対応した機械語へと翻訳するために、まずは字句解析および構文解析でソースコードの意味を解析する。
字句解析：ソースコードから単語を切り出す(=今回の記事)
構文解析：字句解析で単語を切り出した後、それらの単語から構文規則をチェックする。ついでに内部表現に落とし込む。(=次回以降の記事)

今回の記事はとりあえず字句解析の部分をまとめます。

字句解析

字句解析の一例
例えば下のようなコードがあった時、

int foo ( int a ) {
    int val ;
    if ( a > 0 ) {
        val = 10 * ( a + 3 ) ;
    } else {
        val = 10 * a + 3 ;
    }
    return val ;
}

字句解析によって以下のように単語(=トークン)毎に分割される。
f:id:rei_624:20190521002825p:plain

そして、これらの字句解析は何らかの規則によって分割するパターンを定義する必要がある。(例えばintやifのようにアルファベット複数の文字からなる単語で分割するようにしないと、i,n,tのようにそれぞれで分割されてしまう。)

字句解析のルール

例：<名前>→<英字>{<英字>|<数字>}*
というルールの時。(記号については後で)<名前>は必ず<英字>で始まり、その後ろに0個以上の<英字>または<数字>を繰り返したものと定義される。

 | := または。今回の場合は<英字>または<数字>
{}* := スター閉包。0個以上の{}内の文字の繰り返し
{}+ := 正スター閉包。1個以上の{}内の文字の繰り返し(==スター閉包からεを除いたもの。)

また、上記の例を状態遷移図で表すと以下の図のようになり、ここでは最終的に2に到達する文字列のみが受理され(=<名前>であった)、それ以外は不受理(=<名前>でなかった)と判断される。

f:id:rei_624:20190604112218p:plain

上記の生成規則を満たす例：waseda、masakari

上記を満たす状態遷移図さえ作ることができれば、字句解析器を自動生成することができる。
→字句の表現方法を定義することで状態遷移表を生成する。(=字句をある規則に従った文字列の集合とみなす。)

正規表現

基本的な用語の定義(一部再掲)

アルファベット
・記号(シンボル)の有限集合→{a, b, c, d}など
記号列
・記号の列(0文字以上の記号の連続)→{a, ab, abcd}など
・一つも記号がない記号列をεとする
集合の積
・A,Bを記号列の集合とした時、ABの集合の積は
　→AB={xy|x $\in$ A, y $\in$ B}
$A^*$ (スター閉包)
・0個以上の{}内の文字の繰り返し
$A^+$ (正スター閉包)
・1個以上の{}内の文字の繰り返し(==スター閉包からεを除いたもの。)

正規表現

詳しくは情報数学のスライドか教科書を見てください(オートマトン・言語理論)
ある記号の有限集合 $\mathit{\Sigma}$ 上の正規表現と定義されるもの
・空集合
・{ε}
・aを $\mathit{\Sigma}$ 中のある1要素としたとき、{a}
・ $R$ 、 $S$ をそれぞれ $\mathit{\Sigma}$ 上の正規表現とした時、以下の3つ
　1. $R|S$
　2. $RS$
　3. $R^*$
あとは上記を有限回繰り返して得られる集合のみが $\mathit{\Sigma}$ 上の正規表現である。

有限オートマトン

決定性有限オートマトンと非決定性有限オートマトン
違い：ε遷移があるかどうか。
　非決定性→ある。決定性→ない。
できること：同じ

オートマトンとは？
与えられた記号列を読みながら、有限個の状態間を遷移しつつ記号列を認識するもの。
つまりは上記の状態遷移図でいうと、それぞれの記号を読みながらそれが<名前>かどうかを判定する機械

ある非決定性有限オートマトンは等価な決定性有限オートマトンにできる。→部分集合構成法とかをGoogleや教科書で調べましょう。

lex(flex)

規則を与えるとそれに応じた字句解析器を自動生成してくれるツール。
なんか今後使うから多少の書き方を知っていると便利。

まとめ

字句解析ってどんなもの？→ある定義を設定してその定義の元ソースコードから単語を切り出す。

2019-05-21

言語処理系のまとめ #0

はじめに

お久しぶりです。前回のアルゴリに引き続きなんとなくまとめたくなったので言語処理系をまとめます。
例のごとく、間違っている可能性や言葉が足りない可能性、僕個人の理解で話しているところや他人から見たら何言ってるのかわからないというところがあるかもしれません。その時はコメントしたりTwitterに直接言ったりしてください、可能であればなんとかします。

また、このまとめでは基本的にスライド配布の部分をメインにする予定です。