编译原理作业实战：词法分析、语法分析与错误恢复的完整实现

简介：北京邮电大学计算机科学与技术专业大三上学期编译原理课程作业完整资料包，作业得分97分。内容覆盖词法分析与语法分析两大核心模块，包含可直接运行的源代码、实验报告、文档说明及配套PPT和PDF讲义，适合正在学习编译原理、需要完成课程设计或准备答辩的计算机相关专业学生参考，也可供教师作为教学案例使用。压缩包约2.7MB，携带方便，文件以源码、报告、演示文稿和说明文档为主，便于对照代码理解分析流程与实现细节。目前已有121人学习下载，源码均经过充分测试，运行成功后才上传，可直接用于快速搭建演示环境，也能作为课程设计或项目初期立项的素材。通过这套资料可以系统梳理词法规则、语法树构建及错误处理思路，对提升编译原理的动手实践能力很有帮助。

1. 词法分析与语法分析:编译原理课内作业的工程化完成方案

大三上学期编译原理课内作业布置下来,很多人最直接的反应是翻教材,可教材从正则文法讲到LALR分析表,从头推导一遍要几天,落成代码反而不知从哪一行开始。这个作业表面上是"写一个词法分析器加一个语法分析器",实际考察的是三件事:能不能把正则到DFA、文法到分析表这两条理论链路映射到代码上;能不能在错误输入面前不崩;能不能把设计思路写清楚让老师一眼看到工作量。得分97的代码不一定用了多么高级的算法,而是把每一条规则、每一个错误恢复、每一处文档都做到位。

2. 词法分析器的设计与实现:从正则到Token的最小工程闭环

词法分析器的任务是拿源代码字符流换Token流。常见做法两条路:手写状态机,或用Flex这类生成器。课内作业我会先用Flex把流程跑通,再手写一遍理解DFA内部机制,这样代码正确率和报告理论深度能同时保证。

2.1 正则表达式到DFA:写代码前先搞清三个关键点

词法分析的理论基础是正则语言。正则表达式经Thompson构造法转为NFA,再子集构造法确定化为DFA,最小化后得到最少状态数。这个推导流程不需要自己实现,但有三个点直接决定代码怎么组织。

第一,最长匹配与优先级。Flex的规则是匹配最长字符串,同长时取最先定义的那条。关键字与标识符的区分就靠这个:关键字规则写在标识符之前,输入int时命中关键字规则,输入integer时命中标识符规则。第二,DFA的状态数。运算符规则拆得越碎,合并后的状态越多,作业代码里表现为难以调试的冲突。第三,词法错误要在这个阶段就拦截。未闭合字符串、非法字符、数字格式错误,语法分析器拿到的是Token流,看不到原始字符,这类错误必须在词法层报出来。

2.2 用Flex实现词法分析:最小可运行的.l文件

Flex文件的总体结构分三段:C声明、规则段、用户代码段。一个能识别整数、标识符和运算符的最小例子:

