C++の構文解析手法

C++はそのつぎはぎ発展の過程において様々な意味不明な特殊な状況下での み効果を持つ機能及び文法及び意味上のあいまいさをぶち込まれ獲得してきたために通常のコンパイラ技術で使われる構文 解析手法はあまり有効とはいえない。ここではその問題について八つ当たり考察してみようと思う。(それにつけても気に なるのはcfrontの実装法である・・・どうしてこのような代物になったのでしょうか?)

最終更新:2003-Sep-21

もっとも有名な問題点 −− 宣言と式があいまい
C++のパーサを作ろうとするものがまず考えなければならない問題とされているところである。この時点でほとんどの開発者はC++が相当 の設計ミスいくらかの問題点を抱えている言語であることをいやでも知る羽目になるが まだ氷山の一角に過ぎない
(実は私もstroustrup博士の本の付録にある文法をそのままyaccのソースコードにしてコンパイルを試みたところ、shift/reduce conflict が百数十個とreduce/reduce conflictが十数個という思いもかけないメッセージが出てきてしまったがために、この問題に取り組むことになったのです。)
それはさておき対策はいくつか考え出されている。

字句解析機に細工をする
cfrontが採用しているようなので割合有名な手である。字句解析のところでトークンをどんどん先読みして宣言か式かを識別し、それを擬似トークンとし て構文解析機に渡すという方法である。パーサがするべき仕事の一部をする羽目になるレキサーはかなり複雑になる。

バックトラッキングを行う
prologを知っている方は御馴染のバックトラックを構文解析時に行うというものである。文法上あいまいな(つまりバックトラックが必要な)部分がある 程度長くなると計算量が指数関数的に増大するのでコンパイルはかなり遅くなるものと思われる。しかしそのような機能をサポートしたパーサ生成ツール (btyaccというものがある)を使うことによって開発は最も楽になる・・・かもしれない。

とりあえずツリーだけ組み立てて意味解析は後回しにする
これは私が採用した方法なので(他に採用した人いるかな?)比較的詳しく知っている上に思わず自画自賛してしまうところであるが、構文ツリーを式と宣言で 共通に扱えるように設計し、評価が必要になった時点でどちらかを識別してから評価するというものである。
文法は比較的奇妙なものになるがあいまいさはほとんどない(shift/reduce conflictがひとつだけ残る)上にパーサの構造はかなり単純になる。あとに述べるクラスや関数の再評価との相性が良いなどの特徴がある。


事実上関数内関数がある
Pascalにあるような関数内関数はCには無いのだが、C++ではクラスの定義の中でメソッドの本体を記述できるために関数内クラス内関数と言うややこ しいことが可能になっている。C++のパーサーは当然このことを考慮しなければならない。せめてクラスの定義の中ではメンバ関数のプロトタイプのみが許さ れると言うような仕様になっていれば後に述べる評価順序の問題ももっとまともなものになっていたと思うのだが・・・

クラスの再評価と評価順序
これはあまり有名ではないようだが(私も規格案を見てはじめて知った。)コンパイラの基本設計に大きな影響を与える実に困った仕 様である。以下のコードを見ていただきたい:

typedef int A;

class T {

A m1;
typedef double A;
A m2;

};

もしメンバ m1 は int で、 m2 は double になると考えた方は常識的な判断力をお持ちと思われるがC++の標準規格ではどちらも double になる。
これはどうも cfront のバグ(と考えられる挙動)をそのまま標準規格に持ち込んだためと考えられるが、プログラム言語の常識を超えている上にどのようなメリットがあるのかさっ ぱりわからないすごい機能である。このようなものが導入された理由として一つ考えられるのはC++のコンパイラ開発の敷居をうんと高くして市場の独占を図 ろうとしていると言うことだが、そのために標準に準拠していると言う建前のコンパイラは少なからぬバグを抱える羽目になるのであまり賢明なこととも言えな いであろう。 また typedef名を参照する上でもっとも内側のネームスペースを最優先すべきだから(ネームスペースの仕様を考えるとこの可能性は低い)とも考えられる が、その場合はク ラスの定義の中で通常のメンバを宣言した後は typedef やクラスの定義を出来なくするといったような制限を設けるべきであろう。
クラスの評価順序が問題となるようなコードはあまり多くは無いはずであるが、コンパイラの開発者が手を入れることが多いためか標準ライブラリの中にそのよ うなコードが見られるのは困ったことである。

staticメンバ
これは比較的些細な、慣例の問題だとは思うがなぜ "static" メ ンバという名前をつけたのであろうか?オブジェクトの外部にあるそのクラス共通のデータならば "extern" メンバという名前のほうがより妥当なのではないかと思うのだが。

関数の多義化
オーバーローディングそのものは大きな問題を抱えてはいないようだが、同じ様な関数がいくつも並んでいるのを見ると個人的には眠くなってくる。C++では 型の扱いがCとは少し異なる(例えば、 charsigned char とも unsigned char とも異なる型として扱われる)ためにどの多義化関数を呼べば良いのかはっきりしなくなることがあるが、これにテンプレートが絡んでくるとどれを呼び出そう としているのかますますはっきりしなくなるためさらに眠くなってくる。多義化機能のデバッグ自体は難しくなかったはずだが睡眠薬代わりにバグを残しておけ ば良かったかも知れない。
ついでに言うとKoenig lookup と言う割と変な機能がここにも追加されている。実装はそれほど難しくはないが全然意図しないネームスペースからの関数を呼び出してくれそうである・・・と 思ったがこれは恐らくテンプレートに関係していて、引数の中にテンプレート型がある場合自動的に正しいインスタンスを選び出してそこから呼び出してくれ る・・・と思ったがグローバルネームスペースに関数テンプレートを定義すれば済むことなのでやはりこの手の機能を弁護するのは難しいようだ。

多重継承
いわゆるオブジェクト指向の概念の中には、多重継承は早いうちから存在したようだが現在でもこれを標準仕様に入れている言語はあまり多くはない。最近現れ たオブジェクト指向言語の多くは意識的にこれを避けて代わりにインターフェースを装備するのが普通である。これは(よく言われているように)データやメ ソッドをスーパークラスの中から探し出すときに混乱を生じさせないためであろうが、C++の標準化委員会は当然ながらそのようなことは気にしないので、コ ンパイ ラの中では継承の優先度のようなものを考える羽目になる。あ〜〜〜〜〜めんどくさ。
あと virtual を付けて継承することが本当に必要なのはいったいどういうときなのであろうか? virtual がつくとクラスのレイアウトがかなり崩れてスーパークラスへのポインタすら求められなくなるときがあるのだが。別の言い方をすると、それでもかまわないか らスーパークラスのメンバを一意に保つ必要がある状況とは一体?
ところで「オブジェクト指向、多重継承なし、インターフェースあり、文法はCの改変版、実行はバーチャルマシンを使用する」高級言語はいったいいくつ出来 たんだ?(私が挙げられるのは3つ)。

例外処理
1990年ごろcfrontの開発チームはどのような形で例外処理を実装するかについて様々な調査を行ったようだが結局実装されることは無かった(現在の バージョンでどうなのかは知らない)。しかしC++の標準化委員会は誰かが代わりに実装してくれることを期待して例外処理を標準規格の中に入れてしまっ た。これは技術的な挑戦と言わざるを得ないが、どこかのコンパイラメーカーがそれに成功してしまったので例外処理はC++の言語仕様の一部であるとの認識 を 得てしまった。さらに悪いことには、C++の例外処理は規格の段階でいくつかの厄介な問題を( newdelete から例外を投げるとどうなるかといったような有名な問題のほかにも)抱えているために将来相当形が変わる可能性がある。まあ仕事が多いのは良いことかもし れませんが・・・

mutable
embedded C++ では const データは極力ROMに格納することになっているために mutable は意味がないとして取り除かれている。私にはどのような状況で mutable が必要なのかはよくわからない。最初から const にしなければ良いのでは?

explicit
暗黙の型変換にはならない、明示的にコンストラクタとして呼び出さなければならない関数と言う意味だが、このように中途半端なものを導入するぐらいならば コンストラクタ宣言の頭に ctor とか型変換関数宣言の頭に typecast とかいうような予約語を入れる ようにすればはるかに紛らわしくない上に、コンストラクタ宣言と通常のメンバの宣言が文法的にあいまいであることを解消できて良いと思っている。そもそも 型変換関数とコンストラクタを兼用すると言う発想が私には疑問だ。

friend 修飾子
如何にもコンパイルする上での障害になりそうな機能ではあるが、比較的初期のころからこのような仕様があったことからも言語の性格が伺える。できることな ら using に一本化してほしいところだ(ただし friendusing はソースファイルの中にあるべき位置が異なるので書き換えは面倒なものになるかもしれない)。

テンプレート (注 意:ここはほかの項目より感情的です。)
テンプレートに関する愚痴問題は多いのだが思いついたものをいくつか挙げると

