compilium v2 におけるdeclarationの実装

この記事は、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;について図示してみたものが以下です。

f:id:hikalium:20181224205850p:plain — 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;とかなら

f:id:hikalium:20181224215246p:plain — 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];`のような`TPIE*`(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);`のような`TPIE`(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コンパイラ自作ライフを楽しみましょう！

参考文献

ISO/IEC 9899:201x Committee Draft April 12, 2011 N1570