セルフホスティングCコンパイラを書いた

C言語 プログラミング コンパイラ

セルフホスト(自分自身をビルド)できるCコンパイラnoccを書きました。

github.com

はじめに

去年の夏あたりからCコンパイラを書くのが流行っていたのでやってみました。

例によって@rui314さんの8cc、9ccと低レイヤを知りたい人のためのCコンパイラ作成入門を参考にしていますが、バックエンドにはLLVMを使用しています。

工夫した点

以下、作る上で工夫した点です。

言語仕様に制限をつける

C言語の全仕様を網羅しようとすると到底完成は不可能なのでサポートする言語仕様に制限をつけまくりました。 制限には例えば以下のようなものがあります。

  • 変数宣言が初期値を取れない。
  • 複数の変数をコンマ区切りで宣言できない。
  • typedef宣言や型のconst修飾などはその語順を固定している。
  • 型解析時は型のconst修飾を無視する。
  • 関数のプロトタイプ宣言はトップレベルでのみ行える。
  • 関数ポインタが使えない。(関数ポインタ自体は実装してあるが関数ポインタ型の変数を宣言できない)
  • 列挙体が使えない。
  • etc

セルフコンパイルに不要そうな機能はあらかた切り捨て、また、そのような機能はできる限り使用せずにコードを書くことで比較的短期間でセルフコンパイルに漕ぎつけることができました。(最初のコミットが2019年4月4日 12:02でセルフコンパイルに成功したのが2019年4月14日 14:30 前後なのでだいたい10日間くらい)

テスト駆動的に開発する

noccの開発はテスト駆動的に行いました。

テストの記述にはLLVMのJITコンパイルが非常に役に立ちました。

参考: nocc/test_engine.c at master · Ryooooooga/nocc · GitHub

意味解析器を構文解析器から分離

構文解析器の中に型検査やシンボルの解決などのコードを書くと、コードが肥大化したり見通しが悪くなったりしがちです。

文脈自由言語であれば、構文解析フェーズで(型情報なしの)抽象構文木を生成し、そのあとで木訪問器(Visitor)を使ってその抽象構文木に型情報やシンボルの情報を追加する手法が取られることがあります。

しかし、C言語は文脈依存言語であるため、(typedef宣言をサポートする場合) シンボルの登録や解決を構文解析と同時に行う必要があります。

例えば、a * b;というC言語のコードがあったとして、このコードがどのような意味を持つのかはそれ以前の文脈に依存します。

{
    int a;
    int b;

    a * b; /* ここでは乗算 */
}
{
    typedef int a;

    a * b; /* ここではint*型の変数bの宣言 */
}

そこでnoccではswiftcなどを参考に意味解析器をモジュール化し、構文解析器から呼び出されるコールバック関数として実装することで構文解析と意味解析のコードを分割することにしました。

実際のコードを示しながらどのように分割を行ったか述べます。

識別子式の解析

以下の関数、parse_identifier_expr()は単一の識別子からなる式(a, ctx, printfのような)の構文解析を行う関数です。

ExprNode *parse_identifier_expr(ParserContext *ctx) {
    const Token *t;

    /* トークンを読む */
    t = consume_token(ctx);

    /* トークンが識別子であることをチェックする */
    if (t->kind != token_identifier) {
        fprintf(stderr, "expected identifier, but got %s\n", t->text);
        exit(1);
    }

    /* 意味解析モジュールの呼び出し */
    return sema_identifier_expr(ctx, t);
}

parser.c 298行目 ~ 311行目

見ての通り、実装としてはトークンを1つ読んで識別子かどうかを確かめているだけの単純なものです。

このparse_identifier_expr()から呼び出されている関数、sema_identifier_expr()が意味解析モジュールのコールバック関数です。

これは1つの識別子トークンを受け取り、シンボルの解決や型情報の解決を行ったあとその式を表す抽象構文木のノードを返す関数です。