%{ #include "token.h" int line_no = 1; /* 全局行号,供报错使用 */ %} digit [0-9] letter [a-zA-Z_] identifier {letter}({letter}|{digit})* integer {digit}+ %% [ \t]+ ; /* 空白只跳过,不产生Token */ "\n" { line_no++; } "int"|"float" { return KW_TYPE; } {identifier} { strcpy(yylval.id, yytext); return ID; } {integer} { yylval.ival = atoi(yytext); return INT; } "+"|"-"|"*"|"/" { yylval.op = yytext[0]; return OPERATOR; } "("|")"|"{"|"}" { return BRACKET; } . { report_lex_error(line_no, yytext); } %% int yywrap() { return 1; } /* 告知Flex只有一个输入文件 */

每一行是一条正则到动作的映射。[ \t]+不返回Token,仅跳过空白;换行时行号自增;关键字规则写在前面,利用Flex的优先级区分关键字与同名标识符。.匹配任何未匹配的单个字符,是词法错误捕获的兜底。yytext保存匹配到的字符串,yylval用来往语法分析器传属性值。yywrap返回1表示不再有后续输入文件。

配套的token.h里定义Token类型和yylval的结构:

typedef enum { KW_TYPE, ID, INT, OPERATOR, BRACKET, END } TokenType; typedef struct { TokenType type; int line; union { int ival; char id[64]; char op; } value; } Token;

再回来说Flex最常见的两个坑:一个是没有%option noyywrap,链接时报找不到yywrap,上面手动定义函数绕开;另一个是yylval的类型。如果语法分析器还需要行号,联合体装不下,建议把yylval定义成结构体,或者用独立的全局变量记录行号。

注意:Flex的规则排序直接影响匹配结果,优先级相同但顺序颠倒会让关键字被当成标识符。调试此类问题先检查规则顺序。

2.3 符号表设计:作用域栈式管理,词法层只登记不检查

很多参考代码把符号表做成一个大全局表,词法阶段就把标识符全塞进去。课内作业不建议这么做。词法层的职责是识别,不是语义检查。符号表只要两条能力:登记名字,按作用域遮蔽规则查询。

typedef struct Symbol { char name[64]; struct Symbol *next; } Symbol; typedef struct Scope { Symbol *head; struct Scope *parent; } Scope;

进入一个花括号作用域时压入新Scope,出作用域时弹掉。查询名字时从当前Scope往上遍历,先命中的就是当前环境应该看到的名字。这个设计在报告里一句话能交代清楚——"采用栈式作用域管理,与C语言的名称遮蔽规则一致",比描述成全局哈希表更有原理性。

3. 语法分析器的实现:递归下降与LR(1)的选型与落地

语法分析器是真正干活的地方。作业给的文法如果是表达式、赋值和简单语句,递归下降几乎总是最稳妥的选择;如果文法规则超过三四十条,用Bison生成LR分析器会更省力。两种方案各有脾气,这一章把关键路径都走一遍。

3.1 文法设计:先把左递归消掉,再算FIRST和FOLLOW

表达式文法最标准的写法:

expr → term { (+|-) term } term → factor { (*|/) factor } factor → ID | NUM | ( expr )

花括号代表零次或多次,是EBNF的表示法。如果原始定义里有expr → expr + term,必须先改写,否则递归下降函数会无限递归到栈溢出。改写后紧接着手算FIRST集和FOLLOW集,这一步不是作业的摆设:FIRST集决定解析函数看到什么Token才能进对应分支,FOLLOW集决定错误恢复时机。手算一遍之后,再遇到类似if (expr) stmt else stmt的悬空else问题,就能理解为什么else要与最近的if结合,这背后是LR或LL分析表中移进-归约冲突默认移进的规则。

3.2 递归下降分析法:Token流到AST的关键代码

递归下降的骨架是每个非终结符一个函数。以加减乘除表达式为例:

ASTNode *parse_expr() { ASTNode *left = parse_term(); while (current_token.type == PLUS || current_token.type == MINUS) { Token op = current_token; match(op.type); /* 消费当前Token并前移 */ ASTNode *right = parse_term(); left = make_binop(op, left, right); } return left; } ASTNode *parse_term() { ASTNode *left = parse_factor(); while (current_token.type == STAR || current_token.type == SLASH) { Token op = current_token; match(op.type); ASTNode *right = parse_factor(); left = make_binop(op, left, right); } return left; } ASTNode *parse_factor() { if (current_token.type == ID || current_token.type == INT) { ASTNode *node = make_leaf(current_token); advance(); return node; } if (current_token.type == LPAREN) { advance(); ASTNode *node = parse_expr(); expect(RPAREN); /* 括号不闭合时触发错误恢复 */ return node; } recover_from_error(); return NULL; }

match校验当前Token与参数一致,一致则前移;expect用于强制要求的Token,失败时走错误恢复。make_binop(op, left, right)把新节点挂在旧节点上方,从左往右组合,天然实现左结合。括号的优先级靠递归层级实现——越晚调用的函数优先级越高,这里factor优先级最高,expr最低。

AST节点用最简结构:

typedef enum { NODE_BINOP, NODE_LEAF } NodeKind; typedef struct ASTNode { NodeKind kind; Token op; struct ASTNode *left; struct ASTNode *right; } ASTNode;

3.3 Bison路线:什么时候用,语法文件怎么写

文法规则多且改动频繁时,手写递归下降每加一条语法就要动好几个函数。Bison把文法直接写进.y文件,改一条产生式重新生成就行。最小可用的Bison片段:

%{ #include "ast.h" %} %token ID INT %token PLUS MINUS STAR SLASH LPAREN RPAREN %left PLUS MINUS %left STAR SLASH %% expr: term { $$ = $1; } | expr PLUS term { $$ = make_binop($2, $1, $3); } ; term: factor { $$ = $1; } | term STAR factor { $$ = make_binop($2, $1, $3); } ; factor: ID { $$ = make_leaf($1); } | INT { $$ = make_leaf($1); } | LPAREN expr RPAREN { $$ = $2; } ; %%

%left声明加法和乘法的优先级,后者在先所以优先级更高。$1、$2、$3引用产生式右侧符号的属性值,$$是左侧非终结符的结果。与递归下降相比,Bison最大优势是不用手写循环与分支,产生式即代码;劣势在错误信息,默认是一条没带行号的parse error,需要重写yyerror增强可读性。课内作业我给的建议是:如果报告里文法规则少于30条,递归下降性价比更高,能同时掌控AST构建、错误恢复和调试逻辑;Bison也许一小时就把语法写完,但把错误恢复调舒服可能要一整晚。

4. 错误恢复与调试:让分析器面对坏代码也不崩溃

课内作业的验收环节,老师一定会输入错误代码。错误恢复能力是区分"能跑通"和"能扛住"的分水岭。

4.1 Panic Mode的错误恢复策略

最简单的错误恢复是Panic Mode:发现错误后丢弃Token,直到遇到同步标记再继续。同步标记通常是分号、右括号、右花括号或语句关键字。实现:

void synchronize() { while (!is_end()) { if (current_token.type == SEMICOLON || current_token.type == RBRACE || current_token.type == KW_IF || current_token.type == KW_WHILE) { return; /* 到达安全点,停止丢弃 */ } advance(); } }

调用时机在语句起始处,如果当前Token不属于任何语句的FIRST集,先报错再同步:

void parse_stmt() { if (!in_first_set(current_token.type)) { report_error("第%d行: 语句起始符号不合法", current_token.line); synchronize(); return; } /* 正常解析分支 */ }

Panic Mode的效果不是纠正错误,而是让分析器一次运行能报告多个错误。如果不用任何恢复,第一个语法错误就退出,测试脚本跑一半就停,演示体验非常差。用上同步策略后,错误行被跳过,后续语句继续分析,不会出现连环误报。

4.2 调试工具三件套:AST打印、断言、日志开关

分析器最常见的故障是死循环和错误归约。AST树形打印是第一个有效手段:

void dump_ast(ASTNode *node, int depth) { for (int i = 0; i < depth; i++) printf(" "); if (node->kind == NODE_BINOP) printf("%s\n", token_name(node->op.type)); else printf("%s(%s)\n", token_name(node->op.type), node->op.value.id); if (node->left) dump_ast(node->left, depth + 1); if (node->right) dump_ast(node->right, depth + 1); }

第二个是断言。在match函数里加一行assert(expected == current_token.type),开发期能立刻定位到逻辑断裂点。提交前编译开-DNDEBUG,断言被剔除,不影响运行。

第三个是日志开关。全局变量debug_level大于某阈值时,每读一个Token就打印类型和行号:

int debug_level = 1; void log_token(Token t) { if (debug_level >= 1) { fprintf(stderr, "[debug] %s @ %d\n", token_name(t.type), t.line); } }

调试时开日志,提交时关掉,用一份代码兼顾两种场景。日志输出走stderr,演示时不会污染标准输出里的程序结果。

4.3 测试用例分层:把「对的」和「错的」都放进来

测试文件建议分四层,整体落在tests/目录下:

每一层不只跑一下看结果,还要对照输出里的行号信息,确认报错位置与真实出错行一致。行号对不上,说明词法阶段的行号维护有问题,这类实现细节在验收演示时第一个被看到。

5. 从源代码到高分作业:实验报告、PPT与交付结构

作业的评分里,代码只占一部分,文档说明、实验报告和展示PPT同样在打分项里。97分不是单一亮点堆出来的,而是四个交付物都踩在验收点上。

5.1 实验报告:按验收视角组织四个模块

报告建议按这个顺序写:Token表与DFA图、文法与FIRST/FOLLOW集、AST示例与打印输出、错误恢复说明。Token表用三列:Token类型、正则表达式、优先级,一张表把词法设计说明白。DFA画最小化后的结果,不要画NFA。AST给一个带输入源码的实例,画树形结构图,和dump_ast的输出对应。错误恢复说明写清楚Panic Mode的同步标记集合和触发时机。

困难描述要具体。写"最初左递归没有消除,parse_expr遇到减号时反复调用自身导致栈溢出",比写"调试困难"有力得多。报告里加一段前后对比:崩溃的表现、定位手段、最终改动,这构成完整的技术叙事,也和代码里的Git提交记录呼应。

5.2 PPT演示:先跑对的,再跑错的

PPT控制在10页左右,前三页放系统架构与数据流,中间四页放关键设计与源代码,两页放测试与错误恢复,最后一页放演示脚本。演示顺序固定成一条线:

这个顺序把正确性、错误处理、可观测性三个特性都演示出来。提交时报告和文档说明统一导出PDF,避免Word在不同机器上排版错乱。目录里src/放源代码,tests/放分层测试用例,docs/放文档说明,report/放实验报告,slides/放PPT,Makefile放根目录。README附上一句编译命令和运行命令,验收的人不需要猜。

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