chibicc - 小さなCコンパイラ

(A small C compiler)

Created at: 2019-08-03 10:22:25
Language: C
License: MIT

chibicc:小さなCコンパイラ

(古いマスターは 歴史的/古い ブランチに移動しました。これは2020年9月にアップロードされた新しいものです。)

chibiccは、ほとんどのC11機能を実装するもう1つの小さなCコンパイラです。他の小さなコンパイラと同じように、おそらく「おもちゃのコンパイラ」カテゴリに分類されますが、chibiccは、コンパイルされたプログラムに変更を加えることなく、 GitSQLitelibpng、chibicc自体を含むいくつかの実際のプログラムをコンパイルできます。これらのプログラムの生成された実行可能ファイルは、対応するテストスイートに合格します。したがって、chibiccは実際にはさまざまなC11機能をサポートしており、実際のCコードの数十万行を正しくコンパイルすることができます。

chibiccは、私が現在Cコンパイラと低水準プログラミングについて書いている本のリファレンス実装として開発されています。この本は、インクリメンタルなアプローチで広大なトピックをカバーしています。最初の章では、読者は「言語」として1つの数字だけを受け入れる「コンパイラ」を実装します。これにより、コンパイラが受け入れる言語がC11と一致するまで、本の各セクションで一度に1つの機能が得られます。仕様は指定します。私はAbdulazizGhuloumの論文からこの漸進的なアプローチを採用しました。

このプロジェクトの各コミットは、本のセクションに対応しています。この目的のために、プロジェクトの最終状態だけでなく、各コミットは読みやすさを念頭に置いて注意深く書かれました。読者は、このプロジェクトの1つまたはいくつかのコミットを読むだけで、C言語機能を実装する方法を学ぶことができるはずです。たとえば、これは while[]?:、およびthread-local変数 が実装される方法です。十分な時間がある場合は、最初のコミットからそれを読むのが楽しいかもしれません。

このプロジェクトが気に入ったら、本が入手可能になったら購入を検討してください。😀私はここでソースコードを公開して、人々が早期にアクセスできるようにします。本を公開した後、とにかくパーミッシブオープンソースライセンスでそれを行うことを計画していたからです。ソースコードに料金を請求しないのであれば、それを非公開にしておくことは私にはあまり意味がありません。2021年に本を出版したいと思っています。ここでサインアップして、無料の章がオンラインで利用可能になったとき、または本が出版されたときに通知を受け取ることができます。

私はchibiccをcheebeeceeceeと発音します。「ちび」は日本語で「ミニ」または「スモール」を意味します。「cc」はCコンパイラの略です。

状態

chibiccは、C11のほぼすべての必須機能とほとんどのオプション機能、およびいくつかのGCC言語拡張機能をサポートしています。

小さなコンパイラでは欠落していることが多いが、chibiccでサポートされている機能には、次のものがあります(ただしこれらに限定されません)。

  • プリプロセッサ
  • float、double、およびlong double(x87 80ビット浮動小数点数)
  • ビットフィールド
  • alloca()
  • 可変長配列
  • 複合リテラル
  • スレッドローカル変数
  • 原子変数
  • 一般的な記号
  • 指定イニシャライザー
  • L、u、U、およびu8文字列リテラル
  • x86-64 SystemV ABIで指定されているように、構造体を値として受け取るまたは返す関数

chibiccは、複素数、K&Rスタイルの関数プロトタイプ、およびGCCスタイルのインラインアセンブリをサポートしていません。有向グラフと三字記号は意図的に省略されています。

chibiccは、ソースコードでエラーを検出すると、シンプルですが優れたエラーメッセージを出力します。

最適化パスはありません。chibiccは、GCCの出力よりもおそらく2倍以上遅いひどいコードを出力します。フロントエンドが完了したら、最適化パスを追加する予定です。

開発プラットフォームとしてx86-64用のUbuntu20.04を使用しています。chibiccがUbuntu18.04、Fedora 32、Gentoo 2.6で動作するようにいくつかの小さな変更を加えましたが、現時点では移植性は私の目標ではありません。Ubuntu20.04以外のシステムでは動作する場合と動作しない場合があります。

内部

chibiccは、次の段階で構成されています。

  • Tokenize:トークナイザーは文字列を入力として受け取り、それをトークンのリストに分割して返します。

  • 前処理:プリプロセッサは、トークンのリストを入力として受け取り、マクロ拡張トークンの新しいリストを出力します。マクロを展開しながら、プリプロセッサディレクティブを解釈します。

  • 解析:再帰下降パーサーは、プリプロセッサーの出力から抽象構文ツリーを構築します。また、各ASTノードにタイプを追加します。

  • Codegen:コードジェネレーターは、指定されたASTノードのアセンブリテキストを出力します。

貢献

このコンパイラでバグを見つけたら、バグを発生させた元のコミットに戻り、最初からそのようなバグがなかったかのようにコミット履歴を書き直します。これはバグを修正する珍しい方法ですが、本の一部として、すべてのコミットをバグのない状態に保つことが重要です。

したがって、このリポジトリではプルリクエストを受け取りません。バグを見つけた場合はプルリクエストを送信できますが、パッチを読み取り、履歴を書き換えて以前のコミットに適用する可能性が非常に高くなります。私はどこかにあなたの名前をクレジットしますが、あなたの変更はこのリポジトリに提出される前に私によって書き直されます。

また、履歴を書き換えるために、ローカルリポジトリをこのパブリックリポジトリに強制的にプッシュすることがあると想定してください。このプロジェクトのクローンを作成し、その上にローカルコミットを行う場合、新しいコミットを強制的にプッシュするときに、変更を手動でリベースする必要があります。

設計原則

chibiccのコアバリューは、そのシンプルさとソースコードの信頼性です。この目標を達成するために、私はコードを書くときにあまり賢くならないように注意しました。それが何を意味するのか説明させてください。

多くの場合、コードベースに慣れる につれて、より多くの抽象化と巧妙なトリックを使用してコードを改善したくなるでしょう。しかし、そのような改善は、初めての読者の読みやすさを常に改善するとは限らず、実際にそれを傷つける可能性があります。私は可能な限り落とし穴を避けようとしました。私はこのコードを私のためではなく、初めての読者のために書きました。

ソースコードを見ると、馬鹿げたコードがいくつか見つかります。これらは意図的にそのように書かれています(しかし、場所によっては実際に何かが欠けているかもしれません)。ここにいくつかの注目すべき例があります:

  • 再帰下降パーサーには、似たような生成文法規則のための似たような関数が多数含まれています。高階関数やマクロを使って重複を減らすために改善したいと思うかもしれませんが、それは複雑すぎると思いました。代わりに、小さな複製を許可することをお勧めします。

  • chibiccは、メモリを節約するために一生懸命努力しません。たとえば、トークナイザーが起動する前に、入力ソースファイル全体が最初にメモリに読み込まれます。

  • nが大きすぎないことがわかっている場合は、遅いアルゴリズムで問題ありません。たとえば、プリプロセッサのセットとしてリンクリストを使用するため、メンバーシップチェックはO(n)を取ります。ここで、nはセットのサイズです。しかし、nは通常非常に小さいことがわかっているので、それで問題ありません。また、nが非常に大きくなる可能性がある場合でも、ベンチマークによってボトルネックであることが証明されるまで、単純な低速アルゴリズムを使用します。

  • 各ASTノードタイプは、構造体メンバーの少数のメンバーのみを使用します

    Node
    。他の未使用
    Node
    のメンバーは、実行時にメモリを浪費するだけです。ユニオンを使用してメモリを節約することもできますが、代わりにすべてを同じ構造体に配置することにしました。非効率性はごくわずかだと思います。重要な場合でも、いつでもユニオンを使用するようにコードを変更できます。時期尚早の最適化を避けたかったのです。

  • chibiccは常に、を使用してヒープメモリを割り当てます。これは、メモリをゼロでクリア

    calloc
    するバリアントです。より少し遅いですが、それは無視できるはずです。
    malloc
    calloc
    malloc

  • 最後になりましたが、chibiccはを使用してメモリを割り当てます

    calloc
    が、を呼び出すことはありません
    free
    。割り当てられたヒープメモリは、プロセスが終了するまで解放されません。このメモリ管理ポリシー(またはその欠如)は非常に奇妙に見えると確信していますが、コンパイラなどの短命のプログラムには意味があります。Dプログラミング言語のコンパイラであるDMDは、同じ理由で同じメモリ管理スキームを使用します(例:[1])。

著者について

上山るいです。私は趣味のCコンパイラである8ccの作成者であり、さまざまなオペレーティングシステムや大規模なビルドシステムで使用される本番品質のリンカーであるLLVMlldリンカーの現在のバージョンの元の作成者でもあります。

参考文献

[1] https://www.drdobbs.com/cpp/increasing-compiler-speed-by-over-75/240158941

DMDは、少し卑劣な方法でメモリ割り当てを行います。コンパイラーは短命のプログラムであり、速度が重要であるため、DMDはただマロックし、解放されることはありません。