うさぎでもわかるコンパイラ　第4羽　左再帰の除去

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

前回は1文字だけの先読みで構文解析ができる文法であるLL(1)文法について説明していきました。

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

2022.9.19

こんにちは、ももやまです。 コンパイラ（言語処理系）の勉強をしていると、 LL(1)文法First集合Follow集合Director集合 などの不思議な用語が出てきますよね。しか...

しかし、文法の中に左再帰な規則が入ってしまうと、文法内の他の規則に関わらず、絶対にLL(1)文法となることはありません。言い換えると、左再帰な規則は先読みしながらの構文解析の壁の1つといえます。

そこで今回は、

• そもそも左再帰とは？
• 左再帰な規則が入るとLL(1)文法でなくなる理由
• 左再帰の除去（例題・練習問題あり）

について、お勉強していきましょう。

※

スポンサードリンク

1. 左再帰・左再帰文法とは？

左再帰(規則)とは、生成規則の中に生成元の非終端記号と生成先の文字列の1文字目(先頭)が同じになっている規則、つまり規則中に \( \textcolor{red}{A} \to \textcolor{blue}{A} \alpha \) となる規則のことをさします。

また、左再帰 \( \textcolor{red}{A} \to \textcolor{red}{A} \alpha \) が含まれている文法のことを左再帰文法と呼びます。（ただし \( \alpha \not = \varepsilon \)）

例えば、生成規則が\[\begin{align*}
P = \{ \ \ \ \ S & \to aA \\ \textcolor{red}{A} & \textcolor{red}{\to Aba} \ | \ cd \\ B & \to Sc \ | \ a \ \ \ \ \ \ \ \}
\end{align*}
\]で表される文法は、左再帰 \( \textcolor{red}{A \to Aba } \) が含まれていますね。そのため、この文法は左再帰文法です。

左再帰文法には、左再帰の核部分 \( \textcolor{red}{A} \to \textcolor{red}{A} \alpha \) に加えて再帰をストップする規則の形 \( A \to \beta \) が含まれているのが特徴です。

[余談1] 右再帰とは？

「左再帰があるなら、右再帰な文法もあるんじゃね？」と思った人もいると思います。

想像の通り、右再帰もあります。具体的には、\( \textcolor{red}{A} \to \alpha \textcolor{blue}{A} \) の形の規則を右再帰と呼び^[1]日本語で説明すると、生成元の非終端記号と生成先の文字列の終端が同じになっている規則が右再帰です。、右再帰な規則が含まれている文法のことを右再帰文法と呼びます。（左再帰の時と同じく \( \alpha \not = \varepsilon \)）

右再帰文法も、左再帰文法と同じように規則の核部分に加えて再帰をストップする規則の形 \( A \to \beta \) が含まれているのが特徴です。

[余談2] 間接的な左(右)再帰

下の文法\[
\textcolor{red}{A \to Bb, \ \ \ B \to Aa} , \ \ \ A \to \alpha
\]のように、見た目的には左再帰になっていないものの、規則を適用していくと、\[
\textcolor{red}{A} \xrightarrow{A \to Bb} Bb \xrightarrow{B \to Aa} \textcolor{red}{A}ab
\]のように左再帰な形が出てくる規則のことを、間接左再帰と呼びます^[2]一方、見た目的に明らかな左再帰の形 \( \textcolor{red}{A} \to \textcolor{red}{A} \alpha \) をしている左再帰のことを、直接左再帰と呼ぶこともあります。。

同じように下の文法\[
\textcolor{blue}{A \to bB, \ \ \ B \to aA} , \ \ \ A \to \alpha
\]のように、見た目的には右再帰になっていないものの、規則を適用していくと、\[
\textcolor{blue}{A} \xrightarrow{A \to bB} bB \xrightarrow{B \to aA} ba \textcolor{blue}{A}
\]のように右再帰な形が出てくる規則のことを、間接右再帰と呼びます^[3]一方、見た目的に明らかな右再帰の形 \( \textcolor{blue}{A} \to \alpha \textcolor{blue}{A} \) が含まれている場合、直接右再帰と呼ぶこともあります。。