Standard Template Library
Cの標準ライブラリとは似ても似つかない、iterator というテンプレート型を巧妙に利用して作られた、私には実 用的価値がよくわからないライブラリ(まあC と機械語に染まっているからといえばそれまでだが)。以下に述べるテンプレートの変わった仕様はどうもこれをよりエレガントに実装できるようにご 都 合主義的に導入されたようだが、そのために言語仕様のエレガントさを少なからず犠牲にしているところに標準化委員会の見識を感じる。

部分特殊化 (partial specialization)
C++のテンプレートは単なるマクロではなく、与えるパラメータによってメンバの構成すら異なる全く別のクラスにも出来るという変わった機能。もしテンプ レートをプリプロセッサのマクロの延長で実装していたらここではまる可能性大であるが(?)、qccではすべてのクラスと関数を再評価可能な形で処理して いるために、比較的スムーズに実装できているのではないかと自負している。

パラメータの導出
さて、パラメータが与えられたら部分特殊化を試みるわけですけどその前にコンパイラは部分特殊化クラスへのパラメータ(これはコード中に出てくるパラメー タとは異なる)をパターンマッチングによって導出しなければなりません。これは prolog を意識した(????)仕様と考えられますがどうしてこのようなことをC++のコンパイラが行わなくてはならないのかははっきりとはわかりません。比較的 好意的な解釈としては・・・クラスの設計などには関わらないでコーディングするだけならばいいかも知れませんな。

テンプレートの具体化 (instantiation)

ネームスペース
 
// ここはグローバルネームスペースです。
int a;
class T { typedef int a; int b; };
void function(void) {
T::a
}

ここまで書いてから何を述べようとしたのか忘れてしまった!!!!!

NULL (void *)0 ではない
なぜこのようになったのかはまだ調べている最中であるが、考えられる理由のひとつにメンバへのポインタがある。これはクラスの先頭からメンバへのオフセッ トを値として持つために、最初のメンバを指す場合は0を”有効な”値として見なければならない。このことを考慮に入れてしまったために NULL とは異なる値を持つに至った可能性があるが、C++の標準規格では (int)0 NULL として良いようなので説得力はいまいちである。

関数型型変換
このように一見して文法があいまいになる機能を導入しまくることをいろいろと述べるとなんだか某標準化委員会を攻撃しているような気がしてくるが、まあそ のように思っても結構です。この機能のためにイニシャライザ付きインスタンスの定義や関数プロトタイプ宣言でミスパースするコンパイラは結構あるようなの で、qccの優位性を主張できるひとつの根拠になってくれています。見方によっては良い機能です。(ううう・・・文体が・・・)

C++はCのスーパーセットか?  (注意:建前上はそうなっている)
むむむ・・・宣伝文句としては悪くは無いが、C++ のコンパイラを開発する際にそのような先入観を持ち続けていたら必要な人月はそうでない場合と比べて数倍に増えるであろう。 それだけならばコンパイラの開発にかかわることに過ぎないが、「 ansi-c の規格は良かったから C++ も良い規格なんだろう」 などとあらぬ誤解を招く事の方がより深刻な問題である。C++の規格が教えてくれるのは、オブジェクト指向システム記述言語は如何にあるべきか(ちょっと 面白いテーマだと思わないか?)という (個人的には期待していた)ことではなく、標準規格はあくまでも互換性を保つためのものであるということである(もっともこの点においてもあまりうまくい かな いではあろうが)。

その他 −− あるいは未知の仕様
私がはじめてC++を知ったのは1989年頃のこと。当時の言語仕様はまだCにクラスを導入した程度の物でしかなく、しかも私はまだそれを疑 うことを知らなかった。
あれから10年・・・C++のパーサを開発するべく訪問した標準化委員会のサイト http://anubis.dkuug.dk/jtc1/sc22/open/n2356/index.html で私が見たものは
(中略)
運良く思い付いたアイデアのために、(未知の仕様であった)文法の曖昧さを克服することは出来たが、クラスの再評価というとんでもない(未知の)仕様の為 に 基本設計をやり直す羽目になり、(未知の仕様の宝庫であるところの)テンプレートの為に何ヶ月もバグを出しまくり、(未知というより意味不明なところが多 かった)例外処理対策としてコードジェネレータの改造まで考える羽目になった(そこまでする必要はなかったが)。
しかし未知の仕様はなくなりはしない・・・それどころかまだ増えるかもしれないのだ(詳細については http://anubis.dkuug.dk/jtc1/sc22/WG21/  を参照のこと)。

書き忘れていたけど未知の仕様はバグではないので念のため。

[ Home ]