排查)
简介这份面向编译原理学习者与课程实验需求的C语言LR(0)语法分析器工程围绕自底向上语法分析的核心环节展开涉及上下文无关文法表示、项集构造、状态机建立、状态转移表生成以及输入串的接受与报错判定适合用于编译技术课程实验、课程设计或自学实践。压缩包共14个文件、约224KB包含cpp源代码、dsp与dsw工程配置、exe可执行程序以及obj、pch、pdb等编译中间文件和调试信息较完整地保留了早期VC开发环境下的项目组织方式便于对照源码、工程配置与运行结果理解分析器结构。目前已有841人学习说明其在相关学习场景中具有一定参考价值。读者可从注释较完整的源码中梳理LR(0)分析流程并借助可执行程序输入语句片段观察状态转移、归约与语法判定结果进而体会LR(0)在处理左递归和复杂语法结构时的局限为继续学习LR(1)、LALR(1)等增强方法打下基础。1. 词法过了语法卡住C语言语法分析器到底在解决什么词法分析把a 1 2 * 3;切成ID ASSIGN INT PLUS INT STAR INT SEMI之后真正决定*先于计算、if后面必须跟括号、赋值语句必须以分号收尾的是 C语言写的语法分析器。它不负责识别字符而是拿着 token 流对照文法判断结构是否合法并顺手构造 AST 或直接求值。写解释器、配置 DSL、编译器前端的人都会碰到它用 C 实现的好处是游标、内存和递归调用全在手里出问题能定位到具体函数而不是面对一个黑匣子。下面按“先定文法、再写递归下降、最后排查”的顺序把一套能跑的最小方案拆开。2. 文法与接口把 EBNF 变成 C 语言能执行的约束2.1 用 EBNF 把目标语言切成 token 与产生式手写解析器最怕一上来就写函数。我一般先把目标语言压到一个足够小的子集整数、变量、赋值、if/else、while、块语句、四则运算和括号。文法写成 EBNF*表示零次或多次?表示可选program - stmt* EOF stmt - ID expr ; | if ( expr ) stmt (else stmt)? | while ( expr ) stmt | { stmt* } expr - term (( | -) term)* term - factor ((* | /) factor)* factor - INT | ID | ( expr )这份文法已经消除了直接左递归适合递归下降。每个非终结符对应一个 C 函数函数体就是产生式右部的展开。真正的约束在 token 层关键字不能和标识符混在一起和要分开换行要记录行号。先把 token 类型定死后面解析函数才有稳定的比较对象。非终结符First 集Follow 集programID, if, while, {, EOFEOFstmtID, if, while, {ID, if, while, {, }, EOF, elseexprINT, ID, (), ;, {, EOF, elsetermINT, ID, (, -, ), ;, {, EOF, elsefactorINT, ID, (*, /, , -, ), ;, {, EOF, else这张表不是摆设。stmt的候选分支首符集互不相交if分支和ID分支不会打架else出现在 Follow 集里说明if语句结束后可以安全地看下一个 token 是不是else。如果两个候选分支的 First 集有交集递归下降就得靠回溯或提取左公因子复杂度立刻上去。token 结构体不需要花哨但字段要够用typedef enum { TOK_EOF, TOK_ID, TOK_INT, TOK_ASSIGN, TOK_PLUS, TOK_MINUS, TOK_STAR, TOK_SLASH, TOK_LPAREN, TOK_RPAREN, TOK_LBRACE, TOK_RBRACE, TOK_SEMI, TOK_IF, TOK_ELSE, TOK_WHILE, TOK_ERROR } TokenKind; typedef struct { TokenKind kind; const char *lexeme; /* 指向词法器内部缓冲生命周期要小心 */ int line; int col; long value; /* 仅 TOK_INT 有效 */ } Token; typedef struct Lexer Lexer; Token lexer_next(Lexer *lx);line和col是后面报错定位的命根子词法器在跳过空白和注释时必须同步更新。value只对整数字面量有意义别在别的 token 上读它。lexeme如果指向词法器的临时缓冲区解析器就不能长期保存这个指针要么在 token 构造时拷进 arena要么保证词法器缓冲在整次解析期间不被覆盖。这个坑在后面第 5 章还会展开。2.2 消除左递归与提取左公因子手写解析器的前置手术递归下降不能直接吃左递归。产生式expr - expr term | term写成 C 函数就是AstNode *parse_expr(Parser *p) { AstNode *left parse_expr(p); /* 一进来就递归token 一个没消费 */ /* ... */ }调用会原地打转直到栈溢出。标准变换是把左递归改成右递归加循环A - A α | β 等价于 A - β A A - α A | ε落到表达式就是expr - term expr_rest expr_rest - ( | -) term expr_rest | ε手写时更常见的做法是不生成expr_rest函数直接在parse_expr里用while循环消费运算符。这样既消除了左递归又自然得到左结合。提取左公因子也是同理stmt - ID expr ; | ID ( args ) ;这种前缀相同的分支先读一个ID再根据下一个 token 决定走赋值还是调用。递归下降的预测能力来自“看 enough token 再决定”不是来自回溯。做这一步时最好把改后的文法重新算一遍 First/Follow。比如stmt的if分支里else是可选的else不会出现在stmt的 First 集里但会出现在 Follow 集里。手写代码里对应的是AstNode *then_branch parse_stmt(p); AstNode *else_branch NULL; if (match(p, TOK_ELSE)) { else_branch parse_stmt(p); }match只在前瞻 token 是TOK_ELSE时消费否则原样返回。这个“可选”判断依赖的就是 Follow 集当前 token 不在else上说明if语句到此结束。别小看这一点很多“解析完 if 后莫名报错”都是因为把可选分支写成了强制expect。2.3 词法与语法接口Token 结构体和预读缓冲解析器不需要自己扫描字符但需要稳定的“当前 token”和“往前看一个”的能力。我一般给 Parser 结构体只放词法器指针和当前 token不搞多层 lookahead因为这份文法 LL(1) 足够typedef struct { Lexer *lx; Token cur; int had_error; } Parser; static void advance(Parser *p) { p-cur lexer_next(p-lx); } static int check(Parser *p, TokenKind k) { return p-cur.kind k; } static int match(Parser *p, TokenKind k) { if (check(p, k)) { advance(p); return 1; } return 0; }advance是唯一移动游标的地方所有消费都必须经过它。check只看不消费match条件消费。把这三个函数收拢在一个文件里后面排查“为什么报错位置总在下一个 token”时只需要盯住advance的调用点。参数上Parser里的had_error用于错误恢复后继续解析不要一报错就exit否则测试用例只能看到第一个错误。词法器返回TOK_EOF后继续调用lexer_next应该稳定返回TOK_EOF而不是越界读缓冲区。这个约定要写进词法器的实现里文件尾指针不动每次返回同一个 EOF token。解析器的很多循环用while (!check(p, TOK_EOF))收尾EOF 不稳定就会变成死循环或随机崩溃。3. 递归下降落地一个非终结符一个 C 函数3.1 解析器骨架与游标管理match/expect/peek 三件套骨架先把错误处理定下来。expect在期望 token 没出现时记录位置并返回一个占位 token解析继续往下走由调用方决定是否同步到分号或右花括号static Token expect(Parser *p, TokenKind k, const char *what) { if (check(p, k)) { Token t p-cur; advance(p); return t; } fprintf(stderr, line %d:%d: expected %s, got token %d\n, p-cur.line, p-cur.col, what, p-cur.kind); p-had_error 1; Token bad p-cur; bad.kind TOK_ERROR; return bad; }expect不消费错误 token 是故意的。当前 token 不是期望值时消费它可能把后面的同步点一起吃掉保留在原地让上层parse_stmt或parse_block决定跳到;还是}。what参数是给错误信息用的自然语言描述比如;不要传semicolon这种和词法 token 对不上的词。parse_program的骨架很短AstNode *parse_program(Parser *p) { advance(p); /* 装入第一个 token */ AstNode *block ast_block(); while (!check(p, TOK_EOF) !p-had_error) { AstNode *s parse_stmt(p); if (s) ast_block_append(block, s); else break; } return block; }这里advance在进入循环前调用一次把cur从零值变成第一个真实 token。如果词法器在构造时已经预读这一步就要改成对应的初始化函数。关键是全程序只有一处“第一次装 token”避免某个分支里cur还是空的就开始check。3.2 语句解析block、if、while、assign 的落点语句解析是递归下降里最容易写乱的部分因为分支多、嵌套深。我一般按 First 集顺序写if链每个分支入口先match关键字匹配成功再expect后续符号static AstNode *parse_stmt(Parser *p) { if (match(p, TOK_LBRACE)) { AstNode *b ast_block(); while (!check(p, TOK_RBRACE) !check(p, TOK_EOF)) { AstNode *s parse_stmt(p); if (!s) break; ast_block_append(b, s); } expect(p, TOK_RBRACE, }); return b; } if (match(p, TOK_IF)) { expect(p, TOK_LPAREN, (); AstNode *cond parse_expr(p); expect(p, TOK_RPAREN, )); AstNode *then_s parse_stmt(p); AstNode *else_s NULL; if (match(p, TOK_ELSE)) { else_s parse_stmt(p); } return ast_if(cond, then_s, else_s); } if (match(p, TOK_WHILE)) { expect(p, TOK_LPAREN, (); AstNode *cond parse_expr(p); expect(p, TOK_RPAREN, )); AstNode *body parse_stmt(p); return ast_while(cond, body); } if (check(p, TOK_ID)) { Token name expect(p, TOK_ID, identifier); expect(p, TOK_ASSIGN, ); AstNode *value parse_expr(p); expect(p, TOK_SEMI, ;); return ast_assign(name.lexeme, value); } fprintf(stderr, line %d:%d: unexpected token in statement\n, p-cur.line, p-cur.col); p-had_error 1; return NULL; }match(TOK_LBRACE)已经把左花括号消费掉所以块内循环直接从下一条语句开始。while循环的退出条件是TOK_RBRACE或 EOF前者由expect消费后者用于防止文件提前结束导致死循环。if的else采用“就近匹配”then_s递归解析完一个语句后如果当前 token 是else就归当前if。这和 C 语言的 dangling else 规则一致不需要额外维护栈。注意parse_stmt在遇到ID时先读名字再expect 如果实际是函数调用或多变量声明这里会报错这份文法只支持赋值报错是预期行为不要为了“兼容”偷偷加分支把文法搞乱。块语句返回AST_BLOCK内部用动态数组挂子节点。空块{}也合法循环一次都不进直接expect }。如果块里某条语句返回NULL说明已经报错直接 break避免在错误状态上继续构造半截 AST。3.3 表达式解析优先级爬升还是分层递归表达式用分层递归最直观parse_expr处理加减parse_term处理乘除parse_factor处理原子和括号。每层用while循环消费同层运算符天然左结合static AstNode *parse_expr(Parser *p) { AstNode *node parse_term(p); while (check(p, TOK_PLUS) || check(p, TOK_MINUS)) { Token op p-cur; advance(p); AstNode *rhs parse_term(p); node ast_binary(op.kind, node, rhs); } return node; } static AstNode *parse_term(Parser *p) { AstNode *node parse_factor(p); while (check(p, TOK_STAR) || check(p, TOK_SLASH)) { Token op p-cur; advance(p); AstNode *rhs parse_factor(p); node ast_binary(op.kind, node, rhs); } return node; } static AstNode *parse_factor(Parser *p) { if (check(p, TOK_INT)) { Token t p-cur; advance(p); return ast_int(t.value, t.line); } if (check(p, TOK_ID)) { Token t p-cur; advance(p); return ast_var(t.lexeme, t.line); } if (match(p, TOK_LPAREN)) { AstNode *inner parse_expr(p); expect(p, TOK_RPAREN, )); return inner; } fprintf(stderr, line %d:%d: expected expression\n, p-cur.line, p-cur.col); p-had_error 1; return ast_int(0, p-cur.line); /* 占位避免上层解引用 NULL */ }parse_expr里node ast_binary(op.kind, node, rhs)的旧 node 作为左子树新 rhs 作为右子树所以1 - 2 - 3会变成(1 - 2) - 3。如果写成递归parse_expr - parse_expr - term不仅左递归结合性也会变成右结合减法结果直接翻车。parse_factor在错误时返回一个占位整数节点而不是NULL是为了让上层继续构造 AST最后由had_error统一决定退出码。这个占位节点不会被求值但能避免“错误恢复时到处判空”的连锁崩溃。运算符更多时分层递归的函数会变多可以换成优先级爬升一张{token, 优先级, 结合性}表加一个循环。对这份只有四则运算的文法分层递归更好读函数名直接对应文法非终结符调试时栈帧也清楚。方案适合场景代价分层递归运算符少、优先级固定每加一层多一个函数优先级爬升运算符多、需要表驱动循环边界和结合性要写对预测分析表文法稳定、想自动生成需要 First/Follow 和表生成器4. AST 与表达式让语法分析器输出可遍历的结构4.1 AST 节点设计与构造/释放语法分析器不能只判断对错还要把结构留给后面的求值或代码生成。AST 节点用 tagged union节点种类枚举和文法非终结符对应但不要一个产生式一个节点类型按语义合并typedef enum { AST_INT, AST_VAR, AST_BIN, AST_ASSIGN, AST_IF, AST_WHILE, AST_BLOCK } AstKind; typedef struct AstNode AstNode; struct AstNode { AstKind kind; int line; union { long ival; struct { const char *name; } var; struct { TokenKind op; AstNode *lhs, *rhs; } bin; struct { const char *name; AstNode *value; } assign; struct { AstNode *cond, *then_s, *else_s; } if_s; struct { AstNode *cond, *body; } while_s; struct { AstNode **items; int count, cap; } block; } u; };line每个节点都带后面报“变量未定义”时能指回源码行。name是const char *必须指向稳定内存不能直接存词法器里的临时指针。内存管理我一般用 arena解析过程中所有节点和字符串都从 arena 分配解析结束一次性释放。错误恢复时不会出现“一半节点已 malloc、一半没释放”的烂摊子typedef struct ArenaBlock { struct ArenaBlock *next; size_t used; size_t cap; unsigned char data[]; } ArenaBlock; typedef struct { ArenaBlock *head; } Arena; void *arena_alloc(Arena *a, size_t n) { const size_t align 8; n (n align - 1) ~(align - 1); if (!a-head || a-head-used n a-head-cap) { size_t cap n 4096 ? n : 4096; ArenaBlock *b malloc(sizeof(ArenaBlock) cap); if (!b) { perror(arena); exit(1); } b-next a-head; b-used 0; b-cap cap; a-head b; } void *p a-head-data a-head-used; a-head-used n; return p; }align取 8 是为了让long、指针和double都不越界cap小于 4096 时统一给 4096减少小块分配次数。arena_alloc返回的内存不对齐到 16 字节如果后面要放 SIMD 类型再调大。字符串拷贝用arena_strdup内部先strlen再arena_alloc最后memcpy保证 AST 里的变量名不依赖词法器缓冲。4.2 用访问者/递归打印验证 ASTAST 建完先别急着求值打印成 S-表达式最方便回归测试。递归函数按节点种类分派static void ast_print_indent(const AstNode *n, int depth) { if (!n) return; for (int i 0; i depth; i) putchar( ); switch (n-kind) { case AST_INT: printf((int %ld)\n, n-u.ival); break; case AST_VAR: printf((var %s)\n, n-u.var.name); break; case AST_BIN: printf((bin %d\n, n-u.bin.op); ast_print_indent(n-u.bin.lhs, depth 2); ast_print_indent(n-u.bin.rhs, depth 2); printf()\n); break; case AST_ASSIGN: printf((assign %s\n, n-u.assign.name); ast_print_indent(n-u.assign.value, depth 2); printf()\n); break; case AST_IF: printf((if\n); ast_print_indent(n-u.if_s.cond, depth 2); ast_print_indent(n-u.if_s.then_s, depth 2); ast_print_indent(n-u.if_s.else_s, depth 2); printf()\n); break; case AST_WHILE: printf((while\n); ast_print_indent(n-u.while_s.cond, depth 2); ast_print_indent(n-u.while_s.body, depth 2); printf()\n); break; case AST_BLOCK: printf((block\n); for (int i 0; i n-u.block.count; i) ast_print_indent(n-u.block.items[i], depth 2); printf()\n); break; } }打印时缩进两格嵌套结构一眼能看出。AST_BIN直接打印op的枚举值在调试期够用正式测试可以换成, -的字符串表。这个函数不修改 AST参数const AstNode *后面加语义检查时可以直接复用。4.3 用测试用例锁住文法从 token 流到期望 AST 文本解析器最容易在改文法时悄悄回归。准备一组输入和期望输出用脚本跑#!/usr/bin/env bash # 每行: 输入文件|期望的 S-表达式前缀 set -u fail0 while IFS| read -r src expect; do got$(printf %s\n $src | ./parser 2/dev/null) if ! printf %s $got | grep -qF $expect; then echo FAIL: $src echo expect: $expect echo got: $got fail1 fi done CASES a 1 2 * 3;|(assign a (bin 5 (int 1) (bin 6 (int 2) (int 3)))) if (a) b 1; else b 2;|(if (var a) (assign b (int 1)) (assign b (int 2))) while (a) { b b - 1; }|(while (var a) (block (assign b (bin 4 (var b) (int 1))))) CASES exit $failgrep -qF做子串匹配避免 S-表达式的空白差异导致假失败真正严格时可以换成 Python 脚本做结构化比较。set -u防止变量拼写错误静默通过。退出码0表示全过1表示至少一条失败CI 里直接可用。测试用例要覆盖空输入、缺分号、多余 token、嵌套if、负数如果文法没一元负号负数应该报错而不是被当成0 - 1。每个用例都对应一个文法分支改文法时先跑这组比肉眼盯代码可靠。5. 语法分析器排查五类翻车现场与定位手法5.1 一改文法就栈溢出左递归没有消除现象输入12程序没有输出调试器里parse_expr重复出现几百层最后段错误。原因产生式写成了expr - expr term | termC 函数第一行就递归调用自己token 游标没有前进。解决把直接左递归改成循环或右递归。手写解析器优先用循环AstNode *node parse_term(p); while (check(p, TOK_PLUS)) { advance(p); node ast_binary(TOK_PLUS, node, parse_term(p)); }改完在parse_expr入口加一个断言每次进入函数后必须至少消费一个 token 或直接返回否则打印当前 token 并 abort。这个断言在开发期能第一时间抓住间接左递归。5.2 减法算反结合性写成了右结合现象1 - 2 - 3求值得到2期望-4打印 AST 发现是1 - (2 - 3)。原因parse_expr写成了递归调用自身AstNode *rhs parse_expr(p); /* 错误右结合且左递归 */解决同层运算符用while循环左操作数累积到node右操作数只调用下一层parse_term。改完用 AST 打印确认形状是((1-2)-3)。除法和减法都要求左结合乘除同样处理。5.3 报错位置总在下一个 token游标提前消费现象输入a 1缺分号报错说“expected ;, got EOF”行号却是第 2 行或者报错指向后面的 token。原因expect之前调用了advance或者match在失败时也消费了 token。另一种常见情况是词法器在换行时先line再返回上一行的 token导致位置整体偏移。解决把所有消费收拢到advancematch失败不移动游标expect报错使用p-cur的位置而不是lexer_next预读的位置。词法器里line和col在读到\n时更新token 的位置取起始字符的位置不要取结束位置。5.4 空产生式导致死循环可选分支没有前进现象解析if (a) ;或空块时卡死CPU 占满。原因某个可选分支匹配了零个 token 就返回外层while又用同一个 token 继续循环。比如parse_stmt在无法识别时返回NULL但调用方没有 break。解决每个解析函数要么消费 token要么明确返回“没有进展”。块循环里加保护int before p-cur.kind; AstNode *s parse_stmt(p); if (!s || p-cur.kind before) break;更根本的做法是检查文法里所有ε产生式只有当前 token 在 Follow 集里才允许走空分支否则报错并同步到;或}。5.5 AST 里的变量名变成乱码存了词法器临时指针现象解析多个赋值后打印 AST 发现前面的变量名被后面的覆盖或者释放词法器后访问崩溃。原因Token.lexeme指向词法器内部复用的缓冲区ast_assign(name.lexeme, ...)直接保存了指针。词法器读到下一个标识符时覆盖了同一块内存。解决在构造 AST 时把名字拷进 arenachar *arena_strdup(Arena *a, const char *s) { size_t n strlen(s) 1; char *p arena_alloc(a, n); memcpy(p, s, n); return p; }所有长期保存的字符串都走这个函数。释放时只释放 arena 的块不逐个free节点。开发期开 AddressSanitizer 跑测试用例悬垂指针和越界读会直接报出来。6. 用 LL(1) 预测表交叉验证手写解析器手写递归下降写完后我习惯再用 First/Follow 生成一张 LL(1) 预测表不是为了替换代码而是做交叉检查。表里每个[非终结符, token]单元格最多只能有一个产生式如果出现两个说明文法有冲突手写代码里的if顺序只是把冲突藏起来了。以stmt为例表片段大致是非终结符IDifwhile{}EOFstmtID expr ;if ...while ...{ stmt* }报错报错exprterm expr_rest报错报错报错εεexpr在)、;、}、EOF 上走空产生式这正好对应parse_expr里while循环不进入、直接返回term的行为。如果表里expr在)上有两个候选手写代码就会在某个嵌套表达式里提前消费右括号表现为“括号不匹配”的假报错。同步集也用 Follow 集来做错误恢复parse_stmt报错后一直advance到;、}或 EOF再返回上层。这样一次输入能报出多个错误而不是第一个错误就停。参数上同步集不要包含ID和if否则会把下一条合法语句一起吃掉。这套方案值不值得做取决于你要不要长期维护文法。如果只是解析一个固定配置文件手写两百行递归下降足够如果文法会频繁加语句、加运算符先把 First/Follow 表和测试用例建起来再改解析函数返工次数会少很多。我自己的习惯是每加一条产生式先补一个期望 AST 文本的用例再动 C 代码跑不过就先看 token 流不要一上来就怀疑递归函数。希望帮到你。本文还有配套的精品资源点击获取
