日々の流転

λ. “Parsing Expression Grammars: A Recognition-Based Syntactic Foundation” by Bryan Ford

•  <URL:http://portal.acm.org/citation.cfm?id=964011>
•  <URL:http://pdos.csail.mit.edu/~baford/packrat/popl04/>
•  スライド

PEGのオリジナル論文だが、今頃になって読んだ。

PEGって理論的な性質とか全然証明されていないものだと思い込んでいたけど、結構色々証明されてるのね。 そんなことも知らずに、「CFG⊆PEGならO(n²)より小さな計算量のBMMが作れて矛盾、とか言えないんだろうか。」*1とか言ってたのかよ、という感じだけど。

面白かったのは、やはりPEGで表現できる空列εを含まない言語は、述語(predicate)を含まないPEGで表現できるという話。 述語を除去する変形がとても巧妙。

関連

• Parsing expression grammar (PEG) - ヒビルテ(2006-09-09)
• Packrat Parsing: Simple, Powerful, Lazy, Linear Time. Bryan Ford - ヒビルテ(2006-01-09)