用两个可运行的程序演示「C 语言如何自举」这一思想,由 CMake 管理、CTest 验证。
要编译 C 代码需要 C 编译器,而 C 编译器本身又用 C 写成——先有鸡还是先有蛋。 解决办法是分阶段引导:
- 种子阶段:用更底层的工具(汇编,或另一台机器上已有的编译器)造出第一个 只支持部分语言特性的简陋 C 编译器。
- stage1:用种子编译器编译「完整版编译器的源码」,得到功能完整的编译器。
- stage2(验证):用 stage1 再编译同一份源码得到 stage2;若 stage1 与 stage2
逐字节一致,说明编译器自洽正确。GCC 的
make bootstrap做的正是这件事。
一旦引导完成,编译器就能编译自己的源码,形成闭环——这就是「自托管 (self-hosting)」。
一个能逐字节输出自身完整源码的程序。这是「程序精确产生自己」的不动点, 正是自托管编译器「编译自己 → 逐字节一致」在最小尺度上的体现。
关键技巧:用 %c 配合 ASCII 码(34=引号、10=换行)在运行时生成引号和换行,
绕开「字符串里写引号要转义、转义又要转义」的死循环;用 %s 把源码字符串塞回
它自己在源码里的位置。Windows 上还需 _setmode(..., _O_BINARY) 关掉
\n→\r\n 的文本模式转换,才能做到逐字节一致。
把一个极小语言 Mini 翻译成 C 源码,再由系统编译器编成原生程序:
Mini 源码 --minicc--> C 源码 --系统编译器--> 原生可执行文件
对应自举里最基础的一环:高级语言 → C → 机器码。
诚实的边界:minicc 本身是用 C 写的,不是用 Mini 写的,所以它不是真正的 self-hosting 编译器。真正的 self-hosting 要求语言强大到足以表达自己的编译器 (C/TCC/GCC 那种规模)。这里演示的是翻译链条与验证手法,不是完整自举。
Mini 语言支持:整型变量(let)、print、+ - * /、括号、# 行注释,
比较运算(< > == != <= >=),控制流 if/else ... end、while ... end
(块用 end 收尾,不用花括号),函数 fn ... end、return、函数调用,
以及定长数组(arr)、下标读写、字符字面量('A' '\n')、按字符输出(putc)
字符串常量输出(puts),全局变量(global 标量与数组,跨函数共享状态),
以及从标准输入读字符(getc,文件末尾返回 -1)。
示例见 examples/demo.mini、
examples/control.mini、
examples/func.mini、
examples/array.mini、
examples/string.mini、
examples/global.mini、
examples/tokenizer.mini、
examples/fizzbuzz.mini。
控制流示例:
let sum = 0;
let i = 1;
while i <= 10
let sum = sum + i;
let i = i + 1;
end
print sum; # 55
函数示例(递归):
fn fact(n)
if n <= 1
return 1;
end
return n * fact(n - 1);
end
print fact(5); # 120
数组与字符示例:
arr sq[5];
let i = 0;
while i < 5
let sq[i] = (i + 1) * (i + 1);
let i = i + 1;
end
putc 'H'; putc 'i'; putc '\n'; # 输出 Hi 加换行
字符串示例:
puts "answer = ";
print 6 * 7; # answer = 42
全局变量示例(跨函数共享状态):
global arr buf[16]; # 全局数组
global sp; # 全局游标
fn push(v)
let buf[sp] = v; # 直接读写全局,无需参数传递缓冲区
let sp = sp + 1;
return 0;
end
let ignore = push(10);
let ignore = push(20);
print sp; # 2,全局状态在调用间持续
输入示例(getc 读标准输入):
let c = getc; # 读一个字符,返回其字符码
while c != 0 - 1 # EOF 时 getc 返回 -1(Mini 无一元负号,用 0-1 表示)
putc c; # 原样回显
let c = getc;
end
有了 getc,Mini 就凑齐了写「编译器最前端」所需的全部要素:读输入、维护跨步骤
的全局状态、多路分支判断、算术与输出。examples/tokenizer.mini
用这些特性写了一个逐字符分词器——读 stdin 的源码,把每个字符按 minicc 词法器
同一套规则分类(数字 / 标识符字符 / 空白 / 符号),四类计数存在全局变量里,读到
EOF 后输出统计。这是「Mini 已经强大到能表达自己编译器的词法阶段」的实证。
$ printf 'let x = 42;\nprint x + 8;\n' | tokenizer
digit=3
ident=10
space=8
symbol=4
它本身就是一个用 Mini 写、经 minicc 翻译成 C、再由系统编译器编成原生程序的分词器—— 翻译链的每一环都真实跑通。当然,完整的 self-hosting 还需要 Mini 能表达符号表、 可变长字符串、结构化 token 等(见下方「诚实的边界」),但词法分类这一最前端环节已经 可以完全用 Mini 写出来。
变量提升:块作用域里首次声明、块外使用的变量在 C 里会编译失败。minicc
先扫一遍收集所有 let 变量,统一在函数(或 main)顶部声明,再生成语句体,
从而避开 C 的块作用域问题。
函数(局部作用域):函数只通过参数和返回值通信,各自局部变量独立,不引入
全局变量。生成分三趟:① 为每个 fn 发前向原型(因此支持任意顺序调用与
递归/互递归);② 生成各函数定义;③ 顶层裸语句收进 main。
数组与字符:arr NAME[N] 声明定长数组(N 为字面量),和标量一样在扫描阶段
统一收集、提升到函数/main 顶部并零初始化(long NAME[N] = {0};),避开 C 的块
作用域问题。let a[i] = e; 是元素赋值,a[i] 在表达式里是元素读取——靠 let 后
变量名的下一个 token 是不是 [ 来区分标量与数组。字符字面量('A'、'\n')在
Mini 与 C 里语法一致,词法整段抄下、原样发到 C;putc e 翻译成 putchar((int)(e)),
让 Mini 能逐字符输出文本(编译器生成 C 源码所必需)。数组暂不作参数或返回值。
字符串常量:puts "..." 输出一段固定文本,翻译成 fputs("...", stdout)(用
fputs 而非 printf,串里的 % 不会被当格式符)。字符串字面量与 C 语法一致、
支持 \n \t \" \\ 转义,词法整段抄下原样发出。它只作 puts 的直接实参——不进变量、
不作参数、不拼接(延续"一切皆 long"的简单模型)。有了它,编译器才能一句话发一段
#include、long 之类的固定 C 文本,而不必逐字符 putc。
全局变量(无遮蔽):global NAME; 与 global arr NAME[N]; 声明跨函数共享的
状态——这是写分词器/符号表所必需(源码缓冲区、当前位置游标天然是全局的)。生成
多加一趟 Pass 0:线性扫全文收集所有 global,把标量 long NAME = 0;、数组
long NAME[N] = {0}; 发到 C 的文件作用域(#include 之后、函数原型之前)。
关键在于:局部变量收集时凡命中全局名一律跳过,函数/main 内就不发同名局部声明,
于是 C 对该名字的引用自然解析到文件作用域的全局——代码生成(变量引用、赋值、
下标读写)完全不用改。无遮蔽:名字一旦是全局,处处指同一个变量。
标准输入(getc):getc 是一个表达式(factor),不是语句——它从 stdin 读
一个字符、返回其字符码,文件末尾返回 -1,可直接用在 let c = getc; 或比较里。
翻译极简:getc 原样发成 C 的 getchar()(同样在 EOF 返回 -1,语义天然对齐),
编译器主体一行未改。有了输入,Mini 才从「只能算、只能写」变成「能读、能处理外部
数据」,也就凑齐了写词法器所需的最后一块。
cmake -S . -B build # 配置
cmake --build build --config Debug # 编译 quine 和 minicc
cd build && ctest -C Debug # 运行九个验证测试九个 CTest 测试:
quine_self_reproduces— quine 的输出与quine.c逐字节一致。minicc_pipeline—demo.mini经 minicc 翻译、编译、运行后,输出等于 examples/demo.expected(42 / 26 / 25 / 28)。minicc_control_flow—control.mini(while / if-else / 比较)输出55 / 5 / 0。minicc_functions—func.mini(fn / 调用 / 参数 / 递归)输出120 / 42 / 55。minicc_arrays—array.mini(arr / 下标读写 / 字符 / putc)输出55 / 50 / Hi。minicc_strings—string.mini(puts / 字符串转义 / 与 print、putc 混用)。minicc_globals—global.mini(global 标量/数组跨函数共享状态)输出60 / 3 / 7。minicc_tokenizer—tokenizer.mini(getc 读 stdin,逐字符分类计数), 用 examples/tokenizer.input 作输入,输出digit=3 / ident=10 / space=8 / symbol=4。minicc_fizzbuzz—fizzbuzz.mini(while / 嵌套 if-else / 整数取模模拟 / puts / putc / print)输出经典 FizzBuzz(1..15)。
./build/Debug/minicc examples/demo.mini out.c # 翻译成 C
cat out.c # 看生成的 C 代码cppmini/
├── quine.c # 输出自身源码的程序
├── minicc.c # Mini -> C 玩具编译器
├── CMakeLists.txt # 工程定义 + 九个 CTest 测试
├── cmake/
│ ├── check_quine.cmake # quine 自洽性验证脚本
│ └── check_minicc.cmake # minicc 翻译链端到端验证脚本
└── examples/
├── demo.mini # 四则运算示例
├── control.mini # 控制流示例(if/while)
├── func.mini # 函数示例(递归)
├── array.mini # 数组与字符示例(arr/下标/putc)
├── string.mini # 字符串示例(puts/转义)
├── global.mini # 全局变量示例(global 跨函数共享)
├── tokenizer.mini # 迷你分词器(getc 读 stdin,逐字符分类)
└── fizzbuzz.mini # FizzBuzz(while/嵌套 if/取模/puts/print)