解析表現文法のこと

パーサーにかかわることについて勉強していて引っかかったのがPEG（解析表現文法）という文法です。CFG（文脈自由文法）やCSG(文脈依存文法）は生成文法、つまり文章を生成するときに使いやすい表記であるのに対し、PEGは解析、つまりパース時に使いやすい表記になっているという特徴があります。

Packrat Parsing: a Practical Linear-Time Algorithm with Backtrackingという論文を読んでいるのですが、これはPEGの一種であるところのTDPL:Top down parsing languageという種類の文法で表現された言語をパースするパーサーを生成するPappyというパーサージェネレーターライブラリをHaskellで実装する論文です。

まだ消化し切れてはいないのですが、TDPLという文法は再帰降下型パーサーの動作にとても近い形で文法を表現できるという特徴があり、さらに、CFGとは違いAmbiguityを文法表現に含むことができないという特徴を持っているようです。ちなみにある文法がAmbiguousであるというのはどういうことかというと、それはつまり一つの文章の解釈が2通り以上あるということです。
前回も書いた受け売りですが、あるCFGで記述された言語があるときに、それがAmbiguousであるかどうかというのは一般的にはundecidableなので、Amibiguityを取り扱いたくない場合にはPEGは有利ですね。(逆に言うとAmbiguityが当然のようにある自然言語などはPEGは不適ということになりますね。)

更に、CFGで記述された言語を解析するパーサーの計算コストはO(n^2)からO(n^3)の間で、CFGがAmbiguousでない言語を解析するパーサーの中にはO(n^2)の計算コストのものが存在するようです。これに対して今回の論文で取り上げられているパーサーはPEGな文法で表現された言語をO(n)でパースすることができるようです。計算コストを抑えるためにpackratという呼び名の由来であるメモ化をして、メモリ消費を増やして計算コストを抑えるという戦略をとっているようです。

CFGといえば代表的なものの一つとしてBNFがあるわけですが、プログラミング言語がBNFで表記されたものを見ると、大体トークン単位で、変数名や関数名の定義などの部分では文字単位まで踏み込んでいたりすることもありますが、いわゆる予約語、Haskellで言うところのimportとかmoduleとかnewtypeなどはトークン単位であって、実際パーサーを書くときには文字レベルでパースする段階で予約語と変数名などを判別するためのCFGを書こうとすると相当複雑になってしまうようです。それ以前にソースコード内のタブ、改行、スペースなどからなる空白を適切に扱うことすらかなり面倒なことをしなくてはいけないようで、実情として、CやC++のソースコードを文字列で読み込んで、じかに構文木を吐き出すパーサーというのは存在しないとまでは言いませんが（何分不勉強ですので）、かなり珍しい&難しいもののようです。だいたいが多段式のパーサーになっているようです。

振り返って、PEGのほうでは、予約語や空白などの処理も文法表記に割りと自然に組み込むことができて更に構文木を出力するのもCFGベースのパーサーに比べてずいぶんと楽なようです。

こうなってくるとCFGとはおさらばしてPEGでやったほうが全然よさそうですね。

なんと言うか、概要の概要になってしまって、あんまり実がないのですが、今日はとりあえずこの辺で…

ではでは。