简介：本资源是面向高校计算机专业本科生及编译原理初学者的课程设计实践项目，聚焦C-语言（C语言简化子集）的词法与语法分析器自主实现，帮助学习者深入理解编译前端核心机制。压缩包共22个文件，含7个txt（含词法/语法分析结果、测试用例及语法规则定义）、5个cpp与5个h（核心分析器源码模块，如LexicalAnalyzer.cpp、SyntaxParser.cpp、CharScanner.cpp及配套头文件）、4个json（VS 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中，明确处理\n：if (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时重置colno=0，其他字符时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) 预测表，一帧帧映射到真实的内存执行流中。这才是编译原理课程设计的终极目标——让抽象概念变成你敲n（next）时眼里的寄存器值。

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()...

每一步n（next）都对应文法中的一次产生式选择。把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-check=full ./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 构建和销毁是闭环。编译原理不是只讲前端，内存管理是工程师的基本功。

希望帮到你。

本文还有配套的精品资源，点击获取