C 言語の構文解析
Tagged:  •  

スクリプト言語や Java が隆盛を極めている昨今の風潮からすると、 あまり流行りでは無いのかもしれませんが、 弊社では C 言語による(そこそこの規模の) 開発案件もコンスタントに手掛けています。

そういった案件で既存のソース(あるいは利用するライブラリ) の調査を行う場合、 文字列ベース(e.g.: grep 結果)ではなく、 C 言語としての文法解釈を経て得られる情報が必要となることもあります。 例えば、 連結操作("##")マクロによるシンボル定義はコード上からは見えない、 といった問題があるためです。

今時は C 言語の字句解析用定義(所謂「lex ソース」) も構文解析用定義(所謂「yacc ソース」ないし「BNF 定義」) も入手可能なのですが、 ではこれだけあれば C 言語のソースを解析可能かというと、 実はそうではありません。

型名情報の蓄積

例えば以下の C 言語のコードは:

    int * i;
int 型へのポインタ変数の宣言

int 型へのポインタ変数の宣言ですし、 以下のコードは:

    size_t * i;
size_t 型へのポインタ変数の宣言

size_t 型へのポインタ変数の宣言ですが、 さてそれでは:

    hoge * i;
hoge 型へのポインタ変数の宣言?

上記のコードは hoge 型へのポインタ変数の宣言でしょうか? それとも変数 hoge と変数 i の積を求める式でしょうか?

C 言語の文法上こういった紛らわしさは随所にあり、 そのため識別子トークンと型名トークンとを字句解析側で区別する必要があるのです!

冒頭でリンクを張っている字句解析用定義ファイルでも:

/*
* pseudo code --- this is what it should check
*
*	if (yytext == type_name)
*		return(TYPE_NAME);
*
*	return(IDENTIFIER);
*/
苦肉の策のコメント

というコメントを記述することで、 字句解析・構文解析の連携が必要であることを示しています。

文脈依存な字句種別判定

「では typedef を検出して、 型名管理テーブルにシンボルを登録すればよいのでは?」 と思われるかもしれません。 実際、私もそう思ったのですが、 事はそう簡単には行きません。

例えば、 以下のコードの1行目で typedef された hoge を、 構文解析部が型名管理テーブルに追加したとします。

1| typedef int hoge;
2|
3| hoge * i;
4|
5| struct hoge
6| {
7|     int field;
8| } ;
型名と同名の構造体

字句解析を特に細工無く実装した場合、 型名管理テーブルへの問い合わせを元に、 以後検出された hoge は全て型名トークンとみなされます。

これにより、 3行目のような記述は適切に解釈されるでしょう。

しかし5行目のような構造体定義の場合、 構文上 struct キーワードの次は識別子トークンが要求されることから、 構文エラーとなってしまいます。 「構造体名」の指定なのですから、 「型名」が不適切なのは当然ですね。

つまり、 単に typedef を検出して型名を管理するだけではなく、 次のトークンとして型名が有り得るか否かという文脈情報を、 字句解析と構文解析の間でやり取りしなければならないのです。

まとめ

ここまでの話をまとめると、 文法的に正しいソースをただ読み込むだけであっても、 字句解析定義・構文解析定義を入手した上で:

  • 型名と識別子を区別するための情報管理
  • 次トークンに型名が有り得るか否かの文脈情報管理

といった部分を別途実装しない限り、 C 言語の構文解析を行うことができない、 ということです。

つまるところ、 言語を設計する人は、 是非とも構文解析処理を書き易い言語を設計して欲しいなぁ、 ということが言いたかったわけです。 ビットシフトの ">>" と区別が付かないような、 C++ Template (ないし Java Generic)の入れ子の末尾 (e.g.: "Outer<Inner<param>>")なども、 なんとかして欲しかったところ。

もっとも、 Lisp みたいな極北の領域まで簡素さを突き詰めると、 それはそれでアレなのですが。