パーサーのこと

Parser

id:kazu-yamamotoさんのとりとめのないパーサー談義に刺激されて
パーサーのことを勉強しているところです。yamamotoさんは｢パーサーに詳しい人に答えていただけるととても嬉しい」といわれていますが、勉強がてら自分なりの答えを書いてみようと思います。

疑問1) GLR法は、文脈依存文法(CSG)(の一部)も解析できるのか？

はなから、怪しい解答になってしまうのですが、WikiPediaの文脈自由文法(CFG)の解説によると、ある文脈依存文法により生成される言語が文脈自由言語かどうかを判断することはundecidable (判別不能？）だそうです。これはつまり、文脈依存文法での全体集合の中には文脈自由言語しか生成しない部分集合もあると言うことらしく、そういった意味では文脈自由文法を解析する能力があるGLR法は文脈依存文法の一部を解析する能力があるということはできるでしょう。

さらに、Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers – Principles, Techniques and Tools.　によると、CやJavaなどの言語の多くは文脈依存な部分があるけれど、コンパイラ内でSyntactic解析を行うコンポーネントとしてのパーサーは多くの場合パーサーの複雑性を抑えるために文脈依存性に起因するエラーは無視してしまうようです。

C＋＋などでの文脈依存性としての例として挙げられてるのが変数や関数などの宣言と参照(宣言せずに参照するとエラーになる）や、関数のパラメタ（同様に宣言と呼び出しのミスマッチはエラーになるべき)などが挙げられています。

C++コンパイラ内のパーサーの単純化についてはテンプレートをネストするときの表現が思い出されます：

TFoo< TBar> a;

みたいなことをやりたかったら、＞＞の部分にスペースを入れてやらないとコンパイルできなかったりしますよね…素人考えですが、これは文脈依存性で表現できるような気もするし、あるいはGLRでちゃんとカバーできる問題なような気もしないでもありません。

疑問2) C++ は GLR で解析できますが、文脈依存文法でしょうか？

ということで、C++は文脈依存文法であるということはできると思います。ただし、文脈依存言語を解析するパーサーが文脈依存性を解析しなくてはいけないかというと、それは必ずしもそうではないようです。要はどんな解析をさせたいかというところにかかっていて、例えば、ソースファイル内のカッコの対応がちゃんと取れているか調べるだけだったら、LL(n<∞)でも十分な気がします。そして、C++をとことんまで解析しているはずのコンパイラでさえ、パーサーの部分では文脈依存性に関する解析は行わないこともよくあるようです…
もっとも、この回答は少しあざといですね。というか、パーサをあんまり使ったことがない人がちょっと勉強しただけで出す答えかもしれません。もっと有用な問題の解釈はC++は構文木を生成させるパーサーが理解しなくてはいけない部分において文脈依存的な文法があるか？ということになるかと思うのですが、これは今の僕にはまだ理解が足らなくて答えられません。この場合は宣言と参照の違いを無視してもよいことになるので、それ以外の部分で文脈依存性があるかどうかということになります…
Wikipediaの文脈依存文法の項に出てくる文脈依存言語の例は
{a^nb^nc^n : (n >= 1)}
というもので、要は何を言っているかというと、a, b, cの3文字がそれぞれ同じ回数だけ繰り返す文字列、つまり、

abc
aabbcc
aaabbbccc
ただし
aaacccbbb
abcabcabc
などのような文字列は含まれない

なわけで、C＋＋でもカッコなどの対応はこれと似たようなパターンをとりますね。確かにファイルの先頭に｝を書くことはできないので、これは立派な文脈依存性といえるのかもしれません。あとはコメントとかも当てはまりそうですね…

疑問3) Perl も、LALR ではなく GLR を使わないと解析でないと聞きましたが本当でしょうか？ 簡単な例はありますか？
疑問4) Ruby の << や BASIC の = も GLR を使わないと解析できませんか？

PerlとRubyは知識不足で、BASICも細かいところを忘れちゃったのでスキップです…

疑問5)BNFは、文脈自由文法全体を表現する能力があるか？

WikipediaのBNFの項によると、BNFは文脈自由文法を表現するためにデザインされたようなことが書いてあります。なので、答えは「ある」ということになるような気がします。文脈自由文法の定義の一つとして、
「一つの非終端記号を任意の長さの終端と非終端記号の混ざった記号列に置き換える置き換えルールの集合で表せる文法」
というのがあるようなので、BNFでCFGが表現できるというのは妥当な気がします…

疑問6)このパーサーは、文脈自由文法全体を解析する能力があるか？

ちょっと長くなっちゃったので、これはまたの機会に…(汗)


パーサーのことを少し勉強してみてわかったのは、チョムスキーはすごいなーということ、今日この頃はブッシュ批判とか、色々政治的な活動をしているようですが、昔はこんなことやってたんですね…あとは、CFGやCSGなどは定義がずいぶんと明確なんですが、実際の言語となると、プログラミング言語も含めて「ほぼCFG」みたいな感じで結構ファジーになっちゃうんだなーということです…

ではでは。