尧图网页设计 
简介一份面向编译原理课程设计的实验资源围绕PL/0教学编译器的词法分析、语法分析与语义处理改造展开适合广工及同类高校需要完成保留字扩展实验的学生使用。内容明确要求新增ELSE、FOR、TO、DOWNTO、RETURN五个保留字加入、-、、--运算符同时把不等号#改为并为条件语句补充ELSE子句能够较完整地体现编译前端从识别到语法、语义处理的联动修改过程。压缩包共24个文件644KB主要包含cpp/h源代码、Word实验报告、exe可执行程序以及pdb、obj、ilk等Visual C工程调试辅助文件便于打开工程直接对照源码与运行结果。目前已有789人学习下载。借助这份紧凑的资源可快速定位保留字和运算符的词法定义位置、ELSE子句在语法与语义模块中的插入点并通过实验报告梳理改造思路适合作为课程实验、期末复习或答辩前的参考资料。1. 广工编译原理实验先搞清楚这门课到底要你做什么编译原理实验是广工计算机学院里最容易被当成“玄学”的一门课其实它要你动手的只有一件事把一段源代码变成计算机能执行的目标代码哪怕只是中间表示。很多人的误区是以为要背一堆自动机理论实际做的时候才发现词法分析就是“正则匹配”语法分析就是“递归下降或LR表”并没有那么抽象。这门实验通常分三到四个阶段从词法分析到语法分析再到语义分析和中间代码每一阶段都会给一个可运行的验收程序。适合两类人一是要应付实验报告和验收的同学二是想真正搞懂编译器前端的从业者。我下面按广工常见实验要求把从环境搭建到出结果的完整路径走一遍每一步都有可以直接复现的命令和代码。2. 环境与工具选型用 flexbison 还是手写递归下降2.1 三个主流方案的取舍广工编译原理实验允许的语言和工具比较宽常见做法有三种。第一用 C/C 配合 flex 和 bison这是最经典、资料最多的方案也是我推荐优先使用的。第二用纯 C 或 Java 手写词法分析和递归下降解析器适合实验限定“不许用生成器”的年份。第三直接用 LLVM 工具链做中间代码和目标代码但本科阶段很少要求到那一步一般在高级选修课里才出现。从验收角度讲flexbison 生成的代码统一、错误处理清晰老师调起测试用例来也顺手。从学习角度讲手写一遍你对状态机和递归下降的理解确实更深。我的建议是如果实验不禁止生成器就用 flexbison如果明确要求手写那就手写词法 手写递归下降不要硬套 LR 构造表。两种路线我都带人走过踩过的坑会在第 5 章集中列出来。2.2 用 flexbison 跑通最小可运行示例先把工具装上在 Ubuntu/Debian 下执行sudo apt update sudo apt install flex bison gcc make装完以后建一个工作目录里面放三个文件lexer.l、parser.y、Makefile。下面是一个能计算四则运算的最小示例。先写lexer.l%{ #include stdio.h #include parser.tab.h %} %% [0-9] { yylval atoi(yytext); return NUMBER; } { return PLUS; } - { return MINUS; } * { return TIMES; } / { return DIVIDE; } ( { return LPAREN; } ) { return RPAREN; } \n { return NEWLINE; } [ \t] { /* 忽略空白 */ } . { fprintf(stderr, Unknown char: %s\n, yytext); return -1; } %% int yywrap(void) { return 1; }再写parser.y%{ #include stdio.h void yyerror(const char *s); %} %token NUMBER PLUS MINUS TIMES DIVIDE LPAREN RPAREN NEWLINE %left PLUS MINUS %left TIMES DIVIDE %% program: program line | /* empty */ ; line: expr NEWLINE { printf(Result: %d\n, $1); } ; expr: expr PLUS expr { $$ $1 $3; } | expr MINUS expr { $$ $1 - $3; } | expr TIMES expr { $$ $1 * $3; } | expr DIVIDE expr { $$ $1 / $3; } | LPAREN expr RPAREN { $$ $2; } | NUMBER { $$ $1; } ; %% int yyerror(const char *s) { fprintf(stderr, Error: %s\n, s); return 0; } int main(void) { return yyparse(); }编译命令bison -d parser.y flex lexer.l gcc parser.tab.c lex.yy.c -o calc这里bison -d会同时生成parser.tab.c和parser.tab.h头文件里声明了 token 的宏定义lexer.l里#include parser.tab.h就靠它。flex lexer.l生成lex.yy.c里面包含词法分析函数yylex()语法解析器会回调它。最后一行把两个生成文件一起编译成可执行文件calc。运行一下输入34*2再回车应该输出11因为乘号优先级更高。如果没有输出或者报语法错误多半是 token 编号不一致检查parser.tab.h和lexer.l里返回的 token 名称是否完全一样。2.3 构建命令和 Makefile 中的参数细节每次手动敲三条编译命令很烦而且容易漏参数。建议直接用 Makefile我常用的写法CC gcc CFLAGS -Wall -g OBJS parser.tab.o lex.yy.o calc: $(OBJS) $(CC) $(OBJS) -o calc parser.tab.c parser.tab.h: parser.y bison -d parser.y lex.yy.c: lexer.l flex lexer.l clean: rm -f calc parser.tab.c parser.tab.h lex.yy.c *.o注意几个容易被忽略的参数。bison -d的-d是必须的否则没有头文件编译lex.yy.c时找不到 token 定义。如果报错undefined reference to yywrap就是链接时缺了字符串表函数可以加-lfl链接 flex 库或者像我在lexer.l里那样自己写一个yywrap返回 1。另外你写的parser.y里如果没有定义main链接也会报undefined reference to main所以上面示例里我把main放在parser.y尾部。2.4 手写递归下降方案何时更合适如果你所在的广工实验室要求不能使用生成器或者你想把原理吃透那就必须手写。词法部分可以写一个循环扫描字符流遇到字母开头就累计成标识符遇到数字就累计成整数。语法部分最常用的是递归下降给每个非终结符写一个函数函数里根据当前 token 类型决定调用哪个分支。比如一个简单的表达式文法expr - term ( ( | - ) term )*可以写成int expr() { int left term(); while (tok PLUS || tok MINUS) { int op tok; next(); int right term(); left (op PLUS) ? left right : left - right; } return left; }这种写法的好处是代码结构和你写的文法一一对应调试时很容易定位坏处是如果文法里有公因子或左递归需要先手动改写。我第一次手写时就是忘了处理while条件里tok PLUS之后要调用next()结果死循环吞掉了所有 token。手写方案没有生成器帮你检测冲突所以每写一个函数都要测试一个对应的输入用例。3. 词法分析实验从正则表达式到能跑的状态机3.1 词法 token 的类型和代码组织词法分析是编译实验的第一关它要做的事就是读入源文件字符流切分成一个又一个 token同时记录每个 token 的种类、值、行号列号。在广工实验里token 一般分五类关键字if、else、while、标识符变量名和函数名、常量整数、浮点数、字符串、运算符、-、*、/、、!、界符分号、逗号、括号。这些 token 的定义必须放在一个公共头文件里比如token.h否则词法分析器和语法分析器各搞一套接口对不上。实际写代码时我会把 token 类型设成一个枚举再配一个结构体保存文本和值typedef enum { TOKEN_IF, TOKEN_ELSE, TOKEN_WHILE, TOKEN_IDENTIFIER, TOKEN_NUMBER, TOKEN_PLUS, TOKEN_MINUS, TOKEN_MUL, TOKEN_DIV, TOKEN_LPAREN, TOKEN_RPAREN, TOKEN_SEMICOLON, TOKEN_EOF } TokenType; typedef struct { TokenType type; char text[256]; int value; int line; int col; } Token;然后在词法主循环里每调用一次getToken()就返回一个Token。实验要求高一点的话还要支持和的区别以及、之类的复合运算符。3.2 用 flex 精确描述词法规则优先级与最长匹配flex 的规则格式是“模式 动作”模式是正则表达式动作是在匹配成功后执行的 C 代码。写规则时最重要的两个原则第一关键字规则必须写在标识符规则之前第二flex 默认按“最长匹配”来决定哪个规则命中如果两个规则匹配到同样长度的文本则排在前面的规则优先。例如下面的lexer.l片段%% if { return TOKEN_IF; } else { return TOKEN_ELSE; } while { return TOKEN_WHILE; } [a-zA-Z_][a-zA-Z0-9_]* { yylval.str strdup(yytext); return TOKEN_IDENTIFIER; } [0-9] { yylval.value atoi(yytext); return TOKEN_NUMBER; } { return TOKEN_EQ; } { return TOKEN_ASSIGN; }为什么关键字要放在前面因为if本身也匹配标识符规则[a-zA-Z_][a-zA-Z0-9_]*但 flex 看到两个规则都能匹配if时会优先选择更靠前的规则。如果把标识符规则放在前面那if、else就永远是标识符关键字就废了。和也是一样的道理如果在先写上规则输入时flex 按最长匹配会选择因为的长度是 2是 1所以即使顺序反了也不会错。但为了可读性我习惯把复合运算符放在前面。3.3 手写词法分析器的状态机实现不用 flex 时词法分析器就是一个确定有限自动机。你可以写一个全局的 token 类型判断函数也可以用状态转移表。状态转移表适合机器生成但手写时维护很痛苦我更推荐直接分情况处理。下面是一个识别整数和标识符的简化版手写函数Token getToken() { Token tok; // 跳过空白 while (isspace(current)) { advance(); } // 数字 if (isdigit(current)) { StringBuilder sb; while (isdigit(current)) { append(sb, current); advance(); } tok.type TOKEN_NUMBER; tok.value atoi(sb.buf); return tok; } // 标识符或关键字 if (isalpha(current) || current _) { StringBuilder sb; while (isalnum(current) || current _) { append(sb, current); advance(); } if (strcmp(sb.buf, if) 0) tok.type TOKEN_IF; else if (strcmp(sb.buf, else) 0) tok.type TOKEN_ELSE; else tok.type TOKEN_IDENTIFIER; strcpy(tok.text, sb.buf); return tok; } // 运算符 switch (current) { case : advance(); tok.type TOKEN_PLUS; return tok; case : advance(); if (current ) { advance(); tok.type TOKEN_EQ; } else tok.type TOKEN_ASSIGN; return tok; } }这段逻辑里最大的坑是“偷看下一个字符”。处理时advance()后必须立即判断current如果模式就把current消耗掉这里很容易漏掉advance()导致无限循环。另一个坑是字符串构建器记得在末尾补\0否则strcmp读到越界内存。3.4 行号记录与错误恢复词法分析器除了返回 token还要记录行号和列号因为语法分析器和后续的报错会用到。在 flex 里你可以在动作里维护全局变量line和col遇到换行时line、col0否则col。手写时同理在advance()函数里更新它们。错误恢复也有讲究遇到不认识的字符最简单的做法是打印“illegal character”然后跳过它但不要直接退出。因为编译实验的测试用例里常常夹杂着注释或预编译指令如果一碰到不认识的字就终止后面所有测试都会挂掉。我一般会这样写default: fprintf(stderr, Line %d: unexpected char %c\n, line, current); advance(); break;这样词法分析器能继续往下走语法分析器也会收到错误信息最后的错误统计会好看很多验收也不会因为一个字符就整体崩溃。4. 语法分析实验从文法改写到一个能跑通的解析器4.1 文法设计消除左递归与优先级语法分析的核心是把 token 流按文法组织成语法树。你从实验指导书里拿到的文法往往是“教学文法”比如expr → expr term | term term → term * factor | factor factor → ( expr ) | number这种左递归文法可以直接用在 bison 里因为 yacc/bison 采用 LR 分析天然支持左递归。但如果要求手写递归下降就必须先改写成 LL(1) 形式消除左递归变成expr → term rest rest → term rest | ε term → factor rest2 rest2 → * factor rest2 | ε factor → ( expr ) | number改写的本质是把左递归变成右递归同时保留左结合性。很多同学在这里翻车因为改写后的文法虽然能识别同样的语言但如果rest的语义动作没写对加减法的结合律会变反。我会在 4.3 节给出一个处理方案。4.2 用 bison 实现完整语法规则bison 里用%left声明优先级可以避免写繁琐的层次文法。前面的计算器已经展示了左右递归的写法。这里再来一个带符号和语句的版本对应广工实验里常见的“赋值语句 表达式”%token IDENTIFIER NUMBER ASSIGN SEMICOLON %left PLUS MINUS %left TIMES DIVIDE %% program : program statement | /* empty */ ; statement : IDENTIFIER ASSIGN expr SEMICOLON { printf(Assign %s %d\n, $1, $3); } ; expr : expr PLUS expr { $$ $1 $3; } | expr MINUS expr { $$ $1 - $3; } | expr TIMES expr { $$ $1 * $3; } | expr DIVIDE expr { $$ $1 / $3; } | IDENTIFIER { $$ lookup($1); } | NUMBER { $$ $1; } ; %%这里IDENTIFIER的语义值$1默认是字符串指针你需要把它转换成变量值。所以词法规则要用yylval.str strdup(yytext)在语法规则里用lookup($1)查符号表。参数%left PLUS MINUS声明了加法和减法的优先级并且它们左结合%left TIMES在下面一行优先级更高所以乘法会先归约。如果你把%left写成了%right那1-2-3就会算成1-(2-3)2这是新手最容易犯的错误。4.3 手写递归下降解析器以表达式为例手写递归下降时我把每个非终结符写成一个函数每个函数开头先检查当前 token 是否属于它的 FIRST 集。下面是改写后的表达式子项term_rest的处理重点在循环里控制结合性int expr() { int left term(); while (tok PLUS || tok MINUS) { int op tok; next(); int right term(); left (op PLUS) ? left right : left - right; } return left; } int term() { int left factor(); while (tok TIMES || tok DIVIDE) { int op tok; next(); int right factor(); left (op TIMES) ? left * right : left / right; } return left; }很多教材把rest写成独立的函数那个版本很容易掉进空产生式死循环。我的习惯是直接用while循环匹配同一优先级的运算符每读到一个运算符就递归下降到下一优先级计算完再更新左值。这样写出来的代码直觉上就是左结合也不需要额外的ε处理。如果输入的表达式很长这个方案每次循环只next()一次不会无限消耗输入。4.4 构建 AST 节点并输出上面的计算器只在产生式里直接计算数值但实验要求往往要生成抽象语法树AST。AST 的结构通常是typedef struct Node { NodeType type; union { struct { struct Node* left; struct Node* right; } binary; char* name; int value; } data; } Node;在 bison 动作里创建节点expr: expr PLUS expr { $$ makeNode(BINARY_OP, , $1, $3); }然后写一个printAST(Node*)递归遍历。我建议在调试阶段先打印 AST再用一个eval(Node*)计算值。比如输入23*4AST 根是一个左边是叶子2右边是*节点。打印出来大概是这样 ├── 2 └── * ├── 3 └── 4如果打印出的结构和你手算的优先级不一样那一定是语法规则里优先级或递归写错了。AST 输出是验证语法分析正确性最直接的手段比看printf中间结果更可靠。5. 常见问题排查你的程序为什么一到测试用例就翻车5.1 现象关键字被识别成标识符原因词法规则顺序错了标识符正则写在关键字前面。解决调整顺序把关键字规则放在标识符规则之前。如果用的是手写词法在识别完字母序列后不要直接返回标识符先查一张关键字表if (strcmp(buf, if) 0) return TOKEN_IF; else if (strcmp(buf, else) 0) return TOKEN_ELSE; else return TOKEN_IDENTIFIER;5.2 现象bison 报 shift/reduce 冲突原因文法有二义性比如没声明运算优先级或表达式嵌套时出现空产生式。解决给 token 声明%left和%right并确保优先级按从低到高排列。如果还是冲突检查是不是%prec用错了。我的经验是先注释掉冲突的规则逐条加回来每次只加一条再用bison -v生成.output文件看冲突所在状态那里面能定位到具体是哪两个规则打架。5.3 现象手写递归下降死循环或栈溢出原因某个解析函数在遇到空串时没有消耗 token比如while (tok PLUS)内部忘记next()或者term_rest处理ε时无限调用自身。解决在函数开头打核心不变量每次调用必须消耗至少一个 token除非是遇到期望的结束符。我习惯在每个解析函数第一行加一条fprintf(stderr, Enter %s: %s\n, __func__, tokenText(tok));一旦死循环立即看打印停在哪一行。5.4 现象编译链接时报yylex或yyerror未定义原因flex生成的文件里的yylex符号在bison里被重命名了或者yyerror只声明没定义。解决确认lexer.l和parser.y里使用了相同的全局函数名。如果编译命令里用了%option reentrant则函数签名会变复杂需要查阅 flex/bison 对应版本的文档。最简单的办法是先用默认模式别开reentrant或locations这种高级选项跑通再改。5.5 现象运行一开始就崩溃错误信息指向yyin或yyrestart原因yyin文件指针没初始化或者程序代码里错误地使用了yyrestart。解决yyparse默认从标准输入读如果想从文件读在main里写extern FILE *yyin; yyin fopen(argv[1], r); if (!yyin) { perror(open file failed); return 1; } return yyparse();如果使用yyrestart一定要在调用前确保yyin已经打开。还有一次我遇到的是项目里同时引用了两个头文件yyin被声明成char*导致运行时乱跳后来加#include stdio.h才解决。6. 进阶验证技巧用符号表和中间代码把整个实验串起来6.1 用 AST 可视化验证语法树完成语法分析后不要急着写中间代码先把 AST 打印出来对照每一个测试用例人工检查。我常用一个递归打印函数输出括号嵌套形式void printAST(Node *n) { if (!n) return; if (n-type NUM) printf(%d, n-value); else if (n-type ID) printf(%s, n-name); else if (n-type BINOP) { printf((%c , n-op); printAST(n-left); printf( ); printAST(n-right); printf()); } }输入23*4应该输出( 2 (* 3 4))如果输出(* ( 2 3) 4)那就是优先级处理反了。这一步能过滤掉一半以上的逻辑错误。6.2 用符号表验证变量信息符号表是语义分析的核心也常被当成实验的最后加分项。你可以在语法分析过程中每遇到一个IDENTIFIER ASSIGN expr就把变量名和当前值登记进一个哈希表。表达式中用到标识符时先从符号表查值查不到就报“undefined variable”。写一个简单的线性表就够了typedef struct Symbol { char name[64]; int value; } Symbol; Symbol table[100]; int tableSize 0;然后在处理赋值语句时table[i].value $3处理表达式中的标识符时遍历查找。这样整个实验从词法到语义就串成了一条完整的工具链。最后建议你做一个总调试脚本把input.txt、lexer.l、parser.y、make命令和期望输出放在一起每次改完代码跑一遍回归测试比手工敲命令可靠得多。我自己的习惯是每个实验阶段结束前强制自己写一个test_all.sh把所有老师可能给的测试用例跑一遍并记录输出。这样验收时哪怕临时加一个边界用例我也能快速定位是哪个模块出了问题。如果从头到尾只会在命令行里手动敲几个输入那实验做得再好考试或答辩时也容易手忙脚乱。这条建议来自一个在广工被测试用例挂掉过的学长希望帮到你。本文还有配套的精品资源点击获取 编译原理实验通关指南：flex+bison与手写递归下降实践
简介一份面向编译原理课程设计的实验资源围绕PL/0教学编译器的词法分析、语法分析与语义处理改造展开适合广工及同类高校需要完成保留字扩展实验的学生使用。内容明确要求新增ELSE、FOR、TO、DOWNTO、RETURN五个保留字加入、-、、--运算符同时把不等号#改为并为条件语句补充ELSE子句能够较完整地体现编译前端从识别到语法、语义处理的联动修改过程。压缩包共24个文件644KB主要包含cpp/h源代码、Word实验报告、exe可执行程序以及pdb、obj、ilk等Visual C工程调试辅助文件便于打开工程直接对照源码与运行结果。目前已有789人学习下载。借助这份紧凑的资源可快速定位保留字和运算符的词法定义位置、ELSE子句在语法与语义模块中的插入点并通过实验报告梳理改造思路适合作为课程实验、期末复习或答辩前的参考资料。1. 广工编译原理实验先搞清楚这门课到底要你做什么编译原理实验是广工计算机学院里最容易被当成“玄学”的一门课其实它要你动手的只有一件事把一段源代码变成计算机能执行的目标代码哪怕只是中间表示。很多人的误区是以为要背一堆自动机理论实际做的时候才发现词法分析就是“正则匹配”语法分析就是“递归下降或LR表”并没有那么抽象。这门实验通常分三到四个阶段从词法分析到语法分析再到语义分析和中间代码每一阶段都会给一个可运行的验收程序。适合两类人一是要应付实验报告和验收的同学二是想真正搞懂编译器前端的从业者。我下面按广工常见实验要求把从环境搭建到出结果的完整路径走一遍每一步都有可以直接复现的命令和代码。2. 环境与工具选型用 flexbison 还是手写递归下降2.1 三个主流方案的取舍广工编译原理实验允许的语言和工具比较宽常见做法有三种。第一用 C/C 配合 flex 和 bison这是最经典、资料最多的方案也是我推荐优先使用的。第二用纯 C 或 Java 手写词法分析和递归下降解析器适合实验限定“不许用生成器”的年份。第三直接用 LLVM 工具链做中间代码和目标代码但本科阶段很少要求到那一步一般在高级选修课里才出现。从验收角度讲flexbison 生成的代码统一、错误处理清晰老师调起测试用例来也顺手。从学习角度讲手写一遍你对状态机和递归下降的理解确实更深。我的建议是如果实验不禁止生成器就用 flexbison如果明确要求手写那就手写词法 手写递归下降不要硬套 LR 构造表。两种路线我都带人走过踩过的坑会在第 5 章集中列出来。2.2 用 flexbison 跑通最小可运行示例先把工具装上在 Ubuntu/Debian 下执行sudo apt update sudo apt install flex bison gcc make装完以后建一个工作目录里面放三个文件lexer.l、parser.y、Makefile。下面是一个能计算四则运算的最小示例。先写lexer.l%{ #include stdio.h #include parser.tab.h %} %% [0-9] { yylval atoi(yytext); return NUMBER; } { return PLUS; } - { return MINUS; } * { return TIMES; } / { return DIVIDE; } ( { return LPAREN; } ) { return RPAREN; } \n { return NEWLINE; } [ \t] { /* 忽略空白 */ } . { fprintf(stderr, Unknown char: %s\n, yytext); return -1; } %% int yywrap(void) { return 1; }再写parser.y%{ #include stdio.h void yyerror(const char *s); %} %token NUMBER PLUS MINUS TIMES DIVIDE LPAREN RPAREN NEWLINE %left PLUS MINUS %left TIMES DIVIDE %% program: program line | /* empty */ ; line: expr NEWLINE { printf(Result: %d\n, $1); } ; expr: expr PLUS expr { $$ $1 $3; } | expr MINUS expr { $$ $1 - $3; } | expr TIMES expr { $$ $1 * $3; } | expr DIVIDE expr { $$ $1 / $3; } | LPAREN expr RPAREN { $$ $2; } | NUMBER { $$ $1; } ; %% int yyerror(const char *s) { fprintf(stderr, Error: %s\n, s); return 0; } int main(void) { return yyparse(); }编译命令bison -d parser.y flex lexer.l gcc parser.tab.c lex.yy.c -o calc这里bison -d会同时生成parser.tab.c和parser.tab.h头文件里声明了 token 的宏定义lexer.l里#include parser.tab.h就靠它。flex lexer.l生成lex.yy.c里面包含词法分析函数yylex()语法解析器会回调它。最后一行把两个生成文件一起编译成可执行文件calc。运行一下输入34*2再回车应该输出11因为乘号优先级更高。如果没有输出或者报语法错误多半是 token 编号不一致检查parser.tab.h和lexer.l里返回的 token 名称是否完全一样。2.3 构建命令和 Makefile 中的参数细节每次手动敲三条编译命令很烦而且容易漏参数。建议直接用 Makefile我常用的写法CC gcc CFLAGS -Wall -g OBJS parser.tab.o lex.yy.o calc: $(OBJS) $(CC) $(OBJS) -o calc parser.tab.c parser.tab.h: parser.y bison -d parser.y lex.yy.c: lexer.l flex lexer.l clean: rm -f calc parser.tab.c parser.tab.h lex.yy.c *.o注意几个容易被忽略的参数。bison -d的-d是必须的否则没有头文件编译lex.yy.c时找不到 token 定义。如果报错undefined reference to yywrap就是链接时缺了字符串表函数可以加-lfl链接 flex 库或者像我在lexer.l里那样自己写一个yywrap返回 1。另外你写的parser.y里如果没有定义main链接也会报undefined reference to main所以上面示例里我把main放在parser.y尾部。2.4 手写递归下降方案何时更合适如果你所在的广工实验室要求不能使用生成器或者你想把原理吃透那就必须手写。词法部分可以写一个循环扫描字符流遇到字母开头就累计成标识符遇到数字就累计成整数。语法部分最常用的是递归下降给每个非终结符写一个函数函数里根据当前 token 类型决定调用哪个分支。比如一个简单的表达式文法expr - term ( ( | - ) term )*可以写成int expr() { int left term(); while (tok PLUS || tok MINUS) { int op tok; next(); int right term(); left (op PLUS) ? left right : left - right; } return left; }这种写法的好处是代码结构和你写的文法一一对应调试时很容易定位坏处是如果文法里有公因子或左递归需要先手动改写。我第一次手写时就是忘了处理while条件里tok PLUS之后要调用next()结果死循环吞掉了所有 token。手写方案没有生成器帮你检测冲突所以每写一个函数都要测试一个对应的输入用例。3. 词法分析实验从正则表达式到能跑的状态机3.1 词法 token 的类型和代码组织词法分析是编译实验的第一关它要做的事就是读入源文件字符流切分成一个又一个 token同时记录每个 token 的种类、值、行号列号。在广工实验里token 一般分五类关键字if、else、while、标识符变量名和函数名、常量整数、浮点数、字符串、运算符、-、*、/、、!、界符分号、逗号、括号。这些 token 的定义必须放在一个公共头文件里比如token.h否则词法分析器和语法分析器各搞一套接口对不上。实际写代码时我会把 token 类型设成一个枚举再配一个结构体保存文本和值typedef enum { TOKEN_IF, TOKEN_ELSE, TOKEN_WHILE, TOKEN_IDENTIFIER, TOKEN_NUMBER, TOKEN_PLUS, TOKEN_MINUS, TOKEN_MUL, TOKEN_DIV, TOKEN_LPAREN, TOKEN_RPAREN, TOKEN_SEMICOLON, TOKEN_EOF } TokenType; typedef struct { TokenType type; char text[256]; int value; int line; int col; } Token;然后在词法主循环里每调用一次getToken()就返回一个Token。实验要求高一点的话还要支持和的区别以及、之类的复合运算符。3.2 用 flex 精确描述词法规则优先级与最长匹配flex 的规则格式是“模式 动作”模式是正则表达式动作是在匹配成功后执行的 C 代码。写规则时最重要的两个原则第一关键字规则必须写在标识符规则之前第二flex 默认按“最长匹配”来决定哪个规则命中如果两个规则匹配到同样长度的文本则排在前面的规则优先。例如下面的lexer.l片段%% if { return TOKEN_IF; } else { return TOKEN_ELSE; } while { return TOKEN_WHILE; } [a-zA-Z_][a-zA-Z0-9_]* { yylval.str strdup(yytext); return TOKEN_IDENTIFIER; } [0-9] { yylval.value atoi(yytext); return TOKEN_NUMBER; } { return TOKEN_EQ; } { return TOKEN_ASSIGN; }为什么关键字要放在前面因为if本身也匹配标识符规则[a-zA-Z_][a-zA-Z0-9_]*但 flex 看到两个规则都能匹配if时会优先选择更靠前的规则。如果把标识符规则放在前面那if、else就永远是标识符关键字就废了。和也是一样的道理如果在先写上规则输入时flex 按最长匹配会选择因为的长度是 2是 1所以即使顺序反了也不会错。但为了可读性我习惯把复合运算符放在前面。3.3 手写词法分析器的状态机实现不用 flex 时词法分析器就是一个确定有限自动机。你可以写一个全局的 token 类型判断函数也可以用状态转移表。状态转移表适合机器生成但手写时维护很痛苦我更推荐直接分情况处理。下面是一个识别整数和标识符的简化版手写函数Token getToken() { Token tok; // 跳过空白 while (isspace(current)) { advance(); } // 数字 if (isdigit(current)) { StringBuilder sb; while (isdigit(current)) { append(sb, current); advance(); } tok.type TOKEN_NUMBER; tok.value atoi(sb.buf); return tok; } // 标识符或关键字 if (isalpha(current) || current _) { StringBuilder sb; while (isalnum(current) || current _) { append(sb, current); advance(); } if (strcmp(sb.buf, if) 0) tok.type TOKEN_IF; else if (strcmp(sb.buf, else) 0) tok.type TOKEN_ELSE; else tok.type TOKEN_IDENTIFIER; strcpy(tok.text, sb.buf); return tok; } // 运算符 switch (current) { case : advance(); tok.type TOKEN_PLUS; return tok; case : advance(); if (current ) { advance(); tok.type TOKEN_EQ; } else tok.type TOKEN_ASSIGN; return tok; } }这段逻辑里最大的坑是“偷看下一个字符”。处理时advance()后必须立即判断current如果模式就把current消耗掉这里很容易漏掉advance()导致无限循环。另一个坑是字符串构建器记得在末尾补\0否则strcmp读到越界内存。3.4 行号记录与错误恢复词法分析器除了返回 token还要记录行号和列号因为语法分析器和后续的报错会用到。在 flex 里你可以在动作里维护全局变量line和col遇到换行时line、col0否则col。手写时同理在advance()函数里更新它们。错误恢复也有讲究遇到不认识的字符最简单的做法是打印“illegal character”然后跳过它但不要直接退出。因为编译实验的测试用例里常常夹杂着注释或预编译指令如果一碰到不认识的字就终止后面所有测试都会挂掉。我一般会这样写default: fprintf(stderr, Line %d: unexpected char %c\n, line, current); advance(); break;这样词法分析器能继续往下走语法分析器也会收到错误信息最后的错误统计会好看很多验收也不会因为一个字符就整体崩溃。4. 语法分析实验从文法改写到一个能跑通的解析器4.1 文法设计消除左递归与优先级语法分析的核心是把 token 流按文法组织成语法树。你从实验指导书里拿到的文法往往是“教学文法”比如expr → expr term | term term → term * factor | factor factor → ( expr ) | number这种左递归文法可以直接用在 bison 里因为 yacc/bison 采用 LR 分析天然支持左递归。但如果要求手写递归下降就必须先改写成 LL(1) 形式消除左递归变成expr → term rest rest → term rest | ε term → factor rest2 rest2 → * factor rest2 | ε factor → ( expr ) | number改写的本质是把左递归变成右递归同时保留左结合性。很多同学在这里翻车因为改写后的文法虽然能识别同样的语言但如果rest的语义动作没写对加减法的结合律会变反。我会在 4.3 节给出一个处理方案。4.2 用 bison 实现完整语法规则bison 里用%left声明优先级可以避免写繁琐的层次文法。前面的计算器已经展示了左右递归的写法。这里再来一个带符号和语句的版本对应广工实验里常见的“赋值语句 表达式”%token IDENTIFIER NUMBER ASSIGN SEMICOLON %left PLUS MINUS %left TIMES DIVIDE %% program : program statement | /* empty */ ; statement : IDENTIFIER ASSIGN expr SEMICOLON { printf(Assign %s %d\n, $1, $3); } ; expr : expr PLUS expr { $$ $1 $3; } | expr MINUS expr { $$ $1 - $3; } | expr TIMES expr { $$ $1 * $3; } | expr DIVIDE expr { $$ $1 / $3; } | IDENTIFIER { $$ lookup($1); } | NUMBER { $$ $1; } ; %%这里IDENTIFIER的语义值$1默认是字符串指针你需要把它转换成变量值。所以词法规则要用yylval.str strdup(yytext)在语法规则里用lookup($1)查符号表。参数%left PLUS MINUS声明了加法和减法的优先级并且它们左结合%left TIMES在下面一行优先级更高所以乘法会先归约。如果你把%left写成了%right那1-2-3就会算成1-(2-3)2这是新手最容易犯的错误。4.3 手写递归下降解析器以表达式为例手写递归下降时我把每个非终结符写成一个函数每个函数开头先检查当前 token 是否属于它的 FIRST 集。下面是改写后的表达式子项term_rest的处理重点在循环里控制结合性int expr() { int left term(); while (tok PLUS || tok MINUS) { int op tok; next(); int right term(); left (op PLUS) ? left right : left - right; } return left; } int term() { int left factor(); while (tok TIMES || tok DIVIDE) { int op tok; next(); int right factor(); left (op TIMES) ? left * right : left / right; } return left; }很多教材把rest写成独立的函数那个版本很容易掉进空产生式死循环。我的习惯是直接用while循环匹配同一优先级的运算符每读到一个运算符就递归下降到下一优先级计算完再更新左值。这样写出来的代码直觉上就是左结合也不需要额外的ε处理。如果输入的表达式很长这个方案每次循环只next()一次不会无限消耗输入。4.4 构建 AST 节点并输出上面的计算器只在产生式里直接计算数值但实验要求往往要生成抽象语法树AST。AST 的结构通常是typedef struct Node { NodeType type; union { struct { struct Node* left; struct Node* right; } binary; char* name; int value; } data; } Node;在 bison 动作里创建节点expr: expr PLUS expr { $$ makeNode(BINARY_OP, , $1, $3); }然后写一个printAST(Node*)递归遍历。我建议在调试阶段先打印 AST再用一个eval(Node*)计算值。比如输入23*4AST 根是一个左边是叶子2右边是*节点。打印出来大概是这样 ├── 2 └── * ├── 3 └── 4如果打印出的结构和你手算的优先级不一样那一定是语法规则里优先级或递归写错了。AST 输出是验证语法分析正确性最直接的手段比看printf中间结果更可靠。5. 常见问题排查你的程序为什么一到测试用例就翻车5.1 现象关键字被识别成标识符原因词法规则顺序错了标识符正则写在关键字前面。解决调整顺序把关键字规则放在标识符规则之前。如果用的是手写词法在识别完字母序列后不要直接返回标识符先查一张关键字表if (strcmp(buf, if) 0) return TOKEN_IF; else if (strcmp(buf, else) 0) return TOKEN_ELSE; else return TOKEN_IDENTIFIER;5.2 现象bison 报 shift/reduce 冲突原因文法有二义性比如没声明运算优先级或表达式嵌套时出现空产生式。解决给 token 声明%left和%right并确保优先级按从低到高排列。如果还是冲突检查是不是%prec用错了。我的经验是先注释掉冲突的规则逐条加回来每次只加一条再用bison -v生成.output文件看冲突所在状态那里面能定位到具体是哪两个规则打架。5.3 现象手写递归下降死循环或栈溢出原因某个解析函数在遇到空串时没有消耗 token比如while (tok PLUS)内部忘记next()或者term_rest处理ε时无限调用自身。解决在函数开头打核心不变量每次调用必须消耗至少一个 token除非是遇到期望的结束符。我习惯在每个解析函数第一行加一条fprintf(stderr, Enter %s: %s\n, __func__, tokenText(tok));一旦死循环立即看打印停在哪一行。5.4 现象编译链接时报yylex或yyerror未定义原因flex生成的文件里的yylex符号在bison里被重命名了或者yyerror只声明没定义。解决确认lexer.l和parser.y里使用了相同的全局函数名。如果编译命令里用了%option reentrant则函数签名会变复杂需要查阅 flex/bison 对应版本的文档。最简单的办法是先用默认模式别开reentrant或locations这种高级选项跑通再改。5.5 现象运行一开始就崩溃错误信息指向yyin或yyrestart原因yyin文件指针没初始化或者程序代码里错误地使用了yyrestart。解决yyparse默认从标准输入读如果想从文件读在main里写extern FILE *yyin; yyin fopen(argv[1], r); if (!yyin) { perror(open file failed); return 1; } return yyparse();如果使用yyrestart一定要在调用前确保yyin已经打开。还有一次我遇到的是项目里同时引用了两个头文件yyin被声明成char*导致运行时乱跳后来加#include stdio.h才解决。6. 进阶验证技巧用符号表和中间代码把整个实验串起来6.1 用 AST 可视化验证语法树完成语法分析后不要急着写中间代码先把 AST 打印出来对照每一个测试用例人工检查。我常用一个递归打印函数输出括号嵌套形式void printAST(Node *n) { if (!n) return; if (n-type NUM) printf(%d, n-value); else if (n-type ID) printf(%s, n-name); else if (n-type BINOP) { printf((%c , n-op); printAST(n-left); printf( ); printAST(n-right); printf()); } }输入23*4应该输出( 2 (* 3 4))如果输出(* ( 2 3) 4)那就是优先级处理反了。这一步能过滤掉一半以上的逻辑错误。6.2 用符号表验证变量信息符号表是语义分析的核心也常被当成实验的最后加分项。你可以在语法分析过程中每遇到一个IDENTIFIER ASSIGN expr就把变量名和当前值登记进一个哈希表。表达式中用到标识符时先从符号表查值查不到就报“undefined variable”。写一个简单的线性表就够了typedef struct Symbol { char name[64]; int value; } Symbol; Symbol table[100]; int tableSize 0;然后在处理赋值语句时table[i].value $3处理表达式中的标识符时遍历查找。这样整个实验从词法到语义就串成了一条完整的工具链。最后建议你做一个总调试脚本把input.txt、lexer.l、parser.y、make命令和期望输出放在一起每次改完代码跑一遍回归测试比手工敲命令可靠得多。我自己的习惯是每个实验阶段结束前强制自己写一个test_all.sh把所有老师可能给的测试用例跑一遍并记录输出。这样验收时哪怕临时加一个边界用例我也能快速定位是哪个模块出了问题。如果从头到尾只会在命令行里手动敲几个输入那实验做得再好考试或答辩时也容易手忙脚乱。这条建议来自一个在广工被测试用例挂掉过的学长希望帮到你。本文还有配套的精品资源点击获取