※ 今回の記事では、\( A \to A \alpha \) の形が出てくる直接的な左再帰の除去だけについて説明します。（間接的な左再帰の除去は本記事では割愛します。）

スポンサードリンク

2. 左再帰文法の問題点

左再帰が含まれている文法（左再帰文法）の最大の問題点は、絶対にLL(1)文法とはならないからです。言い換えると、左再帰が含まれている文法は、1文字先読みすることで後戻りなしに構文解析することができません。

LL(1)文法にならない理由を具体例を踏まえてみていきましょう。

例えば、次の左再帰規則\[
A \to Aa , \ \ A \to b
\]を持つ文法があったとします。（出発記号 \( A \)）

ここで、もしLL(1)文法であれば、1文字先読みするだけで \( A \to Aa \), \( A \to b \) のどちかを判別することができますよね。

しかしこの2つの規則は、

• \( A \to \textcolor{red}{A} a \)：生成先の先頭 \( A \) は最終的に \( A \to b \) により \( b \) になる
• \( A \to \textcolor{ded}{b} \) ：生成先の先頭 \( \textcolor{red}{b} \) である

ため、1文字先読みしたとしても、どちらの規則を適用すればよいかわかりません。

厳密に証明してみる

[お知らせ] 証明で使うDirector集合・First集合・Follow集合の解説はこちらで行っています。

もっと厳密に、Director集合を使って左再帰規則\[
A \to A \alpha , \ \ A \to \beta
\]がLL(1)文法でないことを示してみましょう。

まず、生成規則 \( \textcolor{magenta}{A} \to \textcolor{deepskyblue}{Aa} \) に関するDirector集合 \( \mathrm{Director} ( \textcolor{magenta}{A} , \textcolor{deepskyblue}{A \alpha} ) \) は、\[\begin{align*}
\mathrm{Director} ( \textcolor{magenta}{A} , \textcolor{deepskyblue}{A \alpha} ) & = \mathrm
{First} ( \textcolor{deepskyblue}{A \alpha} )
\\ & = \mathrm{First} ( A )
\\ & = \mathrm{First} ( \beta )
\end{align*}\]と計算できます。

※ \( \varepsilon \notin \mathrm{First} ( A \alpha) = \mathrm{First} ( \beta ) \) の条件を仮定

また、 \( \textcolor{magenta}{A} \to \textcolor{deepskyblue}{ \beta } \) に関するDirector集合は、 \( \varepsilon \notin \mathrm{First} ( \beta ) \) のとき\[\begin{align*}
& = \mathrm{First} (\textcolor{deepskyblue}{A \alpha} )
\\ & = \mathrm{First} (A)
\\ & = \mathrm{First} ( \beta )
\end{align*}\]と計算できます。

※ \( \varepsilon \notin \mathrm{First} ( \beta ) \) の条件を仮定

よって、\( \varepsilon \notin \mathrm{First} ( \beta ) \) のときに\[
\mathrm{Director} ( A , A \alpha ) \cap \mathrm{Director} ( A , \beta ) = \mathrm{First} ( \beta )
\]が成立するため、LL(1)文法ではない。

※ ほんの一部の条件に対してでもDirector集合の積集合が \( \phi \) 以外になったらLL(1)文法ではない。

右再帰文法は大丈夫なの？

右再帰文法（生成規則に右再帰が含まれている）だからといって絶対にLL(1)文法ではなくなるとは限りません。

例えば、\[
A \to a A , \ \ \ A \to b
\]のような文法は \( A \to aA \) が含まれているため右再帰文法ですが、

• \( A \to \textcolor{red}{a} A \)：生成先の先頭 \( A \) は \( a \) である
• \( A \to \textcolor{blue}{b} \) ：生成先の先頭 \( A \) は \( b \) である

