* PEG 文法について

0. このテキストについて

PEG 文法の説明。十分に理解できていないために、まずい説明となっている。
雰囲気だけでも伝えられれば、と。

文法の定義は、EBNF を使うのが最も簡単であり、人間にとってわかりやすい。
しかし、それを使わずに、LALR(1) 文法等を使ってきた理由は、
解析の効率の問題にあった。
PEG は、現在の潤沢になってきたメモリ等を背景に考えると、書きやすさや、
表現できる文法の広さと、解析速度とのバランスにおいて、
今後有望な技術である。

1. 構文解析について

与えられた記号列が既定の文法に則しているかを判定する。
判定しながら、木構造を構築していくことが多い。

2. 文法の種類と力関係

正規文法 < 文脈自由文法 < 文脈依存文法 < 制限のない文法

右に行くほど表現できる文法の幅が広がる。
正規文法はくりかえしは表現できるが、入れ子になった文法は表現できない。
文脈自由文法は入れ子になった文法も表現できる。
文脈依存文法は前後の要素によって
それらにはさまれる部分の解釈を変えることができる。

現在一般的に使われているのは文脈自由文法の範囲での構文解析器である。
文脈自由文法をコンピュータで解析する方法に以下のような種類がある。
力関係(表現できる文法の広さ)で昇順に並べる。

LL法 < SLR法 < LALR法 < LR法 < GLR法

LL(1)、LALR(1)、LR(1) のように後ろに数字をつけて「先読み」の数を示す。
先読みがひとつである、というのはひとつ先のトークンを読めば解析結果が
唯だひとつに定まるということ。

GLR法は文脈自由文法のすべてを解析できる。この場合、解析結果は複数になる。
しかし、速度は最悪の場合 O(n^3) となる。
つまり、入力の長さの3乗のオーダーで速度が低下する。

解析の効率(速度)と解析できる文法の広さのバランスから、LALR(1) が広く使われている。
yacc も LALR(1) を使っている。

3. BNF 記法

文脈自由文法を表現する表記法のひとつである。人間にとって書きやすい表記法であると思われる。

例:
statement = statement-1 | prenex statement

この表記の意味は、statement は statement-1 の前に 0個以上の prenex をつけたもの
ということ。

4. PEG 文法

BNF と記法自体はよく似ている。
ただし、BNF では曖昧性を許すのに対して PEGでは曖昧さがない。
PEG ではそれぞれの選択肢に優先順位がある。
考えかたとして、PEG ではその表記がコンピュータの動作に対応づけられる。

e1 / e2 という選択において、コンピュータの動作としては、
まず e1 を試み、それが失敗した場合にのみ e2 を試みる、という動作となる。

例
statement = statement-1 / prenex statement

5. PEG の力

PEG で表現可能な文法の幅がどの程度なのかよくわからないが、
すくなくとも LALR よりは広いと思われる。
おそらく文脈自由文法の大部分と、文脈依存文法の一部といったところか。

6. Packrat parsing

上記のように PEG 文法はコンピュータの動作と対応しているので
構文解析器を作るのは簡単である。
しかし、素直な設計にしてしまうと、指数関数的に処理速度が低下してしまう(O(c^n))。
よって、途中の結果をメモしながら構文解析する方法として、
Packrat parsing という手法がある。
この手法だと線形時間(O(n))で解析が終了する。
これは、Haskell の遅延評価(必要とされるまで計算を遅らせること)という仕組みを
うまく使うことで比較的簡単に作ることができる。
ただし、この場合、メモリの使用量も入力に比例して増加する。
コンピュータのメモリ搭載量が潤沢になったので実用的となった。

例
message = greeting name
greeting = "hello" / "good-bye"
name = "world" / "iocikun"

上記のような文法で ["hello", "iocikun"] をパースするとする。
すると、

+----------+------------------------+----------------+
| position | 0                      | 1              |
+----------+------------------------+----------------+
| message  | "hello" "iocikun" -> 2 | Nothing        |
+----------+------------------------+----------------+
| greeting | "hello" -> 1           | Nothing        |
+----------+------------------------+----------------+
| name     | Nothing                | "iocikun" -> 2 |
+----------+------------------------+----------------+
| token    | "hello" -> 1           | "iocikun" -> 2 |
+----------+------------------------+----------------+

