関数ポインタを返す関数のパースと型の構築

2021-05-20
#compiler #c

C言語の文法は型の記述が複雑で、特に関数ポインタが絡むと非情にややこしくなる。

例えば signal という標準関数は なにかシグナルが発生したときに呼び出される関数ポインタ（シグナルハンドラ）を設定する関数で、

void (*signal(int sig, void (*func)(int)))(int);

となっている。 パッと見たところどういう宣言なのかわからないけど、これはシグナル番号int sigと関数ポインタvoid (*func)(int)を取る2引数関数で、戻り値に以前に設定されていた関数ポインタvoid (*)(int)が返る。 シグナルハンドラはintを1つ取る関数で、発生したシグナル番号が渡される。

この文法をパースして対応する型を構築するのに手間取った。 特に再帰下降法とは相性が悪いように思う。

型のBNF

C言語の型に関するBNFを The syntax of C in Backus-Naur form から抜粋すると、

<declaration> ::=  {<declaration-specifier>}+ {<init-declarator>}* ;

<declaration-specifier> ::= <storage-class-specifier>
                          | <type-specifier>
                          | <type-qualifier>

<init-declarator> ::= <declarator>
                    | <declarator> = <initializer>

<declarator> ::= {<pointer>}? <direct-declarator>

<direct-declarator> ::= <identifier>                                        // (a)
                      | ( <declarator> )                                    // (b)
                      | <direct-declarator> [ {<constant-expression>}? ]    // (c)
                      | <direct-declarator> ( <parameter-type-list> )       // (d)
                      | <direct-declarator> ( {<identifier>}* )             // (e)

<pointer> ::= * {<type-qualifier>}* {<pointer>}?

（<type-specifier>はintやstructなどの具体的な型、<type-qualifier>はconstなど）。

<declaration> ルールの {<declaration-specifier>}+ がベースとなる型の部分で、関数の場合は戻り値の型になる。

<direct-declarator> ルールの(a)だと単純にその型、 (b)の ( <declarator> ) は <declarator> のポインタが結合する先の変更、 (c)のブラケットが配列型、(d)が関数型となる （(e)はなにかわからんのでひとまず無視）。

<direct-declarator> は左再帰になっていて、(a)か(b)の後に、(c)か(d)を任意回受け付ける。

ちなみにこのBNFだと、 int (x)、はたまた int (((y))) などという宣言も合法。

再帰下降法によるパースの順序と型の生成のミスマッチ

再帰下降法によって上記の型のパースを擬似コードとして書き下すと（<init-declarator> を省略して）

declaration() {
  declaration_specifier();
  declarator();
}

declarator() {
  pointers();
  direct_declarator();
}

direct_declarator() {
  if (token is '(') {
    declarator();                // (1)
    consume(')');
    direct_declarator_suffix();  // (2)
  } else {
    consume(`ident`);
    direct_declarator_suffix();
  }
}

direct_declarator_suffix(Type *type) {
  if (token is '[') {
    const_expr();
    consume(']');
    direct_declarator_suffix();
  } else if (token is '(') {
    parameter_type_list();
    consume(')');
    direct_declarator_suffix(type);
  }
}

direct_declarator では左再帰を再帰下降法に変換するために、後半部分を別関数にして再帰させている。 実際には各関数からの戻り値としてパースによって構築された型を返す。

問題はdirect_declarator 内の(1)と(2)の部分で、パースの順序としては(1)→(2)の順なんだけど、型の入れ子順としては(2)→(1)とする必要がある。

具体的には例えば signal の場合、宣言の最初の括弧 (*signal...) のアスタリスクによるポインタ指定は戻り値型にかかるが そのパース時点では型がvoidまでしか読まれておらず、括弧外最後の(int)は読まれてないので型が決定してない。 なのでその時点でどの型に対するポインタ型かというのを構築することができない。

対処法

プレースホルダーとして型を作成して(1)のdeclarator()に渡すようにして、戻り値が結果の型になる。 (2)のdirect_declarator_suffix()にはdirect_declarator()に渡された型を渡す。 その結果がプレースホルダーの中身となるので、memcpyしてやる。

実際のソースの該当箇所はこちら。

他のソースを見てみる

chibicc

低レイヤを知りたい人のためのCコンパイラ作成入門の参考リポジトリとなるchibiccを見てみた。 箇所はdeclarator関数で、

static Type *declarator(Token **rest, Token *tok, Type *ty) {
  ty = pointers(&tok, tok, ty);

  if (equal(tok, "(")) {
    Token *start = tok;
    Type dummy = {};
    declarator(&tok, start->next, &dummy);
    tok = skip(tok, ")");
    ty = type_suffix(rest, tok, ty);
    return declarator(&tok, start->next, ty);  // (3)
  }

  ...

「memcpyしてない…！」と驚愕したんだけど、トリックはdeclarator()呼び出し、type_suffix()呼び出しに続いて(3)で再度declartor()を呼び出しているところ。 chibiccでは最初にソースをすべてトークンに分割してリンクリストにしていて任意の箇所からパースできるのがポイントで、 最初のdeclarator()呼び出しはトークンを読み進めるだけで結果はdummyに受け取るが使用しておらず、 型の構築としてはtype_suffix()が先に行われて、もう一度同じトークンstart->nextからdeclarator()呼び出しの結果を最終的な型としている。

続きのトークンはtype_suffix()で消費した次のトークンがrestに格納され、辻褄が合う。

8cc

chibiccの前身であるところの8ccも見てみた。 箇所はread_declarator関数で、

static Type *read_declarator(char **rname, Type *basety, Vector *params, int ctx) {
    if (next_token('(')) {
        // '(' is either beginning of grouping parentheses or of a function parameter list.
        // If the next token is a type name, a parameter list must follow.
        if (is_type(peek()))
            return read_declarator_func(basety, params);
        // If not, it's grouping. In that case we have to read from outside.
        // For example, consider int (*)(), which is "pointer to function returning int".
        // We have only read "int" so far. We don't want to pass "int" to
        // a recursive call, or otherwise we would get "pointer to int".
        // Here, we pass a dummy object to get "pointer to <something>" first,
        // continue reading to get "function returning int", and then combine them.
        Type *stub = make_stub_type();
        Type *t = read_declarator(rname, stub, params, ctx);
        expect(')');
        *stub = *read_declarator_tail(basety, params);
        return t;
    }
    ...

で、こちらはトークンを逐次得る方式のようで、stubを渡しておいて後から中身にはread_declarator_tail()の結果を書き込むようになっている。

感想

  • この文法になったのもクレイジーだし、それをパースできるようにしたのもよくできたなぁという感想。
  • 単に関数ポインタのアスタリスクの位置がまずかっただけの問題な気もするが…普通の後置アスタリスク(void func(int))* だったら複雑にならなかったかも。
  • yaccとか使ったらまだマシなのかしら？と思って試してみたが（RaccによるC言語パーサを使って） direct_declarator のアクション型生成すると型のネスト方向が逆になってしまい、構文木を構築して後から型を構築するのもいろいろ大変そうな気がした。
  • 「低レイヤ」のネストしている型の読み方に、signal関数の型の読み方が書いてあってオススメ。
    • またそれを含むCの型の構文で型の内部表現がわかりやすい。

関連記事

新着記事