Route 477(2008-10-23)

2008-10-23

■ [prog] 正規文法、文脈自由文法、解析表現文法

について調べたのでまとめ。それぞれ Regular Grammer(RG), Context Free Grammer(CFG), Parsing Expression Grammer(PEG)とも。

解析表現文法はPEGって呼ばれる方がずっと多いよね。てかPEGが「文法」の一種であることを今まで分かってなかった(^^; 「パーズ関係の新しいやつでしょ」みたいな。

正規文法 < 文脈自由文法 =?< 解析表現文法の順で、表現できる言語が増える。 (追記：CFG<PEGであるとはまだ証明されていないそうです(コメント欄を参照))

正規文法はいわゆる正規表現のもとになったやつ。(現在のLLのRegexpは拡張されまくりなので正規文法以上のものも解析できる)
文脈自由文法はBNF記法で書けるやつ。
- 文脈自由文法(のサブセット)の解析方法として、LL法とかLR法がある。さらに、いくつ先読みを許すかによってLR(1)とかLL(k)がある。
- 先読み個数が多いほど文脈自由文法の限界に近づけるが、多くのプログラミング言語の文法はLR(1)の範囲で解析できるらしい。
  - LR法の中にさらに「○○LR法」という分類があり、例えばyaccやbisonが対応しているのはLALR法。
解析表現文法(PEG)はわりと新しい文法で、プログラミング言語の解析に向いているらしい(曖昧さが残らないとか、レキサーがいらないとか)。
- PEGの範囲の言語は再帰下降方式*1で解析できるらしい。
- もっと効率のいい解析方法として、Packrat Parserが知られている。

図にすると以下のような理解でいいのかな。

(複雑)
  ↑
  ｜ 解析表現文法(PEG)?
  ｜ 文脈自由文法(CFG) - BNF
  ｜       LL(k) LR(k)
  ｜         :     :
  ｜       LL(1) LR(1) - yacc, bison (LALR(1))
  ｜
  ｜ 正規文法(RG)
  ↓
(単純)

*1 一言でいうと、パーザを手書きしたらこうなるよねっていう感じのやつ

本日のツッコミ(全3件) [ツッコミを入れる]

□ k.inaba (2008-10-23 16:35)

"文脈自由文法 < 解析表現文法" とは限らない、と思います（CFGで書けるけどPEGでは書けない文法がある、と予想されています。PEGは必ずPackrat ParserでO(n)時間でParseできるけれど、CFGについては知られている最速のアルゴリズムがO(n^2.6)くらい…という現状などが傍証）。

□ shiro (2008-10-23 17:46)

まだ証明はされていないんでしたっけ＞CFGで書けるけどPEGで書けない文法 何か回文のようなやつがPEGでは無理なんじゃないか (unbounded backtrackを必要とするもの)、というような話はどこかで見たことがあるような気がするのですが… (ざっと検索するとそういう質問は出てくるけどはっきりした答えは見つけられませんでした。)

□ yhara (2008-10-23 20:04)

ありがとうございます。 Wikipediaに > 全ての形式言語が文脈自由ではない。文脈自由でない例として {a^n b^n c^n | n>=0} がある。 > この言語は解析表現文法（PEG）で生成できる。PEG はプログラミング言語に適した新たな定式化のひとつである。 とあったので、CFG<PEGと勘違いしてしまいました。英語版には同様の記述がないなぁ。

トップ «前の日記(2008-10-22) 最新次の日記(2008-10-29)» 編集

Route 477

2008-10-23

■ [prog] 正規文法、文脈自由文法、解析表現文法

最近のツッコミ

自著

はてブ