言語処理系のまとめ #2 - 某大学の講義録

前回まで何やったの？

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)文法かどうかを判断することができる。