文脈自由文法についてド初心者が調べてみた

社内の勉強会でThe Java® Language Specificationの第2章を担当することになりました。
プログラミング初心者なりに調べてまとめてみたので、qiitaにもアウトプットしてみようと思います。
今回は2-1 Context-Free Grammarsについてまとめます。

※「もっとわかりやすい説明あるよ！」「そこ間違ってるよ！」とかあれば、どしどしご指摘いただけると嬉しいです。

直訳

文脈自由文法は、多数の生成規則から構成される。各生成規則には、左辺に非終端記号と呼ばれる抽象記号があり、右辺に 一つ以上の非終端記号と終端記号がある。各文法において、終端記号は固有のアルファベットから作成される。

目標記号は、文脈自由文法は言語を定義し、単一の一意に識別する非終端記号で始まる。言語は、生成規則の左辺の非終端記号を右辺の任意の非終端記号で繰り返し置き換えていった終端記号の組合わせとする。

…………

は？？？( ゜A゜；)

ってなったので、調べてみた。

どんなもの？

文脈自由文法とは生成規則の左辺が1字のみである文法のことを指す（A→a+bは文脈自由文法だが、AB→a+b+c+dのように左辺が1字以上の場合は文脈自由文法とは言わない）。

……

「文法」は、言葉や文章を正しく組み立てるルールのこと。

「文脈自由」は、そのルールが柔軟で、ある部分を別のものに置き換えることができるということ。

例えば、「数字を2倍にする」というプログラムを書くとき、文脈自由文法を使うと「数字を○○倍にする」という形になる。○○の中にはどんな数字を入れても文法的には合っているので、柔軟にいろんな数字を2倍にすることができる。

構成

文脈自由文法は、以下の4つの要素で構成される。

（G）

文脈自由文法の名前

非終端記号（変数）N

空ではない有限集合。生成規則Pによって書き換えることができるような文字（記号）の集まり。

数学で言う「nとおく」のnみたいなもの。

終端記号 Σ

空ではない有限集合。それ以上書き換えることができない文字の集まり。

生成規則 P

1文字の終端記号を終端記号と非終端記号が組み合わされた複数の記号に変換するためのルール。「◯は～だ」のルールが集まっているもの。

基本的には

のように、「（生成元の非終端記号）→（生成される文字列）」の形で書くのが一般的。

他にも、文字列を列挙して書く方法や、

→ を ::=と書く方法もある。

出発記号 S

文法解析の出発記号（通常は非終端記号の1つ）を表す。最初に置き換える記号。

※「開始記号」は、形式言語論において文法の生成過程を開始する非終端記号を指す。「出発記号」は、文脈自由文法の文法規則において生成の機転となる非終端記号を指す。
（この場合は多分出発記号のほうが適切かも？）

読み方

以下の画像がどんな文法なのかを調べてみる。

①文字列の導出の方法

出発記号Sから生成規則を連鎖的に適用していく。

ここで言う「連鎖的」とは、ある非終端記号を選んで規則を適用して得られた新しい記号列に、別の非終端記号が含まれている場合、それを新たに選んで規則を適用するというプロセスを指す。

例えば、以下の生成規則のとき、

文字列は、

S ⇒ AB ⇒ aB ⇒ abBb ⇒ abbb

のように導出することができる。

生成規則は1つ1つ順番に適用すること。A⇒aA⇒aaAをA⇒aaAと省略して書くのはダメ。
テストでやったら減点されるみたい。

導出するときの書き方とかも細かいルールがあるみたいだけど、今回は割愛。

②最左導出・最右導出

「適当に非終端記号選んで置き換えちゃえ！(´O∀O)/」とやると、文法によっては正しい構文構造を得ることができなくなることがある（列挙忘れとかもありそう）。

実際に受理する文字列を列挙する際には、左から優先的に非終端記号を変形していく最左導出、右から優先的に非終端記号を変形していく最右導出のどちらかで行う。

最右導出の例

①で行った導出は、最左導出を用いている。
最右導出で適用すると、

S ⇒ AB ⇒ AbBb ⇒ Abbb ⇒ abbb

となる。（結果は同じね）

③列挙する

実際に上の文法Gに含まれるような言語L(G)を列挙していく。

例えば、6文字以下のL(G)に含まれる言語を探すとき、最左導出で構造木を用いて列挙すると、以下の画像のようになる。

よって、L(G)に含まれる6文字以下の文字列は

ab, abbb, abbbbb, aaab, aaabbb,aaaaab

の6個になる。

④列挙結果から言語を推測する

与えられた文字列や記号列の集合をもとに、それが属するであろう言語を推測する。

今回の場合、aが奇数回続いた後にbがさらに奇数回続くような文字列が受理されていることが分かる。

数式で表すと以下のようになる。

例題

Q1

以下の生成規則の中で、文脈自由文法の生成規則となりうるものを全て選べ

1. aXb → aYb
2. S→GoldenDatabase
3. 式→式＋項
4. 数式→数字＋記号
5. AcA→acaa

答え

「左辺が非終端記号1つの生成規則」のみが文脈自由文法の生成規則としてふさわしいので、➁ , ➂ , ➃ が正解。

Q2

以下の文脈自由文法Gのとき、

A→abA
A→B
B→bC
C→c

Gが生成する記号列を正規表現で表せ。

答え

A⇒abA⇒abB⇒abbC⇒abbc
A⇒abA⇒ababA⇒ababB⇒ababbC⇒ababbc
A⇒abA⇒ababA⇒abababA⇒abababB⇒abababbC⇒abababbc

となるので、導出される記号列は

である。

文脈自由文法以外の文法

文法の種類は、制限の強さによって4種類に分類することができる。

置き換えルールに制限がない0型が最も複雑な言語であり、3型が最も単純な言語だと言える。

基本・応用情報技術者試験においては、文脈自由文法しか出題されない（らしい）。

参考