在 1024 字节里写一个 Python 解释器：极简解析器与代码压缩实战

一篇技术博文（作者 Austin Henley，田纳西大学副教授）记录了一个代码挑战：把 Python 子集解释器压缩到 1024 字节 C 代码。它不解析成 AST、不编译字节码，只用递归下降解析器边解析边执行，依赖 C 调用栈实现控制流。本文基于该博文，解读实现思路与压缩技巧。

挑战设定

目标不是实现完整 Python，而是做一个"看起来像 Python"的解释器——能跑 fizzbuzz：有 def、冒号、缩进、if 不需要括号。

第一次尝试失败：512 字节不够

作者先试 512 字节：从 1 + 2 的表达式计算器开始，逐步加赋值和 if 语句——结果只是"做了一个计算器"，而且已经超限。于是重新规划：先列出"看起来像 Python"的元素清单，先让它工作，再让它变小。

实现架构

真正的 CPython 要分词、解析成 AST、分析优化、发射字节码、解释执行。这个极简版本全都不做：

• 状态放在少量全局变量里
• 固定长度数组（999）存原始 Python 代码
• 变量和函数名放进单个数组
• 表达式用标准递归下降解析器，边解析边执行

char src[999];  /* 整个程序（去掉大部分空格） */
int vars[256];  /* 符号表 */
int pos;        /* src 中的下一个字符 */
int ch;         /* 当前字符 */
int line_start; /* 当前行的起始位置 */

完全没有错误处理，对代码正确性做大量假设（如关键字必须拼写正确）。

控制流魔法：用 C 调用栈

• 执行代码块直到缩进减少，此时返回，由调用者处理下一行——用 C 程序的调用栈处理递归
• 循环：什么都没编译，循环靠跳回源码位置重新解析实现。while 和 for 都记录条件表达式的位置，循环体执行完跳回继续解析
• 函数：解析函数定义时符号表记住函数在源码中的位置；调用时保存调用者位置、跳到函数体、执行完恢复调用者位置
• 没有中间表示也能实现递归——相当优雅

压缩技巧

可读版本超过 4800 字节，压缩到 1024 字节用了这些技巧：

• 单字母变量和函数名
• 假设编译器会链接 libc
• 用全局变量做临时变量（全局变量零初始化）
• C89 允许声明隐式为 int，函数默认返回 int
• 用函数参数做临时变量（保留在调用栈上）
• 用 ASCII 值代替字符字面量
• 三元运算符和逗号运算符
• 用位运算代替逻辑运算

示例：可读的 parse_sum 被压成 e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;}。

最终实现的功能

• 整型变量（单字母）和字面量
• 变量赋值
• • • • % 算术（含优先级；一元 +/- 只在表达式开头）
• < > <= >= == 比较（每个表达式一个）
• 整数真值
• if 和 else
• while 循环（含 else 块）
• for x in range(y) 循环（含 else 块）
• 无参函数定义
• 函数调用（含递归）
• 基于缩进的块（无作用域）
• 带单个字符串字面量或整型表达式的 print
• 注释

总结

这个 1024 字节解释器展示了三个关键思想：一是极简解析——递归下降解析器边解析边执行，不构建任何中间表示；二是用宿主语言调用栈实现控制流——循环靠跳回源码位置重解析，函数靠保存/恢复调用者位置；三是代码压缩的工程学——单字母命名、依赖 C 隐式规则、ASCII 值替代字符字面量等技巧把 4800 字节压进 1024。作者提醒：比较表达式是被砍掉的大块（if n%15: 的真值仍能工作），如果只做 fizzbuzz 可以压到 800 字节以下。对想理解解释器原理或对代码体积敏感的开发者，这是个有趣的参考。

来源：https://austinhenley.com/blog/python1024.html