简介词法分析器与语法分析器是编译器的核心前端组件也是UESTC编译原理课程设计的典型选题。资源内两个Python脚本分别完成词法单元拆分与抽象语法树构建前者将源代码拆为关键字、标识符、运算符等记号后者依据文法规则验证结构并生成语法树同时还配有文法定义、错误报告、中间输出等文件方便学习者把运行结果与理论对照。压缩包共8个文件除两个Python脚本外还包含文法定义、中间结果与错误信息等辅助类型便于调试和复习整体仅4KB轻量易读。已有176人浏览学习。通过这套代码学习者可以直观掌握正则匹配、语法分析策略以及错误处理的基本思路理解从源代码到抽象语法树的完整转换过程包体虽小但结构完整适合快速上手和二次改进无论用于期末设计还是深入理解编译前端都是有力的参考。1. 一个压缩包背后的编译原理课程设计从词法到语法的完整落点拿到“UESTC-编译原理-词法分析器-语法分析器.zip”这个压缩包时大多数人关心的是里面有没有能直接交差的代码、能不能跑通、老师查重和验收会问什么。但如果你真想从这次课程设计里带走点东西核心只有两件事一是词法分析器怎么把字符流切成 token 流二是语法分析器怎么把 token 流组装成语法树。这两层正是编译原理的前端也是龙书前三章最硬的实战部分。这篇博文不猜这个 zip 里装了哪份源码而是把这类课程设计最常见的完整方案拆开讲词法部分从正规式走到 DFA语法部分用递归下降把 LL(1) 落到实处最后给出 Flex Bison 自动生成与手写实现两条路线以及调试和验证的实战技巧。无论你是在 UESTC 还是在别的学校做同样的题目这套路径基本是通用的。适合读这篇文章的人正在做编译原理课程设计的学生、要快速上手 Flex/Bison 的开发者以及想搞清楚词法分析器和语法分析器接口怎么对上的自学党。废话不多说直接开工。2. 词法分析器把字符流变成 token 流的那台状态机2.1 为什么词法分析用正规式而不是上下文无关文法词法分析器要解决的问题是给定一段源代码字符流识别出其中所有的关键字、标识符、数字、运算符和界符并给每个词法单元打上类别标签。这件事之所以不用语法分析那套文法来做是因为词法单元的结构足够简单——它们都能用正则表达式描述。这个“足够简单”是关键。比如标识符就是“字母或下划线开头后面跟字母、数字或下划线”整型常量就是“[0-9]”浮点常量就是“[0-9].[0-9]”。这些都是正规语言用有穷自动机就能识别不需要栈不需要回溯。如果把词法规则也写成语法制分析器能处理的文法一方面文法规模会爆炸另一方面会严重拖慢分析速度。正规式到词法分析器的经典路径是正则表达式 → NFA → DFA → 最小化 DFA。NFA 因为存在 ε 转移和同一状态多出口不适合直接做驱动程序DFA 状态确定每个字符输入最多只有一个后继状态所以实际代码里驱动的是一个状态转移表或者 switch 语句。2.2 手写一个词法分析器核心代码与状态转移手写词法分析器最常见的方式是“一个全局指针 一个 getNextToken 函数 多个匹配分支”。下面这个简化版能识别关键字、标识符、整数、运算符足够应付大多数课程设计的文法规模。#include stdio.h #include string.h #include ctype.h #define MAX_ID_LEN 32 typedef enum { TOK_KEYWORD, TOK_IDENT, TOK_INT, TOK_OP, TOK_EOF, TOK_ERROR } TokenType; typedef struct { TokenType type; char lexeme[MAX_ID_LEN]; int value; int line; } Token; static const char *keywords[] {if, else, while, return, int}; static const char *operators[] {, -, *, /, , , !}; // 判断是否为关键字 static int isKeyword(const char *s) { for (int i 0; i sizeof(keywords)/sizeof(keywords[0]); i) { if (strcmp(s, keywords[i]) 0) return 1; } return 0; } Token getNextToken(const char **src, int *line) { Token tok; const char *p *src; while (*p || *p \t || *p \n) { if (*p \n) (*line); p; } if (*p \0) { tok.type TOK_EOF; *src p; return tok; } // 标识符或关键字 if (isalpha(*p) || *p _) { int len 0; while ((isalnum(*p) || *p _) len MAX_ID_LEN - 1) { tok.lexeme[len] *p; } tok.lexeme[len] \0; tok.type isKeyword(tok.lexeme) ? TOK_KEYWORD : TOK_IDENT; *src p; return tok; } // 整数常量 if (isdigit(*p)) { int val 0; while (isdigit(*p)) { val val * 10 (*p - 0); p; } tok.type TOK_INT; tok.value val; *src p; return tok; } // 运算符包括双字符的 和 ! for (int i 0; i sizeof(operators)/sizeof(operators[0]); i) { int len strlen(operators[i]); if (strncmp(p, operators[i], len) 0) { strcpy(tok.lexeme, operators[i]); tok.type TOK_OP; *src p len; return tok; } } tok.type TOK_ERROR; *src p 1; return tok; } int main(int argc, char *argv[]) { const char *test int a 42; if (a 42) a a 1;; const char *p test; int line 1; Token tok; do { tok getNextToken(p, line); printf(line %d: type%d, lexeme%s, line, tok.type, tok.lexeme); if (tok.type TOK_INT) printf(, value%d, tok.value); printf(\n); } while (tok.type ! TOK_EOF); return 0; }这段代码的核心逻辑是每调用一次 getNextToken就从当前扫描位置开始按“空白 → 标识符/关键字 → 整数 → 运算符 → 错误”的顺序依次尝试匹配。这里有一个容易被忽略的工程点就是运算符匹配时必须排在前面否则输入时会被先切出两个。解决方法是按字符串长度从长到短排序或者干脆用最大匹配法最长匹配优先。注意这个手写版是“局部匹配”而不是“最大匹配”它每次只按预设分支命中一个 token。对于类 C 语言这种词法规则简单的场景完全够用但如果你要识别还是就得在运算符表里严格按长度降序排列。另一个改善方向是把每个字符的处理改成统一的有限状态机在一遍循环里完成全部 token 切分代价是代码可读性明显下降。2.3 用 Flex 自动生成词法分析器如果不想手写状态转移逻辑Flex 是工业界最常用的词法分析器生成工具。它的输入文件分为三段定义段、规则段、用户代码段。下面是一个识别上述 token 的 Flex 文件%{ #include stdio.h #define TOK_KEYWORD 1 #define TOK_IDENT 2 #define TOK_INT 3 #define TOK_OP 4 %} %% if|else|while|return|int { printf(KEYWORD: %s\n, yytext); } [a-zA-Z_][a-zA-Z0-9_]* { printf(IDENT: %s\n, yytext); } [0-9] { printf(INT: %s\n, yytext); } |!||-|*|/| { printf(OP: %s\n, yytext); } [ \t\n] { /* skip whitespace */ } . { printf(ERROR: %s\n, yytext); } %% int main(int argc, char *argv[]) { yylex(); return 0; } int yywrap(void) { return 1; }用flex lexer.l gcc lex.yy.c -o lexer -lfl编译后就得到一个可执行词法分析器。Flex 自动完成了从正规式到 DFA 的构造和最小化规则段里每条规则后面的动作语句就是命中该规则时的处理逻辑。同一时刻有多条规则可匹配时Flex 默认选择最长匹配的规则等长时靠前规则优先——这正好解决了手写版里和冲突的问题。Flex 生成的核心函数是yylex()它会从yyin指向的文件默认 stdin读取输入每次调用返回一个 token 编号。yytext指向当前匹配到的字符串。课程设计里需要一边返回 token 给语法分析器一边记录行号和列号这时可以在动作里维护一个全局line变量遇到换行符就自增。3. 语法分析器从 token 流到语法树的那套推导规则3.1 上下文无关文法与两类主流分析法词法分析器吐出的 token 流只是切碎了的事实语法分析器的职责是判断这些 token 的排列方式是否符合语言文法并构建出语法树。这个阶段使用的数学工具是上下文无关文法CFG产生式形如E - E T | T。自顶向下分析和自底向上分析是两条路线。自顶向下从开始符号出发尝试用产生式推导出整个 token 流代表性方法是 LL(1) 递归下降自底向上从输入串出发不断归约到开始符号代表性方法是 LR(1) 及其变种 LALR(1)Yacc/Bison 用的就是这条路线。课程设计选哪条路线主要看文法规模和你的调试耐心。递归下降对每个非终结符写一个函数代码直观、出错时易定位但要求文法不含有左递归否则会无限递归。Bison 则自动处理 LR 分析表的构造能接受更大的文法子集但出错信息难读牵一发动全身。3.2 递归下降分析器每个非终结符一个函数假定你要分析一个简单算术表达式文法无左递归版本expr - term expr expr - term expr | - term expr | ε term - factor term term - * factor term | / factor term | ε factor - ( expr ) | num对应的递归下降分析器核心代码如下#include stdio.h #include stdlib.h typedef struct { int type; // 1INT, 2OP, 3EOF char text[32]; } Token; Token curToken; int pos 0; // 简单的 token 序列模拟num num * num Token tokenStream[] { {1, 42}, {2, }, {1, 7}, {2, *}, {1, 3}, {3, } }; void advance() { pos; curToken tokenStream[pos]; } int expect(int type, const char *op) { if (curToken.type type) { if (op strcmp(curToken.text, op) ! 0) { fprintf(stderr, expect %s but got %s\n, op, curToken.text); exit(1); } advance(); return 1; } fprintf(stderr, unexpected token %s\n, curToken.text); exit(1); } // expr - term expr int expr() { term(); while (curToken.type 2 (strcmp(curToken.text, ) 0 || strcmp(curToken.text, -) 0)) { printf(op: %s\n, curToken.text); advance(); term(); } return 0; } // term - factor term用 while 消去左递归 int term() { factor(); while (curToken.type 2 (strcmp(curToken.text, *) 0 || strcmp(curToken.text, /) 0)) { printf(op: %s\n, curToken.text); advance(); factor(); } return 0; } // factor - ( expr ) | num int factor() { if (curToken.type 1) { // INT printf(num: %s\n, curToken.text); advance(); } else if (curToken.type 2 strcmp(curToken.text, () 0) { advance(); expr(); expect(2, )); } else { fprintf(stderr, syntax error at %s\n, curToken.text); exit(1); } return 0; } int main() { curToken tokenStream[0]; expr(); if (curToken.type ! 3) { fprintf(stderr, trailing tokens after expression\n); return 1; } printf(parse OK\n); return 0; }这段代码是全程序的关键所在。expr()和term()里用while循环处理/-/*//的迭代出现这是对文法左递归消除之后的直接编码方式——文法里是expr - term expr | ε代码里就是“先匹配一个 term然后不断看下一个 token 是不是或-是就继续匹配”。这种写法避免了递归函数调用栈的无限增长也更容易在循环里做错误恢复。这里有个必须讲清楚的边界就是上述代码只做了语法判断没有构建真正的语法树节点。课程设计如果要求输出语法树在expr()和term()里每成功匹配一个产生式就应当malloc一个节点并返回由上层函数把子节点拼到父节点下。如果你只想验证语法正确性这种“边走边打印”的精简版足够跑通验收。3.3 用 Bison 做 LALR 分析免去手写回溯递归下降写法直观但遇到复杂的运算符优先级文法时手写判断顺序很容易出错。Bison 的做法是把优先级写进声明里让表的构造去处理冲突。下面这个和上面表达式文法等价的 Bison 文件%{ #include stdio.h int yylex(void); void yyerror(const char *s); %} %token NUM %left - %left * / %% expr : expr expr | expr - expr | expr * expr | expr / expr | ( expr ) | NUM ; %% int yylex(void) { int c getchar(); if (c 0 c 9) { yylval c - 0; return NUM; } return c; } void yyerror(const char *s) { fprintf(stderr, syntax error: %s\n, s); } int main() { return yyparse(); }注意%left声明的顺序从低优先级到高优先级排列*//在/-之后声明所以它们优先级更高。Bison 会根据%left/%right/%nonassoc自动消解分析表中的移进-归约冲突。Bison 生成的文件默认是 C 代码编译命令是bison -d parser.y flex lexer.l gcc parser.tab.c lex.yy.c -o parser -lfl。这里的-d参数会生成parser.tab.h里面定义了每个 token 的宏编号Flex 文件#include这个头文件后yylex()返回的 token 编号就和 Bison 里的%token NUM严格一致了。3.4 Flex 和 Bison 怎么对接yylval 的传值机制Flex 和 Bison 的协作模式是Bison 的yyparse()反复调用yylex()获取 tokenyylex()每识别出一个 token 就返回其类型编号如果这个 token 需要携带语义值比如数字的值就把值赋给全局变量yylval。这里有一个最常见的课程设计翻车点写 Bison 文法时用了$$ $1 $3但 Flex 文件里忘了给yylval赋值导致所有数字的值都是 0。另一个翻车点是 Bison 默认yylval类型是int但你想在语法树节点里塞指针这时必须改%union并用%type声明每个非终结符的语义值类型。一个完整可复现的最小例子Flex 识别数字时执行yylval atoi(yytext); return NUM;Bison 文法里每个产生式用$$表示左部非终结符的语义值用$1、$3表示右部第一个、第三个符号的语义值。两者通过同一个全局变量和parser.tab.h里的宏完成握手。4. 中间代码生成必不可少吗不先说符号表与错误处理4.1 符号表的基本实现与作用域管理词法分析器和语法分析器能不能对接得上不只看 token 类型还看符号表是否设计到位。符号表管两件事标识符的去重声明以及属性信息的记录与查询。课程设计的文法规模下用简单的链表就能支撑typedef struct Symbol { char *name; int type; // 变量类型 int scope; // 作用域深度 struct Symbol *next; } Symbol; static Symbol *table NULL; static int currentScope 0; void enterScope() { currentScope; } void leaveScope() { // 删除当前作用域的所有符号 } Symbol *lookup(const char *name) { Symbol *s; for (s table; s ! NULL; s s-next) { if (strcmp(s-name, name) 0) return s; } return NULL; } void insert(const char *name, int type) { Symbol *s (Symbol *)malloc(sizeof(Symbol)); s-name strdup(name); s-type type; s-scope currentScope; s-next table; table s; }插入操作放在头部的做法是典型的栈式符号表实现。查找时遍历整个链表也能正确找到嵌套作用域中的全局符号——因为作用域深的符号后插入排在链表前面查找到即返回不会覆盖成外层的同名符号。这就是“最近作用域优先”原则的代码体现。真正复杂的部分在leaveScope()的实现。一个常见的稳妥做法是插入时记录原有表头退出作用域时从表头一路释放到当前作用域第一个符号之前。另一种做法是给每个符号打作用域编号退出时惰性删除简单但会拖慢查找。4.2 语法错误恢复panic mode 其实够用课程设计的语法分析阶段一定会有错误处理的要求。Bison 自带的yyerror只在语法错误时打印一条消息然后立即终止分析。这在实际验收时往往不够——老师会输入一个带语法错误的程序期望分析器报错并指出位置而不是直接崩溃退出。最简单的有效策略是 panic mode恐慌模式在yyerror中打印出错 token 和所在行然后丢弃输入直到遇到同步 token通常是分号或右花括号再恢复分析。Bison 中可以在文法规则里显式插入error终结符来指定恢复点stmt : ; | expr ; | error ; { yyerrok; } ;这条规则的含义是语法出错时Bison 自动匹配error终结符然后跳过分号之前的所有 token再从分号之后重新开始分析。yyerrok宏的作用是把错误状态复位避免连续报错时状态机锁死。这样处理之后一个输入文件里多个独立错误能逐个报出来而不是第一处错就让整个分析戛然而止。4.3 有没有必要做到中间代码生成很多课程设计的题目描述里只写了“词法分析器 语法分析器”没提中间代码。这时要不要顺手做三地址码或语法树输出我的建议是语法树必须做三地址码可选。语法树是分析结果的自然产物也是验证文法正确性的唯一直观手段三地址码涉及语义处理需要给每个节点挂类型和值工作量和调试难度都上了一个台阶。如果题目对中间代码没有硬性要求把精力放在“能正确构造语法树 能输出树形结构”上性价比最高。树形输出的格式可以是简单的缩进打印每个节点一行子节点加缩进验收时非常直观。如果需要生成三地址码常见做法是在每个产生式的语义动作里为子节点生成临时变量编号再输出形如t1 a b的文本。5. 针对本标题的项目落地实战两个压缩包里的经典写法5.1 最小可行方案Flex Bison 直通结合上面各章的底层准备现在给出一个最小的 Flex Bison 完整项目骨架可以直接套用到 UESTC 这类课程设计的报告和验收中。项目目录建议按下面的结构摆放project/ ├── lexer.l # Flex 词法规则 ├── parser.y # Bison 语法规则 ├── ast.h / ast.c # 语法树节点定义与打印 ├── symtab.h / symtab.c# 符号表 ├── Makefile # 一键编译 └── test/ # 测试用例Makefile 中最关键的三行编译命令是lexer.c: lexer.l flex lexer.l parser.tab.c parser.tab.h: parser.y bison -d parser.y all: lexer.c parser.tab.c gcc -o compiler lex.yy.c parser.tab.c ast.c symtab.c -lflBison 文件里要声明%locations才能拿到每个 token 的行列信息Flex 动作里必须维护好yylloc的值否则报错时定位永远是 1:1这一点在验收时会被追问。还有一种常见做法是 Flex 里用#line指令配合yyline变量手动维护行号遇到多行字符串或注释时尤其要小心否则后续所有报错行号都会漂移。另外yywrap()必须存在。链接-lfl会自动补一个返回 1 的默认版本但如果你在 Windows 下用 win_flex/bison这个库可能不存在此时在文件末尾手动实现int yywrap(void) { return 1; }即可绕过链接问题。5.2 手写路线递归下降 词法状态机另一条不需要 Flex/Bison 的纯手写路线同样适合课程设计前提是文法足够小。手写词法器时建议直接用一个状态标志变量模拟 DFA 状态而不是用前面那种“多分支判断”的写法。对于 C 语言子集状态至少需要开始态、标识符态、整数态、实数态、字符串态、注释态、结束态。一个很容易踩坑的细节是注释的右边界*/和除法运算符/共享同一个/字符词法分析器必须在读取/后预读下一个字符是*就进入注释态否则按除号处理。类似地//行注释要读到换行才结束。这些都是课程设计测试用例中必然覆盖的边界情况。手写递归下降时每个非终结符函数开头打印当前的 token 序列结尾打印“reduce”信息是快速定位错误最有效的方法。打印信息要包含 token 文本和行号不要只打印类型编号。调试时把输出重定向到文件里再和测试用例对照一眼就能看出是哪个产生式匹配失败。5.3 测试用例怎么设计测试用例是课程设计报告里最容易拉开差距的部分。不要只给一个“hello world”式的输入。至少要覆盖以下五类基本类型与变量声明、赋值、算术表达式验证核心功能运算符优先级嵌套如a (b c) * (d - e) / f验证语法树正确性错误输入系列未定义变量、类型不匹配、缺少分号、括号不匹配、非法字符验证错误恢复和报错定位边界输入空文件、只有注释、超长标识符、嵌套深达 50 层的括号表达式验证健壮性字符串和注释中包含关键字与保留字验证词法切分不受上下文干扰每一类测试都要在报告里贴出输入、期望输出、实际输出。如果实际输出和期望不一致直接在报告里写“该用例暴露了 XX 问题通过修改 XX 解决”这样的描述比任何结论都有说服力。6. 验证与进阶用 trace 选项和断言给分析器上保险正规式转换、FIRST/FOLLOW 集计算、LL(1) 冲突判断这些很多同学写进报告但没验证过。这里给出几个可操作的验证手段。第一招用断言语义验证语法树结构。每构造完一个语法规约立刻检查子节点数量和类型是否符合该产生式的预期不符合就assert(false)。这样可以保证“语法树上每一条边都有文法依据”是代码审查时最容易被老师认可的一点assert(node-type NODE_BINARY_EXPR); assert(node-children_count 3); assert(node-children[1]-type NODE_OPERATOR); // 中间是运算符第二招利用 Bison 的--reportall选项导出完整分析表。运行bison -d --reportall parser.y后会生成parser.output文件里面有所有状态下的 ACTION 和 GOTO 表。检查表中是否存在“冲突”标记如果有结合%left声明是否缺失排查。这一步能让“我调好了分析器”从口头描述变成可查的证据。第三招给递归下降分析器加一个 token 预读计数限制。超过阈值直接报“potential infinite recursion detected”。原因是某些文法虽然没有直接左递归但存在间接左递归比如A - B | x和B - A y递归下降进去就出不来。预读计数能帮你快速定位这类问题而不必等栈溢出static int depth 0; #define MAX_DEPTH 1000 void enter() { if (depth MAX_DEPTH) { fprintf(stderr, parse depth exceeded, possible left recursion\n); exit(1); } } void leave() { depth--; }第四招用yydebug启动 Bison 内置的解析轨迹输出。在代码里设置extern int yydebug; yydebug 1;或者在运行时加--debug参数就能看到每一步是移进还是归约、当前栈的内容是什么。学习 LALR 分析表的行为时这比盯着parser.output死看效率高得多。以上这些技巧不止是从“代码能跑”到“我能解释它为什么这样跑”的跨越也是课程设计验收和面试里拉开差距的细节所在。把它们落到你的压缩包里那这份 UESTC 编译原理大作业才真正算你自己的东西。本文还有配套的精品资源点击获取