C言語のBNF、typedef で苦しむ。

低レイヤを知りたい人のためのCコンパイラ作成入門 は、小さな機能からはじめてボトムアップでC言語のコンパイラを作成します。本格的な C の文法をカバーする際にBNF を参考にしくなり規格を見てみました。規格のドラフトはここにあります。BNF を元に作業していたら typedef でつまずきまして。

また時間を食われたのでメモとして残しておきます。

C言語は文脈に依存すると言われていて、この typedef がひとつの例となってます。解決方法は色々あるようで、lexer hack と言って parse フェーズに回したものをまた lex へ流して解決する等あるらしいです。私はこの記事などが役に立ちました。この記事にも書いてありますが、llvm/Clang は lexer hack ではない方法らしく、ソースをちらっと見てみました。良くわかりませんが多分ソースのこのコメントの通りなんでしょう。最初に typedef を吸って記憶しておき、後で識別子が出た時に判断。

作り方は色々あると思いますが、自分の場合は下の部分が問題になりました。

ドラフトの 6.7.2: Type specifiers は以下の様になっています。

1 type-specifier:
void
char
short
int
long
float
double
signed
unsigned
_Bool
_Complex
atomic-type-specifier
struct-or-union-specifier
enum-specifier
typedef-name

この最後の typede-name は結局変数名などと同じで、字句解析する時点では他の識別子と変わりません。そしてこの type_specifier が複数回許されているんですよね。

それが、6.7 Declarations にある、declaration-specifiers。
declaration-specifiers:

storage-class-specifier declaration-specifiers(opt)
type-specifier declaration-specifiers(opt)
type-qualifier declaration-specifiers(opt)
function-specifier declaration-specifiers(opt)
alignment-specifier declaration-specifiers(opt)

long long int 等出来ることから分かるように、types-specifier が複数取れるということはもちろん合点がいく話ですが、そうするといくつでもtypedef-name で識別子が取られてしまいます。つまり、int func(); の func も type-specifier で吸い取られてしまう。int func(); の文法は、本来は direct-declarator の場所で取られて欲しいはず。じゃないと関数として AST 内で区別出来ません。カッコがあるから出来るのでは？と思うところですが、このカッコは入れ子になった宣言のパターンの場合のカッコとして吸われます。そして引数に相当する場所で解析エラー。引数がなければ、type-specifier + typespecifer + ネストのカッコとしてそのままスルー。

結局のところ、typedef が登場したことをどこかで覚えておいて、後で識別子が来た時に判断するのが正解なのでしょう。今の所はこのくらいしか思いつきません。