Skip to content
dialougPublic

About

/

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

8 Commits

Folders and files

Repository files navigation

cppmini — C 自举与 quine 演示

用两个可运行的程序演示「C 语言如何自举」这一思想,由 CMake 管理、CTest 验证。

什么是自举(bootstrapping)

要编译 C 代码需要 C 编译器,而 C 编译器本身又用 C 写成——先有鸡还是先有蛋。 解决办法是分阶段引导:

  1. 种子阶段:用更底层的工具(汇编,或另一台机器上已有的编译器)造出第一个 只支持部分语言特性的简陋 C 编译器。
  2. stage1:用种子编译器编译「完整版编译器的源码」,得到功能完整的编译器。
  3. stage2(验证):用 stage1 再编译同一份源码得到 stage2;若 stage1 与 stage2 逐字节一致,说明编译器自洽正确。GCC 的 make bootstrap 做的正是这件事。

一旦引导完成,编译器就能编译自己的源码,形成闭环——这就是「自托管 (self-hosting)」。

本项目的两个演示

1. quine.c — 自举思想的最小内核

一个能逐字节输出自身完整源码的程序。这是「程序精确产生自己」的不动点, 正是自托管编译器「编译自己 → 逐字节一致」在最小尺度上的体现。

关键技巧:用 %c 配合 ASCII 码(34=引号、10=换行)在运行时生成引号和换行, 绕开「字符串里写引号要转义、转义又要转义」的死循环;用 %s 把源码字符串塞回 它自己在源码里的位置。Windows 上还需 _setmode(..., _O_BINARY) 关掉 \n→\r\n 的文本模式转换,才能做到逐字节一致。

2. minicc.c — 玩具编译器(自举链条的翻译阶段)

把一个极小语言 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

用 Mini 写的实证:迷你分词器

有了 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)。

手动试玩 minicc

./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)

About

/

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages