kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

おーぷんぷろぶれむ!(1) ~ PEL ⊃ CFL 問題

こんばんは。久しぶりにブログ書いてみることにしたのですが、以前と同じネタだとモチベーションが保てないので、今回はちょっと変わったタイトルにしてみました。

平仮名にしたかっただけだろうおまえと言われそうですね。はいそうです。

というのはおいといて、たいとるのおーぷんぷろぶれむ(Open Problem)ですが、日本語では未解決問題と訳すことが多いようです。読んで字のごとく、未だ解決されていない問題のことです。存在する(はず)だけど見つかっていないアルゴリズムとか、真か偽かがまだわかってない命題とかのことですね。ちなみに、当たり前ですが、解決された時点でOpen Problemでなくなってしまいます。

第何回まで続くか1回で終わるかはわかりませんが、第1回では、PEL ⊃ CFL問題について紹介します。この問題は、2004年にBryan Fordによって、論文 "Parsing Expression Grammars: A Recognition-Based Syntactic Foundation""中で提起されたものです。

このOpen Problemについて非常にざっくりとした形で説明してみます。

Parsing Expression Grammar(PEG)はFordによって2004年に発表された形式文法の一種で、構成要素が非常にシンプルでありながらパワフルであり、この文法に基づいた構文解析器生成系(パーザジェネレータ)は字句解析器なしに、線形時間で入力を解析可能(Packrat Parsing)なように最適化可能という好ましい特徴を持っています。

字句解析器が不要というのは最近のプログラミング言語にはよくある文字列補間やヒアドキュメント、空白センシティブな文法といった、字句解析器殺しの文法要素を扱うのに非常に適しています。また、プログラミング言語構文解析器を考える上では、線形時間で解析可能というのも重要な要素です(入力長nに対して n2に比例した時間がかかる構文解析器なんて使いたくありませんよね)。PEGについての詳しい解説は Parsing Expression Grammar - Wikipedia辺りを参照してください。

これと対比して論じられる形式文法にNoam Chomskyが提唱した、Context Free Grammar(CFG)があります。CFGに関しては過去、現在にわたって膨大な研究が行われており、CFGおよびその変種・拡張が、形式言語の研究において主流であるといっても過言ではないでしょう。現在もっとも有名であろうパーザジェネレータであるyacc(およびその後継であるbison)はCFGに基づいた構文解析アルゴリズムであるLR法が使われています(ただし、bisonでは線形時間の保証という特徴を失うものの、LR法の拡張であるGLR法を使うこともできます)。CFGについての詳しい解説は、文脈自由言語 - Wikipedia辺りを参照してください。

形式文法の特徴をはかる一つの指標として、表現力というものが挙げられます。たとえば、言語 an bn cn(enは文字eのn回の繰り返しを表現するものとする)は CFGにより表現できないが、以下のPEGにより表現可能であることが知られています。

S ← &(A !b) a+ B !.
A ← a A? b
B ← b B? c

また、有名な例として、Regular Expressionでは一般に括弧の対応を判定できないが、CFGでは判定できるという事実があります。ある形式文法によって表現可能な言語(=文字列の集合)の集合を指して、言語クラスと呼びます。PEL(Parsing Expression Language)はPEGが表現可能な言語クラスを、CFL(Context Free Language)はCFGが表現可能な言語クラスを表します。

ようやくタイトルの、PELとCFLという用語が出てきました。PELとCFL、この2つの言語クラスはどんな関係にあるのかがFordによって説明されているOpen Problemです。まず、CFL ⊃ PELでないことは、言語 an bn cnがPEGによって表現できるがCFGによって表現不可であるという事から確実です。

では、PEL ⊃ CFLはなりたつのか、つまり、CFGによって表現できるがPEGによって表現できない言語が存在するのでしょうか。これについては未だにわかっていません。しかし、そのような言語が存在するだろうという予想はあります。どんなPEGに対しても、そこから線形時間で構文解析を行うことができる構文解析アルゴリズム(Packrat Parsing)が存在しますが、CFGに関するアルゴリズムは現在まで様々な研究があるにも関わらず、super-linearなアルゴリズムしか存在しません。もちろん、あくまで、現在までということなので、CFGに対してlinearな解析アルゴリズムがある日発見される可能性はなくはありませんが、そちらに賭けるのはどうにも分が悪そうです。

CFGでは表現可能だが、PEGでは表現不可能な言語を一つ見つけて証明するのが手っ取り早そうですが、今のところ回文がそうではないかと予想されているものの、まだ証明はありません。私も以前何日か継続して考えてみたのですが、悔しいことに、まだ証明を書くことができていません。というわけで、CFL ⊃ PELかどうかについて、良さげな証明方針のお持ちの方が居れば連絡お待ちしております(半分冗談)。

というわけで、おーぷんぷろぶれむ!(1)はPEL ⊃ CFL 問題でしたー。