简介这份资源聚焦编译技术中的LR(0)语法分析器实现面向正在学习编译原理、希望动手理解自底向上分析流程的高校学生与开发者。它通过一套可运行的C语言程序帮助读者把上下文无关文法、项集构建、状态机与状态转移表等抽象概念落到代码层面解决“看得懂理论却写不出分析器”的常见困境。压缩包共14个文件约224KB以cpp源码为核心辅以exe可执行文件、obj与pch等编译中间产物以及dsp、dsw等工程配置文件和pdb调试符号方便直接运行观察分析过程。目前已有841人学习下载。源码注释较为完整读者可输入C语言语句片段跟踪分析器如何依据状态转移表逐步匹配文法、判定语法正误并借此理解LR(0)在处理左递归与复杂结构时的局限为后续学习LR(1)、LALR(1)打下基础适合作为编译原理课程的实践参考。1. 从一段报错代码说起语法分析器到底在解决什么问题你写下一行int a 3 *p;编译器没吭声就过了你改成int a 3 * ;它立刻甩给你一个syntax error。这中间的差别就是语法分析器在干活。很多人学 C 语言时把「编译器」当成一个黑匣子直到自己动手写一个语法分析器才发现原来while和do-while的区别、scanf为什么一定要按格式读、指针声明为什么那么绕全都能在语法规则里找到答案。语法分析器parser做的事很具体把词法分析器吐出来的 token 序列按照一套文法规则组装成一棵抽象语法树AST或者在组装失败时告诉你哪一行、哪个 token 不符合规则。它上承词法分析下接语义分析和代码生成是编译原理里最能「看得见摸得着」的一环。这篇文章面向的是已经会写 C、想真正搞懂编译器前端的人也适合做课程设计、想拿一个能跑通的递归下降解析器当练手项目的同学。我会用一个支持变量声明、赋值、四则运算和括号的迷你语言做例子把词法接口、文法设计、递归下降实现、错误恢复、AST 遍历验证整条链路走一遍代码可以直接抄下来编译运行。2. 文法先行把 EBNF 写成能落地的规则2.1 为什么先写文法再写代码语法分析器的本质是「按规则匹配 token」。规则没定清楚就写代码最后一定是一堆if-else堆出来的玄学。常见做法是先写一份 EBNF扩展巴科斯范式把优先级和结合性显式表达出来再翻译成递归下降函数。递归下降的好处是每个非终结符对应一个函数代码结构和文法一一对应调试时看调用栈就知道卡在哪条规则上。代价是它只能处理 LL(1) 文法遇到左递归必须改写。下面这份文法覆盖了声明、赋值、加减乘除、括号和一元负号优先级从低到高排列program - statement* statement - declaration | assignment | expr_stmt declaration - int IDENT ( expr)? ; assignment - IDENT expr ; expr_stmt - expr ; expr - term (( | -) term)* term - factor ((* | /) factor)* factor - (- | )? primary primary - NUMBER | IDENT | ( expr )这份文法里expr和term的写法已经把左递归消掉了expr - term ((|-) term)*用循环代替了expr - expr term。这是递归下降能跑起来的前提。优先级体现在层级上——expr管加减term管乘除factor管一元符号primary管括号和原子。结合性靠循环实现1-2-3会先算1-2再减3符合左结合。把这份文法贴在显示器边上后面每个函数都能对上号。2.2 Token 定义与词法接口语法分析器不关心字符只关心 token。所以第一步是定义 token 类型和结构词法分析器负责把源码切成 token 数组。下面这份定义用枚举区分类型用联合体存值是 C 里比较常见的写法// token.h #ifndef TOKEN_H #define TOKEN_H typedef enum { TOK_EOF, TOK_INT, TOK_IDENT, TOK_NUMBER, TOK_PLUS, TOK_MINUS, TOK_STAR, TOK_SLASH, TOK_ASSIGN, TOK_LPAREN, TOK_RPAREN, TOK_SEMI, TOK_UNKNOWN } TokenType; typedef struct { TokenType type; union { long num; // TOK_NUMBER 时有效 char *name; // TOK_IDENT 时有效 } value; int line; // 出错时报行号 } Token; #endifunion让一个 token 结构同时能存数字和标识符省内存也省得写两套结构。line字段是后面错误提示的关键没有它你只能告诉用户「出错了」有了它才能说「第 3 行第 7 个 token 出错」。词法分析器对外只暴露一个函数比如Token *lex(const char *src, int *count)返回 token 数组和数量。语法分析器内部维护一个pos下标peek()看当前 tokenadvance()往后走一格。这个接口简单到可以先用假数据测试——手写一个 token 数组喂给 parser不用等词法器写完就能调语法逻辑这是分模块开发的好处。2.3 递归下降函数骨架每个非终结符一个函数函数返回 AST 节点指针。先看最底层的primary和factor// parser.c 片段 static ASTNode *parse_primary(Parser *p) { Token t peek(p); if (t.type TOK_NUMBER) { advance(p); return ast_new_num(t.value.num); } if (t.type TOK_IDENT) { advance(p); return ast_new_var(t.value.name); } if (t.type TOK_LPAREN) { advance(p); ASTNode *inner parse_expr(p); expect(p, TOK_RPAREN, expected )); return inner; } error_at(p, unexpected token in primary); return NULL; } static ASTNode *parse_factor(Parser *p) { Token t peek(p); if (t.type TOK_MINUS || t.type TOK_PLUS) { advance(p); ASTNode *operand parse_factor(p); // 递归处理 --x return ast_new_unary(t.type, operand); } return parse_primary(p); }parse_factor里对-的处理用了递归这样--x和-(-x)都能正确解析。expect是个辅助函数当前 token 类型不对就报错并跳过避免死循环。parse_term和parse_expr结构一样只是运算符集合不同static ASTNode *parse_term(Parser *p) { ASTNode *left parse_factor(p); while (peek(p).type TOK_STAR || peek(p).type TOK_SLASH) { Token op peek(p); advance(p); ASTNode *right parse_factor(p); left ast_new_binary(op.type, left, right); } return left; } static ASTNode *parse_expr(Parser *p) { ASTNode *left parse_term(p); while (peek(p).type TOK_PLUS || peek(p).type TOK_MINUS) { Token op peek(p); advance(p); ASTNode *right parse_term(p); left ast_new_binary(op.type, left, right); } return left; }while循环负责左结合left不断被新的二元节点替换最终形成左倾的树。参数上唯一要注意的是peek不能越界token 数组末尾必须有一个TOK_EOF哨兵否则while会读到数组外面去。这个骨架跑通之后加新运算符只需要在对应层级加一个case扩展成本很低。3. 语句层声明、赋值与符号表的衔接3.1 语句分派与前瞻语句层要区分「声明」「赋值」「表达式语句」三种情况。它们开头都是标识符或int所以需要前瞻一到两个 token。int开头一定是声明标识符开头看下一个 token 是不是是就是赋值否则当表达式语句。这种「看两个 token」的做法在递归下降里很常见代价是 parser 要能随机访问 token 数组不能只支持流式读取。分派函数长这样static ASTNode *parse_statement(Parser *p) { Token t peek(p); if (t.type TOK_INT) { return parse_declaration(p); } if (t.type TOK_IDENT peek_at(p, 1).type TOK_ASSIGN) { return parse_assignment(p); } ASTNode *e parse_expr(p); expect(p, TOK_SEMI, expected ; after expression); return ast_new_expr_stmt(e); }peek_at(p, 1)是看下一个 token实现上就是p-tokens[p-pos 1]前提是数组末尾有 EOF 兜底。这里有个容易翻车的点如果标识符后面跟的是(那可能是函数调用但这份迷你语言不支持函数所以直接当表达式处理报错信息会指向(而不是更友好的「不支持函数调用」。想做得细一点可以在parse_primary里检测IDENT后跟(时给出专门提示这是错误信息质量的优化不影响正确性。3.2 声明语句与变量登记声明语句解析完要顺手把变量登记到符号表否则后面赋值时不知道变量是否存在。符号表在这个阶段可以先用一个简单的链表或动态数组存变量名和声明行号static ASTNode *parse_declaration(Parser *p) { expect(p, TOK_INT, expected int); Token name peek(p); if (name.type ! TOK_IDENT) { error_at(p, expected identifier after int); return NULL; } advance(p); ASTNode *init NULL; if (peek(p).type TOK_ASSIGN) { advance(p); init parse_expr(p); } expect(p, TOK_SEMI, expected ; after declaration); symtab_add(p-sym, name.value.name, name.line); return ast_new_decl(name.value.name, init); }init允许为空对应int a;这种只声明不初始化的写法。symtab_add要处理重复声明——同一个作用域里int a; int a;应该报错。这份迷你语言没有块作用域符号表全局有效所以重复声明直接报错即可。如果后面要加{}块符号表就得改成栈式结构进块压栈、出块弹栈这是后话。参数上name.line存进去是为了后面「使用了未声明变量」时能提示「变量 a 在第 2 行声明第 5 行使用」调试体验会好很多。3.3 赋值语句与左值检查赋值语句左边必须是标识符右边是表达式。解析完要检查左边变量是否已声明static ASTNode *parse_assignment(Parser *p) { Token name peek(p); advance(p); // 吃掉 IDENT expect(p, TOK_ASSIGN, expected ); ASTNode *rhs parse_expr(p); expect(p, TOK_SEMI, expected ; after assignment); if (!symtab_find(p-sym, name.value.name)) { error_at(p, assignment to undeclared variable); } return ast_new_assign(name.value.name, rhs); }这里把「未声明变量」的检查放在语法分析阶段严格来说属于语义分析但递归下降里顺手做掉很常见能提前暴露问题。如果你想把职责分清楚也可以只建 AST等遍历 AST 时再查符号表。两种做法都行区别是报错时机——语法阶段报错能更早停AST 阶段报错能收集更多错误。我一般会在语法阶段做「明显错误」的检查比如未声明变量、重复声明把类型检查留给后面。4. 避坑与排查递归下降最容易翻车的 5 个地方4.1 左递归没消干净导致栈溢出现象解析123时程序卡死或栈溢出崩溃。原因文法里写了expr - expr term递归下降直接翻译成parse_expr里第一句就调parse_expr无限递归。解决把左递归改写成循环expr - term ((|-) term)*对应代码里先调parse_term再用while处理后续运算符。改完之后123会解析成((12)3)结合性也对了。4.2 忘记消费 token 导致死循环现象遇到语法错误后程序不退出一直转。原因expect报错后没有advancewhile循环里peek始终返回同一个错误 token。解决expect失败时要么advance跳过当前 token要么直接longjmp跳出整个解析。我一般用「报错 跳过到下一个分号或 EOF」的策略这样一次解析能报多个错误而不是遇到第一个就停。4.3 优先级写反导致12*3算成 9现象AST 遍历求值结果是 9 而不是 7。原因parse_expr里直接调了parse_factor跳过了parse_term乘除和加减同级了。解决严格按文法层级调用expr调termterm调factorfactor调primary一层都不能跳。验证方法是打印 AST看*是否比更深一层。4.4 一元负号和减法混淆现象3-2被解析成一元负号加3结果不对。原因parse_factor里看到-就当成一元运算符没区分它是二元减法的右操作数。解决一元符号只在factor开头位置处理也就是parse_term调parse_factor时如果当前 token 是-且它前面没有操作数才当一元。实现上parse_factor只在被parse_term或parse_expr调用时处理前导-二元-由parse_expr的while循环消费两者不会冲突。4.5 行号丢失导致报错定位不准现象报错只说「syntax error」不说是哪一行。原因token 里没存行号或者error_at只打印 token 类型。解决词法分析时每遇到\n就line存进 tokenerror_at打印line和 token 原文。这一步在项目初期就要做后期补很痛苦因为所有 token 构造点都要改。5. AST 遍历验证与错误恢复的进阶技巧写完 parser 只是第一步怎么确认它真的对比写它更花时间。我一般用两条路验证一条是打印 AST 的括号表示肉眼比对另一条是写一个求值器遍历 AST用已知结果的表达式做回归测试。括号表示实现很简单每个节点打印成(op left right)或(num 3)12*3应该输出( (num 1) (* (num 2) (num 3)))。这个格式一眼就能看出优先级对不对比调试器里翻结构体快得多。void ast_print(ASTNode *n) { if (!n) return; switch (n-kind) { case AST_NUM: printf((num %ld), n-num); break; case AST_VAR: printf((var %s), n-name); break; case AST_BINARY: printf((%s , op_name(n-op)); ast_print(n-left); printf( ); ast_print(n-right); printf()); break; case AST_UNARY: printf((%s , op_name(n-op)); ast_print(n-left); printf()); break; default: printf((?)); break; } }求值器就是后序遍历遇到数字返回遇到变量查符号表遇到二元节点递归求左右再算。用一组测试用例跑一遍比如int a 3; int b a * (2 1); b - 1;期望结果是 8。如果结果不对先看 AST 打印九成问题出在优先级或结合性上。错误恢复是另一个值得花时间的地方。最粗暴的做法是遇到错误直接exit(1)但这样用户改一个错要重新编译一次体验很差。好一点的做法是「恐慌模式恢复」报错后不断advance直到遇到;或}或 EOF然后从下一个语句继续解析。这样一次能报出多个错误。实现上给Parser加一个error_count超过阈值比如 10 个就停避免错误太多刷屏。报错信息里带上行号和期望的 token 类型比如line 3: expected ; but got 比单纯syntax error有用得多。最后一个技巧是关于扩展性的。这份迷你语言只有表达式和赋值想加if、while怎么办答案是加非终结符和对应函数文法里加statement - if ( expr ) statement代码里加parse_if在parse_statement的分派里加一个TOK_IF分支。因为递归下降的结构和文法一一对应扩展时改动是局部的不会牵一发动全身。我自己的习惯是每加一个语法特性先改 EBNF再改函数最后补测试用例三步走完再提交。这样即使过了半年回头看也能顺着文法把代码读懂。语法分析器这个项目写一遍只能算入门真正让你有感觉的是加第二个、第三个特性的时候——那时候你会发现编译原理课上那些「消除左递归」「提取公因子」不是考试题是每天都要用的手艺。希望帮到你。本文还有配套的精品资源点击获取