これはML Advent Calendar 2017の17日目の記事です。
TL;DR
Standard MLで予測型構文解析表を生成できるようにした。
コードはGitHubにある。
詳しいことは文献(プログラミング言語 Standard ML入門, 最新コンパイラ構成技法)を読んでほしい。
Standard ML
Standard MLはML(Meta Language)の一つであり，"The Definition of Standard ML" [1]において定義が記述されている。
言語への入門は「プログラミング言語 Standard ML入門」[2]などが詳しい。
処理系にはStandard ML of New Jersey(SML/NJ)，MLton，Moscow ML，SML#などがある。
どの処理系にも共通してThe Standard ML Basis Libraryというライブラリが実装されており，また処理系固有のライブラリ(例えばSML/NJだとこれ)も存在する。
構文解析
記号と生成文法
記号(symbol)には終端記号(nonterminal symbol)と非終端記号(terminal symbol)がある。
終端記号はこれ以上生成規則により置換されない記号であり，文法のつくる言語のアルファベットとなる。
記号のうち終端記号でないものは非終端記号である。非終端記号は変数とも呼ばれる。
- $N$; 非終端記号(nonterminal symbol)の有限集合
- $T$; 終端記号(terminal symbol)の有限集合
- $\Sigma^*$; $\Sigma$のクリーネ閉包(Kleene closure)，すなわち$\Sigma$の要素の(0回以上の)繰り返しがつくる記号列全体を表す
生成文法(generative grammar)とは生成規則によって作られる文法である。
生成規則は記号列($(N \cup T)^*$)上の二項関係$\rightarrow \subseteq (N \cup T)^* \times (N \cup T)^*$である。
文脈自由文法(Context Free Grammar, CFG)
文脈自由文法(context free grammar)とは生成文法のうち，生成規則の左辺がただ一つの非終端記号からなる文法をいう。
従って，文脈自由文法の生成規則は非終端記号と記号列の二項関係$\rightarrow \subseteq N \times (N \cup T)^*$である。
文脈自由とは，ある非終端記号に対して，文脈(前後関係)を使わずに生成規則を適用できるという意味である。
- $P$; 生成規則(production)の有限集合
- $S$; 開始記号(start symbol) ($S \in N$)
実際に，src/rule.smlでは記号と生成規則を次のように定義した。
datatype Symbol = TerminalSymbol of string
| NonTerminalSymbol of string;
type Rule = Symbol * Symbol list;
導出
文法の生成規則を適用することで，ある終端記号からなる列がある言語に属しているかを判定したい。この判定法には大別して二つの方法がある。
一つは，終端記号列から生成規則を右辺から左辺に向けて繰り返し適用することで，開始記号へ戻ることを確認する再帰的推論(recursive inference)である。
もう一つは，開始記号から生成規則を左辺から右辺に向けて繰り返し適用することで，入力の終端記号の列を得ることができるかを確認する方法である。文法規則をこのように使うことを導出(derivation)という。
導出の過程を記述するために，文脈自由文法$G$に対して，新たな二項関係$\underset{G}{\Rightarrow}$を定義しよう。
文脈自由文法$G=(N, T, P, S)$について，ある生成規則$A \rightarrow \gamma \in P$を考える。
文法$G$において，記号列$\alpha A \beta$から生成規則$A \rightarrow \gamma$を適用して$\alpha \gamma \beta$が導出できることを，二項関係$\alpha A \beta \underset{G}{\Rightarrow} \alpha \gamma \beta$と表すことにする。
(あるいは，$\alpha A \beta \underset{G}{\Rightarrow} \alpha \gamma \beta \overset{\textrm{def}}{\Longleftrightarrow} A \rightarrow \gamma \in P$と定義してもよい。)
さらに，導出を0回以上繰り返し用いて記号列$\alpha$から$\beta$となることを$\alpha \underset{G}{\overset{*}{\Rightarrow}} \beta$と表す。
文脈自由言語
文脈自由文法$G$の生成する言語$L(G)$は開始記号$S$から生成規則を繰り返し用いることで導出される終端記号列全体の集合である。 $$ L(G) = \left\{ w \in T^* \mid ~ S \underset{G}{\overset{*}{\Rightarrow}} w \right\} $$ 文脈自由文法$G$の言語$L(G)$は文脈自由言語(context free language)と呼ばれる。
例示1
文脈自由文法$G_1 = (N, T, P, S)$として次のようなものを考える。
- $N = \left\{ S \right\}$
- $T = \left\{ \textrm{a}, \textrm{b} \right\}$
- $P = \left\{ S \rightarrow \varepsilon, S \rightarrow \textrm{a}S\textrm{b} \right\}$
特に指示がなければ，$\varepsilon$は空列を表す($\left| \varepsilon \right| = 0$)。
val S = NonTerminalSymbol "S";
val non_terminal_symbols = [S];
val a = TerminalSymbol "a";
val b = TerminalSymbol "b";
val terminal_symbols = [a, b];
val rule1 = (S, [a, S, b]);
val rule2 = (S, nil);
val rule_list = [rule1, rule2] : Rule list;
この文法$G_1$の生成する言語$L(G_1)$は$\textrm{a}$を$n$回繰り返した後，同じ回数($n$回)だけ$\textrm{b}$を繰り返す記号列全体の集合$L(G_1) = \left\{ \textrm{a}^n \textrm{b}^n \mid n \geq 0 \right\}$である。
終端記号列$\textrm{aaabbb}$が言語$L(G_1)$に属するかを判定するために，実際に導出過程を記してみる。 $$\begin{align*} S & \underset{G_1}{\Rightarrow} \textrm{a} S \textrm{b} & (S \rightarrow \textrm{a} S \textrm{b}) \\ & \underset{G_1}{\Rightarrow} \textrm{a} \textrm{a} S \textrm{b} \textrm{b} & (S \rightarrow \textrm{a} S \textrm{b}) \\ & \underset{G_1}{\Rightarrow} \textrm{a} \textrm{a} \textrm{a} S\textrm{b} \textrm{b} \textrm{b} & (S \rightarrow \textrm{a} S \textrm{b}) \\ & \underset{G_1}{\Rightarrow} \textrm{a} \textrm{a} \textrm{a} \textrm{b} \textrm{b} \textrm{b} & (S \rightarrow \varepsilon) \end{align*}$$ $S \underset{G_1}{\overset{*}{\Rightarrow}} \textrm{aaabbb}$ゆえ，$\textrm{aaabbb} \in L(G_1)$である。
なお，ある終端記号列$w$が文脈自由文法$G$の生成する言語$L(G)$に含まれるか($w \in L(G)$)を判定する問題をメンバーシップ問題という。この問題はCYK法やEarley法というアルゴリズムで解くことができる。
先程の導出を開始記号を根とする根付き木として表すと下図のようになる。これを導出木(derivation tree)又は構文木(parse tree)という。
例示2 (曖昧な文法)
文脈自由文法$G_2 = (N, T, P, E)$として次のようなものを考える。
- $N = \left\{ E \right\}$
- $T = \left\{ -, x, y, z \right\}$
- $P = \left\{ E \rightarrow E - E, E \rightarrow x, E \rightarrow y, E \rightarrow z \right\}$
val E = NonTerminalSymbol "E";
val non_terminal_symbols = [E];
val minus = TerminalSymbol "-";
val x = TerminalSymbol "x";
val y = TerminalSymbol "y";
val z = TerminalSymbol "z";
val terminal_symbols = [minus, x, y, z];
val rule1 = (E, [E, minus, E]);
val rule2 = (E, [x]);
val rule3 = (E, [y]);
val rule4 = (E, [z]);
val rule_list = [rule1, rule2, rule3, rule4] : Rule list;
開始記号を左辺とする規則が複数あり，開始記号を明確に制限したいときは，新たな非終端記号$S \notin N$を導入して，新たな文法${G_2}' = (N \cup \{ S \}, T, P \cup \{ S \rightarrow E \}, S)$を定義すればよい。この新たな文法${G_2}'$を文法$G_2$の拡大文法(augmented grammar)という。
言語$L(G)$は三つの文字$x$，$y$，$z$をオペランドとする減法($-$)からなる数式を表す記号列全体をなす。
実際，終端記号列$x - y - z$は$L(G_2)$に含まれる。実際$E \overset{*}{\Rightarrow} x - y - z$は，例えば， $$\begin{align*} E & \Rightarrow E - E & (E \rightarrow E - E) \\ & \Rightarrow E - E - E & (E \rightarrow E - E) \\ & \Rightarrow E - y - E & (E \rightarrow y) \\ & \Rightarrow E - y - z & (E \rightarrow z) \\ & \Rightarrow x - y - z & (E \rightarrow x) \end{align*}$$ のように導出できる。文法$G$が明らかな場合は，導出$\underset{G}{\Rightarrow}$を単に$\Rightarrow$で表せる。
ところで，記号列の導出はただ一通りであるとは限らない。
いま，一回の導出$\Rightarrow$によって現れた記号列の最も左にある非終端記号に対して，次の導出を行うことを考えよう。 この方法による導出を先程の終端記号列に対して行うと次のようになる。 $$\begin{align*} E & \Rightarrow E - E & (E \rightarrow E - E) \\ & \Rightarrow x - E & (E \rightarrow x) \\ & \Rightarrow x - E - E & (E \rightarrow E - E) \\ & \Rightarrow x - y - E & (E \rightarrow y) \\ & \Rightarrow x - y - z & (E \rightarrow z) \end{align*}$$ このような導出の方法を最左導出(leftmost derivation)といい，$\overset{*}{\underset{lm}{\Rightarrow}}$と表す。
対して，一回の導出$\Rightarrow$によって現れた記号列の最も右にある非終端記号に対して，次の導出を行うことを考える。 この方法による導出を先程の終端記号列に対して行うと次のようになる。 $$\begin{align*} E & \Rightarrow E - E & (E \rightarrow E - E) \\ & \Rightarrow E - z & (E \rightarrow z) \\ & \Rightarrow E - E - z & (E \rightarrow E - E) \\ & \Rightarrow E - y - z & (E \rightarrow y) \\ & \Rightarrow x - y - z & (E \rightarrow x) \end{align*}$$ このような導出の方法を最右導出(rightmost derivation)といい，$\overset{*}{\underset{rm}{\Rightarrow}}$と表す。
例示2ではじめに上げた導出は最左導出でも最右導出でもない。
一般に導出$S \underset{G}{\overset{*}{\Rightarrow}}\gamma$が存在すれば，それと同等の結果をもたらす最左導出$S \overset{*}{\underset{G,lm}{\Rightarrow}} \gamma$と最右導出$S \overset{*}{\underset{G,rm}{\Rightarrow}} \gamma$がそれぞれ存在する。
上の最左導出と最右導出それぞれに対する導出木は下図のようになる。
このように，文法$G$について少なくとも一つ記号列$w \in L(G)$に対する導出木が2つ以上あるとき，この文法は曖昧(ambiguous)であるという。逆に，任意の記号列$w \in L(G)$について導出木がただ一つに定まるならば，この文法は曖昧でない(unambiguous)という。
従って例示2の文法$G_2$は曖昧である。例示1の文法$G_1$は曖昧ではない。
(注意) 次のような導出を考える。 $$\begin{align*} E & \Rightarrow E - E & (E \rightarrow E - E) \\ & \Rightarrow E - E - E & (E \rightarrow E - E) \\ & \Rightarrow x - E - E & (E \rightarrow x) \\ & \Rightarrow x - y - E & (E \rightarrow y) \\ & \Rightarrow x - y - z & (E \rightarrow z) \end{align*}$$ この導出において，$\class{math-yellow}{E} - E \Rightarrow \class{math-yellow}{E - E} - E$は左辺における左側の$E$に対して生成規則の適用が行われたとする。 すると，この導出は定義より明らかに最左導出である。(紛らわしいが，この導出の導出木は上図で最右導出とした(b)と一致する。)
このように曖昧な文法に対しては最左導出や最右導出が複数存在しえる。 なお，同様に上述の最右導出とは異なった最右導出をつくることができる。 逆に，曖昧でない文法では最左導出も最右導出もそれぞれただ一つに定まる。
例示3 (曖昧でない文法)
文脈自由文法$G_3 = (N, T, P, E)$として次のようなものを考える。
- $N = \left\{ E, I \right\}$
- $T = \left\{ -, x, y, z \right\}$
- $P = \left\{ E \rightarrow E - I, E \rightarrow I, I \rightarrow x, I \rightarrow y, I \rightarrow z \right\}$
val E = NonTerminalSymbol "E";
val I = NonTerminalSymbol "I";
val non_terminal_symbols = [E, I];
val minus = TerminalSymbol "-";
val x = TerminalSymbol "x";
val y = TerminalSymbol "y";
val z = TerminalSymbol "z";
val terminal_symbols = [minus, x, y, z];
val rule1 = (E, [E, minus, I]);
val rule2 = (E, [I]);
val rule3 = (I, [x]);
val rule4 = (I, [y]);
val rule5 = (I, [z]);
val rule_list = [rule1, rule2, rule3, rule4, rule5] : Rule list;
先程の例示2と同様に，$x - y - z \in L(G_3)$である。
この終端記号列に対する最左導出は $$\begin{align*} E & \Rightarrow E - I & (E \rightarrow E - I) \\ & \Rightarrow E - I - I & (E \rightarrow E - I) \\ & \Rightarrow I - I - I & (E \rightarrow I) \\ & \overset{*}{\Rightarrow} x - y - z & (I \rightarrow x, I \rightarrow y, I \rightarrow z) \end{align*}$$ であり，最右導出は $$\begin{align*} E & \Rightarrow E - I & (E \rightarrow E - I) \\ & \Rightarrow E - z & (I \rightarrow z) \\ & \Rightarrow E - I - z & (E \rightarrow E - I) \\ & \Rightarrow E - y - z & (I \rightarrow y) \\ & \overset{*}{\Rightarrow} x - y - z & (E \rightarrow I, I \rightarrow x) \end{align*}$$ となる。 これらの導出は共に右図のような導出木で表される。
この文法$G_3$は曖昧ではない。すなわち，任意の終端記号列$w \in L(G_3)$に対して導出木が一意に定まる。
(従って，先程の終端記号列$x - y- z$に対する最左導出，最右導出はそれぞれ先程挙げた導出一つのみである。)
実際に，算術式としてこれらの記号列を捉えると，減算($-$)が左に結合しており，計算結果も期待通りのものになる。 もし，生成規則$E \rightarrow E - I$を$E \rightarrow I - E$と取り替えると，減算は右結合となり，計算結果も直感とは反することになる。
文脈自由文法上の計算
この後，曖昧でない文脈自由文法よりさらに狭い文法を対象として構文解析(下降型構文解析)を行うための手法について述べる。 そのための準備として，$\textrm{nullable}$(空可能性)，$\textrm{FIRST}$，$\textrm{FOLLOW}$という3つの文法上の関数(実装上はテーブル)を定義し，それらを構成するアルゴリズムを与える。
$\textrm{nullable}[X]$は記号$X$が空列を導出できるか否かを表す。
そして，$\textrm{nullable}(\gamma)$は記号列$\gamma$が空列を導出できるか否かを表す。
今，各記号$X \in (N \cup T)$に対して$\textrm{nullable}[X]$が計算されているとき， $$ \textrm{nullable}(\gamma) = \left\{ \begin{array}{ll} \textrm{true} & (\gamma = \varepsilon) \\ \textrm{nullable}[Y_1] \wedge \textrm{nullable}[Y_2] \wedge \cdots \wedge \textrm{nullable}[Y_k] & (\gamma = Y_1 Y_2 \cdots Y_k) \end{array} \right. $$ と計算できる。
$\textrm{nullable}$の求め方 (src/nullable.sml)
-
はじめに各記号$X \in (N \cup T)$に対して$\textrm{nullable}[X] \leftarrow \textrm{false}$と初期化する。
fun initialize_nullable symbols = List.foldl (fn (symbol, nullable) => Nullable.insert (nullable, symbol, false)) Nullable.empty symbols; -
各生成規則$X \rightarrow \gamma$毎に，
- $\gamma = \varepsilon$ならば，$\textrm{nullable}[X] \leftarrow \textrm{true}$とする。
- $\gamma = Y_1 Y_2 \cdots Y_k$ならば，$\textrm{nullable}[X] \leftarrow \textrm{nullable}[X] \vee\left( \textrm{nullable}[Y_1] \wedge \textrm{nullable}[Y_2] \wedge \cdots \wedge \textrm{nullable}[Y_k] \right)$とする。
fun do_refresh_nullable nullable ((x, nil) : Rule) = Nullable.insert (nullable, x, true) | do_refresh_nullable nullable ((x, ys) : Rule) = let val f = List.all (fn x => x) (List.map (fn y => Nullable.find (nullable, y)) ys); val g = Nullable.find (nullable, x); in Nullable.insert (nullable, x, (f orelse g)) end; -
2.の操作を$\textrm{nullable}$が変化しなくなるまで繰り返し行う。
fun refresh_nullable nullable rule_list = let val new_nullable = List.foldl (fn (rule, hash) => do_refresh_nullable hash rule) nullable rule_list; in if Nullable.equal (op =) (nullable, new_nullable) then new_nullable else refresh_nullable new_nullable rule_list end;
$\textrm{FIRST}[X]$は，記号$X$から導出される終端記号列$w$の最初の記号となれる終端記号の集合である。
そして，$\textrm{FIRST}(\gamma)$は記号列$\gamma$から導出される終端記号列$w$の最初の記号となれる終端記号の集合である。
今，各記号$X \in (N \cup T)$に対して$\textrm{FIRST}[X]$が計算されているとき， $$ \textrm{FIRST}(Y \gamma) = \left\{ \begin{array}{ll} \textrm{FIRST}[Y] & (\textrm{nullable}[Y] = \textrm{true}) \\ \textrm{FIRST}[Y] \cup \textrm{FIRST}(\gamma) & (\textrm{nullable}[Y] = \textrm{false}) \end{array} \right. $$ と計算できる。
$\textrm{FIRST}$の求め方 (src/first.sml)
-
はじめに，各記号$X \in (N \cup T)$毎に，
- $X \in N$ならば，$\textrm{FIRST}[X] \leftarrow \emptyset$
- $X \in T$ならば，$\textrm{FIRST}[X] \leftarrow \{ X \}$
fun initialize_first symbols = List.foldl ( fn (symbol, first) => First.insert ( first, symbol, ( case (symbol) of ( TerminalSymbol s) => SymbolSet.add (SymbolSet.empty, symbol) | (NonTerminalSymbol s) => SymbolSet.empty ) ) ) First.empty symbols; -
各生成規則$X \rightarrow Y_1 Y_2 \cdots Y_k$毎に，
- $k = 0$(つまり，$X \rightarrow \varepsilon$)のとき，何もしない。($\textrm{FIRST}[X] \leftarrow \textrm{FIRST}[X]$)
$k \geq 1$のとき，
各$i \in [1, k]$に対して$\textrm{nullable}(Y_1 Y_2 \cdots Y_{i - 1})$が真ならば $$\textrm{FIRST}[X] \leftarrow \textrm{FIRST}[X] \cup \textrm{FIRST}[Y_i]$$
これはすなわち，$Y_1$から始まる$\textrm{nullable}[Y_i] = \textrm{true} ~ (1 \leq i < j)$を満足する最長部分列$Y_1 Y_2 \cdots Y_{j - 1}$に対して $$\textrm{FIRST}[X] \leftarrow \textrm{FIRST}[X] \cup \left( \textrm{FIRST}[Y_1] \cup \textrm{FIRST}[Y_2] \cup \cdots \cup \textrm{FIRST}[Y_j] \right)$$ とすることと同じである。(ただし，$j - 1 = k$のときは，$\textrm{FIRST}[Y_j] = \emptyset$と約束する。)
この計算は，生成規則$X \rightarrow Y_1 Y_2 \cdots Y_k$の初めの$i -1$個から成る列$Y_1 \cdots Y_{i-1}$が空列を導出する可能性があるならば，非終端記号$X$の最初に現れるような終端記号の集合$\textrm{FIRST}[X]$には記号$Y_i$の最初に現れるような終端記号の集合$\textrm{FIRST}[Y_i]$を部分集合にもつことを表している。
fun do_refresh_first first nullable ((x, ys) : Rule) = let val first_x_set = First.find (first, x); fun subList pred nil = nil | subList pred (y::ys) = if (pred y) then y::(subList pred ys) else [y]; val zs = subList (fn y => Nullable.find (nullable, y)) ys; val first_x_set = List.foldl ( fn (symbol, set) => SymbolSet.union(set, First.find(first, symbol)) ) first_x_set zs; in First.insert (first, x, first_x_set) end -
2.の操作を$\textrm{FIRST}$が変化しなくなるまで繰り返し行う。
fun refresh_first first nullable rule_list = let val new_first = List.foldl ( fn (rule, hash) => do_refresh_first hash nullable rule ) first rule_list; in if First.equal SymbolSet.equal (first, new_first) then new_first else refresh_first new_first nullable rule_list end;
$\textrm{FOLLOW}[X]$は記号$X$の直後に来ることのできる終端記号の集合である。
$\textrm{FOLLOW}$の求め方(src/follow.sml)
-
はじめに各記号$X$毎に，$\textrm{FOLLOW}[X] \leftarrow \emptyset$と初期化する。
fun initialize_follow symbols = List.foldl (fn (symbol, hash) => Follow.insert (hash, symbol, SymbolSet.empty)) Follow.empty symbols; -
各生成規則$X \rightarrow Y_1 Y_2 \cdots Y_k$毎に，
-
各$i \in [1, k]$に対して，$\textrm{nullable}(Y_{i+1} Y_{i+2} \cdots Y_k) = \textrm{true}$であるならば， $$ \textrm{FOLLOW}[Y_i] \leftarrow \textrm{FOLLOW}[Y_i] \cup \textrm{FOLLOW}[X] $$
これはすなわち，$Y_k$で終わる$\textrm{nullable}[Y_j] = \textrm{true} ~ (i < j \leq k)$を満足する最長部分列$Y_{i + 1} Y_{i + 2} \cdots Y_k$に対して $$ \textrm{FOLLOW}[Y_i] \leftarrow \left( \textrm{FOLLOW}[Y_i] \cup \textrm{FOLLOW}[Y_{i + 1}] \cup \cdots \cup \textrm{FOLLOW}[Y_k] \right) \cup \textrm{FOLLOW}[X] $$ とすることと同じである。(関数
refresh_follow_1に相当する。)この計算は，生成規則$X \rightarrow Y_1 Y_2 \cdots Y_k$の最後の$k - i$個からなる列$Y_{i + 1} \cdots Y_k$が空列を導出する可能性があるならば， $Y_i$の直後に来ることのできる終端記号の集合$\textrm{FOLLOW}[Y_i]$は生成規則の左辺である非終端記号$X$の直後に来ることのできる終端記号の集合$\textrm{FOLLOW}[X]$を部分集合としてもつことを表している。
例えば生成規則$W \rightarrow \alpha X \beta$があり，この導出の過程で先程の生成規則$X \rightarrow Y_1 Y_2 \cdots Y_i Y_{i+1} \cdots Y_k$を用いることを考えれば，$Y_i$の直後に来れる終端記号の集合$\textrm{FOLLOW}[Y_i]$は$X$の直後に来れる終端記号の集合$\textrm{FOLLOW}[X]$を部分集合として含む(そして，これはおそらく次のiiの計算から$\textrm{FIRST}(\beta)$となるだろう)ことが直感的に読み取れるだろう。
-
各$i \in [1, k]$，$j \in [i + 1, k]$に対して，$\textrm{nullable}(Y_{i+1} Y_{i+2} \cdots Y_{j - 1}) = \textrm{true}$であるならば， $$ \textrm{FOLLOW}[Y_i] \leftarrow \textrm{FOLLOW}[Y_i] \cup \textrm{FIRST}[Y_j] $$ (関数
refresh_follow_2に相当する。)この計算は，生成規則$X \rightarrow Y_1 Y_2 \cdots Y_k$の右辺の記号列の部分列$Y_{i+1} \cdots Y_{j - 1}$が空列を導出する可能性があるならば，$Y_i$の直後に来ることのできる終端記号の集合$\textrm{FOLLOW}[Y_i]$は，$Y_j$の最初に現れる記号の集合$\textrm{FIRST}[Y_j]$を部分集合として含むことを表している。
fun do_refresh_follow follow first nullable ((x, ys) : Rule) = let fun isNullableList ys = let val zs = List.map (fn y => Nullable.find (nullable, y)) ys; in List.all (fn x => x) zs end and refresh_follow_1 follow ((x, ys) : Rule) = let fun subList v = let val f = fn v => List.tabulate (List.length v, (fn x => x)); val u = List.map (fn n => List.drop (v, n)) (f v); val u = List.map (fn t => (hd t, tl t)) u; in u end; val zs = List.filter (fn (y, ys) => isNullableList ys) (subList ys); val follow = List.foldl ( fn ((y, ys), follow) => Follow.insert ( follow, y, ( SymbolSet.union ( Follow.find (follow, y), Follow.find (follow, x) ) ) ) ) follow zs; in follow end and refresh_follow_2 follow ((x, ys) : Rule) = let fun subList v = let val f0 = fn v => List.tabulate (List.length v, (fn x => x + 0)); val f1 = fn v => List.tabulate (List.length v, (fn x => x + 1)); fun g (x::xs) = let val ys = List.rev xs; val y = List.hd ys; val ys = List.rev (List.tl ys); in (x, ys, y) end; val u = List.map (fn n => List.take (v, n)) (f1 v); val u = List.map (fn v => List.map (fn n => List.drop (v, n)) (f0 v)) u; val u = List.foldl List.@ nil u; val u = List.filter (fn v => List.length v > 1) u; val u = List.map (fn v => g v) u; in u end; val zs = List.filter (fn (x1, ys, x2) => isNullableList ys) (subList ys); val follow = List.foldl ( fn ((x1, ys, x2), follow) => Follow.insert ( follow, x1, ( SymbolSet.union ( Follow.find (follow, x1), Follow.find (first, x2) ) ) ) ) follow zs; in follow end; val follow = refresh_follow_1 follow ((x, ys) : Rule); val follow = refresh_follow_2 follow ((x, ys) : Rule); in follow end; -
-
2.の操作を$\textrm{FOLLOW}$が変化しなくなるまで繰り返し行う。
fun refresh_follow follow first nullable rule_list = let val new_follow = List.foldl ( fn (rule, hash) => do_refresh_follow hash first nullable rule ) follow rule_list; in if Follow.equal SymbolSet.equal (follow, new_follow) then new_follow else refresh_follow new_follow first nullable rule_list end;
再帰降下型構文解析
下降型構文解析(top-down parsing)とは開始記号に対して導出を行うことで，入力として与えられた終端記号列を得ることができるかを調べる方法である。 下降型構文解析の代表的な方法としてLL法がある。
逆に，入力した終端記号列に生成規則を右辺から左辺に向かって適用することで，開始記号を得ることができるかを調べる方法は上昇型構文解析(bottom-up parsing)という。 上昇型構文解析の代表的な方法としてLR法がある。
LL文法もLR文法も曖昧でない文脈自由文法の真なサブクラスである。
再帰降下型構文解析(recursive descent parsing)は下降型構文解析を再帰的な方法(通常は相互再帰的に定義された関数乃至手続き)によって実現する方法である。 この方法では，ある非終端記号を導出する際に，どの生成規則を適用するかを選ぶ必要がある。
生成規則の選び方にはいくつかの手法が存在する。
一つはバックトラックを用いる方法である。 この方法では，可能性のある生成規則を試行し，成功した生成規則を採用する。
もう一つは，トークンを先読みすることで，生成規則が一意に定まる文法を用いる方法である。 このとき，未消費な入力の終端記号列の初め$k$個を読めば，使うべき生成規則が一意に定まるような文法を$\textrm{LL}(k)$文法という。 いくつかのトークンを先読みすれば使うべき生成規則が一意に定まるという意味で，このような構文解析は予測的(predictive)であるという。
予測型構文解析表
曖昧でない文脈自由文法$G = (N, T, P, S)$を考える。 このとき，ある非終端記号$X \in N$と，先読みできる$k$個の終端記号からなる列$t \in T^k$の組$(X, t)$を定めれば生成規則の部分集合$\left\{ X \rightarrow \gamma, \cdots \right\} \subseteq P$を求めることができる。 これを非終端記号$X$を行，終端記号列$t$を列とした表として記述したものを予測型構文解析表(predictive parsing table)という。
ここでは，$\textrm{LL}(1)$文法を念頭に，$|t| = 1$であるような予測型構文解析表を作る。 (もし，$k > 1$なLL文法を解析する場合は，先程の$\textrm{FIRST}$，$\textrm{FOLLOW}$を更に拡張させる必要がある。)
予測型構文解析表を作るために次のようにすればよい。(src/parsing_table.sml)
全ての生成規則$X \rightarrow \gamma \in P$について以下の操作を行う。
- 生成規則$X \rightarrow \gamma$を$X$行の$t \in \textrm{FIRST}(\gamma)$であるような$t$列に加える。(関数
process1に相当する。) - もし$\textrm{nullable}(\gamma) = \textrm{true}$ならば，$X$行の$t \in \textrm{FOLLOW}[X]$を満たす$t$列に加える。(関数
process2に相当する。)
fun do_build_parsing_table nullable first follow parsing_table rule_list symbol = let
val rules = List.filter (fn (x, ys) => x = symbol) rule_list;
fun parsing_table_insert parsing_table key value = let
val old_set = ParsingTable.find (parsing_table, key);
val new_set = RuleSet.add (old_set, value);
in ParsingTable.insert (parsing_table, key, new_set) end;
fun process1 parsing_table rules = let
fun get_first_symbols ys = let
val zs = List.map (fn y => (First.find (first, y), Nullable.find (nullable, y))) ys;
fun do_get_first_symbols nil = SymbolSet.empty
| do_get_first_symbols ((set, flag)::vs) =
if flag
then SymbolSet.union (set, (do_get_first_symbols vs))
else set;
in do_get_first_symbols zs end;
val zs = List.map (fn (x, ys) => ((x, ys), get_first_symbols ys)) rules;
fun q (x, ys) symbols parsing_table =
List.foldl
(fn (symbol, parsing_table) => parsing_table_insert parsing_table (x, symbol) (x, ys))
parsing_table
(SymbolSet.listItems symbols);
val parsing_table =
List.foldl
(fn ((rule, symbols), parsing_table) => q rule symbols parsing_table)
parsing_table
zs;
in parsing_table end;
fun process2 parsing_table rules = let
fun isNullableList ys = Nullable.find (nullable, (hd ys)) handle Empty => true;
val nullable_rules = List.filter (fn (x, ys) => isNullableList ys) rules;
fun q (x, ys) parsing_table = let
val follow_x = Follow.find (follow, x);
val parsing_table =
List.foldl
(fn (symbol, parsing_table) => parsing_table_insert parsing_table (x, symbol) (x, ys))
parsing_table
(SymbolSet.listItems follow_x);
in parsing_table end;
val parsing_table =
List.foldl
(fn ((x, ys), parsing_table) => q (x, ys) parsing_table)
parsing_table
nullable_rules;
in parsing_table end;
val parsing_table = process1 parsing_table rules;
val parsing_table = process2 parsing_table rules;
in parsing_table end;
fun build_parsing_table non_terminal_symbols terminal_symbols rule_list nullable first follow =
List.foldl
(
fn (symbol, parsing_table) =>
do_build_parsing_table
nullable first follow
parsing_table rule_list symbol
)
(initialize_parsing_table non_terminal_symbols terminal_symbols)
non_terminal_symbols;
もし，与えられた文法が$\textrm{LL}(1)$文法ならば，この表の各セルにある生成規則は高々一つである。 逆に，この表が複数の生成規則を含むセルを持つならば，与えられた文法は$\textrm{LL}(1)$文法でない。
例示4 (LL(1)文法ではない文法)
例示3で挙げた，文脈自由文法$G_3 = (N, T, P, E)$を考える。
- $N = \left\{ E, I \right\}$
- $T = \left\{ -, x, y, z \right\}$
- $P = \left\{ E \rightarrow E - I, E \rightarrow I, I \rightarrow x, I \rightarrow y, I \rightarrow z \right\}$
更に，記号列の終端を表す特別な終端記号$\$$を加えた文法$G_4 = (N, T, P, E)$を考える。
- $N = \left\{ E, I \right\}$
- $T = \left\{ -, x, y, z, \$ \right\}$
- $P = \left\{ E \rightarrow E - I \$, E \rightarrow I \$, I \rightarrow x, I \rightarrow y, I \rightarrow z \right\}$
val E = NonTerminalSymbol "E";
val I = NonTerminalSymbol "I";
val non_terminal_symbols = [E, I];
val minus = TerminalSymbol "-";
val x = TerminalSymbol "x";
val y = TerminalSymbol "y";
val z = TerminalSymbol "z";
val dollar = TerminalSymbol "$";
val terminal_symbols = [minus, x, y, z, dollar];
val rule1 = (E, [E, minus, I, dollar]);
val rule2 = (E, [I, dollar]);
val rule3 = (I, [x]);
val rule4 = (I, [y]);
val rule5 = (I, [z]);
val rule_list = [rule1, rule2, rule3, rule4, rule5] : Rule list;
$\textrm{nullable}$，$\textrm{FIRST}$，$\textrm{FOLLOW}$をそれぞれ計算し，予測型構文解析表を作ると次のようになる。
nullable = [E: false, I: false]
FIRST = [E: [x, y, z], I: [x, y, z]]
FOLLOW = [E: [-], I: [$]]
| | | | | |
| | | | | |
| | | | | |
この構文解析表は重複を含むセルが存在する。 従って，この文法$G_4$は$\textrm{LL}(1)$文法ではない。 (すなわち，$k = 1$個のトークンを先読みするだけでは，使うべき生成規則が一意に定まらない。)
例示5 (LL(1)文法)
文脈自由文法$G_5 = (N, T, P, E)$として次のようなものを考える。
- $N = \left\{ E, E', I \right\}$
- $T = \left\{ -, x, y, z, \$ \right\}$
- $P = \left\{ E \rightarrow I E' \$, E' \rightarrow - I E', E' \rightarrow \varepsilon, I \rightarrow x, I \rightarrow y, I \rightarrow z \right\}$
val E = NonTerminalSymbol "E";
val Ed = NonTerminalSymbol "E'";
val I = NonTerminalSymbol "I";
val non_terminal_symbols = [E, Ed, I];
val minus = TerminalSymbol "-";
val x = TerminalSymbol "x";
val y = TerminalSymbol "y";
val z = TerminalSymbol "z";
val dollar = TerminalSymbol "$";
val terminal_symbols = [minus, x, y, z, dollar];
val rule1 = (E, [I, Ed, dollar]);
val rule2 = (Ed, [minus, I, Ed]);
val rule3 = (Ed, nil);
val rule4 = (I, [x]);
val rule5 = (I, [y]);
val rule6 = (I, [z]);
val rule_list = [rule1, rule2, rule3, rule4, rule5, rule6] : Rule list;
$\textrm{nullable}$，$\textrm{FIRST}$，$\textrm{FOLLOW}$をそれぞれ計算し，予測型構文解析表を作ると次のようになる。
nullable = [E: false, E': true, I: false]
FIRST = [E: [x, y, z], E': [-], I: [x, y, z]]
FOLLOW = [E: [], E': [$], I: [$, -]]
| | | | | |
| | | | | |
| | | | | |
| | | | | |
従って，この文法$G_5$は$\textrm{LL}(1)$文法である。
この文法$G_5$を解析するための$\textrm{LL}(1)$パーサは，例えば次のように書ける。
exception ParseError;
fun parse tokens = let
val stack = ["E"];
val (tokens, stack) = parseE tokens stack;
in tokens = nil andalso stack = nil end
and parseE tokens stack = let
val () = if (hd stack) = "E" then () else raise ParseError;
in
case (hd tokens)
of "x" => let
val stack = "I"::"E'"::(tl stack);
val (tokens, stack) = parseI tokens stack;
val (tokens, stack) = parseEd tokens stack;
in (tokens, stack) end
| "y" => let
val stack = "I"::"E'"::(tl stack);
val (tokens, stack) = parseI tokens stack;
val (tokens, stack) = parseEd tokens stack;
in (tokens, stack) end
| "z" => let
val stack = "I"::"E'"::(tl stack);
val (tokens, stack) = parseI tokens stack;
val (tokens, stack) = parseEd tokens stack;
in (tokens, stack) end
| _ => raise ParseError
end
and parseEd tokens stack = let
val () = if (hd stack) = "E'" then () else raise ParseError;
in
(
case (hd tokens)
of "-" => let
val stack = "I"::"E'"::(tl stack);
val tokens = eatToken "-" tokens;
val (tokens, stack) = parseI tokens stack;
val (tokens, stack) = parseEd tokens stack;
in (tokens, stack) end
| _ => raise ParseError
)
handle Empty => (tokens, (tl stack))
end
and parseI tokens stack = let
val () = if (hd stack) = "I" then () else raise ParseError;
in
case (hd tokens)
of "x" => let
val tokens = eatToken "x" tokens;
val stack = tl stack;
in (tokens, stack) end
| "y" => let
val tokens = eatToken "y" tokens;
val stack = tl stack;
in (tokens, stack) end
| "z" => let
val tokens = eatToken "z" tokens;
val stack = tl stack;
in (tokens, stack) end
| _ => raise ParseError
end
and eatToken expect tokens = if (hd tokens) = expect then tl tokens else raise ParseError;
val f1 = parse ["x"];
(* val f1 = true : bool *)
val f2 = parse ["x", "-", "y"];
(* val f2 = true : bool *)
val f3 = parse ["x", "-", "y", "-", "z"];
(* val f3 = true : bool *)
val g = parse ["x", "-"];
(* val g = false : bool *)
ただし，この文法の通りに構文木をつくると減算($-$)が右結合となり，計算結果は直感と反することになる。
例示6
文脈自由文法$G_6 = (N, T, P, S)$として次のようなものを考える。
- $N = \left\{ S, E, E', T, T' F \right\}$
- $T = \left\{ (, ), \textrm{num}, \$ \right\}$
- $P = \left\{ \begin{array}{lll} S \rightarrow E \$, & & \\ E \rightarrow T E', & & \\ E' \rightarrow + T E', & E' \rightarrow - T E', & E' \rightarrow \varepsilon, \\ T \rightarrow F T', & & \\ T' \rightarrow * F T', & T' \rightarrow / F T', & T' \rightarrow \varepsilon, \\ F \rightarrow ( E ), & F \rightarrow \textrm{num} & \end{array} \right\}$
val S = NonTerminalSymbol "S";
val E = NonTerminalSymbol "E";
val Ed = NonTerminalSymbol "E'";
val T = NonTerminalSymbol "T";
val Td = NonTerminalSymbol "T'";
val F = NonTerminalSymbol "F";
val non_terminal_symbols = [S, E, Ed, T, Td, F];
val plus = TerminalSymbol "+";
val minus = TerminalSymbol "-";
val star = TerminalSymbol "*";
val slash = TerminalSymbol "/";
val lparen = TerminalSymbol "(";
val rparen = TerminalSymbol ")";
val num = TerminalSymbol "num";
val dollar = TerminalSymbol "$";
val terminal_symbols = [plus, minus, star, slash, lparen, rparen, num, dollar];
val rule1 = (S, [E, dollar]);
val rule2 = (E, [T, Ed]);
val rule3 = (Ed, [plus, T, Ed]);
val rule4 = (Ed, [minus, T, Ed]);
val rule5 = (Ed, []);
val rule6 = (T, [F, Td]);
val rule7 = (Td, [star, F, Td]);
val rule8 = (Td, [slash, F, Td]);
val rule9 = (Td, []);
val rule10 = (F, [lparen, E, rparen]);
val rule11 = (F, [num]);
val rule_list = [rule1, rule2, rule3, rule4, rule5, rule6, rule7, rule8, rule9, rule10, rule11] : Rule list;
この文法$G_6$は$\textrm{num}$に対する括弧を含む四則演算を実現する。
$\textrm{nullable}$，$\textrm{FIRST}$，$\textrm{FOLLOW}$をそれぞれ計算し，予測型構文解析表を作ると次のようになる。
nullable = [S: false, E: false, E': true, T: false, T': true, F: false]
FIRST = [S: [(, num], E: [(, num], E': [+, -], T: [(, num], T': [*, /], F: [(, num]]
FOLLOW = [S: [], E: [$, )], E': [$, )], T: [$, ), +, -], T': [$, ), +, -], F: [$, ), *, +, -, /]]
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
従って，この文法$G_6$は$\textrm{LL}(1)$文法である。
結論
文脈自由文法の定義から，$\textrm{nullable}$，$\textrm{FRIST}$，$\textrm{FOLLOW}$を計算する手法を紹介し，$\textrm{LL}(1)$文法の予測型構文解析表を構築する方法について述べた。
参考文献
- Robin Milner, Mads Tofte, Robert Harper and David MacQueen. "The Definition of Standard ML (Revised)", The MIT Press, 1997.
http://sml-family.org/sml97-defn.pdf - 大堀淳. "プログラミング言語 Standard ML入門", 共立出版社, 2001.
https://www.amazon.co.jp/dp/4320120248 - John E. Hopcroft, Jeffrey D. Ullman and Rajeev Motwani. "オートマトン 言語理論 計算論 Ⅰ", サイエンス社, 2003.
https://www.amazon.co.jp/dp/4781910262 - Andrew W. Appel. "最新コンパイラ構成技法", 翔泳社, 2009.
https://www.amazon.co.jp/dp/4798114685