結果としては、このような表が作られる
(ただし、遅延評価なので、終了時に、この表のすべてのマスがうめられているとは限らない)

その作られかたを説明する。
欲しい結果は message というルールを先頭 (位置 0) に適用した結果なので、
(message, 0) を見る。
message の先頭は greeting なので、(greeting, 0) を見る。
greeting の中身は token であり、その内容は "hello" または "good-bye" で、
今回の token の内容は "hello" であり一致する。
-> のさきは次に進む位置を示している。
よって (greeting, 0) は "hello" -> 1 となり、
(message, 0) は "hello", (name, 1) となる。
(name, 1) を見ると同様に "iocikun" -> 2 となっているので、
結果として message は "hello" "iocikun" -> 2 となる。

7. PEG を使ううえでの注意点

まずは、知ってる人は知っている、左再帰の問題がある。
PEG だけではなく、LL などの再帰下降型パーサに分類されるものであれば同じことだが、
以下のような文法は解析できない。

tanru = tanru brivla / brivla
( melbi cmalu nixli ckule -> ((melbi cmalu) nixli) ckule )

これは、
tanru = brivla tanru / brivla
( melbi cmalu nixli ckule -> melbi (cmmalu (nixli ckule)) )
のような形に直してやる必要があり、木構造は後で調整する必要がある。

また、たとえば、
abc = ab 'c'
ab = 'a' 'b' 'c' / 'a' 'b'
のような文法において、abc は 'a' 'b' 'c' にはマッチしない。
これは、PEG においては、非終端記号を越えて、バックトラックしない、ということだ。
つまり、一度 ab の値が 'a' 'b' 'c' に決まってしまったらそれは変化しない。

これは、たとえば、
SE = 'f' 'a' / 'f' 'a' 'i' のようにしてはならず、
SE = 'f' 'a' 'i' / 'f' 'a' のようにするか、あるいは、
SE = 'f' 'a' !'i' / 'f' 'a' 'i' のようにする必要があることを示す。
(! は否定の先読み、つまり上の場合では次に続く文字が 'i' では無いということ)

8. PEG と yacc(LALR(1))

実際に使われている例を一見して明らかな大きな違いは、
yacc がまずは字句解析によって、
文字列をトークン列に変えてから構文解析するのに対して、
PEG では字句解析と構文解析とを統一的に行うことができるということがある。
PEG が無読に先読みが可能であり、文字をトークンとすることができるためだ。

9. ZOI と PEG

ZOI によって作られる構造はプレインな PEG で直接扱うことはできない。
以前に作ったパーサでは ZOI の後に来るセパレータを NULL 文字に置き換えるという
ad-hoc なやりかたを取った。

10. papillon

ZOI をパースすることのできる独自のパーサジェネレータ papillon を作成中。
解析中に読んだ値を、後の解析で利用できる。
papillon 自体のパーサが papillon で作られている。
機能はほぼできあがり、機能の検証とソースコードのリファクタリング中。
ただし、まだ、細かい修正が必要。

ZOI は以下のようにできる。
zoi :: Type = b:word ws:(w:word[w /= b] { w })* e:word[e == b]	{ (b, ws, e) }
読みくだすと、まずは word を読み、その値を b に保存。
b ではない word (w /= b) を 0個以上(*) 読み込み、その後に b に等しい word (e == b)
を読み込む、となる。

ちなみに回文もパース可能(以下は偶数文字の回文のパーサ)。
palindrome :: String = c0 p:palindrome c1:[c1 == c0] { c0 : p ++ [c1] } / { "" }

訂正(2015/01/22):
	「回文もパース可能」という表現は半分だけしか正しくない。
	「回文の"一部は"パース可能」ということだ。
	たとえば「abbaabba」のような並びも回文だが、
	この場合ひとつめのabbaまででパースが終了してしまうため、
	全体をパースすることはできない。