ExprNode *sema_identifier_expr(ParserContext *ctx, const Token *t) {
    /* 抽象構文木のノードを表す構造体 */
    IdentifierNode *p;

    /* ノードの構築 (省略) */

    /* 現在のスコープからシンボルの宣言を探す */
    p->declaration = scope_stack_find(ctx->env, t->text, true);

    if (p->declaration == NULL) {
        /* シンボルが見つからなかった */
        fprintf(stderr, "undeclared symbol %s\n", t->text);
        exit(1);
    }

    /* (省略) */

    /* 式の型は宣言された変数の型と同じ */
    p->type = p->declaration->type;

    /* 構築したノードを構文解析器に返す */
    return (ExprNode *)p;
}

sema.c 399行目 ~ 434行目

[2019/04/15 追記]

次はより複雑な文の解析を行う場合を見てみます。

複合文の解析

{ ... } によって表現される複合文 (Compound Statement)はレキシカルスコープを形成します。

この文の構文解析は以下の関数、parse_compound_stmt()によって行われます。

StmtNode *parse_compound_stmt(ParserContext *ctx) {
    const Token *open;
    const Token *close;
    Vec *stmts;

    /* 複合文の形成するレキシカルスコープに入る */
    sema_compound_stmt_enter(ctx);

    /* トークンを読む */
    open = consume_token(ctx);

    /* トークンが 「{」 であることを確認する */
    if (open->kind != '{') {
        fprintf(stderr, "expected {, but got %s\n", open->text);
        exit(1);
    }

    /* 内部の文の抽象構文木ノードを格納するvectorを生成する */
    stmts = vec_new();

    /* 「}」 トークンが出現するまで繰り返し文を解析する */
    while (current_token(ctx)->kind != '}') {
        vec_push(stmts, parse_stmt(ctx));
    }

    /* トークンを読む */
    close = consume_token(ctx);

    /* トークンが 「}」 であることを確認する */
    if (close->kind != '}') {
        fprintf(stderr, "expected }, but got %s\n", close->text);
        exit(1);
    }

    /* 抽象構文木ノードを生成し、レキシカルスコープから抜ける */
    return sema_compound_stmt_leave(ctx, open, (StmtNode **)stmts->data,
                                    stmts->size, close);
}

parser.c 835行目 ~ 869行目

上のコードでは、識別子式の例とは異なり意味解析モジュールが2回呼び出されています。

  1. sema_compound_stmt_enter() 関数
  2. sema_compound_stmt_leave() 関数

これらはそれぞれ「{」の出現時、「}」の出現時に呼び出されるコールバック関数であり、複合文が形成するレキシカルスコープの生成と破棄を担当します。

/* 複合文の開始時に呼び出されるコールバック関数 */
void sema_compound_stmt_enter(ParserContext *ctx) {
    /* 新しいスコープをスタックにプッシュする */
    sema_push_scope(ctx);
}

/* 複合文の終了時に呼び出されるコールバック関数 */
StmtNode *sema_compound_stmt_leave(ParserContext *ctx, const Token *open,
                                   StmtNode **stmts, int num_stmts,
                                   const Token *close) {
    /* 抽象構文木のノードを表す構造体 */
    CompoundNode *p;

    /* (省略) */

    /* スタックからスコープを取り除く */
    sema_pop_scope(ctx);

    /* ノードの構築 (省略) */

    /* 構築したノードを構文解析器に返す */
    return (StmtNode *)p;
}

sema.c 972行目 ~ 1005行目

[2019/04/15 追記ここまで]

このように構文解析と意味解析を分離する試みは結果的に成功し、構文解析器 (parser.c) と 意味解析器 (sema.c) 双方の見通しの良さを保つことができました。

まとめ

コード生成はLLVMにおんぶにだっこであんまりちゃんと書けた気がしません。

気が向いたらx86_64のコードを吐けるようにしてみようと思います。