手写C-词法与语法分析器：打通编译原理任督二脉

简介本资源是面向高校计算机专业本科生及编译原理初学者的课程设计实践项目聚焦C-语言C语言简化子集的词法与语法分析器自主实现帮助学习者深入理解编译前端核心机制。压缩包共22个文件含7个txt含词法/语法分析结果、测试用例及语法规则定义、5个cpp与5个h核心分析器源码模块如LexicalAnalyzer.cpp、SyntaxParser.cpp、CharScanner.cpp及配套头文件、4个jsonVS Code开发环境配置和1个README.md说明文档整体仅25KB轻量易读、结构清晰便于逐模块调试与扩展。已有125人学习下载适合课堂实践、课程设计参考或编译原理实验复现。读者可直接运行分析器处理test1.txt/test2.txt等测试用例观察LexicalAnalyzer-Result.txt与SyntaxParser-Result.txt输出对比理解Token流生成与AST构建过程同时通过修改cminus.txt语法规则或源码添加新关键字掌握从规则定义到解析器实现的完整闭环。1. 为什么手写一个 C- 语言的词法语法分析器比直接跑 yacc/bison 示例更能打通编译原理的任督二脉这不是一个“交作业就完事”的课程设计压缩包——它是一套可调试、可打断点、可逐字符追踪、可改规则立刻验证的微型编译前端实战沙盒。C- 语言注意是带短横线的 C-不是 C 减是《编译原理》教材中经典的教学子集保留了 C 的核心骨架变量声明、if/while、算术表达式、函数调用但砍掉了指针、结构体、预处理等干扰项专为教学设计。你打开lexer.c和parser.y看到的不是黑匣子生成的千行代码而是你自己能一行行读懂、能加printf打印 token 流、能在yyparse()里插断点看归约栈变化的活体分析器。很多同学卡在“知道 LL(1) 表怎么填但不知道 parser 真正执行时怎么查表”或者“能背出 DFA 状态转换图却不会把图转成 switch-case”。这个项目逼你把纸面理论焊进内存地址——比如int x 3 y * 2;这行输入你会亲眼看见 lexer 如何把int切成 KEYWORD 类型、x切成 ID、切成 ASSIGN_OP再看着 parser 用递归下降或 LALR(1) 规则一步步把3 y * 2归约为Expr节点。它不追求工业级健壮性但每行代码都对应课本第二章词法分析和第四章语法分析的定义。如果你正在啃清华大学出版社第三版教材、刚做完山东科技大学或燕山大学的编译原理实验、甚至对着“第三版第二章答案”反复核对却仍觉得抽象——这个 zip 包就是你的实体教具解压即编译输入即反馈崩溃即线索。2. 从零搭建 C- 词法分析器手写 DFA 状态机驱动拒绝正则黑盒C- 语言的词法规则足够清晰但足够典型关键字int,void,if,else,while,return、标识符字母开头字母数字下划线、整数常量十进制无负号、无前导零、运算符,-,*,/,,,!,,,,、分隔符;,,,(,),{,}、注释//行注释。手写词法分析器的核心不是堆 if-else而是用确定有限自动机DFA状态迁移逻辑把识别过程显式化。常见做法是用enum定义状态START,IN_ID,IN_NUM,IN_COMMENT,IN_EQ,IN_LE等用switch-case驱动状态跳转并在终态返回对应 token 类型。2.1 状态机设计与关键边界处理C- 的词法难点不在复杂而在边界模糊处的优先级判定。例如和必须区分先读到后若下一个字符是则归为EQ_OP否则归为ASSIGN_OP。这要求 lexer 必须支持“回退一个字符”ungetch。同样和、!和!也需类似处理。状态机必须包含IN_EQ已读、IN_LE已读、IN_NE已读!等中间态并在读到非预期字符时退回并输出基础 token。// lexer.c 关键状态迁移片段简化版 typedef enum { START, IN_ID, IN_NUM, IN_COMMENT, IN_EQ, IN_LE, IN_GE, IN_NE } State; Token next_token() { int state START; char c; while ((c getch()) ! EOF) { switch (state) { case START: if (isalpha(c)) { state IN_ID; buf[0] c; buf_pos 1; } else if (isdigit(c)) { state IN_NUM; buf[0] c; buf_pos 1; } else if (c ) state IN_EQ; else if (c ) state IN_LE; else if (c !) state IN_NE; // ... 其他初始字符处理 break; case IN_EQ: if (c ) return make_token(EQ_OP); else { ungetch(c); return make_token(ASSIGN_OP); } // 回退 case IN_LE: if (c ) return make_token(LE_OP); else { ungetch(c); return make_token(LT_OP); } // ... 其他状态 } } return make_token(END_OF_FILE); }提示buf是字符缓冲区用于暂存标识符或数字字面量getch()从输入流读一个字符ungetch(c)将字符压回输入流。这是手写 lexer 的基础设施不可省略。2.2 关键字识别哈希表 vs 字符串比较为什么这里选后者C- 关键字仅 6 个int,void,if,else,while,return数量极少。工业级 lexer 可能用哈希表如 gperf 生成加速查找但本项目中直接用strcmp比较更直观、更易调试、且无额外依赖。在IN_ID终态后将buf中字符串与关键字列表逐一比对// lexer.c 中识别关键字逻辑 if (state IN_ID) { buf[buf_pos] \0; if (strcmp(buf, int) 0) return make_token(KEYWORD_INT); else if (strcmp(buf, void) 0) return make_token(KEYWORD_VOID); else if (strcmp(buf, if) 0) return make_token(KEYWORD_IF); else if (strcmp(buf, else) 0) return make_token(KEYWORD_ELSE); else if (strcmp(buf, while) 0) return make_token(KEYWORD_WHILE); else if (strcmp(buf, return) 0) return make_token(KEYWORD_RETURN); else return make_token(IDENTIFIER); // 默认为标识符 }参数说明make_token()封装 token 构造通常包含type枚举类型、value字符串值如 ID 名称、line_num行号用于错误定位。line_num在getch()中维护遇到\n时自增——这是调试时定位错误的关键字段。2.3 整数常量解析为什么禁止前导零如何检测溢出C- 规定整数常量为十进制非负整数且不允许前导零即012是非法的。这要求 lexer 在IN_NUM状态中读到第一个数字后若后续字符为0且前面已读过非零数字则需报错。更关键的是溢出检测C- 未指定整数位宽但实际实现中需防止atoi()或手动累加时整数溢出导致未定义行为。安全做法是边读边检查case IN_NUM: if (isdigit(c)) { int digit c - 0; // 检查溢出假设 MAX_INT 2147483647 if (num (INT_MAX - digit) / 10) { fprintf(stderr, Line %d: integer constant overflow\n, line_num); exit(1); } num num * 10 digit; } else { ungetch(c); return make_token(NUMBER, num); } break;血泪经验很多同学忽略溢出检查输入2147483648时程序行为不可预测。C- 虽小但溢出是真实存在的坑必须显式处理。3. 手写递归下降语法分析器用 C 实现教材第四章的预测分析表C- 的语法是典型的 LL(1) 文法非常适合递归下降实现。相比用 yacc/bison 生成 LALR(1) 分析器手写递归下降让你完全掌控每个非终结符的 parse 函数、每个 FIRST/FOLLOW 集的计算依据、以及预测失败时的错误恢复逻辑。本项目采用纯 C 实现无外部工具链依赖所有parse_*()函数一一对应文法产生式。3.1 C- 文法核心产生式与 FIRST/FOLLOW 集推导C- 的核心文法精简版如下Program → ExtDefList ExtDefList → ExtDef ExtDefList | ε ExtDef → Specifier ExtDecList SEMI | Specifier FunDec CompSt | Specifier SEMI Specifer → TYPE ExtDecList → VarDec | VarDec COMMA ExtDecList FunDec → ID LPAREN VarList RPAREN | ID LPAREN RPAREN VarList → ParamDec COMMA VarList | ParamDec ParamDec → Specifier VarDec CompSt → LCURLY LocalDec StmtList RCURLY LocalDec → Def | LocalDec Def Def → Specifier DecList SEMI DecList → VarDec | VarDec COMMA DecList VarDec → ID | ID LBRAK INT RBRAK StmtList → Stmt StmtList | ε Stmt → Exp SEMI | CompSt | RETURN Exp SEMI | IF LPAREN Exp RPAREN Stmt | IF LPAREN Exp RPAREN Stmt ELSE Stmt | WHILE LPAREN Exp RPAREN Stmt Exp → Exp ASSIGNOP Exp | Exp ADDOP Exp | Exp MULOP Exp | Exp RELOP Exp | NOT Exp | MINUS Exp | LPAREN Exp RPAREN | ID | ID LPAREN Args RPAREN | INT Args → Exp | Exp COMMA Args | εFIRST 集决定预测分支FOLLOW 集决定 ε 产生式何时选用。例如StmtList → Stmt StmtList | ε当当前 token 不在FIRST(Stmt)中即不是ID,IF,WHILE,RETURN,LCURLY,SEMI且在FOLLOW(StmtList)即RCURLY,ELSE,SEMI中时才选择 ε 分支。手写 parser 时这些集合不是黑盒而是你写if (token ID || token IF || ...)的直接依据。3.2 递归下降主干parse_StmtList()的典型结构每个非终结符对应一个 parse 函数返回抽象语法树AST节点或 void。parse_StmtList()是典型例子它体现 LL(1) 的预测本质// parser.c ASTNode* parse_StmtList() { ASTNode* head NULL; ASTNode* tail NULL; // 预测若下一个 token 属于 FIRST(Stmt)则递归调用 parse_Stmt() while (lookahead.type ID || lookahead.type IF || lookahead.type WHILE || lookahead.type RETURN || lookahead.type LCURLY || lookahead.type SEMI) { ASTNode* stmt parse_Stmt(); if (head NULL) { head tail stmt; } else { tail-next stmt; tail stmt; } } // 若不满足 FIRST(Stmt)则匹配 ε空语句列返回 NULL return head; }逻辑说明lookahead是全局前瞻 token由next_token()提前读取并缓存。parse_Stmt()内部会消耗 token 并推进lookahead。这种“提前看一个 token 决策”的模式正是 LL(1) 的灵魂。SEMI出现在StmtList的 FOLLOW 集中如if (x) y;后的分号所以必须纳入判断条件。3.3 表达式解析如何解决左递归运算符优先级如何编码原始文法中Exp → Exp ADDOP Exp是左递归无法直接用于递归下降。必须改写为右递归形式并按运算符优先级分层。C- 运算符优先级从高到低括号/函数调用/一元运算符NOT,MINUS→ 乘除MULOP→ 加减ADDOP→ 关系运算符RELOP→ 赋值ASSIGNOP。标准做法是为每层优先级写一个函数ASTNode* parse_Exp() { ASTNode* left parse_AssignExp(); // 最低优先级赋值 return left; } ASTNode* parse_AssignExp() { ASTNode* left parse_RelExp(); if (lookahead.type ASSIGNOP) { consume(ASSIGNOP); ASTNode* right parse_AssignExp(); // 右结合 return make_binary_node(ASSIGN_OP, left, right); } return left; } ASTNode* parse_RelExp() { ASTNode* left parse_AddExp(); while (lookahead.type EQ_OP || lookahead.type NE_OP || lookahead.type LT_OP || lookahead.type LE_OP || lookahead.type GT_OP || lookahead.type GE_OP) { Token op lookahead; consume(op.type); ASTNode* right parse_AddExp(); left make_binary_node(op.type, left, right); } return left; } ASTNode* parse_AddExp() { ASTNode* left parse_MulExp(); while (lookahead.type PLUS || lookahead.type MINUS) { Token op lookahead; consume(op.type); ASTNode* right parse_MulExp(); left make_binary_node(op.type, left, right); } return left; } ASTNode* parse_MulExp() { ASTNode* left parse_UnaryExp(); while (lookahead.type TIMES || lookahead.type DIVIDE) { Token op lookahead; consume(op.type); ASTNode* right parse_UnaryExp(); left make_binary_node(op.type, left, right); } return left; } ASTNode* parse_UnaryExp() { if (lookahead.type NOT) { consume(NOT); return make_unary_node(NOT_OP, parse_UnaryExp()); } else if (lookahead.type MINUS) { consume(MINUS); return make_unary_node(NEG_OP, parse_UnaryExp()); } else if (lookahead.type LPAREN) { consume(LPAREN); ASTNode* exp parse_Exp(); consume(RPAREN); return exp; } else if (lookahead.type ID) { Token id lookahead; consume(ID); if (lookahead.type LPAREN) { // 函数调用 consume(LPAREN); ASTNode* args parse_Args(); consume(RPAREN); return make_call_node(id.value, args); } else { // 普通标识符 return make_id_node(id.value); } } else if (lookahead.type NUMBER) { Token num lookahead; consume(NUMBER); return make_num_node(num.value); } else { syntax_error(Expected expression); return NULL; } }参数说明consume(type)检查lookahead.type是否匹配匹配则调用next_token()更新lookahead否则报错。make_*_node()创建 AST 节点存储类型、子节点、位置信息。这种分层函数结构让优先级和结合性一目了然——parse_AssignExp右结合parse_AddExp左结合无需记忆表格。4. 常见问题排查5 个真实翻车现场与救命命令手写 lexer/parser 最容易在看似 trivial 的地方集体翻车。以下是我在带山东科技大学、燕山大学学生做编译原理实验时高频出现的 5 类问题附带现象、根因和一招毙命的修复方案。4.1 现象lexer 死循环getch()不停读EOF原因getch()函数未正确处理文件结尾或ungetch()缓冲区溢出导致getch()返回无效字符进入START状态后又立即读EOF形成无限循环。解决在getch()开头加assert(buf_pos MAX_BUF_SIZE)在ungetch()中确保buf_pos不越界最关键的是在next_token()主循环中if (c EOF) break;必须放在switch外层而非某个case内部。4.2 现象if (x) y; else z;被解析为if (x) {y; else z;}悬空 else原因Stmt → IF LPAREN Exp RPAREN Stmt | IF LPAREN Exp RPAREN Stmt ELSE Stmt的文法本身存在歧义LL(1) 分析器无法自动解决。教材中明确要求使用“最近匹配”原则即else总是和最近的未配对if结合。解决在parse_Stmt()中ELSEtoken 的预测必须严格限定——只有当lookahead.type ELSE且上一个if的then分支已成功解析即parse_Stmt()返回非 NULL时才进入else分支。代码中需用局部变量标记if是否已解析then。4.3 现象int a[10];解析失败报Expected SEMI原因VarDec → ID | ID LBRAK INT RBRAK中LBRAK[的 FIRST 集与ID冲突。当 lexer 输出IDtoken 后parser 无法预测接下来是SEMI简单声明还是LBRAK数组声明。解决将VarDec拆分为两个函数parse_VarDec_Simple()和parse_VarDec_Array()并在parse_ExtDecList()中根据lookahead.type预测若lookahead.type LBRAK则调用parse_VarDec_Array()否则调用parse_VarDec_Simple()。这相当于手动实现 LL(1) 预测表。4.4 现象a b c * d;的 AST 中节点在*节点之上优先级错误原因parse_AddExp()和parse_MulExp()的调用顺序颠倒或parse_MulExp()内部未正确循环处理连续*//。解决用gcc -g编译后在parse_AddExp()开头设断点单步执行观察left和right的构建顺序。确保parse_AddExp()调用parse_MulExp()获取左操作数且parse_MulExp()自身能处理a*b*c这样的链式表达式通过while循环。4.5 现象// comment后的换行未被 lexer 计入line_num导致后续错误行号错乱原因IN_COMMENT状态中读到\n时未自增line_num或getch()在\n后返回\0导致状态机卡住。解决在IN_COMMENT状态的case中明确处理\nif (c \n) { line_num; state START; continue; }。同时确保getch()对\n返回其 ASCII 值而非\0。注意所有syntax_error()函数必须打印line_num这是定位问题的第一线索。没有行号的错误信息等于没报错。5. AST 构建与错误恢复让分析器不只是“能跑”而是“能说清哪里错了”一个合格的课程设计不能只输出“Syntax OK”或“Segmentation fault”。C- 分析器的价值在于把语法错误转化为开发者能理解的上下文信息并尽可能继续解析以发现更多错误。这需要 AST 节点携带位置信息并在 parser 中植入错误恢复机制。5.1 AST 节点设计位置信息是调试的生命线每个 AST 节点必须包含lineno字段起始行号最好还有colno列号。这要求 lexer 在构造 token 时就记录位置并在make_*_node()中透传typedef struct ASTNode { NodeType type; struct ASTNode* child; struct ASTNode* sibling; char* name; // for ID, TYPE int value; // for NUMBER int lineno; // 行号来自 token int colno; // 列号可选 } ASTNode; ASTNode* make_id_node(char* name) { ASTNode* node malloc(sizeof(ASTNode)); node-type NODE_ID; node-name strdup(name); node-lineno lookahead.lineno; // 关键从 lookahead 获取 node-colno lookahead.colno; return node; }技巧lookahead结构体中增加lineno和colno字段getch()在读到\n时重置colno0其他字符时colno。这样每个 token 都自带精准坐标。5.2 错误恢复同步集Synchronizing Set的 C 语言落地当 parser 在parse_Stmt()中遇到非法 token如int x;后突然出现不能直接 abort而应跳过直到找到“同步记号”synchronizing token如SEMI,RCURLY,ELSE,IF,WHILE。这需要为每个非终结符定义其同步集// parser.c #define SYNC_STMT (SEMI | RCURLY | ELSE | IF | WHILE | RETURN) #define SYNC_EXP (SEMI | RCURLY | COMMA | RPAREN | ELSE) void recover_to(int sync_set) { while (lookahead.type ! EOF !(sync_set (1 lookahead.type))) { next_token(); } } ASTNode* parse_Stmt() { switch (lookahead.type) { case ID: return parse_ExpStmt(); case IF: return parse_IfStmt(); case WHILE: return parse_WhileStmt(); case RETURN: return parse_ReturnStmt(); case LCURLY: return parse_CompStmt(); default: syntax_error(Unexpected token %s at line %d, token_name(lookahead.type), lookahead.lineno); recover_to(SYNC_STMT); // 跳到下一个合法 Stmt 开头 return NULL; } }参数说明sync_set用 bit mask 实现1 token_type映射到对应 bit。recover_to()循环调用next_token()直到lookahead.type在同步集中。这比exit(1)人性化得多——一个文件里有 10 个错误你能看到全部而不是修一个再报下一个。5.3 验证 AST用 dot 图形化查看比 printf 更直观手写 parser 后光看printf(Parsed if stmt)不够。用 Graphviz 的 dot 格式导出 AST一眼看清结构void ast_to_dot(ASTNode* node, FILE* f, int* id) { if (!node) return; int my_id (*id); fprintf(f, n%d [label\%s\\nline:%d\];\n, my_id, node_type_name(node-type), node-lineno); if (node-child) { int child_id *id; ast_to_dot(node-child, f, id); fprintf(f, n%d - n%d [label\child\];\n, my_id, child_id); } if (node-sibling) { int sib_id *id; ast_to_dot(node-sibling, f, id); fprintf(f, n%d - n%d [label\sibling\];\n, my_id, sib_id); } } // 使用生成 ast.dot然后 dot -Tpng ast.dot -o ast.png void print_ast_to_dot(ASTNode* root) { FILE* f fopen(ast.dot, w); fprintf(f, digraph AST {\n); int id 0; ast_to_dot(root, f, id); fprintf(f, }\n); fclose(f); }后悔药我带过的最惨案例是学生写了 3 天 parser最后发现parse_Exp()返回的节点child和sibling指针全反了——用 dot 图一画父子关系全乱5 分钟定位。图形化不是炫技是 debug 的刚需。6. 进阶技巧用 GDB 单步追踪 lexer 状态机把“理论”焊进肌肉记忆当你已经能让test.cminus文件成功解析出 AST下一步不是优化性能而是用调试器把课本上的 DFA 状态图、LL(1) 预测表一帧帧映射到真实的内存执行流中。这才是编译原理课程设计的终极目标——让抽象概念变成你敲nnext时眼里的寄存器值。6.1 GDB 调试 lexer观察状态迁移的原子操作编译时加-g运行gdb ./parser然后对关键函数下断点(gdb) break next_token (gdb) break getch (gdb) break ungetch (gdb) run test.cminus在next_token()断点处用print state查看当前状态print c查看读入字符step进入switch后观察state如何从START→IN_ID→IN_ID读第二个字母→ 终态。特别关注ungetch(c)后getch()是否真的返回了c——这是验证回退逻辑是否正确的铁证。玄学时刻当state IN_EQ且c 时next_token()应返回EQ_OP若此时c x则ungetch(x)后state应回到START且下次getch()必须返回x。GDB 里print buf和print buf_pos能确认缓冲区是否被污染。6.2 GDB 调试 parser跟踪 FIRST 集决策路径在parse_Stmt()开头下断点用display lookahead.type持续显示前瞻 token。输入if (x) y;你会看到第一次lookahead.type IF→ 进入parse_IfStmt()parse_IfStmt()中lookahead.type LPAREN→ 消耗(然后parse_Exp()...parse_Exp()中lookahead.type ID→ 进入parse_UnaryExp()...每一步nnext都对应文法中的一次产生式选择。把parse_Exp()的if-else链和教材第四章的预测分析表逐行对照你会发现lookahead.type ID时走parse_UnaryExp()lookahead.type LPAREN时走parse_Exp()递归lookahead.type NOT时走parse_UnaryExp()的一元分支——这正是 FIRST 集的物理实现。6.3 用 valgrind 捕捉内存泄漏AST 节点的 malloc/free 必须对称C 语言手写 parser 最容易内存泄漏。valgrind --leak-checkfull ./parser test.cminus会报告12345 128 bytes in 8 blocks are definitely lost in loss record 1 of 2 12345 at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) 12345 by 0x1093A9: make_id_node (parser.c:45) 12345 by 0x1094B2: parse_UnaryExp (parser.c:128)这说明make_id_node()分配的内存未被释放。解决方案是写free_ast()递归释放void free_ast(ASTNode* node) { if (!node) return; free_ast(node-child); free_ast(node-sibling); if (node-name) free(node-name); free(node); }我的习惯每次make_*_node()后立刻在对应parse_*()函数末尾写free_ast(result)测试内存释放逻辑确保 AST 构建和销毁是闭环。编译原理不是只讲前端内存管理是工程师的基本功。希望帮到你。本文还有配套的精品资源点击获取