うさぎでもわかるコンパイラ　第3羽　First・Follow・Director集合とLL(1)文法の判定

こんにちは、ももやまです。

コンパイラ（言語処理系）の勉強をしていると、

• LL(1)文法
• First集合
• Follow集合
• Director集合

などの不思議な用語が出てきますよね。しかも、これらの定義（特にFirst集合やFollow集合）の定義は少し難解です。

文法 $G=(V_N,V_T,P,S)$に関して、記号列 $\alpha \in (V_N\cup V_T{)}^{\ast }$、非終端記号 $A\in V_T$ について、$\mathrm{First}(\alpha )$, および $\mathrm{Follow}$ は次のように定義される。$$\mathrm{First}(\alpha )=\{a\mid a\in V_T,\alpha \stackrel{\ast }{\Rightarrow }a\cdots \}$$$$\mathrm{Follow}(A)=\{a\mid a\in V_T,S\stackrel{\ast }{\Rightarrow }\cdots Aa\cdots \}$$ただし $\alpha \stackrel{\ast }{\Rightarrow }\epsilon$ なら $\epsilon \in \mathrm{First}(\alpha )$ とする。

コンパイラ補助資料　佐々木晃 より

そこで今回は、

• LL(1)文法とはそもそも何か？
• First, Follow, Director集合を求めて何がうれしいのか
• First, Follow, Director集合の求め方

の3点を中心に、LL(1)文法とFirst・Follow・Director集合のお勉強をしていきましょう。

スポンサードリンク

1. LL(1)文法とは

ある文字列 $\alpha$ が文法規則を満たすかどうかを一番単純に調べる方法は、下のように「出発記号 $S$ から変換規則を総当たりで試していき、試した中に $\alpha$ が含まれるか」を調べることです。

しかし、やみくもに総当たりで試す方法は、処理的にかなり無駄が発生してしまいます^[1] … Continue reading。

そこで、構文解析をする際に1文字だけ先読みし、どの生成規則を使えばよいかを決めてから実際に変換していく方法が考えられました。

このように、1文字だけ先読みすれば、文字列を後戻りすることなく構文解析ができる（文法を満たすか確認できる）文法からなる文法のことをLL(1)文法と呼びます^[2] … Continue reading。

LL(1)文法とは言えない文法（＝1文字だけ先読みするだけでは文字列を後戻りせずに構文解析ができない）文法の例も見てみましょう。

例えば、非終端記号（かつ出発記号） $S$、終端記号 $a$, $b$、生成規則$$S\to aaS,S\to abS,S\to b$$からなる文法規則があるとします。

この文法規則に $abab$ という文字列が当てはまるかどうかを1文字先読みで見ていきましょう。

しかし、1文字目 $a$ が出てくる生成規則には、

• $S\to aaS$
• $S\to abS$

の2つがあるため、1文字先読みしただけでは $S\to aaS$, $S\to abS$ どちらの生成規則を適用すればいいかわかりません。

この例から分かる通り、LL(1)文法かどうかは文法の生成規則のみで決まります。

ここで、LL(1)文法を満たす生成規則であるかを機械的に確認する手法として導入されたのがFirst・Follow・Director集合という概念なのです！

つぎの第2章からは、

• 実際にFirst, Follow, Director集合の求め方の解説
• なぜ機械的にLL(1)文法を満たすのかがわかるのか

の2点について解説していきます。

スポンサードリンク

2. First集合

(1) First 集合とはなにか

First集合 $\mathrm{First}(\alpha )$ は、「ある文字列 $\alpha$ に対して生成規則を適用して（複数回適用OK）全て終端記号にした際に、先頭（1文字目）に出てくる可能性がある文字を集めた集合」を表します。

数式で書くと、$$\mathrm{First}(\alpha )=\{a\mid a\in V_T,\alpha \stackrel{\ast }{\Rightarrow }a\cdots \}$$となります。（色部分を日本語の説明に対応させています）

例えば、$\mathrm{First}(\alpha )=\{a,b,c\}$ の場合、$\alpha$ に生成規則を適用していった際に出来る文字列の先頭（1文字目）が $a$, $b$, $c$ のいずれかであることを表します。

(2) First 集合で頭にいれておくべき公式

※ 公式を丸暗記するのではなく、理屈を理解してから頭に入れましょう。

規則1[R1] First(a) … 終端記号1文字 $a$ の場合

終端記号 $a$ は、これ以上生成規則を適用することが出来ない文字を表すのでしたね。そのため、$a$ はどう頑張っても他の文字に変換されることはありません。

よって、終端記号1文字 $a$ のFirst集合の要素は終端記号 $a$ だけとなります。$$\mathrm{First}(a)=a$$※ 空文字 $\epsilon$ のFirst集合は、$\mathrm{First}(\epsilon )=\{\epsilon \}$ となります。言い換えると、$\mathrm{First}(\alpha )=\{\epsilon \}$ は、$\alpha$ が空文字であることを表します。

※ 以後、この規則を用いた変換をする場合は $\stackrel{\mathrm{R}1}{=}$ と = の上にR1（規則1）を用いていることを示します。

規則2[R2] First(A) … 非終端記号1文字の場合

非終端記号 $A$ のFirst集合 $\mathrm{First}(A)$ を求める際、下のように樹形図を書いていって先頭1文字目に出てる文字を地味に探しても正しい答えは出てきますが、列挙ミスが発生する場合があります。

なのでもう少し機械的に $\mathrm{First}(A)$ を求めてみましょう。

例えば、$A\to BC$ という生成規則があったとします。これを言い換えると、「$BC$ に対して生成規則を適用し、すべて終端記号に変換した際に出てくる文字列」は、必ず「$A$ に対して生成規則を適用し、すべて終端記号に変換した際に出てくる文字列」 として出てきますね。

言い換えると、「$BC$ に生成先を適用してすべて終端記号にした際に出てくる先頭文字 $\mathrm{First}(BC)$ の集合」の要素に、「$A$ に生成先を適用してすべて終端記号にした際に出てくる先頭文字 $\mathrm{First}(A)$ の集合」が含まれますね。

つまり、 $\mathrm{First}(A)$ を機械的に求める手順としては、$A$ から生成規則 $A\to \alpha$, $A\to \beta$, … を探していき、その生成先の文字列 $\alpha$, $\beta$, … のFirst集合 $\mathrm{First}(\alpha )$, $\mathrm{First}(\beta )$ の要素をすべてFirst集合 $\mathrm{First}(A)$ の要素とすればOKです。

1つ例を見てみましょう。$A$ から始まる生成規則 $A\to \epsilon$, $A\to aB$, $A\to Cb$ が3つあったとします。

この場合、$\mathrm{First}(A)$ の要素は、$\mathrm{First}(\epsilon )$, $\mathrm{First}(aB)$, $\mathrm{First}(Cb)$ の和$$\mathrm{First}(A)=\underset{A\to \epsilon }{\underbrace{\mathrm{First}(\epsilon )}}\cup \underset{A\to aB}{\underbrace{\mathrm{First}(aB)}}\cup \underset{A\to Cb}{\underbrace{\mathrm{First}(Cb)}}$$となります。

ここで1点注意が必要です非終端記号 $A$ から空文字 $\epsilon$ が生成される可能性があるときには、$\mathrm{First}(A)$ の要素に $\epsilon$ が加わる点に注意してください。

※ 以後、この規則を用いた変換をする場合は $\stackrel{\mathrm{R}2}{=}$ と = の上にR2（規則2）を用いていることを示します。

規則3[R3] First(αβ…) … 2文字以上の場合

First集合は、「文字列に生成規則を加えて全て終端記号にした際に、先頭に来る可能性がある終端記号」を表しているのでしたね。

そのため、（First集合を求めるだけであれば）最初の1文字さえわかってしまえば、（最初の1文字が空文字とはならない限り）残りの後ろは何が来ようが関係ありません。

よって、文字列 $\alpha \beta \cdots$ のFirst集合 $\mathrm{First}(\alpha \beta \cdots )$ は、$\alpha$ に空文字が来ない限り（＝ $\epsilon \notin \mathrm{First}(\alpha )$ の場合）は $\mathrm{First}(\alpha )$ と等しくなります。

一方、$\alpha$ に空文字が来る可能性があるとき（＝ $\epsilon \in \mathrm{First}(\alpha )$ の場合）は、2文字目が先頭になる可能性があるため、1文字目に加えて2文字目 $\beta \cdots$ の先頭文字 $\mathrm{First}(\beta \cdots )$ も追加で調べます。つまり、$$\mathrm{First}(\alpha \beta \cdots )=(\mathrm{First}(\alpha )-\{\epsilon \})\cup \mathrm{First}(\beta \cdots )$$が成立します。