のため、生成先の先頭文字を見るだけで \( A \to aA \), \( A \to b \) のどちらを適用すべきかが一意に定まりますね。そのため、LL(1)文法と言えます^[4]厳密に示したい場合は\[\begin{align*}\mathrm{Director} ( A, aA) \cap \mathrm{Director} (A, b) & = \mathrm{First} (a) \cap \mathrm{First} (b)\\ & = \{ a \} \cap \{ b \}\\ & = … Continue reading。

スポンサードリンク

3. 左再帰の除去

(1) 左再帰除去の手順

左再帰文法は、次の公式を使うことによって簡単に左再帰ではない文法に書き換えることができます。

[公式導出] (やみくもに丸暗記するのではなく、導出過程を理解してから覚えましょう！)

まず最初に左再帰が含まれる規則\[
A \to A \alpha \ | \ \beta
\]にはどのような文字列が含まれるかを書きだしてみましょう。

すると、

• \( \beta \)
• \( \beta \alpha \)
• \( \beta \alpha \alpha \)
• \( \beta \alpha \alpha \alpha \)

のように、\( \beta \) が1文字来たあとに \( \alpha \) が連続するような文字列\[
\beta \underbrace{ \alpha \alpha \alpha \cdots }_{\mathrm{0 \ 回以上繰り返し}}
\]が当てはまることがわかりますね。

つまり、左再帰の規則を書き換える際には、左再帰ではない規則で\[
\beta \underbrace{ \alpha \alpha \alpha \cdots }_{\mathrm{0 \ 回以上繰り返し}}
\]となる文字列を表せればOKです。

ここからは、左再帰規則\[
A \to A \alpha \ | \ \beta
\]を左再帰でない規則に書き換えるために文字列\[
\textcolor{red}{\beta} \textcolor{blue}{ \underbrace{ \alpha \alpha \alpha \cdots }_{\mathrm{0 \ 回以上繰り返し}} }
\]を [ア] \( \beta \) の部分と [イ] \( \alpha \) の繰り返し部分に分けます。

[ア] \( \beta \) の部分

\( \beta \) の部分は1回だけ \( \beta \) を出力するために新しい非終端記号 \( A' \) を使って\[
\textcolor{red}{A \to \beta A'}
\]とします。

[イ] 0回以上の \( \alpha \) 繰り返しの部分

つぎに、\( A' \) の部分で0回以上の \( \alpha \) の繰り返しを左再帰を使わずに表します。ここで左再帰は使ったらダメだけど、右再帰を使ったらダメとは一言も言っていない点が重要です。

そのため、0回以上の \( \alpha \) の繰り返しは右再帰\[
\textcolor{blue}{ A' \to \alpha A' \ | \ \varepsilon }
\]を使って表現します。

※ \( \alpha \) は0回以上の繰り返し（＝空文字も含める）なので、右再帰をストップする条件は \( A' \to \varepsilon \) となります。

(a), (b)をまとめる

あとは [ア] と [イ] の規則を合わせるだけで、左再帰の除去をした（元の文法と等価な）文法の完成です！\[\begin{align*}
\textcolor{red}{A} & \textcolor{red}{\to \beta A'} \\
\textcolor{blue}{A'} & \textcolor{blue}{\to \alpha A' \ | \ \varepsilon}
\end{align*}\]

(2) 例題で確認 [左再帰の除去]

[解説1]

(1)

生成規則 \( \textcolor{red}{A} \to \textcolor{blue}{A}cb \) において、生成元の非終端記号と生成先の1文字目(先頭文字)が一致しているため。

(2)

左再帰が発生している部分について、下のように \( \textcolor{red}{\alpha} \), \( \textcolor{blue}{\beta} \) をおきます。\[
A \to A \textcolor{red}{ \underbrace{ cb }_{\alpha} } \ | \ \textcolor{blue}{ \underbrace{ b }_{ \beta } }
\]

あとは、左再帰の除去規則を使って規則を書き換えればOKです。\[\begin{align*}
A & \to \textcolor{blue}{ \underbrace{ b }_{ \beta } } A' \\
A' & \to \textcolor{red}{ \underbrace{ cb }_{\alpha} } A' \ | \ \varepsilon
\end{align*}\]

左再帰の発生に関係のない非終端記号（今回の場合は \( A \) 以外）の生成規則\[
S \to AaB , \ \ \ B \to Sc \ | \ d
\]はそのままでOKなので、文法 \( G \) と等価な左再帰ではない文法 \( G' \) は、\[
G' = \left( \ \{ S,A, \textcolor{magenta}{A'} ,B \} \ , \ \{ a,b,c,d \} \ , \ \textcolor{magenta}{P'} \ , \ S \ \right)
\]\[\begin{align*}
\textcolor{magenta}{P'} = \{ \ \ \ \ S & \to AaB \\
A & \to \textcolor{blue}{ b } A' \\
A' & \to \textcolor{red}{ cb } A' \ | \ \varepsilon
\\ B & \to Sc \ | \ d \ \ \ \ \ \ \ \}
\end{align*}
\]となります。

※ ピンク色を付けて書いた部分は忘れがちなので要注意！

(3) 左再帰が複数含まれる場合

下のように左再帰が複数含まれる規則\[\begin{align*}
\textcolor{magenta}{A} & \textcolor{magenta}{\to A \alpha_1 \ | \ A \alpha_2 \ | \ \cdots} \\\
\textcolor{deepskyblue}{A} & \textcolor{deepskyblue}{\to \beta_1 \ | \ \beta_2 \ | \ \cdots}
\end{align*}\]であっても、左再帰の適用が可能です。

[色の意味]

桃色の規則 … 左再帰の核となる \( A \to A \alpha_k \) が含まれた規則
水色の規則 … 左再帰をストップする規則 \( A \to \beta_k \) が含まれた規則^[5]\( A \) が生成元で、生成先の先頭が \( A \) で始まらない（つまり桃色の規則に当てはまらない）規則は全て水色の規則に含まれる。（ \( A \to bA \) … Continue reading

左再帰が含まれていない \( A \to A \alpha_k \) が含まれた規則

(4) 例題で確認 [左再帰が複数含まれる場合]

左再帰の直接的な原因は \( \textcolor{magenta}{B \to BaA} \), \( \textcolor{magenta}{B \to BS} \) の2つ（共に \( B \) が生成元の規則）ですね。

ここで、\( B \) が生成元の規則は先ほどの2つのほかに \( \textcolor{deepskyblue}{B \to aa} \), \( \textcolor{deepskyblue}{B \to dBa} \), \( \textcolor{deepskyblue}{B \to Cd} \) の3つがあります。

なので、文字列を\[\begin{align*}
B & \to B \underbrace{ aA }_{ \alpha_1 } \ | \ B \underbrace{ S }_{ \alpha_2 } \\
B & \to \underbrace{ aa }_{ \beta_1 } \ | \ \underbrace{ dBa }_{ \beta_2 } \ | \ \underbrace{ Cd }_{ \beta_3 }
\end{align*}\]とおきましょう。

あとは、左再帰の除去公式で置き換えてあげればOKです！\[\begin{align*}
B & \to \underbrace{ aa }_{ \beta_1 } B' \ | \ \underbrace{ dBa }_{ \beta_2 } B' \ | \ \underbrace{ Cd }_{ \beta_3 } B' \\
B' & \to \underbrace{ aA }_{ \alpha_1 } B' \ | \ \underbrace{ S }_{ \alpha_2 } B' \ | \ \varepsilon
\end{align*}\]

左再帰の発生に関係のない非終端記号（今回の場合は \( A \) 以外）の生成規則はそのままでOKなので、文法 \( G \) と等価かつ左再帰ではない文法 \( G' \) は、\[
G' = \left( \ \{ S,A, B, \textcolor{magenta}{B'} \} \ , \ \{ a,b,c,d \} \ , \ P' \ , \ S \ \right)
\]\[\begin{align*}
P' = \{ \ \ \ \
S & \to aBc \\
A & \to bB \ | \ aA \\
\textcolor{magenta}{B} & \textcolor{magenta}{\to aa B' \ | \ dBaB' \ | \ CdB'} \\
\textcolor{magenta}{B'} & \textcolor{magenta}{ \to aAB' \ | \ S B' \ | \ \varepsilon } \\
C & \to cc \ | \ ccc
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \}
\end{align*}
\]となります。（ピンク色を付けて書いた部分が変更箇所）

5. 練習問題

それでは、今回習った左再帰の除去について2問の練習問題を用意しました。

練習1. 左再帰が1つの場合

練習2. 左再帰が複数ある場合

6. 練習問題の答え

解答1. 左再帰が1つの場合

(1)

生成規則 \( \textcolor{red}{S} \to \textcolor{blue}{S} ab \) において、生成元の非終端記号と生成先の1文字目(先頭文字)が一致しているため。

(2)

まず、左再帰が発生している \( S \) が生成元の規則に対して、\( \textcolor{red}{\alpha} \), \( \textcolor{blue}{\beta} \) を以下のようにおく。\[
S \to S \textcolor{red}{ \underbrace{ ab }_{\alpha} } \ | \ \textcolor{blue}{ \underbrace{ c }_{\beta} }
\]

あとは、左再帰の除去規則を使って規則を書き換えればOK。\[\begin{align*}
S & \to \textcolor{blue}{ \underbrace{ c }_{ \beta } } S' \\
S' & \to \textcolor{red}{ \underbrace{ ab }_{\alpha} } S' \ | \ \varepsilon
\end{align*}\]

左再帰の発生に関係のない非終端記号（今回の場合は \( S \) 以外）の生成規則はそのままでOKなので、文法 \( G \) と等価な左再帰ではない文法 \( G' \) は、\[
G' = \left( \ \{ S,A, \textcolor{magenta}{A'} ,B \} \ , \ \{ a,b,c,d \} \ , \ \textcolor{magenta}{P'} \ , \ S \ \right)
\]\[
\begin{align*}
P' = \{ \ \ \ \
S & \to \textcolor{blue}{ c } S' \\
S' & \to \textcolor{red}{ ab } S' \ | \ \varepsilon \\
A & \to BaA \ | \ a \\
B & \to cA \ | \ bb
\ \ \ \ \ \ \ \}
\end{align*}
\]となる。

解答2. 左再帰が複数の場合

左再帰の直接的な原因は \( \textcolor{magenta}{C \to Cab} \), \( \textcolor{magenta}{C \to Cb} \), \( \textcolor{magenta}{C \to CBS} \) の3つ（共に \( C \) が生成元の規則）。

また、\( C \) が生成元の規則は先ほどの3つのほかに \( \textcolor{deepskyblue}{C \to cc} \), \( \textcolor{deepskyblue}{C \to Ad} \) の2つがある。

なので、\( \alpha_1 \), \( \alpha_2 \), \( \alpha_3 \), \( \beta_1 \), \( \beta_2 \) を用いて文字列を\[\begin{align*}
C & \to C \underbrace{ ab }_{ \alpha_1 } \ | \ C \underbrace{ b }_{ \alpha_2 } \ | \ C \underbrace{ BS }_{ \alpha_3 } \\
C & \to \underbrace{ cc }_{ \beta_1 } \ | \ \underbrace{ Ad }_{ \beta_2 }
\end{align*}\]とおく。

あとは、左再帰の除去公式で置き換えるだけ。\[\begin{align*}
C & \to \underbrace{ cc }_{ \beta_1 } C' \ | \ \underbrace{ Ad }_{ \beta_2 } C' \\
C' & \to \underbrace{ ab }_{ \alpha_1 } C' \ | \ \underbrace{ b }_{ \alpha_2 } C' \ | \ \underbrace{ BS }_{ \alpha_3 } C' \ | \ \varepsilon
\end{align*}\]

左再帰の発生に関係のない非終端記号（今回の場合は \( S \) 以外）の生成規則はそのままでOKなので、文法 \( G \) と等価かつ左再帰ではない文法 \( G' \) は、\[
G' = \left( \ \{ S,A, B, C, \textcolor{magenta}{C'} \} \ , \ \{ a,b,c,d \} \ , \ P' \ , \ S \ \right)
\]\[\begin{align*}
P' = \{ \ \ \ \
S & \to dS \ | \ bbab \\
A & \to aA \ | \ bB \ | \ cC \ | \ d \\
B & \to b \ | \ Sb \\
C & \to cc C' \ | \ Ad C' \\
C' & \to ab C' \ | \ b C' \ | \ BS C' \ | \ \varepsilon
\ \ \ \ \ \}
\end{align*}\]となります。

7. さいごに

今回は、左再帰が含まれる文法（左再帰文法）と、左再帰の除去について説明していきました。

最後に左再帰の除去公式をおさらいしておきましょう！

左再帰文法の問題点や、左再帰の除去について少しでも理解していただけたのであれば本当にうれしいです！