形式文法
形式言語とは、文字列の集合（例えば英単語や英文)であって、形式文法は、可能な全ての文字列の集合(終端文字の集合)から言語を定義ための規則(生成文法)と、言語中のある文字列が、どの様な生成規則で生成されたかを調べる規則(分析文法)から成る。
Parsing Expression Grammarは、形式言語を生成するための分析形式文法である。
生成文法
単純な例
終端文字の集合が{$a$}である時、言語{$a,aa$}を生成してみる。
$f:S\rightarrow a$
$g:S\rightarrow aa$
Sは非終端文字であり、開始文字でもある。
非終端文字とは、終端文字でない文字である。
開始文字とは、言語となる非終端文字である。
開始文字を生成規則の再帰的な組み合わせによって変換して得られる終端文字の繰り返しの集合を、言語として定義する。
今の例では、$f,g$を再帰的に適応しても$f,g$そのものしか得られない。
また、$f,g$の右辺は終端文字の繰り返しとなっている。
再帰的な生成の例
終端文字の集合が{$a,b$}の時、言語{$a^nba b^n|n\geq 0$}を生成する。ただし、文字列の累乗は繰り返しを意味する。
次の生成規則を用いればよい。
$f:S\rightarrow ba$
$g:S\rightarrow aSb$
$g$を$n-1$回$g$に作用させると $g^n : S\rightarrow a^nSb^n$という変換規則が生成される。
$f$を$g^n$に作用させると $f\circ g^n : S\rightarrow a^nbab^n$という変換規則が生成される。
従って、生成文字から言語{$a^nba b^n|n\geq 0$}を生成できる。
複雑な左辺の例
形式文法の生成規則において、左辺は、少なくとも1文字の非終端文字を含んでいれば、どの様な終端文字と非終端文字の組み合わせでも良い。
例えば、終端文字の集合が{$a,b,c$}であって、言語{$a^nb^nc^|n\geq 0$}を生成するには次の生成規則を用いればよい。
$f_1:S\rightarrow abc$
$f_2:S\rightarrow aBSc$
$f_3:Bb\rightarrow bb$
$f_4:Ba\rightarrow aB$
これを再帰的に組み合わせると、
$f_1: S\rightarrow abc$
$f_3^n \circ f_4^n\circ f_1^{n-1}\circ f_2^n : S \rightarrow a^n b^n c^n\quad n>1$
以上の例で見た様に、生成文法とは、
終端文字の集合、
非終端文字の集合、
生成文字、
非終端文字と終端文字の組み合わせからなる文字列の変換規則からなる。
また、変換規則を繰り返し作用し、最終的に終端文字列を得る事を導出する等と言う。
演算子
生成文法の記法を簡略化するために、いくつかの生成規則が用いられる事がある。
代表的な物に、
sequence
choice (|)
zero-or-more (*)
one-or-more(+)
optional(-)
等がある。
括弧の中に代表的な対応する演算子を記した。
これらはBNFで良く用いられる。
演算子とは言っても、結局の所、非終端記号である。
sequenceは文字列の連結である。例えば$\mathrm{sequence}(A_1,A_2)\rightarrow A_1 A_2$である。
choiceは、"又は"を意味し、$ A_1|A_2\rightarrow A_1$、$A_1|A_2\rightarrow A_2$という生成規則を持つ事を意味する。
zero-or-moreは、0個以上を意味し、$ *A\rightarrow empty$、$ *A \rightarrow A$、$ *A \rightarrow A ( *A) $ という生成規則を持つ事を意味する。
one-ore-moreは、1個以上を意味し、 $ +A\rightarrow A$、$+A\rightarrow A(+A)$という生成規則を持つ事を意味する。
optionalは、0または1個を意味し、$ -A\rightarrow empty$、$-A\rightarrow A$という生成規則を持つ事を意味する。
一項演算子が前置か後置かは定義によって異なる。ここでは前置とした。
分析文法
ある生成文法で生成された言語において、導出された終端文字列を得るための、生成過程、すなわち変換規則の作用過程を逆に求める事を、分析する、あるいは構文解析等と呼ぶ。
ある導出された文字列が一意な生成過程を持たない生成文法は、曖昧であると呼ぶ。
分析文法とは、生成文法のうち、分析方法が定義される文法である。
分析文法では、導出可能な文字列の集合が言語として定義される。
分析文法では、生成規則を特定しなくても、導出可能かどうかを判定する規則を定義すれば、言語が定義できる。
分析文法の一つとして、Parsing Expression Grammar(PEG)がある。
Parsing Expression Grammar
PEGは分析文法である。
PEGは終端文字の集合と非終端文字の集合を持つ。
分析規則
分析文法は複数の分析規則$S\rightarrow e$及び$e_1\rightarrow e_2$からなる。
$S$は非終端文字で、$e,e_1,e_2$は分析表現である。
ある非終端文字を左辺にもつ分析規則はただ一つでなければならない。
分析規則は終端文字列に対して、bool値と次の分析対象となる文字列を返す。
trueであれば、分析可能であり、falseであれば分析不可能である。
trueを返す事を、マッチする等とも言う。
以下では返り値を$(bool,string)$等と表現する。
分析表現
終端文字、非終端文字、空文字は対応する分析表現を持つ。
分析表現$e,e_1,e_2$に対して、$e_1 e_2$、$e_1|e_2$、$*e$、$+e$、$-e$、$\&e$、$!e$は分析表現である。
空文字に対応する分析表現、$empty$は常に$empty(x)=(true,x)を返す。$x$は終端文字列である。
終端文字$s$に対応する分析表現、$s$は、$s$と$x[0]$が等しければ、$s(x)=(true,x[1...])$、そうでなければ$s(x)=(false,x)$となる。
$x[n]$な文字列の先頭を0番目として数えた$n$番目の文字であり、$x[1...]$は$x[1]x[2]..$という先頭を除いた文字列である。
この様に与えられた文字列が短くなって返る事を入力を消費する等と言う。
非終端文字$S$に対応する分析表現、$S$は、分析規則に$S\rightarrow e$を持ち、$S(x)=e(x)$を返す。
$e\rightarrow e_1 e_2$という分析表現は、$e_1(x)$を実行し、$false$を返せば、$(e_1e_2)(x)$の返値として$(false,x)$を返す。
$e_1(x)$が$true$を返せば、$e_1(x)$の返した文字列$y$を引数として$e_2(y)$を実行し、$e_2(y)$の返値を$(e_1e_2)(x)$の返値として返す。
この定義は重要で、$e_1$がマッチすると、$e_2$のマッチの可否によらず、入力が消費される。
$e\rightarrow e_1|e_2$という分析表現は、$e_1(x)$を実行し、$true$ならば$(e_1e_2)(x)$の返値として$e_1(x)$の返値を返し、$false$ならば$e_2(x)$の返値を返す。
$e\rightarrow *e_1$という分析表現は、$e_1$が返す文字列を引数として$e_1$の呼び出しを繰り返す。$e_1^n(x)$が初めて$false$を返す時、全体の返り値として$e_1^{n-1}(x)$を返す。
$e\rightarrow +e_1$という分析表現は、$e_1(x)$が$false$を返せば、全体の返値として$(false,x)$を返し、$true$を返せば、$e_1(x)$の返す文字列$y$に対して、全体の返値として$*y(x)$を返す。
$e\rightarrow -e_1$という分析表現は、$e_1(x)$が$true$を返せば、全体の返値として$e_1(x)$を返し、$false$を返せば全体の返値として$(true,x)$を返す。
$e\rightarrow \& e_1$という分析表現は、$e_1(x)$が$true$を返せば、全体の返値として$(true,x)$を返し、$false$を返せば、全体の返値として$(false,x)$を返す。
$e\rightarrow ! e_1$という分析表現は、$e_1(x)$が$true$を返せば、全体の返値として$(false,x)$を返し、$false$を返せば、全体の返値として$(true,x)$を返す。
これらの分析表現等の振舞のいくつかは非自明な振舞をするため、パーサーの動作が期待通りにならない時は、定義を良く確認するべきである。