※ $\epsilon$ を引いた理由は、2文字目 $\beta$ の先頭に空文字 $\epsilon$ が来ない場合、文字列 $\alpha \beta \cdots$ に $\beta$ の文字列が残り、文字列 $\alpha \beta \cdots$ が空文字 $\epsilon$ になることはないからです。

まとめると、2文字以上の文字列 $\alpha \beta \cdots$ のFirst集合 $\mathrm{First}(\alpha \beta \cdots )$ は、$$\mathrm{First}(\alpha \beta \cdots )=\{\begin{array}{cc}\mathrm{First}(\alpha )& \epsilon \notin \mathrm{First}(\alpha )\\ (\mathrm{First}(\alpha )-\{\epsilon \})\cup \mathrm{First}(\beta \cdots )& \epsilon \in \mathrm{First}(\alpha )\end{array}$$で求めることができます。

※ 以後、この規則を用いた変換をする場合は $\stackrel{\mathrm{R}3}{=}$ と = の上にR3（規則3）を用いていることを示します。

注意: 左再帰 A → Aα が含まれる場合のFirst集合

$A\to Abc$ のように「生成先の文字列の先頭が生成元の文字列になっている」場合、First集合を求めていくと$$\begin{array}{rl}\mathrm{First}(A)& \stackrel{\mathrm{R}2}{=}\mathrm{First}(Abc)\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(A)\end{array}$$となり、求めたい集合 $\mathrm{First}(A)$ が計算途中に出てくるというよくわからないことが起こります。

この形になった場合は、計算途中に出てくる $\mathrm{First}(A)$ は無視してOKです。例えば、$$\mathrm{First}(A)=\underset{\mathrm{無}\mathrm{視}}{\underbrace{\mathrm{First}(A)}}\cup \mathrm{First}(b)$$となった場合は、左辺にも右辺にも出てくる $\mathrm{First}(A)$ を無視し、$$\mathrm{First}(A)=\mathrm{First}(b)$$として計算してください^[3] $A\to Ab$ のように左再帰文法となる規則を適用しても、先頭文字列は $A$ のまま変わらないため、無視しても問題ない。。

また、$$A\to Bb,B\to Aa,A\to c$$のように、見た目に左再帰になる生成規則は含まれてはいないものの、変形していくと、$$A\to Bb\to Aab$$のように間接的に左再帰の形が出てくる場合、$$\begin{array}{rl}\mathrm{First}(A)& =\mathrm{First}(B)\cup \mathrm{First}(c)\\ \mathrm{First}(B)& =\mathrm{First}(A)\end{array}$$のように、一意には答えを決定できないような形が出てくることがあります。

しかし、左再帰になる規則の部分だけに着目してみると、$\mathrm{First}(A)=\mathrm{First}(B)$, $\mathrm{First}(B)=\mathrm{First}(A)$ 以外の式が出てこず、特に新しい要素が足される気配（例えば $\mathrm{First}(c)$ はありません。

そのため、間接的な左再帰が出てきた際（＝一意に答えが決定できないような形が出てきた場合）には、間接的な左再帰が出てくる式（例えば $A\to Bb$, $B\to Aa$）をすべて無視し、残りの生成規則からFirst集合を求めてください。ただし、間接的な左再帰に寄与している非終端記号（今回の例だと $A$, $B$）同士のFirst集合は等しくなる点は忘れないでください。

今回の場合は、$A\to Bb$, $B\to Aa$, $A\to c$ のうちの赤文字部分が間接的な左再帰なため、まずは間接的な左再帰とは関係ない生成規則 $A\to c$ から$$\begin{array}{rl}\mathrm{First}(A)& \stackrel{\mathrm{R}1}{=}\mathrm{First}(c)\\ & =\{c\}\end{array}$$と求めます。さらに、間接的な左再帰に寄与している $A$, $B$ のFirst集合は等しくなるため、$$\mathrm{First}(B)=\mathrm{First}(A)=\{c\}$$と求めることができます^[4]いったん\[\begin{align*}\mathrm{First} (A) & = \mathrm{First} (B) \cup \mathrm{First} (c)\ & = \underbrace{ \mathrm{First} (A) }_{ \mathrm{無視} } \cup \mathrm{First} (c)\ & = … Continue reading。

(3) 例題で確認！

ここからは、1題例題を実際に解いてみましょう。

解説の前に、First集合を求める手順について確認しておきましょう。

First(S) の求め方

$S$ が生成元になる規則は、$S\to aA$ ただ1つですね。

そのため、$$\begin{array}{rl}\mathrm{First}(S)& \stackrel{\mathrm{R}2}{=}\underset{S\to aA}{\underbrace{\mathrm{First}(aA)}}\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(a)\\ & \stackrel{\mathrm{R}1}{=}\{a\}\end{array}$$で計算できます。

First(A) の求め方

$A$ が生成元になる規則は、$A\to bBa|\epsilon$、つまり $A\to bBa$ と $A\to \epsilon$ の2つですね。

そのため、$$\begin{array}{rl}\mathrm{First}(A)& \stackrel{\mathrm{R}2}{=}\underset{A\to bBa}{\underbrace{\mathrm{First}(bBa)}}\cup \underset{A\to \epsilon }{\underbrace{\mathrm{First}(\epsilon )}}\end{array}$$を求めればＯＫです。

ここで、それぞれのFirst集合は、$$\begin{array}{rl}\mathrm{First}(bBa)& \stackrel{\mathrm{R}3}{=}\mathrm{First}(b)\\ & \stackrel{\mathrm{R}1}{=}\{b\}\end{array}$$$$\begin{array}{rl}\mathrm{First}(\epsilon )& \stackrel{\mathrm{R}1}{=}\{\epsilon \}\end{array}$$となるため、求めたいFirst集合は$$\begin{array}{rl}\mathrm{First}(A)& \stackrel{\mathrm{R}2}{=}\mathrm{First}(bBa)\cup \mathrm{First}(\epsilon )\\ & =\{b\}\cup \{\epsilon \}\\ & =\{b,\epsilon \}\end{array}$$と計算できます。

First(B) の求め方

$B$ が生成元になる規則は、$B\to Sc|d$、つまり $B\to Sc$ と $B\to d$ の2つですね。

そのため、$$\begin{array}{rl}\mathrm{First}(B)& \stackrel{\mathrm{R}2}{=}\underset{B\to Sc}{\underbrace{\mathrm{First}(Sc)}}\cup \underset{B\to d}{\underbrace{\mathrm{First}(d)}}\end{array}$$を求めればＯＫです。

ここで、それぞれのFirst集合は、$$\begin{array}{rl}\mathrm{First}(Sc)& \stackrel{\mathrm{R}3}{=}\mathrm{First}(S)\\ & \stackrel{(1)}{=}\{a\}\end{array}$$$$\begin{array}{rl}\mathrm{First}(d)& \stackrel{\mathrm{R}1}{=}\{d\}\end{array}$$となるため、求めたいFirst集合は$$\begin{array}{rl}\mathrm{First}(B)& \stackrel{\mathrm{R}2}{=}\mathrm{First}(Sc)\cup \mathrm{First}(d)\\ & =\{a\}\cup \{d\}\\ & =\{a,d\}\end{array}$$と計算できます。

※ $\stackrel{(1)}{=}$ は、(1)の答え $\mathrm{First}(S)=\{a\}$ を使っていることを表しています。

スポンサードリンク

3. Follow集合

(1) Follow 集合とはなにか

Follow集合 $\mathrm{Follow}(A)$ は、「ある非終端記号1文字 $A$ 以降の文字をの直後に来る可能性がある文字（終端記号）の候補を集めた集合」を表します。

数式で書くと、$$\mathrm{Follow}(A)=\{a\mid a\in V_T,\alpha \stackrel{\ast }{\Rightarrow }\cdots Aa\cdots \}$$となります。（色部分を日本語の説明に対応させています）

例えば、$\mathrm{Follow}(A)=\{a,b\}$ の場合、$A$ の後ろの文字列をすべて終端記号にした際、$A$ の直後に来る文字列が $a$, $b$ のいずれかであることを表します。

1点注意が必要なのは、Follow集合の要素に「空文字 $\epsilon$」が出てくることは絶対にありません。

その代わりに、「$A$ の直後に来る文字はありません（＝$A$ が文字列の終端になりますよ）」というのを表す記号 $\mathrm{\$}$ がFollow集合の要素で使われます。

(2) Follow 集合で頭にいれておくべき3つの公式

各非終端記号に対してFollow集合を求めていくときには、公式1～公式3で出てきた要素すべての和を取ることで求めます。

そこで、この「(2) Follow集合で頭にいれておくべき3つの公式」では、公式1～公式3の式の紹介だけでなく、何故この式でFollow集合が求められるのかまで説明していきます。

公式1. 出発記号 S の直後は必ず文字列の終端 $

文脈自由文法では、下のようにどの文字列も出発記号 $S$ から与えられた生成規則により変換されていき、導出されます。$$S\stackrel{S\to AaB}{\to }AaB\stackrel{A\to aA}{\to }aAaB\stackrel{A\to a}{\to }aaaB\stackrel{B\to b}{\to }aaab$$

そのため、出発記号の後ろは必ず文字列の終端となりますね。

そのため、最初に出発記号に対するFollow集合 $\mathrm{Follow}(S)$ に対しては、文字列の終端を表す $\mathrm{\$}$ を要素に追加します。$$\mathrm{Follow}(S)+=\{\mathrm{\$}\}$$

※1: 出発記号ではない非終端記号に対しては何もしなくてOKです。
※2: $X+=Y$ は、（集合 $X$ に含まれない）集合 $Y$ の要素を集合 $X$ に加えることを表します。数式で書くと、$X=X\cup Y$ です。

公式2. 直後の文字が空文字にならない場合

Follow集合は、「ある非終端記号の直後に来る（終端記号の）文字の候補」を表すため、Follow集合を求める際には、まずは生成規則の生成元ではなく、生成先側の文字列に着目します。

例えば、$S\to aAcB$ という規則があったとします。この規則を適用すると、$A$ の直後には必ず $cB$ という文字が来ますよね。

このように、$S\to aAcB$ のような求めたい非終端記号 $A$ が生成されている規則を見つけ、その直後に来る文字（今回は $c$）を見つけ出す（＋非終端記号であれば終端記号に変換する）ことでFollow集合を求められそうですね。

もう少し一般化して、$\mathrm{Follow}(A)$ の求め方を公式化していきましょう。

まず、求めたい非終端記号 $A$ が生成されている規則を探し出し、生成先の文字列を $A$ より前にある文字列 $\alpha$ と $A$ より後ろにある文字列 $\beta$ に分け、$S\to \alpha A\beta$ の形にします。

例えば、$S\to aAcB$ であれば、$$S\to \underset{\alpha }{\underbrace{a}}A\underset{\beta }{\underbrace{cB}}$$より、$\alpha =a$, $\beta =cB$ となります。

※1 $\alpha$ はFollow集合の計算ではいらない子なので、求めなくてもOK。
※2 $\alpha$, $\beta$ に空文字が来てもOK。例えば、$S\to aA$ であれば、$\alpha =a$, $\beta =\epsilon$ となる。

ここで、$\mathrm{Follow}(A)$ というのは、$A$ の直後に出てくる文字列でしたね。

また、先ほど生成規則を $S\to \alpha A\beta$ と書き換えましたね。つまり、「 $A$ の直後に出てくる文字列」というのは、「$\beta$ の先頭に来る文字列」と言い換えることができますね。さらにもう1段階言い換えると、「$\beta$ の先頭に来る文字列」は $\mathrm{First}(\beta )$ と書くことができますね。

そのため、生成規則 $S\to \alpha A\beta$ に対して、Follow集合に$$\mathrm{Follow}(A)+=\mathrm{First}(\beta )$$と $\mathrm{First}(\beta )$ を追加します。

ただし、First集合の要素に $\epsilon$ が含まれる場合は、$\epsilon$ を無視してからFollow集合に追加してください。例えば、$S\to \alpha A\beta$ に対して、$\mathrm{First}(\beta )=\{b,c,\epsilon \}$ であれば、$$\begin{array}{rl}\mathrm{Follow}(A)+& =\mathrm{First}(\beta )\\ & =\{b,c\}\end{array}$$と、Follow集合に $b$, $c$ の要素を加えます。そのため、$S\to \alpha A$ のように $A$ の直後の文字列 $\beta$ がそもそも存在しない場合は、この公式でFollow集合の追加は行われません^[6]$\beta$ がそもそも存在しない、つまり $\beta =\epsilon$ のときは、\( \mathrm{First} ( \beta ) = \mathrm{First} ( \varepsilon )  \overset{ \mathrm{R1} }{=} \{ … Continue reading。

さらに、$\mathrm{First}(\beta )$ に $\epsilon$ が含まれる（＝ $\beta$ が空文字になる可能性がある）場合や、$S\to \alpha A$ のように、 そもそも $A$ が生成先の文字列の末尾になる場合は公式2を確認します。

公式3. 直後の文字が空文字になる可能性がある場合

生成規則 $S\to \alpha A\beta$ において、

• $\beta$ 部分がそもそも存在しない
  （つまり $A\to \alpha A$ となるとき）
• $\beta$ 部分が存在していた場合でも $S\to \alpha \alpha AB$, $B\to \epsilon$ のように $\beta$ に空文字が来る可能性がある場合
  （つまり $\epsilon \in \mathrm{First}(\beta )$ となる場合）

は、生成先 $\alpha A\beta$ に着目するだけでは、$A$ の直後に来る文字列（＝ $\mathrm{Follow}(A)$）がわかりません。

ここで、$S$ の直後の文字を $X$ としてから、$SX$ に生成規則 $S\to aA$ を適用することを考えましょう。すると、$$SX\to aAX$$となり、「$A$ の直後の文字」が「$S$ の直後の文字」と同じになっていることがわかりますね。

つまり、$S\to \epsilon \in \mathrm{First}(\beta )$ 、つまり $\beta$ 部分が空文字になる（つまり $S\to aA$ となる）可能性がある場合は$$\mathrm{Follow}(A)+=\mathrm{Follow}(S)$$と、生成元 $S$ の非終端記号の直後の文字、つまり $\mathrm{Follow}(S)$ を $\mathrm{Follow}(A)$ に追加します。

注意: 右再帰 A → αAが含まれる場合

$A\to abA$ のように「生成先の文字列の終端が生成元の文字列になっている」生成規則の場合、$$\begin{array}{rl}\mathrm{Follow}(A)+& =\mathrm{Follow}(A)\\ & =\mathrm{Follow}(A)\cup \mathrm{Follow}(A)\end{array}$$となるため、$\mathrm{Follow}(A)$ に要素が一切追加されません。

そのため、右再帰 $A\to \alpha A$ となる文法に対しては、Follow集合を求める際には無視してください。

特に注意が必要なのが、$$A\to aB,B\to bA$$のように見た目は右再帰な規則は含まれていないものの、変形してみると$$A\to aB\to abA$$のように間接的に右再帰な規則が含まれる場合です。

この場合、生成規則 $A\to aB$ に対しては$A\to aB$ より$$\begin{array}{rl}\mathrm{Follow}(B)+& =\mathrm{Follow}(A)\\ & =\mathrm{Follow}(B)\cup \mathrm{Follow}(A)\end{array}$$が成立するため、$\mathrm{Follow}(B)$ に対して、$\mathrm{Follow}(A)$ の要素を追加されるような式が出てきます。

さらに、$\mathrm{Follow}(A)$ を求めていきましょう。$B\to bA$ より$$\begin{array}{rl}\mathrm{Follow}(A)+& =\mathrm{Follow}(B)\\ & =\mathrm{Follow}(A)\cup \mathrm{Follow}(B)\end{array}$$ なり、$\mathrm{Follow}(A)$ に対して $\mathrm{Follow}(B)$ を追加するような式が出てきます。

すると、

• $\mathrm{Follow}(A)$ を求めるためには追加される要素である $\mathrm{Follow}(B)$ を求める必要がある
• $\mathrm{Follow}(B)$ を求めるためには追加される要素である $\mathrm{Follow}(A)$ を求める必要がある

という「無限ループ」が発生し、訳が分からないことが起こってしまいます。

ここで、式ではなく意味的に考えてみましょう。ある非終端記号 $A$ Follow集合 $\mathrm{Follow}(A)$ とは、「$A$ の直後に来る非終端記号の候補を集めた集合」でしたね。

そこで、ある非終端記号 $A$ を間接的な右再帰規則 $A\to aB$, $B\to bA$ だけで変換していくことで、Follow集合がどうなるかを見てみましょう。

すると、$A\to aB$ の変化から、$A$ の直後の非終端記号（$\mathrm{Follow}(A)$）と $B$ の直後の非終端記号（$\mathrm{Follow}(B)$ には変化がないことがわかりますね。また$aB\to abA$ の変化から、$B$ の直後の非終端記号（$\mathrm{Follow}(B)$）と $A$ の直後の非終端記号（$\mathrm{Follow}(A)$ にも変化がないことがわかりますね。

よって、$A\to aB$, $B\to bA$ のような間接的な右再帰規則が含まれている場合、Follow集合に追加されるような要素は存在しないこと、および $\mathrm{Follow}(A)$, $\mathrm{Follow}(B)$ が等しくなることがわかりますね^[7]$A\to aB$ より、\[\begin{align*}\mathrm{Follow} ( \textcolor{magenta}{B} ) + & = \mathrm{Follow} ( \textcolor{magenta}{A} )\ & = … Continue reading。

そのため、Follow集合を求める際には、直接的な右再帰規則 $A\to \alpha A$ だけでなく、間接的な右再帰規則 $A\to aB$, $B\to bA$ が含まれている場合（＝一意に答えが決定できないような形が出てきた場合）でも、間接的な左再帰が出てくる式（例えば $A\to aB$, $B\to bA$ ）をすべて無視し、残りの生成規則からFollow集合を求めてください。ただし、間接的な左再帰に寄与している非終端記号（今回の例だと $A$, $B$）同士のFirst集合は等しくなる点は忘れないでください。

(3) 例題で確認！

ここからは、例題1でも出てきた文法を使って、実際にFollow集合を求め方を見ていきましょう。

解説の前に、もう1度Follow集合を求める手順について確認しておきましょう。

(1) Follow(S) の求め方

まず、$S$ は出発記号なので、初期状態として要素 $\mathrm{\$}$ を加えます。

つぎに、$S$ が生成先に出てくる規則は、$B\to Sc$ 1つだけなので、この生成規則に着目しましょう。

着目した生成規則の生成先 $Sc$ において、$S$ より後の文字列は $c$ ですね。よって、$\beta =c$ となります。

[公式2] $\beta =c\ne \epsilon$ なので〇

生成規則 $B\to S\underset{\beta }{\underbrace{c}}$ より、$\mathrm{Follow}(S)$ に追加される要素は、$$\begin{array}{rl}\mathrm{Follow}(S)+& =\mathrm{First}(c)-\{\epsilon \}\\ & \stackrel{\mathrm{R}1}{=}\{c\}-\{\epsilon \}\\ & =\{c\}\end{array}$$と求められます。よって、$\mathrm{Follow}(S)$ に $c$ が追加されます。

[公式3] $\epsilon \notin \mathrm{First}(c)=\{c\}$ なので×

よって、$$\begin{array}{rl}\mathrm{Follow}(S)& =\{\$\}\cup \{c\}\\ & =\{c,\mathrm{\$}\}\end{array}$$となります。

(2) Follow(A) の求め方

[公式1] $A$ は出発記号ではないため×

つぎに、$A$ が生成先に出てくる規則は、$S\to aA$, $A\to bBA$ の2つがありますが、$A\to bBA$ は右再帰なので無視します。そのため、[公式2], [公式3] に当てはめる生成規則は $S\to aA$ だけでOKです。

着目した規則の生成先 $aA$ において、$A$ より後の文字列はありません（＝空文字です）ね。よって、 $\beta =\epsilon$ です。

[公式2] $\beta =\epsilon$ なので×

[公式3] $\epsilon \in \mathrm{First}(\epsilon )=\{\epsilon \}$ なので〇

生成規則 $S\to aA$ より、$\mathrm{Follow}(A)$ に追加される要素は、

$$\begin{array}{rl}\mathrm{Follow}(A)+& =\mathrm{Follow}(S)\\ & \stackrel{(1)}{=}\{c,\mathrm{\$}\}\end{array}$$と求められます。よって、$\mathrm{Follow}(A)$ に $c,\mathrm{\$}$ が追加されます。

したがって、$\mathrm{Follow}(A)$ は$$\begin{array}{rl}\mathrm{Follow}(A)& =\{c,\mathrm{\$}\}\end{array}$$と計算できます。

(3) Follow(B) の求め方

[公式1] $B$ は出発記号ではないため×

ここで、$B$ が生成先に出てくる規則は、$A\to bBA$ の1つだけですね。なので [公式2], [公式3] に当てはめる生成規則は $A\to bBA$ だけです。

着目した生成規則の生成先 $bBA$ において、$B$ より後の文字列は $A$ ですね。よって、$\beta =A$ となります。

[公式2] $\beta =A\ne \epsilon$ なので〇

生成規則 $A\to bB\underset{\beta }{\underbrace{A}}$ より、$\mathrm{Follow}(B)$ に追加される要素は、$$\begin{array}{rl}\mathrm{Follow}(B)+& =\mathrm{First}(A)-\{\epsilon \}\\ & =\{b,\epsilon \}-\{\epsilon \}\\ & =\{b\}\end{array}$$と求められます。よって、$\mathrm{Follow}(B)$ に $b$ が追加されます。

[公式3] $\epsilon \in \mathrm{First}(A)=\{b,\epsilon \}$ なので〇

生成規則 $A\to bBA$ より、$\mathrm{Follow}(B)$ に追加される要素は、

$$\begin{array}{rl}\mathrm{Follow}(B)+& =\mathrm{Follow}(A)\\ & \stackrel{(2)}{=}\{c,\mathrm{\$}\}\end{array}$$と求められます。よって、$\mathrm{Follow}(B)$ に $c,\mathrm{\$}$ が追加されます。

したがって、$\mathrm{Follow}(B)$ は$$\begin{array}{rl}\mathrm{Follow}(B)& =\{b\}\cup \{c,\mathrm{\$}\}\\ & =\{b,c,\mathrm{\$}\}\end{array}$$と計算できます。

(4) Follow集合の計算ミスを防ぐコツ：図を書く

※ このアイデアは、国島 丈生様のこちらのサイトを参考にさせていただきました。
（FOLLOW()の計算を間違えにくくする工夫）

Follow集合は、First集合に比べて計算が複雑になるため、計算ミスがかなり出てきます^[8]実際に私もよく計算ミスします。。

そこで、今回の記事では下の図ように「Follow集合にどの集合の要素が追加されているか」を図で表現しています^[9]下の図の場合「$\mathrm{Follow}(S)$ を求めるためには $\mathrm{First}(c)$ と $\{\mathrm{\$}\}$ の要素を追加すればOK」ということを表しています。。

さらに、各非終端記号ごとに書いたFollow集合の計算図示を下のように1つにまとめることで、Follow集合同士の関係（どのFollow集合の要素がどのFollow集合に加えられているのか）も明確にすることができます。

図を書くことで、「矢印に従って集合を追加していく」するだけで簡単にFollow集合を求めることができます！

※ 追加時に $\epsilon$ が出てくる場合は無視してください。

さらに図を書くもう1つメリットは検算が容易にできることです。

理由は、「ある集合 $A$ の要素を集合 $B$ に追加」した場合、集合の包含関係 $A\subseteq B$ は必ず成立するからです^[10]集合 $B$ に集合 $A$ の要素を追加したのに、集合 $B$ の要素の中に集合 $A$ … Continue reading。

例えば、下の図は $\mathrm{First}(c)$ の要素を $\mathrm{Follow}(S)$ に追加しているため、$\mathrm{First}(c)\subseteq \mathrm{Follow}(S)$ が必ず成立します。

この包含関係を、書いた図の中に出てくる矢印それぞれ（下の図の場合は5か所）でチェックします^[11]具体的には、$\{\$\}\subseteq \mathrm{Follow}(S)$, $\mathrm{First}(c)\subseteq \mathrm{Follow}(S)$, $\mathrm{Follow}(S)\subseteq \mathrm{Follow}(A)$, \( \mathrm{First} (A) … Continue reading。矢印すべての箇所で包含関係が成り立っていればOKです。

※ 1つでも成り立っていないものがあれば、計算ミスをしています。

4. Director集合とLL(1)文法の判定

(1) Director集合とは

ある文法がLL(1)文法、つまり「1文字の先読みをするだけで、与えられた文字列を構文解析できる文法」とはどのような文法なのかをもう少し詳しく見ていきましょう。

例えば、文字列 $baba$ が生成規則$$\begin{array}{rl}S& \to aS\\ S& \to bA\\ S& \to bAb\\ A& \to a\end{array}$$の文法を満たすか「1文字の先読み」で判定することを考えましょう。

まず、1文字目を先読みすると $b$ となりますね。出発記号 $S$ から $b$ で始まる規則を探そうとしますが、$S\to bA$ と $S\to bAb$ の2つが存在してしまっているため、どちらの文法規則を使っていいかわかりません。

このように、同じ非終端記号から生成される文字列を終端記号にした文字列の先頭が$$S\to bA,S\to bAb$$のように重複していると、「1文字の先読みだけでは、どの構文規則を適用すればよいかわからなくなるため、与えられた文字列を構文解析できない」ことがわかりますね。

言い換えると、LL(1)文法であるかを判定するためには、同一非終端記号から生成されるすべての生成規則に対し、生成される可能性がある「終端記号の文字列の先頭文字」がすべて異なっていればOKですね。 

(2) Director集合の定義と計算公式

LL(1)文法であるかを機械的に判定するために登場したのがDirector集合です。

Director集合は、生成規則 $A\to \alpha$ に対し、「$A$ から生成される文字列 $\alpha$ をすべて終端記号にしたときの先頭に来る文字の候補」を表しており、$$\mathrm{Director}(A,\alpha )$$と表記します。

[Director集合の計算公式1] αに空文字が来ない場合

ここで、生成規則 $A\to \alpha$ の生成先 $\alpha$ をすべて終端記号にしたときの先頭に来る文字の候補というのは、$\alpha$ に空文字が来ない限り $\mathrm{First}(\alpha$ と書き換えることができます。

よって、$\alpha$ に空文字が来ない場合（$=\epsilon \notin \mathrm{First}(\alpha )$）は、$$\mathrm{Director}(A,\alpha )=\mathrm{First}(\alpha )$$でDirector集合を求めることが可能です。

[Director集合の計算公式2] αに空文字が来る可能性がある場合

しかし、$A\to \epsilon$ が代入される可能性がある（$=\epsilon \in \mathrm{First}(\alpha )$）場合、下のように $A\to \epsilon$ が適用されることで $A$ のつぎの文字列 $X$ が先頭に出てくる可能性があります。$$AX\stackrel{A\to \epsilon }{\to }X$$そのため、$\epsilon \in \mathrm{First}(\alpha )$ となる場合は $\mathrm{First}(\alpha )$ に加えて $A$ の直後に来る終端記号の文字を表す $\mathrm{Follow}(A)$ もDirector集合に加えます。

よって、$\alpha$ に空文字が来る場合（$=\epsilon \in \mathrm{First}(\alpha )$）は、$$\mathrm{Director}(A,\alpha )=\mathrm{Follow}(A)$$でDirector集合を求めることが可能です。

(3) Director集合を用いたLL(1)文法の判定

LL(1)文法であるかどうかは、同一非終端記号から生成されるすべての生成規則に対し、生成される可能性がある「非終端記号の文字列の先頭文字」がすべて異なっていればOKでしたね。

このLL(1)文法であるかの判定をDirector集合を用いて書くと下のようになります。

[例]

生成規則$$\begin{array}{rl}A& \to {\alpha }_1|{\alpha }_2\\ B& \to {\beta }_1\\ C& \to {\gamma }_1|{\gamma }_2|{\gamma }_3\end{array}$$からなる文法の場合、2つ以上の生成元を持つ非終端記号は $A$（2つ）と $C$（3つ）である。

(i) $A$ で確認する内容$$\mathrm{Director}(A,{\alpha }_1)\cap \mathrm{Director}(A,{\alpha }_2)=\varphi$$

(ii) $C$ で確認する内容$$\begin{array}{rl}\mathrm{Director}(C,{\gamma }_1)\cap \mathrm{Director}(C,{\gamma }_2)& =\varphi \\ \mathrm{Director}(C,{\gamma }_1)\cap \mathrm{Director}(C,{\gamma }_3)& =\varphi \\ \mathrm{Director}(C,{\gamma }_2)\cap \mathrm{Director}(C,{\gamma }_3)& =\varphi \end{array}$$※ 3つの生成規則の中から2つを選ぶ組み合わせは、(生成規則1, 生成規則2), (生成規則1, 生成規則3), (生成規則2, 生成規則3) の3通りあるので、3通りとも調べる必要あり。

この(i), (ii)で出てきた式（合計4つ）がすべて成立すればLL(1)文法であることが言えます。一方、どれか1つでも成立しなかった時点でLL(1)文法ではありません。

(4) 例題で確認してみよう

Director集合の算出、およびLL(1)文法の確認を例題で確認していきましょう。

[解説]

LL(1)文法であるか判定するためには、2つ以上の生成規則を持つ各非終端記号に対して、Director集合を取り、その積を確認します。

(i) $A$ が生成元の生成規則 $A\to bBa$, $A\to \epsilon$ に対してDirector集合確認

$A\to bBa$ のDirector集合$$\begin{array}{rl}\mathrm{Director}(A,bBa)& =\mathrm{First}(bBa)\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(b)\\ & \stackrel{\mathrm{R}1}{=}\{b\}\end{array}$$

$A\to \epsilon$ のDirector集合$$\begin{array}{rl}\mathrm{Director}(A,\epsilon )& =\mathrm{Follow}(A)\\ & =\{c,\mathrm{\$}\}\end{array}$$

$A$ に関する各Director集合の積を取ると、$$\begin{array}{rl}\mathrm{Director}(A,bBa)\cap \mathrm{Director}(A,\epsilon )& =\{b\}\cap \{c,\mathrm{\$}\}\\ & =\varphi \end{array}$$となるためOK。

(ii) $B$ が生成元の生成規則 $B\to Sc$, $B\to d$ に対してDirector集合確認

$B\to Sc$ のDirector集合$$\begin{array}{rl}\mathrm{Director}(B,Sc)& =\mathrm{First}(Sc)\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(S)\\ & =\{a\}\end{array}$$

$B\to d$ のDirector集合$$\begin{array}{rl}\mathrm{Director}(B,d)& =\mathrm{First}(d)\\ & \stackrel{\mathrm{R}1}{=}\{d\}\end{array}$$

$B$ に関する各Director集合の積を取ると、$$\begin{array}{rl}\mathrm{Director}(B,Sc)\cap \mathrm{Director}(B,d)& =\{a\}\cap \{d\}\\ & =\varphi \end{array}$$となるためOK。

(i), (ii)よりLL(1)文法であることが確認できた。

※ $S$ に対しては、$S\to aA$ の1つの生成規則しかないため、Director集合は求めなくてOK。

5. 練習問題

それでは、ここまでの学習内容を練習問題を通じておさらいしていきましょう。

今回は、2問の練習問題を用意しています。

練習1.

練習2.

6. 練習問題の答え

解答1.

規則$$\begin{array}{rl}P=\{S& \to aAa\\ A& \to bB|SB\\ B& \to cB|dAb|\epsilon \}\end{array}$$で表される文法に対してFirst集合、Follow集合、Director集合を求めてLL(1)文法を判定する。

(1) First集合の算出

[略解]$$\begin{array}{rl}\mathrm{First}(S)& =\{a\}\\ \mathrm{First}(A)& =\{a,b\}\\ \mathrm{First}(B)& =\{c,d,\epsilon \}\end{array}$$

(i) $\mathrm{First}(S)$ の計算

$S$ が生成元の規則は $S\to aAa$ の1つだけなので、$S\to aAa$ だけに着目すればOK。

$$\begin{array}{rl}\mathrm{First}(S)& \stackrel{\mathrm{R}2}{=}\underset{S\to aAa}{\underbrace{\mathrm{First}(aAa)}}\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(a)\\ & \stackrel{\mathrm{R}1}{=}\{a\}\end{array}$$

(ii) $\mathrm{First}(A)$ の計算

$A$ が生成元の規則は $A\to bB$ と $A\to SB$ の2つがある。

そのため、$\mathrm{First}(A)$ を求める際には $A\to bB$ と $A\to SB$ の2つの規則に着目すればOK。$$\mathrm{First}(A)\stackrel{\mathrm{R}2}{=}\underset{A\to bB}{\underbrace{\mathrm{First}(bB)}}\cup \underset{A\to SB}{\underbrace{\mathrm{First}(SB)}}$$

ここでそれぞれの項のFirst集合は以下のように計算できる。

$$\begin{array}{rl}\mathrm{First}(bB)& \stackrel{\mathrm{R}3}{=}\mathrm{First}(b)\\ & \stackrel{\mathrm{R}1}{=}\{b\}\end{array}$$

$$\begin{array}{rl}\mathrm{First}(SB)& \stackrel{\mathrm{R}3}{=}\mathrm{First}(S)\\ & \stackrel{(1)}{=}\{a\}\end{array}$$

よって、$$\begin{array}{rl}\mathrm{First}(A)& \stackrel{\mathrm{R}2}{=}\underset{A\to bB}{\underbrace{\mathrm{First}(bB)}}\cup \underset{A\to SB}{\underbrace{\mathrm{First}(SB)}}\\ & =\{b\}\cup \{a\}\\ & =\{a,b\}\end{array}$$となる。

(iii) $\mathrm{First}(B)$ の計算

$B$ が生成元の規則は $B\to cB$, $B\to dAb$, $B\to \epsilon$ の3つがある。

そのため、$\mathrm{First}(B)$ を求める際には $B\to cB$, $B\to dAb$, $B\to \epsilon$ の3つの規則に着目すればOK。$$\mathrm{First}(B)\stackrel{\mathrm{R}2}{=}\underset{B\to cB}{\underbrace{\mathrm{First}(cB)}}\cup \underset{B\to dAb}{\underbrace{\mathrm{First}(dAb)}}\cup \underset{B\to \epsilon }{\underbrace{\mathrm{First}(\epsilon )}}$$

ここでそれぞれの項のFirst集合は以下のように計算できる。

$$\begin{array}{rl}\mathrm{First}(cB)& \stackrel{\mathrm{R}3}{=}\mathrm{First}(c)\\ & \stackrel{\mathrm{R}1}{=}\{c\}\end{array}$$

$$\begin{array}{rl}\mathrm{First}(dAb)& \stackrel{\mathrm{R}3}{=}\mathrm{First}(d)\\ & \stackrel{(1)}{=}\{d\}\end{array}$$

$$\begin{array}{r}\mathrm{First}(\epsilon )\stackrel{\mathrm{R}1}{=}\{\epsilon \}\end{array}$$

よって、$$\begin{array}{rl}\mathrm{First}(B)& \stackrel{\mathrm{R}2}{=}\mathrm{First}(cB)\cup \mathrm{First}(dAb)\cup \mathrm{First}(\epsilon )\\ & =\{c\}\cup \{d\}\cup \{\epsilon \}\\ & =\{c,d,\epsilon \}\end{array}$$となる。

(2) Follow集合の算出

[略解]$$\begin{array}{rl}\mathrm{Follow}(S)& =\{a,b,c,d,\mathrm{\$}\}\\ \mathrm{Follow}(A)& =\{a,b\}\\ \mathrm{Follow}(B)& =\{a,b\}\end{array}$$

(i) $\mathrm{Follow}(S)$ の算出式

[公式1] $S$ は出発記号？ → Yes。なので、$\mathrm{Follow}(S)$ に $\mathrm{\$}$ を追加。$$\mathrm{Follow}(S)+=\{\mathrm{\$}\}$$

$S$ が生成先に含まれる規則は、$A\to SB$ のみなので、$A\to SB$ にのみ着目すればOK。

ここで、$A\to S\underset{\beta }{\underbrace{B}}$ より、$\beta =B$ とおく。

[公式2] $\beta \ne \epsilon$？ → $\beta =B\ne \epsilon$ なのでYes。

なので、$A\to SB$ に対し、以下の集合の要素を追加。\( A$$\begin{array}{rl}\mathrm{Follow}(S)+& =\mathrm{First}(B)-\{\epsilon \}\\ & =\{c,d,\epsilon \}-\{\epsilon \}\\ & =\{c,d\}\end{array}$$

[公式3] $\epsilon \in \mathrm{First}(\beta )$？ → $\mathrm{First}(\beta )=\{c,d,\epsilon \}$ なのでYes。

なので、$A\to SB$ に対し、以下の集合の要素を追加。$$\begin{array}{rl}\mathrm{Follow}(S)+& =\mathrm{Follow}(A)\end{array}$$

よって、$\mathrm{Follow}(S)$ に追加される要素は以下の図で示す通り。

(ii) $\mathrm{Follow}(A)$ の算出式

[公式1] $A$ は出発記号？ → No。

$A$ が生成先に含まれる規則は、$S\to aAa$, $B\to dAb$ の2つなので、この2つの規則に着目すればOK。

[a] $S\to aAa$ に着目したとき

$S\to aA\underset{\beta }{\underbrace{a}}$ とおく。（つまり $\beta =a$）

[公式2] $\beta \ne \epsilon$？ → $\beta =a\ne \epsilon$ なのでYes。

なので、$S\to aAa$ に対し、以下の集合の要素を追加。$$\begin{array}{rl}\mathrm{Follow}(A)+& =\mathrm{First}(a)\\ & =\{a\}\end{array}$$

[公式3] $\epsilon \in \mathrm{First}(\beta )$？ → $\mathrm{First}(\beta )=\mathrm{First}(a)=\{a\}$ なのでNo。

[b] $B\to dAb$ に着目したとき

[公式2] $\beta \ne \epsilon$？ → $\beta =b\ne \epsilon$ なのでYes。

なので、$S\to dAb$ に対し、以下の集合の要素を追加。$$\begin{array}{rl}\mathrm{Follow}(A)+& =\mathrm{First}(b)\\ & =\{b\}\end{array}$$

[公式3] $\epsilon \in \mathrm{First}(\beta )$？ → $\mathrm{First}(\beta )=\mathrm{First}(b)=\{b\}$ なのでNo。

よって、$\mathrm{Follow}(A)$ に追加される要素は以下の図で示す通り。

(iii) $\mathrm{Follow}(B)$ の算出式

[公式1] $B$ は出発記号？ → No。

$B$ が生成先に含まれる規則は、$A\to bB$, , $A\to SB$ ,$B\to cB$ の3つ。ただし、$B\to cB$ は右再帰規則のため無視。なので、$A\to bB$, $A\to SB$ の2つの規則に着目すればOK。

[a] $A\to bB$ に着目したとき

$A\to bB$ の $B$ の後ろの文字が存在しない。そのため、$\beta =\epsilon$ である。

[公式2] $\beta \ne \epsilon$？ → $\beta =\epsilon$ なのでNo。

[公式3] $\epsilon \in \mathrm{First}(\beta )$？ → $\mathrm{First}(\beta )=\mathrm{First}(\epsilon )=\{\epsilon \}$ なのでYes。

なので、$A\to bB$ に対し、以下の集合の要素を追加。$$\begin{array}{rl}\mathrm{Follow}(B)+& =\mathrm{Follow}(A)\end{array}$$

[b] $A\to SB$ に着目したとき

$A\to SB$ の $B$ の後ろの文字が存在しない。そのため、$\beta =\epsilon$ である。

[公式2] $\beta \ne \epsilon$？ → $\beta =\epsilon$ なのでNo。

[公式3] $\epsilon \in \mathrm{First}(\beta )$？ → $\mathrm{First}(\beta )=\mathrm{First}(\epsilon )=\{\epsilon \}$ なのでYes。

なので、$A\to SB$ に対し、以下の集合の要素を追加。$$\begin{array}{rl}\mathrm{Follow}(B)+& =\mathrm{Follow}(A)\end{array}$$

※ 式から察している人もいるかもしれませんが、[a] の生成式と全く同じ結果が出てきます。

よって、$\mathrm{Follow}(B)$ に追加される要素は以下の図で示す通り。

それぞれの計算結果をまとめてFollow集合を算出

先ほど出した $\mathrm{Follow}(S)$, $\mathrm{Follow}(A)$, $\mathrm{Follow}(B)$ の計算過程を1つの図に表すと、下のようになる。

あとは、求められるFollow集合から順にFollow集合を求めていけばOK。

※ 今回の場合は、$\mathrm{Follow}(A)$ を求めてから、$\mathrm{Follow}(S)$ と $\mathrm{Follow}(B)$ を求めていく流れになりますね（$\mathrm{Follow}(S)$ と $\mathrm{Follow}(B)$ はどっちから求めてもOK）。

(ii) $\mathrm{Follow}(A)$ の計算結果

[計算式]$$\begin{array}{rl}\mathrm{Follow}(A)& =\mathrm{First}(a)\cup \mathrm{First}(b)-\{\epsilon \}\\ & =\{a\}\cup \{b\}\\ & =\{a,b\}\end{array}$$

(i) $\mathrm{Follow}(S)$ の計算結果

[計算式]$$\begin{array}{rl}\mathrm{Follow}(S)& =\mathrm{First}(B)\cup \mathrm{Follow}(A)\cup \{\mathrm{\$}\}-\{\epsilon \}\\ & =\{c,d,\epsilon \}\cup \{a,b\}\cup \{\mathrm{\$}\}-\{\epsilon \}\\ & =\{a,b,c,d,\mathrm{\$}\}\end{array}$$※ $\epsilon$ を無視するのを忘れずに

(iii) $\mathrm{Follow}(B)$ の計算結果

[計算式]$$\begin{array}{rl}\mathrm{Follow}(B)& =\mathrm{Follow}(A)\\ & =\{a,b\}\end{array}$$※Follow集合の要素には $\epsilon$ が出てこないので、$\epsilon$ を引いていません。（引いてもOKです。）

(3) Director集合の算出とLL(1)文法の判定

各非終端記号に対して、生成元から2つ以上の生成規則を持つものは、

1. $A$ が生成元となる規則：$A\to bB$, $A\to SB$
2. $B$ が生成元となる規則：$B\to cB$, $B\to dAb$, $B\to \epsilon$

である。あとは、非終端記号ごとに「どの生成規則同士の積をとっても、Director集合が空集合になること」を確認すればOK。

1) $A$ が生成元の生成規則 $A\to bB$, $A\to SB$ に対してDirector集合確認

$A\to bB$ のDirector集合$$\begin{array}{rl}\mathrm{Director}(A,bB)& =\mathrm{First}(bB)\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(b)\\ & \stackrel{\mathrm{R}1}{=}\{b\}\end{array}$$

$A\to SB$ のDirector集合$$\begin{array}{rl}\mathrm{Director}(A,SB)& =\mathrm{First}(SB)\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(S)\\ & =\{a\}\end{array}$$

$A$ に関する各Director集合同士の積を取ると、$$\begin{array}{rl}\mathrm{Director}(A,bB)\cap \mathrm{Director}(A,SB)& =\{b\}\cap \{a\}\\ & =\varphi \end{array}$$となるためOK。

2) $B$ が生成元の生成規則 $B\to cB$, $B\to dAb$, $B\to \epsilon$に対してDirector集合確認

$B\to cB$ のDirector集合$$\begin{array}{rl}\mathrm{Director}(B,cB)& =\mathrm{First}(cB)\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(c)\\ & \stackrel{\mathrm{R}1}{=}\{c\}\end{array}$$

$B\to dAb$ のDirector集合$$\begin{array}{rl}\mathrm{Director}(B,dAb)& =\mathrm{First}(dAb)\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(d)\\ & \stackrel{\mathrm{R}1}{=}\{d\}\end{array}$$

$B\to \epsilon$ のDirector集合$$\begin{array}{rl}\mathrm{Director}(B,\epsilon )& =\mathrm{Follow}(B)\\ & =\{a,b\}\end{array}$$

$B$ に関する各Director集合同士の積を取ると、$$\begin{array}{rl}\mathrm{Director}(B,cB)\cap \mathrm{Director}(B,dAb)& =\{c\}\cap \{d\}=\varphi \\ \mathrm{Director}(B,cB)\cap \mathrm{Director}(B,\epsilon )& =\{c\}\cap \{a,b\}=\varphi \\ \mathrm{Director}(B,dAb)\cap \mathrm{Director}(B,\epsilon )& =\{d\}\cap \{a,b\}=\varphi \end{array}$$となるためOK。

1), 2) より、題意の文法はLL(1)文法である。

解答2.

規則$$\begin{array}{rl}P=\{S& \to AaB\\ A& \to cCA|c\\ B& \to S|BA|\epsilon \\ C& \to Bc\}\end{array}$$で表される文法に対してFirst集合、Follow集合、Director集合を求めてLL(1)文法を判定する。

(1) First集合の算出

[略解]$$\begin{array}{rl}\mathrm{First}(S)& =\{c\}\\ \mathrm{First}(A)& =\{c\}\\ \mathrm{First}(B)& =\{c,\epsilon \}\\ \mathrm{First}(C)& =\{c\}\end{array}$$

(i) $\mathrm{First}(S)$ の計算 (途中まで)

$S$ が生成元の規則は $S\to AaB$ の1つだけなので、$S\to AaB$ だけに着目すればOK。

$$\begin{array}{rl}\mathrm{First}(S)& \stackrel{\mathrm{R}2}{=}\underset{S\to AaB}{\underbrace{\mathrm{First}(AaB)}}\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(A)\end{array}$$※ まだ $\mathrm{First}(A)$ が求まっていないため保留

(ii) $\mathrm{First}(A)$ の計算（と $\mathrm{First}(S)$ の計算再開）

$A$ が生成元の規則は $A\to cCA$ と $A\to c$ の2つがある。

そのため、$\mathrm{First}(A)$ を求める際には $A\to cCA$ と $A\to c$ の2つの規則に着目すればOK。$$\mathrm{First}(A)\stackrel{\mathrm{R}2}{=}\underset{A\to cCA}{\underbrace{\mathrm{First}(cCA)}}\cup \underset{A\to c}{\underbrace{\mathrm{First}(c)}}$$

ここでそれぞれの項のFirst集合は以下のように計算できる。

$$\begin{array}{rl}\mathrm{First}(cCA)& \stackrel{\mathrm{R}3}{=}\mathrm{First}(c)\\ & \stackrel{\mathrm{R}1}{=}\{c\}\end{array}$$

$$\begin{array}{rl}\mathrm{First}(c)& \stackrel{\mathrm{R}1}{=}\{c\}\end{array}$$

よって、$$\begin{array}{rl}\mathrm{First}(A)& \stackrel{\mathrm{R}2}{=}\mathrm{First}(cCA)\cup \mathrm{First}(c)\\ & =\{c\}\cup \{c\}\\ & =\{c\}\end{array}$$となる。また、$\mathrm{First}(S)$ も

$$\begin{array}{rl}\mathrm{First}(S)& \stackrel{\mathrm{R}2}{=}\mathrm{First}(AaB)\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(A)\\ & =\{c\}\end{array}$$と求められる。

(iii) $\mathrm{First}(B)$ の計算

$B$ が生成元の規則は $B\to S$, $B\to BA$, $B\to \epsilon$ の3つがある。

ただし、$B\to BA$ は左再帰の文法なので無視する。そのため、$\mathrm{First}(B)$ を求める際には $B\to cB$, $B\to dAb$ の2つの規則に着目すればOK。$$\mathrm{First}(B)\stackrel{\mathrm{R}2}{=}\underset{B\to cB}{\underbrace{\mathrm{First}(cB)}}\cup \underset{B\to dAb}{\underbrace{\mathrm{First}(dAb)}}$$

ここで、$$\begin{array}{r}\mathrm{First}(\epsilon )\stackrel{\mathrm{R}1}{=}\{\epsilon \}\end{array}$$なので、$\mathrm{First}(B)$ は$$\begin{array}{rl}\mathrm{First}(B)& \stackrel{\mathrm{R}2}{=}\mathrm{First}(S)\cup \mathrm{First}(\epsilon )\\ & =\{c\}\cup \{\epsilon \}\\ & =\{c,\epsilon \}\end{array}$$と計算できる。

(iv) $\mathrm{First}(C)$ の計算

$C$ が生成元の規則は $C\to Bc$ だけなので、この規則のみに着目する。

よって、$$\begin{array}{rl}\mathrm{First}(C)& \stackrel{\mathrm{R}2}{=}\underset{C\to Bc}{\underbrace{\mathrm{First}(Bc)}}\\ & \stackrel{\mathrm{R}3}{=}(\mathrm{First}(B)-\{\epsilon \})\cup \{c\}\because (\epsilon \in \mathrm{First}(B))\\ & =\{c\}\cup \{c\}\\ & =\{c\}\end{array}$$※ $\mathrm{First}(B)$ に $\epsilon$ が含まれているため、公式が変化する点に注意！

(2) Follow集合の算出

[略解]$$\begin{array}{rl}\mathrm{Follow}(S)& =\{c,\mathrm{\$}\}\\ \mathrm{Follow}(A)& =\{a,c,\mathrm{\$}\}\\ \mathrm{Follow}(B)& =\{c,\mathrm{\$}\}\\ \mathrm{Follow}(C)& =\{c\}\end{array}$$

(i) $\mathrm{Follow}(S)$ の算出式

[公式1] $S$ は出発記号？ → Yes。なので、$\mathrm{Follow}(S)$ に $\mathrm{\$}$ を追加。$$\mathrm{Follow}(S)+=\{\mathrm{\$}\}$$

ここで、$S$ が生成先に含まれる規則は、$B\to S$ のみなので、$B\to S$ にのみ着目すればOK。

$B\to S$ において、 $S$ の後ろの文字が存在しない。そのため、$\beta =\epsilon$ である。

[公式2] $\beta \ne \epsilon$？ → $\beta =\epsilon$ なのでNo。

[公式3] $\epsilon \in \mathrm{First}(\beta )$？ → $\mathrm{First}(\beta )=\mathrm{First}(\epsilon )=\{\epsilon \}$ なのでYes。

なので、$B\to S$ に対し、以下の集合の要素を追加。$$\begin{array}{rl}\mathrm{Follow}(S)+& =\mathrm{Follow}(B)\end{array}$$

よって、$\mathrm{Follow}(S)$ で追加する要素（計算過程）は以下の図の通りである。

(ii) $\mathrm{Follow}(A)$ の算出式

[公式1] $A$ は出発記号？ →No。なにもしない。

ここで、$A$ が生成先に含まれる規則は、$S\to AaB$, $A\to cCA$, $B\to BA$ の3つがあるが、$A\to cCA$ は右再帰な規則なので無視。よって、$S\to AaB$, $B\to BA$ の2つに着目すればOK。

[ii-a] $S\to aAaB$ に着目したとき

$S\to aA\underset{\beta }{\underbrace{aB}}$ とおく。（つまり $\beta =a$）

[公式2] $\beta \ne \epsilon$？ → $\beta =aB\ne \epsilon$ なのでYes。

なので、$S\to aAaB$ に対し、以下の集合の要素を追加。$$\begin{array}{rl}\mathrm{Follow}(A)+& =\mathrm{First}(aB)\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(a)\\ & \stackrel{\mathrm{R}1}{=}\{a\}\\ & =\{a\}\end{array}$$

[公式3] $\epsilon \in \mathrm{First}(\beta )$？ → $\mathrm{First}(\beta )=\mathrm{First}(aB)=\{\epsilon \}$ = \{ a \} \) なのでNo。

[ii-b] $B\to BA$ に着目したとき

この規則では、$S$ の後ろの文字が存在しない。そのため、$\beta =\epsilon$ である。

[公式2] $\beta \ne \epsilon$？ → $\beta =\epsilon$ なのでNo。

[公式3] $\epsilon \in \mathrm{First}(\beta )$？ → $\mathrm{First}(\beta )=\{\epsilon \}$ なのでYes。

なので、$B\to BA$ に対し、以下の集合の要素を追加。$$\begin{array}{rl}\mathrm{Follow}(A)+& =\mathrm{Follow}(B)\end{array}$$

よって、$\mathrm{Follow}(A)$ に追加される要素は以下の図で示す通り。

(iii) $\mathrm{Follow}(B)$ の算出式

[公式1] $B$ は出発記号？ →No。なにもしない。

ここで、$B$ が生成先に含まれる規則は、$S\to AaB$, $B\to BA$, $C\to Bc$ の3つがあるため、この3つの規則に着目すればOK。

[iii-a] $S\to AaB$ に着目したとき

この規則では、$B$ の後ろの文字が存在しない。そのため、$\beta =\epsilon$ である。

[公式2] $\beta \ne \epsilon$？ → $\beta =\epsilon$ なのでNo。

[公式3] $\epsilon \in \mathrm{First}(\beta )$？ → $\mathrm{First}(\beta )=\mathrm{First}(\epsilon )=\{\epsilon \}$ なのでYes。

なので、$S\to AaB$ に対し、以下の集合の要素を追加。$$\begin{array}{rl}\mathrm{Follow}(B)+& =\mathrm{Follow}(S)\end{array}$$

[iii-b] $B\to BA$ に着目したとき

$B\to B\underset{\beta }{\underbrace{A}}$ とおく。（つまり $\beta =A$）

[公式2] $\beta \ne \epsilon$？ → $\beta =A\ne \epsilon$ なのでYes。

なので、$B\to aBA$ に対し、以下の集合の要素を追加。$$\begin{array}{rl}\mathrm{Follow}(B)+& =\mathrm{First}(A)\\ & =\{c\}\end{array}$$

[公式3] $\epsilon \in \mathrm{First}(\beta )$？ → $\mathrm{First}(\beta )=\mathrm{First}(A)=\{c\}$ なのでNo。

[iii-c] $C\to Bc$ に着目したとき

$C\to B\underset{\beta }{\underbrace{c}}$ とおく。（つまり $\beta =c$）

[公式2] $\beta \ne \epsilon$？ → $\beta =c\ne \epsilon$ なのでYes。

なので、$C\to aBc$ に対し、以下の集合の要素を追加。$$\begin{array}{rl}\mathrm{Follow}(B)+& =\mathrm{First}(c)\\ & =\{c\}\end{array}$$

[公式3] $\epsilon \in \mathrm{First}(\beta )$？ → $\mathrm{First}(\beta )=\mathrm{First}(c)=\{c\}$ なのでNo。

[iii-a]～[iii-c] より、$\mathrm{Follow}(B)$ に追加される要素は以下の図で示す通り。

(iv) $\mathrm{Follow}(C)$ の算出式

[公式1] $C$ は出発記号？ →No。なにもしない。

ここで、$C$ が生成先に含まれる規則は、$A\to cCA$ のみ。なのでこの規則に着目すればOK。

この規則について、$A\to cC\underset{\beta }{\underbrace{A}}$ とおく。（つまり $\beta =A$）

[公式2] $\beta \ne \epsilon$？ → $\beta =A\ne \epsilon$ なのでYes。

なので、$C\to cCA$ に対し、以下の集合の要素を追加。$$\begin{array}{rl}\mathrm{Follow}(C)+& =\mathrm{First}(A)\\ & =\{c\}\end{array}$$

[公式3] $\epsilon \in \mathrm{First}(\beta )$？ → $\mathrm{First}(\beta )=\mathrm{First}(A)=\{c\}$ なのでNo。

よって、$\mathrm{Follow}(C)$ に追加される要素は以下の図で示す通り。

それぞれの計算結果をまとめてFollow集合を算出

先ほど出した $\mathrm{Follow}(S)$, $\mathrm{Follow}(A)$, $\mathrm{Follow}(B)$, $\mathrm{Follow}(C)$ の計算過程を1つの図に表すと、下のようになる。

※ 点線部分は、間接的な右再帰により、2つのFollow集合が等しい（＝一心同体）になっていることを表す。つまり $\mathrm{Follow}(S)=\mathrm{Follow}(B)$。

あとは、求められるFollow集合から順にFollow集合を求めていけばOK。

※ 今回の場合は、$\mathrm{Follow}(A)$ 集合は点線部分のFollow集合が求まらないと計算できません。それ以外の集合は自由な順番で計算できます。

(iv) $\mathrm{Follow}(C)$ の計算結果

[計算式]$$\begin{array}{rl}\mathrm{Follow}(C)& =\mathrm{First}(a)\\ & =\{c\}\end{array}$$

(i), (iii) $\mathrm{Follow}(S)$, $\mathrm{Follow}(B)$ の計算結果（2つのFollow集合は等しい）

[計算式]$$\begin{array}{rl}\mathrm{Follow}(S)& =\{\mathrm{\$}\}\cup \mathrm{First}(A)\cup \mathrm{First}(c)\\ & =\{\mathrm{\$}\}\cup \{c\}\cup \{c\}\\ & =\{c,\mathrm{\$}\}\end{array}$$※ $\mathrm{Follow}(B)$ 加えられている要素もいったん $\mathrm{Follow}(S)$ に足している。

$$\begin{array}{rl}\mathrm{Follow}(B)& =\mathrm{Follow}(S)\\ & =\{c,\mathrm{\$}\}\end{array}$$

(ii) $\mathrm{Follow}(A)$ の計算結果

[計算式]$$\begin{array}{rl}\mathrm{Follow}(A)& =\mathrm{Follow}(B)\cup \mathrm{First}(a)\\ & =\{c,\mathrm{\$}\}\cup \{a\}\\ & =\{a,c,\mathrm{\$}\}\end{array}$$※ $\mathrm{Follow}(B)$ を $\mathrm{Follow}(S)$ としてもOK。

(3) Director集合の計算・LL(1)文法の判定

各非終端記号に対して、生成元から2つ以上の生成規則を持つものは、

1. $A$ が生成元となる規則：$A\to cCA$, $A\to c$
2. $B$ が生成元となる規則：$B\to S$, $B\to BA$, $B\to \epsilon$

である。あとは、非終端記号ごとに「どの生成規則同士の積をとっても、Director集合が空集合になること」を確認すればOK。

1) $A$ が生成元の生成規則 $A\to cCA$, $A\to c$ に対してDirector集合確認

$A\to cCA$ のDirector集合$$\begin{array}{rl}\mathrm{Director}(A,cCA)& =\mathrm{First}(cCA)\\ & \stackrel{\mathrm{R}3}{=}\mathrm{First}(c)\\ & \stackrel{\mathrm{R}1}{=}\{c\}\end{array}$$

$A\to c$ のDirector集合$$\begin{array}{rl}\mathrm{Director}(A,c)& =\mathrm{First}(c)\\ & \stackrel{\mathrm{R}1}{=}\{c\}\end{array}$$

$A$ に関する各Director集合同士の積を取ると、$$\begin{array}{rl}\mathrm{Director}(A,cCA)\cap \mathrm{Director}(A,c)& =\{c\}\cap \{c\}\\ & =\{c\}\end{array}$$となるためNG。

よって、題意の文法はLL(1)文法ではない。

※ 1つでも $\varphi$ にならないものがあればその時点でLL(1)文法ではないことが確認できるため、他のDirector集合は求めなくてOKです。

7. さいごに

かなり長い記事となっていましたが、以上が

• LL(1)文法
• First集合
• Follow集合
• Director集合

に関する説明でした。

この記事を見て、少しでもLL(1)文法やFirst, Follow, Director集合の計算の方法について理解いただけたのであれば非常にうれしいです。

次回は、左再帰な文法についての「問題点」と「左再帰を解消する方法」について説明する予定です。

[練習問題の中に入れられなかったおまけ問題] 生成規則 $A\to B$ に対するDirector集合 $\mathrm{Director}(A,B)$ を求めなさい。ただし、$$\begin{array}{rl}\mathrm{First}(A)& =\{a\}\\ \mathrm{First}(B)& =\{b,\epsilon \}\\ \mathrm{Follow}(A)& =\{c\}\\ \mathrm{Follow}(B)& =\{d,\mathrm{\$}\}\end{array}$$とする。解答はこの注釈に書いています^[12]$\epsilon \in \mathrm{First}(B)$ なので、$B$ が空文字になる可能性を考慮するのがミソです。\[\begin{align*}\mathrm{Director} (A,B) & = \mathrm{First}(B) \cup … Continue reading。