この記事は、C言語 Advent Calendar 2018 のうち、3連続素数和が素数になる最小の数
番目の記事です。
…といったものの、かなり公開が遅れてしまいました。ごめんなさい…(SECCON国内決勝とかぶったりした&計画性がないのが原因です。)
また、言語実装アドベントカレンダー のほうでもcompiliumに関連する内容の記事を書きましたので興味があればご参照ください。
hikalium.hatenablog.jp
はじめに
Cコンパイラ を実装したことのあるみなさんも、変数の宣言や型の宣言を行うdeclarationの実装で詰まってしまった方は多いのではないでしょうか。
この記事では、Cのdeclarationをインクリメンタルにうまく実装する方法について検討した記録と、その実装を一部途中まで進めた話 を紹介します。
仕様についてはもう知ってるので説明不要だよ!というプロの皆様は、下の方にある「インクリメンタルに実装しよう!」を読んでいただくと時間の節約になります。
まずはdeclarationについて知る
何はともあれまずは仕様書を読んで、おおまかに仕様を理解します。いくらインクリメンタルに開発するとはいえ、最終的な到達目標をきちんと理解していないことには、途中で立ち行かなくなってしまいますからね。
というわけで、declarationとは一体どのようなものか、仕様書に沿って見ていくことにしましょう。
そもそもdeclarationってなんだ?
仕様書 によれば、declarationとは、いくつかのidentifierについてその解釈や属性を与えるもので、具体的には
ローカル変数やグローバル変数 などの記憶領域を持つオブジェクト
関数
列挙定数
typedef名
となるような識別子を宣言するものであると書かれています。というわけで、declarationには必ず名前となる識別子が一つ以上、それに対応する属性もいっしょに書かれていることになります。
(ちなみに、_Static_assertも構文上はdeclarationに入っていてこれは識別子を持たないのですが、実質的にはdeclarationではないのでここでは説明しません。)
declarationの最もトップレベ ルな構文としては、以下のようになっています。(末尾のoptは省略可能という意味です。)
declaration:
declaration-specifiers init-declarator-listopt ;
static_assert-declaration
declaration-specifiers:
storage-class-specifier declaration-specifiersopt
type-specifier declaration-specifiersopt
type-qualifier declaration-specifiersopt
function-specifier declaration-specifiersopt
alignment-specifier declaration-specifiersopt
init-declarator-list:
init-declarator
init-declarator-list , init-declarator
init-declarator:
declarator
declarator = initializer
…といって理解できればみんな困らないので、上の構文をint a = 3, *b;
について図示してみたものが以下です。
declaration int a = 3, *b;
みなさんご存知の通り、int a = 3, *b;
を解釈すると、初期値3をもつint型の変数aと、int型へのポインタ変数b、が宣言されますね。
構文的な重要ポイントとしては、
declaration
はdeclaration-specifiers
がひとつと、init-declarator
が複数合わさったものであり
init-declarator
はdeclarator
と、任意でinitializer
をつけることができる
ということです。とりあえず、最初はinitializerのことは無視することにして、いまここで最も重要なことは
declaration-specifiers
+ declarator
でひとつの宣言が出来上がる
ということです。ではdeclaration-specifiers
とdeclarator
について見ていくことにしましょう。
declaration-specifiers
ってなんだ?
上の構文
declaration-specifiers:
storage-class-specifier declaration-specifiersopt
type-specifier declaration-specifiersopt
type-qualifier declaration-specifiersopt
function-specifier declaration-specifiersopt
alignment-specifier declaration-specifiersopt
からわかることとしては、なんとかspecifierとか、なんとかqualifierというのが1つ以上並んだものがdeclaration-specifiers
です。
type-specifier
たとえば、type-specifier
は、よくみるint
やchar
とかunsigned
とかのことです。
type-specifier:
void
char
short
int
long
float
double
signed
unsigned
_Bool
_Complex
atomic-type-specifier
struct-or-union-specifier
enum-specifier
typedef-name
また、これにはstructやunion, enum の型情報も含まれます。つまり、struct KV{const char *key; void *v;}
とかはtype-specifier
, 中でもstruct-or-union-specifier
に含まれるわけです。
さらに、typedefによってつけられた型の別名もここに入ります(typedef-name
)。typedefのせいで、C言語 のパーサはパースしながらdeclarationを解釈しなくてはいけないのです。まあ、最初は実装しなくてもいいのですが。
enum -specifier
enum E{kKey1 = 3, kKey2}
とかのことです。
type-qualifier
const
とかvolatile
とかです。
function-specifier
inline
か_Noreturn
のことです。
storage-class-specifier
typedef
とかextern
とかstatic
とかのことです。
declaration-specifiers
の衝撃の事実
もっと詳しく知りたい方は、仕様書を適当に読んでほしいのですが、面白いネタとしてはこんな話があります。
なんと、上記のspecifierたちは、一部の例外を除いて順序を自由に入れ替えてよいことになっています。したがって、
unsigned long const int long extern
とか書いても全く問題ないわけです。(人間には厳しいですが。)
declarator
ってなんだ?
正直、declaration-specifiers
はやるだけです。簡単です。でもこっちのdeclarator
は、少し冷静になってしっかり理解をする必要があります。
まずdeclarator
そのものは単純明快です。
declarator:
pointeropt direct-declarator
pointer:
* type-qualifier-listopt
* type-qualifier-listopt pointer
これは要するに、ポインタの*
(とその修飾子列の組)が0個以上並んだあとに、direct-declarator
が続くよ、という意味です。たとえば、int *b;
とかなら
int *b;
という感じになります。この例は、direct-declarator
には識別子が一つだけくるケースになっています。
ところが、direct-declarator
はそう単純ではありません。
declarator:
pointeropt direct-declarator
direct-declarator:
identifier
( declarator )
direct-declarator [ type-qualifier-listopt assignment-expressionopt ]
direct-declarator [ static type-qualifier-listopt assignment-expression ]
direct-declarator [ type-qualifier-list static assignment-expression ]
direct-declarator [ type-qualifier-listopt * ]
direct-declarator ( parameter-type-list )
direct-declarator ( identifier-listopt )
なんとdirect-declarator
は自身とdeclarator
を再帰 的に含むことができます。
(これはつまり、declarator
はdeclarator
を再帰 的に含むことができるということです。)
したがって、単にdeclarator
と呼んでしまっては、declarator
の全体をさすのか、部分を指すのか分かりづらくなってしまいます。
というわけで、あるdeclaration
において、他のどのdeclarator
にも含まれないようなdeclarator
のことを、仕様書の言葉を借りてfull-declaratorと呼ぶことにしましょう。
例としては、
int *f(int a, int b);
の*f(int a, int b)
char m[3][4];
のm[3][4]
void (*fp)(int a);
の(*fp)(int a);
がfull-declaratorにあたります。
declarator
の構文をじっくり見ていただくとわかるのですが、いくらdeclarator
が入れ子 になっても、ひとつのfull-declaratorについて、identifier
が現れるのはちょうどひとつになることが分かります。
つまり、declaratorは、宣言の情報のうち
ポインタ
配列
関数
そしてひとつの識別子(declaratonが定義しようとしている名前)
を表現することがわかります。
declarationの構文を書き下してみる
さて、ここまでの情報をもとに、declarationをもう少しわかりやすい形で書き直してみることにしましょう。
結局のところ、declarationは、なんらかの識別子と、その型や属性をペアにしたものを複数同時に表現する構文なわけです。
なぜ複数になるのかというと、init-declarator-listによって、ひとつのdeclarationの中に複数のfull-declarationが入ることがあるためなのですが、とりあえずひとつの識別子について型や属性を知りたいので、ここでは単純にdeclaration = declaration-specifiers + full-declarator
で構成されると考えて説明します。
まず、declarationの各部分を、以下のような文字でおくことにします。
T: declaration-specifier
D: declarator
P: pointer
E: direct-declaratorの各断片
I: Identifier
そしてこれらを用いて、各構文を正規表現 風に記述するとこんな感じになります。
declaration = TD
D = P*[I|(D)]E*
最もシンプルなケース
たとえば、int a;
というdeclarationは、書き下すとTI
になります。
int a;
を回りくどく書けば、a is_a(int)
ですからI(t): Iが識別子Xだとして、X is_a(t) を返す
と考えればよさそうです。
ポインタの適用順
次のケースは、ポインタの場合です。たとえば、int * const * p;
などを考えてみましょう。
ちなみに、これも回りくどく書けばp is_a(pointer_of(const_pointer_of(int)))
となるのはすぐわかるでしょう。
念の為言っておきますと、ポインタ変数そのものは書き換えられますが、1回デリファレンス したものはconstなポインタ変数になるので書き換えできず、2回デリファレンス したものはただのint型なので書き換えられます。
さて、説明を容易にするため、PやEについて、左から右に番号を振ることにします。つまり、
declaration = T P_1 P_2 ... [I | (D)] E_1 E_2 ...
という感じです。
このノリでいくと、
int * const * p;
= T P_1 P_2 I
T: int
P_1: * const
P_2: *
I: p
ということになります。
さて、Pは入れ子 にできますから、
P(t): pointer_of(t)を返す。(constがついているならconst_pointer_of(t)を返す)
とおくと都合がよさそうです。
この型がp is_a(pointer_of(const_pointer_of(int)))
であることを考えると、連続したPは
I(P_2(P_1(T)))
= I(P_2(P_1(int)))
= I(P_2(const_pointer_of(int)))
= I(pointer_of(const_pointer_of(int)))
= p is_a(pointer_of(const_pointer_of(int)))
というように、P_1 P_2 P_3 => ...P_3(P_2(P_1(t)))
と評価すればうまくいきそうです。
配列の適用順
じゃあ次は配列いってみましょうか。
たとえば、よくあるint arr[3][5];
は、arr is_a(Array(size: 3, type: Array(size: 5, type: int)))
という意味です。
ということでE(t): Eがarray declarator [n] ならば、Array(size: n, type: t)を返す。
と考えればよさそうです。
適用順としては、
E_1 E_2 E_3 => E_1(E_2(E_3(t)))
とすれば、
I(E_1(E_2(T)))
= I(E_1(E_2(int)))
= I(E_1(Array(size: 5, type: int)))
= I(Array(size: 3, type: Array(size: 5, type: int)))
= arr is_a(Array(size: 3, type: Array(size: 5, type: int)))
となってうまくいきそうです。
関数の場合
関数も配列と同じdirect-declaratorに含まれるので、配列の適用順を参考にすれば
E(t): Eがfunction declarator (arg1, arg2, ...) ならば、Func(returns: t, args: (arg1, arg2, ...)) を返す。
とすれば、たとえばvoid f(int a);
などは
I(E_1(T))
= I(E_1(void))
= I(Func(returns: void, args: (int a))
= f is_a(Func(returns: void, args: (int a))
となってうまくいきそうです。(引数に関しては、declarationを再帰 的に適用すれば目的の結果が得られるので今回はそのままにしています。)
ところで、関数を要素とするような配列 や、配列・関数を戻り値とするような関数 をつくることはできてはならないと仕様書に明記されています。
したがって、Eが関数の場合にE同士がネストするケースをここで紹介することは不可能です。
E, P, (D)|I
の適用順
たとえば、みんな大好き
void (*signal(int sig, void (*func)(int)))(int);
は、書き下すと
T1(P2_1 I2 E2_1)E1_1
となります。そして、ここから導ける型としては
signal is_a(
Func(
returns: pointer_of(Func(returns: void, args: (int))),
args: (int sig, void (*func)(int))
)
)
となることから、逆に辿って考えてみると、
signal is_a(
Func(
returns: pointer_of(Func(returns: void, args: (int))),
args: (int sig, void (*func)(int))
)
)
= I2(
Func(
returns: pointer_of(Func(returns: void, args: (int))),
args: (int sig, void (*func)(int))
)
)
= I2(E2_1(
pointer_of(Func(returns: void, args: (int)))
))
= I2(E2_1(P2_1(
Func(returns: void, args: (int))
)))
= I2(E2_1(P2_1(E1_1(
void
))))
= I2(E2_1(P2_1(E1_1(T))))
となります。つまり、適用順は
T
-> Pの小さい方から大きい方
-> Eの大きい方から小さい方
-> DがあればD
-> I
という順番になるんですね。
インクリメンタルに実装しよう!
お疲れ様でした。長い説明に付き合ってくださりありがとうございました。(理解しづらいところがあればぜひコメントをください。)
では、簡単なケースからインクリメンタルに実装してみましょう!
int a;
やchar c;
のようなTI
型を処理できるようにする
Tにあたるものとして、BaseTypeという構造体をつくります。
とりあえず、type_specifierひとつだけがBaseTypeだと考えましょう。(int, char, voidとかが表現できるね!)
struct BaseType {
struct Token *type_specifier;
};
次に、D: declaratorにあたるものとして、Declarator構造体をつくりましょう。
最初は簡単な例としてint a;
が表現できればよいので、identifierだけ入れることにしましょう。
struct Declarator {
struct Token *identifier;
};
これらの組をDeclarationPairとしましょう。
struct DeclarationPair {
struct BaseType *base_type;
struct Declarator *decltor;
};
これで、BaseTypeとDeclaratorの組TI
の形式で表現できる宣言をDeclarationPairで表現できるようになりました。
パーサは再帰 下降法で書くだけなので省略します。
DeclarationPairから作成される、型情報の構造体について考えます。
型情報は統一的にTypeという構造体で表すことにして、
struct Type {
enum {
kBaseType,
kIdentifierAttr,
} subtype;
struct BaseType *base_type;
struct Token *identifier;
struct Type *next;
}
というふうにしておきます。nextは、pointer_of(t)
やident is_a(t)
のtにあたるものです。
そしてDeclarationPairからTypeを作るような関数をつくります。
struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
type = AllocAndInitIdentifierAttr(decl_pair->decltor->identifier, type);
return type;
}
これだけで、ひとまずint a;
とかchar c;
とかはいけるようになります。やったね!
int **pp;
のようなTP*I
型を処理できるようにする
つぎは、ポインタに対応しましょう。最初は*const
などのポインタ属性に対応しないと割り切ってしまえば*
の個数を数えればいいので、Declaratorに*
の個数を格納するメンバを追加します。
struct Declarator {
int pointer_count; // new!
struct Token *identifier;
};
そして、Typeにも型だけ追加しておきます。
struct Type {
enum {
kBaseType,
kIdentifierAttr,
kPointerType, // new!
} subtype;
struct BaseType *base_type;
struct Token *identifier;
struct Type *next;
}
そして、CreateTypeFromDeclarationPair()
にコードを追加します。
struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
for(int i = 0; i < decl_pair->decltor->pointer_count){ // this loop
type = AllocAndInitPointerType(type);
}
type = AllocAndInitIdentifierAttr(decl_pair->decltor->identifier, type);
return type;
}
これで、int **pp;
とかが処理できますね!
int *arr[2][3];
のようなTP*IE*
(Eは配列)を処理できるようにする
ポインタができたら、次は配列ですね。配列は、要素数 に整数のみをとると仮定しましょう。
とりあえず、direct-declaratorに対応する構造体をつくります。
struct DirectDeclarator {
enum {
kArrayDeclarator,
} type;
int size;
}
そして、DirectDeclaratorの列E*
を格納するメンバをDeclaratorに追加します。
struct Declarator {
int pointer_count;
struct Token *identifier;
struct List *direct_declarators; // List of DirectDeclarator
};
ここでは、Listの実装の詳細については述べません。
そして、CreateTypeFromDeclarationPair()
にコードを追加します。
struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
for(int i = 0; i < decl_pair->decltor->pointer_count){
type = AllocAndInitPointerType(type);
}
for(int i = GetSizeOfList(decl_pair->decltor->direct_declarators); i >= 0; i--) { // this loop
struct DirectDeclarator **dd =
GetNodeAt(decl_pair->decltor->direct_declarators, i);
if(dd->type == kArrayDeclarator)
type = AllocAndInitArrayType(dd->size, type);
}
type = AllocAndInitIdentifierAttr(decl_pair->decltor->identifier, type);
return type;
}
これで、int *arr[2][3];
とかが処理できますね!
int f(int c);
のようなTP*IE*
(Eは関数)を処理できるようにする
同様にして、関数も処理できるようにしましょう。
とりあえず、direct-declaratorにメンバを追加します。
struct DirectDeclarator {
enum {
kArrayDeclarator,
kFuncDeclarator, // new!
} type;
int size;
struct List *args; // new!
}
一応argsもつけましたが、最初はargsは真面目にチェックしなくてよいと思います。また、argsのパースや型情報への変換もここでは扱いません。そんなに難しくないのですぐにできると思います。
そして、CreateTypeFromDeclarationPair()
にコードを追加します。かんたんですね!
struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
for(int i = 0; i < decl_pair->decltor->pointer_count){
type = AllocAndInitPointerType(type);
}
for(int i = GetSizeOfList(decl_pair->decltor->direct_declarators); i >= 0; i--) { // this loop
struct DirectDeclarator **dd =
GetNodeAt(decl_pair->decltor->direct_declarators, i);
if(dd->type == kArrayDeclarator)
type = AllocAndInitArrayType(dd->size, type);
if(dd->type == kFuncDeclarator)
type = AllocAndInitFuncType(type, dd->args); // here!
}
type = AllocAndInitIdentifierAttr(decl_pair->decltor->identifier, type);
return type;
}
これでint f(int c);
もint **f();
とかも処理できるんですよ。すごくないですか!
ちなみに、この変換コードでは、先ほど説明したような、関数の戻り値に関数/配列を指定できない、配列の要素型に関数を指定できないというチェックを行なっていません。
チェックを追加するのはとてもかんたんなので、読者への課題とします。(最初はやらなくていいと思いますよ!)
ネストしたdeclaratorに対応する
さて、みんな大好きsignal
の定義をパースできるまであともう少しです!ネストしたdeclaratorに対応できれば、表現力はぐっと向上します。
まず、ネストしたdeclaratorを表現できるようにdeclaratorを修正します。
struct Declarator {
int pointer_count;
struct Token *identifier;
struct Declarator *next; // here!
struct List *direct_declarators;
};
例によりパーサは書けると思うので省略します。
そして、CreateTypeFromDeclarationPair()
から関数を切り出して、ネストにうまく対応できるように準備します。(以下のコードは、一つ前のコードと等価な動作をします)
struct Type *CreateTypeFromDeclarator(struct Declarator *decltor, struct Type *type) {
for(int i = 0; i < decltor->pointer_count){
type = AllocAndInitPointerType(type);
}
for(int i = GetSizeOfList(decltor->direct_declarators); i >= 0; i--) {
struct DirectDeclarator **dd =
GetNodeAt(decltor->direct_declarators, i);
if(dd->type == kArrayDeclarator)
type = AllocAndInitArrayType(dd->size, type);
if(dd->type == kFuncDeclarator)
type = AllocAndInitFuncType(type, dd->args);
}
return AllocAndInitIdentifierAttr(decltor->identifier, type);
}
struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
return CreateTypeFromDeclarator(decl_pair->decltor, type);
}
そして、もしもネストしていたら、再帰 的にCreateTypeFromDeclarator()
を呼び出すようにします。
struct Type *CreateTypeFromDeclarator(struct Declarator *decltor, struct Type *type) {
for(int i = 0; i < decltor->pointer_count){
type = AllocAndInitPointerType(type);
}
for(int i = GetSizeOfList(decltor->direct_declarators); i >= 0; i--) {
struct DirectDeclarator **dd =
GetNodeAt(decltor->direct_declarators, i);
if(dd->type == kArrayDeclarator)
type = AllocAndInitArrayType(dd->size, type);
if(dd->type == kFuncDeclarator)
type = AllocAndInitFuncType(type, dd->args);
}
if(decltor->next)
return CreateTypeFromDeclarator(decltor->next, type); // here!
return AllocAndInitIdentifierAttr(decltor->identifier, type);
}
なんとこれだけです!これだけで、あの奇怪なvoid (*signal(int sig, void (*func)(int)))(int);
があなたのコンパイラ でも綺麗に解釈できるようになったのです!
まとめ
本当はここでcompiliumの実際のコードを貼ることになるはずだったのですが、そちらのほうはちょっと間に合いませんでした。申し訳ないです。(27日までには出したいですね。)
実を言うと、上記のコードはブログの編集画面に直接打ち込んだため、バグやtypo 、ロジックのミスなどがあるかもしれません。発見しましたら、どうかそっと教えていただけると助かります。(報告、意見等は大歓迎です!@hikalium までお寄せください。)
駆け足になりましたが、これでC言語 のdeclarationの半分以上を理解していただけたならば私としても嬉しいですし、コンパイラ を書いていてdeclarationの処理で詰まっていた皆様の一助になればいいなと思っております。
ということで、大変遅く&長くなりましたが、これにてひとまずおしまいです。
上の続きとしては、
const pointer
struct/union
enum
typedef
などが待ち受けていますが、ここまでできれば比較的簡単にできると思います。(もちろん、落とし穴はたくさんありますが…。)
長々と読んでいただき、ありがとうございました。
来年もよいCコンパイラ 自作ライフを楽しみましょう!
参考文献