手写递归下降语法分析器：从词法分析到AST求值

简介这份资源是面向编译原理学习者与C语言进阶开发者的LR(0)语法分析器实现项目聚焦自底向上语法分析这一编译器设计核心环节帮助读者理解上下文无关文法、项集构造与状态转移表生成等关键概念。压缩包共14个文件约224KB以cpp源码、exe可执行程序、obj与pch编译中间文件、dsp与dsw工程文件及pdb调试信息为主源码注释较为完整可直接运行并输入C语言语句片段观察分析过程。目前已有841人学习下载。通过阅读与调试读者能够掌握从起始符号扩展产生规则、构建项集与状态机、依据前瞻符号完成状态转移的完整流程并理解LR(0)在处理左递归与复杂语法结构时的局限为后续学习LR(1)、LALR(1)等更强分析器打下基础适合作为编译技术课程实验与课程设计的实践参考。1. 从一段报错代码说起语法分析器到底在解决什么问题你写了个表达式求值器输入3 4 * 2能跑换成(3 4) * 2就崩了再换成3 * 4直接段错误。这不是你逻辑写错了是你跳过了语法分析这一步直接拿字符数组在那儿switch。语法分析器要干的事就一件把词法分析器吐出来的 token 序列按照你定义的文法规则组装成一棵抽象语法树AST让后续的求值、类型检查、代码生成有结构可依。没有这棵树你的程序就只能在字符层面打补丁补到最后自己都看不懂。这篇文章面向的是已经能用 C 语言写几百行代码、但一碰到“解析”就发怵的开发者。我会从零手写一个递归下降的语法分析器覆盖表达式、括号、一元负号、赋值语句和变量声明最后接一个求值器验证整条链路。不依赖任何第三方库只用stdio.h、stdlib.h、string.h、ctype.h这几个标准头。读完你能拿到一套可编译、可扩展的骨架知道每个函数为什么这么写以及在哪里加新语法不会把旧逻辑搞崩。2. 词法分析器把字符流切成 token 序列2.1 为什么语法分析必须先有词法分析很多人一上来就写parseExpression里面直接if (src[i] )结果遇到12 34这种多位数就傻眼遇到\t\n混排的空白就乱套。词法分析器的职责是把“字符”聚合成“有意义的最小单元”也就是 token。语法分析器只认 token不认字符。这样分层的好处是换语言关键字只需要改词法规则换语法结构只需要改语法规则两边互不污染。token 的类型我用枚举定义每个 token 携带类型、原始文本和数值如果是数字的话。这里有个容易翻车的地方数字的text和value必须同时保留因为后面报错时要打印原始输入而求值时要拿数值。// lexer.h #ifndef LEXER_H #define LEXER_H typedef enum { TOKEN_NUMBER, // 123 TOKEN_PLUS, // TOKEN_MINUS, // - TOKEN_STAR, // * TOKEN_SLASH, // / TOKEN_LPAREN, // ( TOKEN_RPAREN, // ) TOKEN_IDENT, // 变量名 TOKEN_ASSIGN, // TOKEN_SEMI, // ; TOKEN_EOF // 结束 } TokenType; typedef struct { TokenType type; char text[64]; // 原始文本用于报错 int value; // 数字值仅 TOKEN_NUMBER 有效 } Token; typedef struct { const char *src; int pos; Token current; } Lexer; void lexer_init(Lexer *lex, const char *src); void lexer_next(Lexer *lex); #endif2.2 手写词法扫描的核心循环扫描逻辑就是一个while循环加一个switch。跳过空白、识别数字、识别标识符、识别单字符运算符。数字识别要处理多位标识符识别要处理字母数字下划线组合。这里最容易踩的坑是lexer_next必须在每次调用时推进pos否则语法分析器会死循环。// lexer.c #include lexer.h #include ctype.h #include string.h #include stdlib.h void lexer_init(Lexer *lex, const char *src) { lex-src src; lex-pos 0; lexer_next(lex); // 预读第一个 token } void lexer_next(Lexer *lex) { const char *s lex-src; int *p lex-pos; // 跳过空白字符 while (s[*p] || s[*p] \t || s[*p] \n || s[*p] \r) { (*p); } Token *t lex-current; t-text[0] \0; t-value 0; char c s[*p]; if (c \0) { t-type TOKEN_EOF; return; } // 数字连续的数字字符 if (isdigit((unsigned char)c)) { int start *p; while (isdigit((unsigned char)s[*p])) (*p); int len *p - start; if (len 63) len 63; strncpy(t-text, s start, len); t-text[len] \0; t-type TOKEN_NUMBER; t-value atoi(t-text); return; } // 标识符字母或下划线开头 if (isalpha((unsigned char)c) || c _) { int start *p; while (isalnum((unsigned char)s[*p]) || s[*p] _) (*p); int len *p - start; if (len 63) len 63; strncpy(t-text, s start, len); t-text[len] \0; t-type TOKEN_IDENT; return; } // 单字符运算符 (*p); t-text[0] c; t-text[1] \0; switch (c) { case : t-type TOKEN_PLUS; break; case -: t-type TOKEN_MINUS; break; case *: t-type TOKEN_STAR; break; case /: t-type TOKEN_SLASH; break; case (: t-type TOKEN_LPAREN; break; case ): t-type TOKEN_RPAREN; break; case : t-type TOKEN_ASSIGN; break; case ;: t-type TOKEN_SEMI; break; default: // 遇到不认识的字符直接报错退出 fprintf(stderr, 词法错误未知字符 %c 在位置 %d\n, c, *p - 1); exit(1); } }lexer_init里预读第一个 token 是个关键设计。这样语法分析器在判断“当前是什么”时不需要反复调用lexer_next只需要在“消费掉当前 token”时调用一次。text字段固定 64 字节超过就截断这是为了简化内存管理实际项目中应该动态分配。atoi在这里够用但如果要支持浮点数就得换strtod。3. 递归下降语法分析用函数调用栈表达文法层级3.1 文法设计先写清楚再写代码递归下降的核心思想是每个非终结符对应一个函数函数体就是该非终结符的产生式。所以动手之前必须先把文法写出来。我用的文法如下优先级从低到高program → statement* statement → ident expr ; | expr ; expr → term (( | -) term)* term → factor ((* | /) factor)* factor → - factor | ( expr ) | number | ident这个文法里expr处理加减term处理乘除factor处理括号、一元负号和原子。优先级通过函数调用层次体现expr调用termterm调用factor越深的函数优先级越高。左结合通过while循环实现每次循环把左边的结果和右边的操作数合并。3.2 AST 节点定义与内存分配语法分析的输出是 AST。节点类型包括数字、变量、二元运算、一元负号、赋值、语句序列。每个节点用malloc分配程序结束前统一释放。这里有个血泪经验如果不在每个parse函数里检查malloc返回值一旦内存耗尽就是段错误连报错信息都看不到。// ast.h #ifndef AST_H #define AST_H typedef enum { AST_NUM, // 数字字面量 AST_VAR, // 变量引用 AST_BINOP, // 二元运算 AST_UNARY, // 一元负号 AST_ASSIGN, // 赋值 AST_SEQ // 语句序列 } ASTType; typedef struct ASTNode { ASTType type; union { int num; // AST_NUM char var[64]; // AST_VAR, AST_ASSIGN struct { // AST_BINOP char op; struct ASTNode *left; struct ASTNode *right; } binop; struct { // AST_UNARY struct ASTNode *operand; } unary; struct { // AST_ASSIGN struct ASTNode *value; } assign; struct { // AST_SEQ struct ASTNode *stmt; struct ASTNode *next; } seq; } data; } ASTNode; ASTNode *ast_new_num(int value); ASTNode *ast_new_var(const char *name); ASTNode *ast_new_binop(char op, ASTNode *left, ASTNode *right); ASTNode *ast_new_unary(ASTNode *operand); ASTNode *ast_new_assign(const char *name, ASTNode *value); ASTNode *ast_new_seq(ASTNode *stmt, ASTNode *next); void ast_free(ASTNode *node); #endif3.3 解析函数逐个落地解析器结构体持有词法分析器和错误计数。每个解析函数返回 AST 节点遇到语法错误时打印信息并返回NULL。expect辅助函数用于消费指定类型的 token不匹配就报错。// parser.c #include parser.h #include stdio.h #include stdlib.h #include string.h // 消费当前 token要求类型匹配 static void expect(Parser *p, TokenType type, const char *what) { if (p-lex.current.type ! type) { fprintf(stderr, 语法错误期望 %s但遇到 %s位置 %d\n, what, p-lex.current.text, p-lex.pos); p-errors; return; } lexer_next(p-lex); } // factor → - factor | ( expr ) | number | ident static ASTNode *parse_factor(Parser *p) { Token t p-lex.current; if (t.type TOKEN_MINUS) { lexer_next(p-lex); ASTNode *operand parse_factor(p); if (!operand) return NULL; return ast_new_unary(operand); } if (t.type TOKEN_LPAREN) { lexer_next(p-lex); ASTNode *inner parse_expr(p); expect(p, TOKEN_RPAREN, )); return inner; } if (t.type TOKEN_NUMBER) { lexer_next(p-lex); return ast_new_num(t.value); } if (t.type TOKEN_IDENT) { lexer_next(p-lex); return ast_new_var(t.text); } fprintf(stderr, 语法错误factor 位置遇到 %s\n, t.text); p-errors; return NULL; } // term → factor ((* | /) factor)* static ASTNode *parse_term(Parser *p) { ASTNode *left parse_factor(p); if (!left) return NULL; while (p-lex.current.type TOKEN_STAR || p-lex.current.type TOKEN_SLASH) { char op (p-lex.current.type TOKEN_STAR) ? * : /; lexer_next(p-lex); ASTNode *right parse_factor(p); if (!right) { ast_free(left); return NULL; } left ast_new_binop(op, left, right); } return left; } // expr → term (( | -) term)* static ASTNode *parse_expr(Parser *p) { ASTNode *left parse_term(p); if (!left) return NULL; while (p-lex.current.type TOKEN_PLUS || p-lex.current.type TOKEN_MINUS) { char op (p-lex.current.type TOKEN_PLUS) ? : -; lexer_next(p-lex); ASTNode *right parse_term(p); if (!right) { ast_free(left); return NULL; } left ast_new_binop(op, left, right); } return left; } // statement → ident expr ; | expr ; static ASTNode *parse_statement(Parser *p) { // 先看是不是赋值ident if (p-lex.current.type TOKEN_IDENT) { Token saved p-lex.current; int saved_pos p-lex.pos; lexer_next(p-lex); if (p-lex.current.type TOKEN_ASSIGN) { lexer_next(p-lex); ASTNode *value parse_expr(p); expect(p, TOKEN_SEMI, ;); return ast_new_assign(saved.text, value); } // 不是赋值回退 p-lex.current saved; p-lex.pos saved_pos; } ASTNode *expr parse_expr(p); expect(p, TOKEN_SEMI, ;); return expr; } // program → statement* ASTNode *parse_program(Parser *p) { ASTNode *head NULL, *tail NULL; while (p-lex.current.type ! TOKEN_EOF) { ASTNode *stmt parse_statement(p); if (!stmt) break; ASTNode *node ast_new_seq(stmt, NULL); if (!head) { head node; tail node; } else { tail-data.seq.next node; tail node; } } return head; }parse_statement里的回退逻辑是重点。因为ident既可能是赋值语句的开头也可能是一个表达式变量引用所以必须先预读一个 token 判断。回退时同时恢复current和pos缺一不可。parse_program用尾指针维护链表避免每次插入都遍历到末尾这是 O(n) 和 O(n²) 的区别。4. 避坑与排查语法分析器最容易翻车的五个地方4.1 左递归导致栈溢出现象parse_expr第一行就调用自己程序刚启动就栈溢出。原因文法写成expr → expr term递归下降无法处理左递归。解决改写成expr → term (( | -) term)*用循环替代递归。这是递归下降的硬性约束不是风格问题。4.2 运算符优先级搞反现象3 4 * 2算出来是 14 而不是 11。原因parse_expr里直接调用了parse_factor跳过了parse_term导致加减和乘除在同一层。解决严格按expr → term → factor的层次调用优先级低的函数在调用链上层。4.3 忘记消费 token 导致死循环现象程序卡在while循环里不退出CPU 跑满。原因某个parse函数在匹配成功后没有调用lexer_next当前 token 永远不变。解决在每个expect和手动匹配分支里确保调用lexer_next可以用gdb打断点看lex.current.type是否在变化。4.4 括号不匹配时返回 NULL 但没释放已分配节点现象输入(3 4时程序报错退出但valgrind显示内存泄漏。原因parse_factor里parse_expr返回了节点但expect失败后直接返回没有释放inner。解决在expect失败的分支里先ast_free(inner)再返回NULL或者用统一的错误清理路径。4.5 变量表未初始化导致求值结果随机现象同一个表达式x 1第一次跑输出 1第二次跑输出 32767。原因变量表数组没清零x的初始值是栈上的垃圾数据。解决变量表用calloc分配或者在eval里遇到未定义变量时显式报错而不是返回默认值。5. 接上求值器从 AST 到可运行程序5.1 环境表与递归求值求值器就是一个后序遍历 AST 的函数。变量存在一个简单的线性表里查找是 O(n)但对于几十个变量的场景完全够用。如果要支持作用域把线性表换成栈式结构即可。// eval.c #include eval.h #include stdio.h #include string.h #define MAX_VARS 128 typedef struct { char name[64]; int value; } VarEntry; static VarEntry vars[MAX_VARS]; static int var_count 0; static int lookup_var(const char *name) { for (int i 0; i var_count; i) { if (strcmp(vars[i].name, name) 0) return vars[i].value; } fprintf(stderr, 运行时错误未定义变量 %s\n, name); return 0; } static void assign_var(const char *name, int value) { for (int i 0; i var_count; i) { if (strcmp(vars[i].name, name) 0) { vars[i].value value; return; } } if (var_count MAX_VARS) { fprintf(stderr, 运行时错误变量表已满\n); return; } strncpy(vars[var_count].name, name, 63); vars[var_count].name[63] \0; vars[var_count].value value; var_count; } int eval(ASTNode *node) { if (!node) return 0; switch (node-type) { case AST_NUM: return node-data.num; case AST_VAR: return lookup_var(node-data.var); case AST_BINOP: { int left eval(node-data.binop.left); int right eval(node-data.binop.right); switch (node-data.binop.op) { case : return left right; case -: return left - right; case *: return left * right; case /: if (right 0) { fprintf(stderr, 运行时错误除以零\n); return 0; } return left / right; } return 0; } case AST_UNARY: return -eval(node-data.unary.operand); case AST_ASSIGN: { int value eval(node-data.assign.value); assign_var(node-data.var, value); return value; } case AST_SEQ: { ASTNode *cur node; int last 0; while (cur) { last eval(cur-data.seq.stmt); cur cur-data.seq.next; } return last; } } return 0; }5.2 主程序与完整测试主程序读入一行输入初始化词法分析器和解析器调用parse_program得到 AST然后逐条语句求值并打印结果。这里用fgets而不是scanf因为scanf遇到空格就停没法处理带空格的表达式。// main.c #include lexer.h #include parser.h #include eval.h #include stdio.h #include string.h int main(void) { char line[1024]; printf(简易语法分析器输入表达式CtrlD 退出\n); while (fgets(line, sizeof(line), stdin)) { // 去掉末尾换行 size_t len strlen(line); if (len 0 line[len-1] \n) line[len-1] \0; if (strlen(line) 0) continue; Parser parser; parser.lex.src line; parser.lex.pos 0; parser.errors 0; lexer_next(parser.lex); ASTNode *ast parse_program(parser); if (ast parser.errors 0) { int result eval(ast); printf( %d\n, result); } ast_free(ast); } return 0; }编译命令gcc -Wall -Wextra -g -o calc lexer.c parser.c ast.c eval.c main.c。测试用例x 3 4 * 2;输出 11(3 4) * 2;输出 14-3 5;输出 2x 1;输出 12如果前面赋过x 11。如果输出不对先用gdb在parse_expr入口打断点看lex.current.type和lex.pos是否符合预期。6. 扩展技巧用优先级表替代硬编码函数层次递归下降写死了优先级层次加一个新运算符就要改三个函数。更灵活的做法是维护一张优先级表用 Pratt 解析器也叫优先级爬升统一处理。核心思路是每个 token 有一个左绑定力left binding powerparse_expr(min_bp)在循环里只处理绑定力大于min_bp的运算符。// 优先级表数值越大绑定越紧 static int left_bp(TokenType t) { switch (t) { case TOKEN_PLUS: return 10; case TOKEN_MINUS: return 10; case TOKEN_STAR: return 20; case TOKEN_SLASH: return 20; default: return 0; } } ASTNode *parse_expr_bp(Parser *p, int min_bp) { ASTNode *left parse_factor(p); if (!left) return NULL; while (1) { int bp left_bp(p-lex.current.type); if (bp 0 || bp min_bp) break; char op p-lex.current.text[0]; lexer_next(p-lex); ASTNode *right parse_expr_bp(p, bp); // 右结合用 bp-1 if (!right) { ast_free(left); return NULL; } left ast_new_binop(op, left, right); } return left; }这样加一个%运算符只需要在left_bp里加一行不用动任何解析函数。右结合运算符比如幂运算^把递归调用改成parse_expr_bp(p, bp - 1)即可。我自己的习惯是表达式不超过五种运算符就用递归下降硬编码超过五种就上 Pratt否则函数层次会深到调试时找不到北。这套骨架我用了三年从计算器到配置文件解析器都是在这个基础上改的希望帮到你。本文还有配套的精品资源点击获取