简介这是一份面向编译器与解释器入门学习者的C语言实践资源围绕「用500多行代码实现微型解释器」展开适合已掌握C语言基础语法、希望理解词法分析、语法分析与AST构建等编译原理核心概念的开发者练手。压缩包共10个文件约25KB以7个Markdown文档为主体系统梳理解释器构造思路与关键步骤另含1个C源码文件、1个.try示例脚本及1个license授权文件结构轻量、便于快速通读与二次修改。目前已有229人学习下载可作为编译原理课程的配套实验素材。读者可从中获得从词法分析到执行阶段的完整实现脉络理解标记流、抽象语法树与逐行解释的运行机制并借助示例脚本验证解释器行为在有限代码量内体会精简设计与错误处理的取舍为深入编译器设计打下基础。1. 500 行 C 语言写一个微型解释器到底能跑多远很多人第一次听到「用 C 语言写解释器」脑子里浮现的是几万行的编译器工程觉得这是只有科班出身才敢碰的东西。但 tryC 这个方向恰恰相反它把词法分析、语法分析、AST 求值压缩到 500 多行 C 代码里跑通一个支持变量、四则运算、括号、比较和条件分支的微型解释器。你不需要先啃完《编译原理》只要熟悉 C 语言基础、指针和结构体就能跟着把整条链路走一遍。它解决的不是「造一个生产级语言」的问题而是让你真正理解一行1 2 * 3从字符串变成结果中间到底发生了什么。适合两类人一类是刚学完 C 语言基础、想找个能落地的项目把指针和内存管理练熟的另一类是想搞懂解释器黑匣子、但被大部头教材劝退的从业者。500 行不是噱头它意味着每个函数你都能读懂每处内存分配你都能追踪翻车了也能自己查。2. 解释器的四段流水线从字符流到结果2.1 为什么是「词法 → 语法 → AST → 求值」而不是边读边算最常见的错误做法是拿到字符串直接switch字符遇到数字就atoi遇到就弹栈计算。这种写法在只支持12时能跑一旦加上括号、优先级、变量赋值就彻底失控。原因很简单字符层面没有「结构」12*3和(12)*3在字符流里长得几乎一样你没法在扫描阶段就知道谁先算。正规做法是把过程切成四段每段只干一件事。词法分析Lexer负责把x 1 2 * 3切成[IDENT(x), ASSIGN, NUM(1), PLUS, NUM(2), STAR, NUM(3), EOF]这样的 token 序列它不关心语法对不对只关心「这是不是一个合法的数字/标识符/运算符」。语法分析Parser拿着 token 序列按优先级和结合性规则搭出一棵抽象语法树AST比如*的节点会成为的子节点。求值器Evaluator递归遍历这棵树自底向上算出结果。这样分层的好处是每一层都能单独测试Lexer 喂字符串看 token 对不对Parser 喂 token 看树形对不对Evaluator 喂树看数值对不对。哪一层出问题一目了然不用在一坨switch里大海捞针。500 行的预算下这个结构依然是最省心的因为每层代码量都在 100 行上下加起来刚好。2.2 用枚举和结构体定义 token 与 AST 节点先定数据结构这是整个解释器的地基。token 类型用枚举token 本身用结构体带上类型和值。AST 节点用带kind标签的结构体配合联合体union存不同节点的数据。这里有个血泪经验union 用起来省内存但调试时容易看错字段新手可以先全部用独立字段跑通再优化。#include stdio.h #include stdlib.h #include string.h #include ctype.h typedef enum { TOK_NUM, TOK_IDENT, TOK_PLUS, TOK_MINUS, TOK_STAR, TOK_SLASH, TOK_LPAREN, TOK_RPAREN, TOK_ASSIGN, TOK_EQ, TOK_LT, TOK_GT, TOK_IF, TOK_ELSE, TOK_EOF } TokKind; typedef struct { TokKind kind; long value; // TOK_NUM 时有效 char name[32];// TOK_IDENT 时有效 } Token; typedef enum { NODE_NUM, NODE_VAR, NODE_BINOP, NODE_ASSIGN, NODE_IF } NodeKind; typedef struct Node { NodeKind kind; // NODE_NUM long value; // NODE_VAR / NODE_ASSIGN char name[32]; // NODE_BINOP TokKind op; struct Node *left, *right; // NODE_IF struct Node *cond, *then_branch, *else_branch; } Node;Token里value和name同时存在会浪费一点空间但 500 行规模下完全无所谓换来的是调试时不用记 union 当前激活的是哪个字段。Node把所有可能用到的指针都摊开NODE_NUM只用valueNODE_BINOP只用op/left/right其余为 NULL。这种「胖节点」写法在微型解释器里是划算的因为节点总数撑死几百个内存不是瓶颈可读性才是。参数上要注意name[32]这个长度标识符超过 31 字符会被截断。如果你打算支持长变量名把它改成char *name配合strdup但那样就得多写释放逻辑。500 行的目标下固定数组是更稳的选择代价是变量名别起太长。2.3 词法分析把字符串切成 token 的 60 行Lexer 的核心是一个游标pos从头扫到尾跳过空白识别数字、标识符和符号。关键字if、else在识别出标识符后再查表判断这是最省事的做法。typedef struct { const char *src; int pos; } Lexer; static Token make_token(TokKind k, long v, const char *name) { Token t; t.kind k; t.value v; if (name) { strncpy(t.name, name, 31); t.name[31] \0; } else t.name[0] \0; return t; } Token next_token(Lexer *lx) { while (isspace(lx-src[lx-pos])) lx-pos; char c lx-src[lx-pos]; if (isdigit(c)) { long v 0; while (isdigit(lx-src[lx-pos])) v v * 10 (lx-src[lx-pos] - 0); return make_token(TOK_NUM, v, NULL); } if (isalpha(c) || c _) { char buf[32]; int i 0; while (isalnum(lx-src[lx-pos]) || lx-src[lx-pos] _) buf[i] lx-src[lx-pos]; buf[i] \0; if (strcmp(buf, if) 0) return make_token(TOK_IF, 0, NULL); if (strcmp(buf, else) 0) return make_token(TOK_ELSE, 0, NULL); return make_token(TOK_IDENT, 0, buf); } lx-pos; switch (c) { case : return make_token(TOK_PLUS, 0, NULL); case -: return make_token(TOK_MINUS, 0, NULL); case *: return make_token(TOK_STAR, 0, NULL); case /: return make_token(TOK_SLASH, 0, NULL); case (: return make_token(TOK_LPAREN, 0, NULL); case ): return make_token(TOK_RPAREN, 0, NULL); case : return make_token(TOK_ASSIGN, 0, NULL); case : return make_token(TOK_LT, 0, NULL); case : return make_token(TOK_GT, 0, NULL); case \0: return make_token(TOK_EOF, 0, NULL); } fprintf(stderr, lex error: unexpected char %c\n, c); exit(1); }逻辑上next_token每次调用返回一个 token 并推进pos。数字用累乘累加解析标识符用缓冲区收集后查关键字表。符号直接switch映射。注意lx-pos在switch之前就执行了所以每个case里不用再推进游标这个顺序别写反否则会漏字符。参数说明buf[32]和 token 里的name[32]保持一致避免拷贝时越界。exit(1)是最粗暴的错误处理生产环境当然要返回错误码但微型解释器里直接退出能让你第一时间看到出错位置。如果你想让解释器在 REPL 里不崩把exit换成返回一个TOK_EOF并打印错误即可。3. 递归下降搭 AST优先级和结合性怎么落到代码里3.1 用函数层级表达优先级比查表更直观语法分析用递归下降核心思想是「每个优先级一个函数」。表达式文法的层级从低到高是赋值 → 比较 → 加减 → 乘除 → 一元 → 原子。低优先级函数调用高优先级函数这样1 2 * 3在解析时右操作数会先被parse_mul吃掉2 * 3自然形成正确的树形。typedef struct { Lexer lx; Token cur; } Parser; static void advance(Parser *p) { p-cur next_token(p-lx); } static Node *parse_expr(Parser *p); // 赋值层 static Node *parse_cmp(Parser *p); // 比较层 static Node *parse_add(Parser *p); // 加减层 static Node *parse_mul(Parser *p); // 乘除层 static Node *parse_atom(Parser *p); // 原子层 static Node *new_node(NodeKind k) { Node *n calloc(1, sizeof(Node)); n-kind k; return n; } static Node *parse_atom(Parser *p) { if (p-cur.kind TOK_NUM) { Node *n new_node(NODE_NUM); n-value p-cur.value; advance(p); return n; } if (p-cur.kind TOK_IDENT) { Node *n new_node(NODE_VAR); strncpy(n-name, p-cur.name, 31); advance(p); return n; } if (p-cur.kind TOK_LPAREN) { advance(p); Node *n parse_expr(p); if (p-cur.kind ! TOK_RPAREN) { fprintf(stderr, parse error: expected )\n); exit(1); } advance(p); return n; } fprintf(stderr, parse error: unexpected token %d\n, p-cur.kind); exit(1); } static Node *parse_mul(Parser *p) { Node *left parse_atom(p); while (p-cur.kind TOK_STAR || p-cur.kind TOK_SLASH) { TokKind op p-cur.kind; advance(p); Node *n new_node(NODE_BINOP); n-op op; n-left left; n-right parse_atom(p); left n; } return left; } static Node *parse_add(Parser *p) { Node *left parse_mul(p); while (p-cur.kind TOK_PLUS || p-cur.kind TOK_MINUS) { TokKind op p-cur.kind; advance(p); Node *n new_node(NODE_BINOP); n-op op; n-left left; n-right parse_mul(p); left n; } return left; }parse_mul里的while循环处理左结合性8 / 4 / 2会先建(8/4)的节点再把它作为左子节点建/2得到(8/4)/2 1而不是8/(4/2) 4。这就是左结合在代码里的体现——循环里始终把已建好的left往左挂。parse_atom是递归的出口遇到数字、变量或左括号就返回。括号的处理是「吃掉左括号递归解析整个表达式再要求右括号」这样括号内的内容会独立成子树优先级自然最高。参数上new_node用calloc而不是malloc因为后面求值时会检查left/right是否为 NULLcalloc帮你把指针清零省得手动初始化每个字段。代价是稍微慢一点但解释器启动阶段这点开销可以忽略。3.2 赋值和 if 语句把语句层接进表达式层到这一步表达式已经能跑了但还缺变量赋值和条件分支。赋值比较特殊它的左边必须是变量右边是表达式所以单独一层parse_expr处理。static Node *parse_expr(Parser *p) { if (p-cur.kind TOK_IDENT) { // 预读一个 token 判断是不是赋值 Token save p-cur; Lexer save_lx p-lx; advance(p); if (p-cur.kind TOK_ASSIGN) { advance(p); Node *n new_node(NODE_ASSIGN); strncpy(n-name, save.name, 31); n-right parse_expr(p); return n; } // 不是赋值回退 p-cur save; p-lx save_lx; } return parse_cmp(p); } static Node *parse_cmp(Parser *p) { Node *left parse_add(p); while (p-cur.kind TOK_EQ || p-cur.kind TOK_LT || p-cur.kind TOK_GT) { TokKind op p-cur.kind; advance(p); Node *n new_node(NODE_BINOP); n-op op; n-left left; n-right parse_add(p); left n; } return left; }这里用了一个「保存-回退」技巧看到标识符先存下当前 token 和 lexer 状态往前看一个 token如果是就走赋值分支否则恢复状态走比较分支。这是递归下降里处理「需要预读」的常见手法代价是要保存Lexer结构体里面只有一个pos拷贝很便宜。if语句的解析放在顶层因为它返回的不是值而是控制流。常见做法是让parse_if解析if (cond) expr else expr把三个部分分别存进NODE_IF的cond/then_branch/else_branch。注意else是可选的解析完then_branch后要检查当前 token 是不是TOK_ELSE不是就留空。4. 求值器与变量表递归遍历 AST 的 80 行4.1 用数组当变量表够用且好调试变量存储最简单的方案是一个固定大小的数组每个元素是「名字 值」。查找用线性扫描500 行规模下变量不会超过几十个线性查找比哈希表省事得多而且调试时能直接打印整个表。typedef struct { char name[32]; long value; } Var; typedef struct { Var vars[128]; int count; } Env; static long *env_find(Env *env, const char *name) { for (int i 0; i env-count; i) if (strcmp(env-vars[i].name, name) 0) return env-vars[i].value; return NULL; } static long *env_define(Env *env, const char *name) { if (env-count 128) { fprintf(stderr, runtime error: too many variables\n); exit(1); } strncpy(env-vars[env-count].name, name, 31); env-vars[env-count].value 0; return env-vars[env-count].value; }env_find返回指针而不是值这样赋值时可以直接*ptr value读的时候*ptr取值。返回 NULL 表示变量未定义求值器遇到就报错。env_define在变量首次赋值时创建条目初始值设 0避免未初始化读。参数上vars[128]是硬上限超过就报错退出。如果你要支持更多变量把这个数字调大或者改成动态数组。name[32]和前面 token、AST 节点保持一致避免拷贝时长度不匹配。4.2 递归求值每个节点类型一个分支求值函数eval接收节点和环境返回long。它按kind分派数字直接返回变量查表二元运算递归求左右再算赋值先求右边再写回if 先求条件再选分支。static long eval(Node *n, Env *env) { switch (n-kind) { case NODE_NUM: return n-value; case NODE_VAR: { long *v env_find(env, n-name); if (!v) { fprintf(stderr, runtime error: undefined variable %s\n, n-name); exit(1); } return *v; } case NODE_BINOP: { long l eval(n-left, env); long r eval(n-right, env); switch (n-op) { case TOK_PLUS: return l r; case TOK_MINUS: return l - r; case TOK_STAR: return l * r; case TOK_SLASH: if (r 0) { fprintf(stderr, runtime error: division by zero\n); exit(1); } return l / r; case TOK_EQ: return l r; case TOK_LT: return l r; case TOK_GT: return l r; default: fprintf(stderr, bad op\n); exit(1); } } case NODE_ASSIGN: { long val eval(n-right, env); long *slot env_find(env, n-name); if (!slot) slot env_define(env, n-name); *slot val; return val; } case NODE_IF: { long c eval(n-cond, env); if (c) return n-then_branch ? eval(n-then_branch, env) : 0; else return n-else_branch ? eval(n-else_branch, env) : 0; } } return 0; }NODE_BINOP里先递归求左右子树这是后序遍历保证子表达式先算完。除零检查放在这里而不是解析阶段因为除数可能是变量只有运行时才知道值。比较运算返回 0 或 1正好能当if的条件用。NODE_ASSIGN先求右边再写左边顺序不能反否则x x 1会读到旧值。env_find找不到就env_define这样变量不需要提前声明用起来像脚本语言。NODE_IF里对then_branch和else_branch做了 NULL 检查因为else可能不存在。条件非零走 then否则走 else都没有就返回 0。4.3 主循环读一行、解析、求值、打印把上面所有部件串起来主函数就是一个 REPL读一行初始化 lexer 和 parser解析出 AST求值打印结果。int main(void) { char line[1024]; Env env; env.count 0; while (1) { printf( ); if (!fgets(line, sizeof(line), stdin)) break; Parser p; p.lx.src line; p.lx.pos 0; advance(p); Node *root parse_expr(p); if (p.cur.kind ! TOK_EOF) { fprintf(stderr, parse error: trailing input\n); continue; } long result eval(root, env); printf(%ld\n, result); } return 0; }fgets读一行sizeof(line)防止溢出。每次循环重建Parser但Env在循环外所以变量能跨行保留。解析完检查是不是到了TOK_EOF不是说明有多余输入报错但继续循环不退出。advance(p)在解析前先取第一个 token这是递归下降的惯例——p.cur始终是「当前待处理的 token」。如果你忘了这一步parse_expr会拿到未初始化的cur行为随机这是新手最容易翻车的地方之一。5. 避坑与排查500 行里最容易翻车的 5 个点5.1 现象输入1 2输出乱码或崩溃原因通常是Parser的cur没初始化就调用parse_expr。advance必须在解析前调用一次否则p.cur.kind是栈上的垃圾值switch走到未定义分支。解决在main里advance(p)紧跟Parser初始化或者在parse_expr开头加断言assert(p-cur.kind 0 p-cur.kind TOK_EOF)。后者能在调试阶段第一时间定位。5.2 现象8 / 4 / 2算出来是 4 而不是 1这是结合性写反了。如果parse_mul里写成n-left parse_atom(p); n-right left;再left n就变成右结合结果错误。解决循环里始终把已建好的left挂到新节点的左边新解析的右操作数挂右边。左结合的本质是「从左往右攒」每次新运算符都把之前的结果当左子树。5.3 现象变量赋值后读出来还是 0原因多半是env_find返回了值而不是指针赋值时改的是副本。或者env_define每次赋值都新建条目读的时候查到的是旧条目。解决env_find必须返回long *赋值走*slot val。env_define只在找不到时才调用找到就复用。调试时打印env.count和每个变量的名字值一眼能看出是不是重复定义。5.4 现象if (1) 2 else 3解析报错常见原因是parse_if里解析完then_branch后没检查TOK_ELSE就直接返回导致else被当成多余输入。或者else分支的解析没递归调用parse_expr只吃了一个原子。解决parse_if的结构应该是「吃if、吃(、解析条件、吃)、解析 then、如果当前是else就吃else再解析 else」。每一步都要检查 token 类型不匹配就报错并打印当前 token 的 kind方便定位。5.5 现象长表达式跑着跑着栈溢出递归下降的深度和表达式嵌套层数成正比。((((...))))嵌套几百层就会爆栈因为每层括号都会递归进parse_atom → parse_expr → parse_cmp → parse_add → parse_mul → parse_atom。解决微型解释器里可以限制嵌套深度比如在parse_atom里加一个全局计数器超过 256 就报错退出。或者把递归改成显式栈的迭代版本但那样代码量会翻倍500 行预算下不划算。实际使用中手写表达式很少超过几十层嵌套加个深度检查就够。6. 从 500 行往外扩加字符串、加循环、加函数调用跑通四则运算和 if 之后你手里已经有一个能用的骨架。往外扩最自然的方向是字符串类型因为很多场景需要打印文本。做法是在Token和Node里加TOK_STR和NODE_STR值用char *存求值时返回指针而不是long。这要求把eval的返回类型改成带标签的Value结构体工作量大概多 100 行但结构不变。加while循环更简单因为语法和if几乎一样只是求值时循环执行body直到条件为假。注意循环里要防止死循环可以在eval里加一个步数计数器超过一百万步就报错退出这是调试时的后悔药。加函数调用是最有挑战的一步需要引入作用域链和调用栈。常见做法是Env改成链表每个函数调用压一个新Env查找变量时从当前层往外找。这一步会让代码量突破 500 行但如果你前面四章都亲手敲过加函数只是时间问题。我自己的习惯是每加一个特性就先写三个测试用例一个正常输入、一个边界输入比如空表达式、除零、一个错误输入未定义变量。跑通了再往下走这样出问题能立刻定位到是哪次改动引入的。500 行的项目最怕的就是一口气加五个特性然后一起调试那时候你连哪行代码是新的都分不清。希望帮到你。本文还有配套的精品资源点击获取