**セクターC：512バイトで実装されたCコンパイラ**

SectorC：512 バイトで動く C コンパイラ

SectorC（GitHub）とは、x86‑16 アセンブリで書かれた C コンパイラです。
1 ブートセクタ（512 バイト）の中に収まります。
C のサブセットをサポートし、実際に面白いプログラムを書けるほどの機能があります。
おそらく「これまでで最も小さい C コンパイラ」だと言えるでしょう。

Base64 形式

6gUAwAdoADAfaAAgBzH/6DABPfQYdQXoJQHr8+gjAVOJP+gSALDDqluB+9lQdeAG/zdoAEAfy+gI
AegFAYnYg/hNdFuE9nQNsOiqiwcp+IPoAqvr4j3/FXUG6OUAquvXPVgYdQXoJgDrGj0C2nUGV+gb
AOsF6CgA68Ow6apYKfiD6AKrifgp8CaJRP7rrOg4ALiFwKu4D4Srq1fonP9ewz2N/HUV6JoA6BkA
ieu4iQRQuIs26IAAWKvD6AcAieu4iQbrc4nd6HkA6HYA6DgAHg4fvq8Bra052HQGhcB19h/DrVCw
UKroWQDoGwC4WZGrW4D/wHUMuDnIq7i4AKu4AA+ridirH8M9jfx1COgzALiLBOucg/j4dQXorf/r
JIP49nUI6BwAuI0G6wyE0nQFsLiq6wa4iwarAduJ2KvrA+gAAOhLADwgfvkx2zHJPDkPnsI8IH4S
weEIiMFr2wqD6DABw+gqAOvqicg9Ly90Dj0qL3QSPSkoD5TGidjD6BAAPAp1+eu86Ln/g/jDdfjr
slIx9osEMQQ8O3QUuAACMdLNFIDkgHX0PDt1BIkEMcBaw/v/A8H9/yvB+v/34fb/I8FMAAvBLgAz
wYQA0+CaANP4jwCUwHf/lcAMAJzADgCfwIUAnsCZAJ3AAAAAAAAAAAAAAAAAAAAAVao=

対応言語機能

• グローバル変数
• 関数

• if

  文

• while

  ループ
• 多彩な演算子（

  +

  ,

  -

  ,

  *

  ,

  &

  ,

  |

  ,

  ^

  ,

  <<

  ,

  >>

  ,

  ==

  ,

  !=

  ,

  <

  ,

  >

  ,

  <=

  ,

  >=

  ）
• ポインタ参照 (

  *(int*)

  )

• asm

  ステートメントによるインライン機械語埋め込み
• シングルラインコメント（

  // …

  ）とマルチラインコメント（

  /* … */

  ）

これらの機能により、コンパイラは十分に実用的です。

例題 – 正弦波を描くプログラム

int y;
int x;
int x_0;

void sin_positive_approx()
{
  y = (x_0 * (157 - x_0)) >> 7;
}

void sin()
{
  x_0 = x;
  while (x_0 > 314) { x_0 -= 314; }
  if (x_0 <= 157)        sin_positive_approx();
  else {
    x_0 -= 157;
    sin_positive_approx();
    y = -y;
  }
  y += 100;
}

int offset, x_end;

void draw_sine_wave()
{
  x      = offset;
  x_end  = x + 314;
  while (x <= x_end) {
    sin();
    pixel_x = x - offset;
    pixel_y = y;
    vga_set_pixel();
    ++x;
  }
}

int v_1, v_2;

void delay()
{
  v_1 = 0;
  while (v_1 < 50) {
    v_2 = 0;
    while (v_2 < 10000) ++v_2;
    ++v_1;
  }
}

void main()
{
  vga_init();
  offset = 0;
  while (1) {
    vga_clear();
    draw_sine_wave();
    delay();
    ++offset;
    if (offset >= 314) offset -= 314;   /* modulo to avoid overflow */
  }
}

設計概要

トークナイザ & パーサ

• トークナイザ は最小限のレキサで、任意のバイトストリームを読み取り

  TOKEN_KEYWORD_INT

  や

  TOKEN_IDENTIFIER

  等のトークンを発行します。
• パーサ は再帰下降方式でトークン列を処理し、シンボルテーブルは不要です。変数は名前を 64 kB セグメントにハッシュしてアクセスします。

Barely C

• 「ベア」な C サブセットでは、スペース区切りで メガトークン を作成しレキサの複雑さを軽減。

• atoi()

  をハッシュ関数として利用：識別子文字列の数値化がキーとなり、検索を簡素化。

サイズ最適化手法

1. 明示ジャンプより フォールスルー を優先。
2. スタック増大を避けるために

   jmp

   で 尾呼び出し。
3. 連続する呼び出しを 結合（call fusion）。

4. lodsw

   ,

   stosw

   の頻繁使用。
5. マシンコードテーブルを可能な限り inline

   stosw

   に置換。

6. cmp ax,imm

   を

   cmp bx,imm

   よりも多用。
7. ジャンプオフセットは 8 ビット以内に収める。

これらの最適化で、コンパイラサイズを 468 バイト から 303 バイト に削減し、新機能（入れ子制御構造や拡張演算子セット）用に約200バイト余裕を残しました。

ランタイムサポート

• rt/lib.c

  ,

  rt/_start.c

  が I/O ルーチン等の低レベルサービスを提供。
• 実行時ランタイムはコンパイル前にソースコードと連結されます。

文法（ASCII）

program     = (var_decl | func_decl)+
var_decl    = "int" identifier ";"
func_decl   = "void" func_name "{" statement* "}"
func_name   = <identifier ending in "()">
statement   =
      "if(" expr "){" statement* "}"
    | "while(" expr "){" statement* "}"
    | "asm" integer ";"
    | func_name ";"
    | assign_expr ";"

assign_expr = deref? identifier "=" expr
deref       = "*(int*)"

expr        = unary (op unary)?
unary       =
      deref identifier
    | "&" identifier
    | "(" expr ")"
    | identifier
    | integer

op          = "+" | "-" | "&" | "|" | "^" | "<<" | ">>"
            | "==" | "!=" | "<" | ">" | "<=" | ">="

コメント（

// …

/* … */

インライン機械語

asm

結論

SectorC は「512 バイトのブートセクタメモリ内で動作する完全機能型 C コンパイラ」が可能だと示しています。
レキサ・パーサ・コード生成を慎重に設計し、すべてのバイトを積極的に最適化することで、複雑な言語機能も厳しい空間制約内で実現できることが証明されました。