計算基礎論文脈自由文法 (context

計算機の能力差
内容
文脈自由文法
構文解析
Chomsky 標準形
計算機の能力差
内容
文脈自由文法
構文解析
Chomsky 標準形
計算機の能力差
2 つの計算機 A と計算機 B
計算基礎論
文脈自由文法
(context-free grammar)
計算機 A でできることで，計算機 B でできないことがある
また，計算機 B でできることで，計算機 A でできないこと
がある
.
⇒ 計算能力の比較不能
.
宮野英次
[email protected]
2009 年
計算機の能力差
内容
文脈自由文法
計算機 A でできることは計算機 B でも必ずできる
しかし，計算機 B でできることで，計算機 A ではできない
ことがある
.
⇒ 計算能力の比較可能
⇒ 計算機 B の方が強力であり，能力が高い
構文解析
Chomsky 標準形
計算機の能力差
内容
内容
第2回 ∼ 第4回
FA と正規表現は，本質的に等価な言語の記憶法
{0n1n|n ≤ 0} のような幾つかの単純な言語を記述不可能
第 5 回，第 6 回
より強力な言語記述法: 文脈自由文法 (context-free
grammar)
文脈自由文法
構文解析
Chomsky 標準形
文脈自由文法の例
回文 (palindrome)
トマト，しんぶんし，
．
．
．
01100110，110101101011，
．
．
．
回文の言語 (回文の集合)
Lpal = {w|w ∈ {0, 1}∗, w = wR}
文脈自由文法
再帰的な構造を記述可能
Lpal は正規言語ではない．正規表現では表せない．
プログラミング言語の仕様記述などで利用
再帰的定義は可能:
(Basis) ε，0，1 は回文
(Intduction) w が回文ならば，0w0，1w1 も回文．0 と 1 で
作られる回文は，これらの規則で構成できるものに限られる
マークアップ言語 (XML, HTML)，文章型定義 (DTD)
コンパイラやインタプリタの構文解析部 (parser)
文脈自由言語 (context-free language)
より強力なプッシュダウン・オートマトン
文脈自由文法: 言語を形式的に記述する記法
計算機の能力差
内容
文脈自由文法
構文解析
Chomsky 標準形
計算機の能力差
内容
文脈自由文法
文脈自由文法
構文解析
Chomsky 標準形
生成文字列
文法
以下の方法で生成された文字列全体を文法が生成する言語
生成規則 (production) または書き換え規則 (substitution
rule) の集まりからなる
書き換え規則は矢印により分離された文字と文字列
.
文字は変数と呼ばれる
文字列は，変数と終端記号と呼ばれる特別な文字からなる
.
.
1
開始変数を書き下す
2
書き下された変数とその変数で始まる規則を探す．
3
書き下された変数を規則の右辺で置き換える
4
変数がなくなるまでステップ 2 および 3 を繰り返す
変数文字は，多くの場合大文字
.
終端記号は，多くの場合小文字，数，特別な文字
.
文法 G1 の場合 (A → 0A1, A → B, B → ])
例えば，文字列 000]111 などを生成
ある変数が開始変数 (第 1 規則の左辺の変数とする)
文法 G1
A → 0A1
A→B
B→]
計算機の能力差
.
文法 G1 は 3 つの規則
G1 の変数は A と B ．A は開始変数
G1 の終端記号は，0, 1, ]
内容
文脈自由文法
構文解析
導出列 (derivationa)
.
A ⇒ 0A1 ⇒ 00A11 ⇒ 000A111 ⇒ 000B111 ⇒ 000]111
.
Chomsky 標準形
計算機の能力差
内容
構文解析木
文脈自由文法
文脈自由文法の言語
構文解析木，parse tree
文法 G1 の場合 (A → 0A1, A → B, B → ])
文法 G1 における 000]111 に対する構文解析木
A ⇒ 0A1 ⇒ 00A11 ⇒ 000A111 ⇒ 000B111 ⇒ 000]111
文脈自由言語
Context-Free Language, CFL
文脈自由文法が生成した文字列の全体
文法 G の言語を L(G) と書く
A
文法 G1 の場合
A
L(G) = {0n]1n|n ≥ 0}
A
0
0
0
A
A → 0A1|B
B
B → ]
#
1
1
1
構文解析
Chomsky 標準形
計算機の能力差
内容
文脈自由文法
構文解析
Chomsky 標準形
計算機の能力差
内容
文脈自由文法の形式的な定義
文脈自由文法
構文解析
Chomsky 標準形
文法の言語 (language of the grammar)
生起する
定義 2.2
u, v, w が変数や終端記号の列
文脈自由文法 (context-free grammar) は 4 個組 (V, Σ, R, S)
A → w が文法規則ならば，
uAv が uwv を生起するといい，uAv ⇒ uwv と書く
1
V は変数 (variable) と呼ばれる有限集合
2
Σ は終端記号 (terminal) と呼ばれる V と共通部分を持た
ない有限集合
3
R は変数 (左辺) および変数と終端記号の文字列 (右辺) から
なる規則 (rule) の有限集合
.
4
u = v であるか，または，
k ≥ 0 に対して，系列 u1 , u2 , · · · , uk が存在し，
u ⇒ u1 ⇒ u2 ⇒ · · · ⇒ uk ⇒ v
∗
であるならば，u ⇒ v と書く
S ∈ V は開始変数
文法の言語
.
∗
集合 {w ∈ Σ∗|S ⇒ w} を文法の言語という
.
.
計算機の能力差
内容
文脈自由文法
構文解析
Chomsky 標準形
計算機の能力差
内容
文脈自由文法
構文解析
.
文脈自由文法の例
.
文脈自由文法の例
文法 G = ({S}, {0, 1}, R, S)
規則集合 R: S → 0S1|ε
例 2.2
文法 G3 = ({S}, {a, b}, R, S)
規則集合 R: S → aSb|SS|ε
.
生成する文字列
生成する文字列
ε, 01, 0011, 000111, 00001111, · · ·
ab, abab, aabb, aaabbb, aababb, · · ·
言語 B = {0n1n|n ≥ 0}
a を左括弧「(」，b を右括弧「)」と見ると，
(), ()(), (()), ((())), (()())
L(G3 ) は，正しく入れ子構造になった括弧列すべてからな
る言語
復習
言語 B = {0n1n|n ≥ 0} は正規ではない
Chomsky 標準形
計算機の能力差
内容
文脈自由文法
構文解析
Chomsky 標準形
計算機の能力差
内容
文脈自由文法
Chomsky 標準形
構文解析
Quiz 5-1
プログラミング言語でのコンパイル
問: 回文に対する文脈自由文法を求めなさい
∗
構文解析
コンパイラの構文解析
Lpal = {w|w ∈ {0, 1} , w = w }
R
コードの「意味」解析
例: 異なる 2 つの式 (文字列)
a+a×a
2 項目の「a × a」を行ってから，1 項目の a と加算を行う
(a + a) × a
1 項目の「a + a」を行ってから，a と乗算を行う
⇓
(異なる) 文脈自由文法における構文解析木に対応
計算機の能力差
内容
文脈自由文法
構文解析
Chomsky 標準形
計算機の能力差
内容
文脈自由文法
文脈自由文法の例
文法 G4 = (V, Σ, R, hEXPRi)
V = {hEXPRi，hTERMi，hFACTORi}
Σ = {a, +, ×, (, )}
規則集合 R
hEXPRi
hTERMi
hFACTORi
→
→
→
異なる hEXPREi に対して異なる構文解析木
<EXPR>
<TERM>
<TERM>
<EXPR>
<EXPR>
<TERM>
(a + a) ×a + a × a
| {z }
| {z }
hTERMi
hFACTORi
|
{z
}
hTERMi
Chomsky 標準形
構文解析木
hEXPRi + hTERMi | hTERMi
hTERMi × hFACTORi | hFACTORi
(hEXPRi) | a
Example:
構文解析
<FACTOR>
<EXPR>
<TERM>
<EXPR>
<TERM>
<FACTOR>
<FACTOR> <FACTOR>
<FACTOR>
<TERM>
<TERM> <FACTOR>
<FACTOR>
a
+
a
a
( a
+
a )
a
計算機の能力差
内容
文脈自由文法
構文解析
Chomsky 標準形
計算機の能力差
内容
曖昧性
文脈自由文法
構文解析
Chomsky 標準形
曖昧の定義
同じ文字列に対しては同じ構文解析木になるか?
No !
曖昧
2 つの異なる構文解析木を持つとき
文法 G5 = {{hEXPRi}, {a, +, ×, (, )}, R, hEXPRi}
2 つの異なる導出列を持つときではない
(単に変数を置き換える順番が異なっている場合など)
規則集合 R
hEXPRi → hEXPRi + hEXPRi | hEXPRi × hEXPRi
最左導出列
hEXPRi → (hEXPRi) | a
変数を置き換える順番を固定
<EXPR>
<EXPR>
<EXPR>
a
<EXPR>
<EXPR>
<EXPR>
<EXPR>
+
a
<EXPR>
a
a
+
導出列で，すべてのステップにおいて最も左に残っている変
数を置き換えるような導出列
<EXPR>
a
<EXPR>
定義 2.7
a
文字列 w が 2 つ以上の異なる最左導出列を持つならば，その文字
列は文脈自由文法 G において曖昧に導出される．文法 G がある
文字列を曖昧に生成するならば，G は曖昧である
上のような文法を曖昧であるという
計算機の能力差
内容
文脈自由文法
構文解析
Chomsky 標準形
計算機の能力差
内容
本質的に曖昧
構文解析
Chomsky 標準形
Chomsky 標準形
文脈自由文法を用いた作業を行うとき，それらを単純化した
形式にすると便利であることが多い
最も単純で有用な形式の一つとして Chmomsky 標準形が知
られている
.
定義 2.8
.
ある曖昧な文法に対して，同じ言語を生成する曖昧でない文
法を見付けることができる場合がある．
しかし，いくつかの文脈自由言語の中に，曖昧な文法によっ
てのみ生成されうるものがある．
すべての規則が
例:
言語 {aibj ck | i = j, または, j = k}
(証明) 省略．
文脈自由文法
..
A → BC
.
A → a
.
という形である文法を Chmosky 標準形 (Chomsky normal
form) という．ここで，a は任意の終端記号，A は任意の変数，
B と C は開始変数ではない任意の変数である．ただし，開始変
数 S に対しては，規則 S → ε を加えてもよい
計算機の能力差
内容
文脈自由文法
構文解析
Chomsky 標準形
計算機の能力差
Chomsky 標準形の性質
内容
文脈自由文法
構文解析
Chomsky 標準形
証明 (定理 2.9)
1．新しい変数 S0 と規則 S0 → S を追加する
定理 2.9
ただし，S は元々の開始変数
任意の文脈自由言語は，Chomsky 標準形の文脈自由文法により
生成される
.
2
A → ε の形式のすべての ε 規則を消去する
3
A → B の形式のすべての単位規則を消去する
4
残りの規則を適切な形式に変換する
.
証明のアイデア:
任意の文法を Chomsky 標準形に変換できることを示す
.
1 新しい開始変数を加える
開始文字が規則の右辺に現れないことを保証
2．A が開始変数でないような A → ε 形式の規則を除去し，そ
の代わりに，規則の右辺に A が出現するたびに，その出現した
A を削除した新しい規則を加える
u と v が変数や終端記号の文字列である規則 R → uAv に
対して，規則 R → uv を加える
規則 R → uAvAw に対しては，R → uvAw ，
R → uAvw，R → uvw を加える
規則 R → A に対しては，以前に規則 R → ε を除去してい
ない限り R → ε を加える
開始変数以外について，これらの作業を繰り返す
計算機の能力差
内容
文脈自由文法
構文解析
Chomsky 標準形
.
証明 (つづき)
.
.
.
3．単位規則 A → B を除去し，その代わりに，規則 B → u が
現れるときはいつでも，規則 A → u を加える．
ただし，A → u が以前に除去した単位規則のときは加え
ない．
すべての単位規則を消去するまで繰り返す
4．残りの規則を適切な形式に変換する
まず，規則 A → u1 u2 · · · uk (k ≥ 3) に対して，
A → u1 A1 ，A1 → u2 A2 ，A2 → u3 A3 ，· · · ，
Ak−2 → uk−1 Ak−1 で置き換える．ただし，ui は変数か終
端記号，Ai は新しい変数である．
k = 2 のとき，規則 A → u1 u2 に対しては，各終端記号 ui
を新しい変数 Ui で置き換え，規則 Ui → ui を加える

Download Report