编译原理课设：手写词法分析器与递归下降语法分析器实践

简介西南交大编译原理课程设计报告围绕词法分析器和语法分析器展开完整展示了一个C语言实现的词法分析器从结构设计到编码调试的全过程。报告首先画出词法分析器总体框图说明源程序输入缓冲区、扫描缓冲区、数据预处理及状态转换图之间的协作关系随后基于保留字表与种别码设计给出GetChar、GetBC、ConCat、Reserve、Retract等核心子程序的功能说明与源码实现。针对标识符、常数、运算符、界符的识别流程报告还提供了详细流程图和注释清晰的完整程序便于读者直接运行验证语法分析部分则介绍如何基于词法单元构建抽象语法树帮助理解递归下降或算符优先分析的基本思想。资源为单个docx文档共1份文件压缩包仅443KB内容紧凑便携。从西南交大课程设计视角出发适合计算机专业本科生、编译原理课程学习者以及准备相关实验与答辩的学生参考已有147人学习使用是一份能直接用于课程报告撰写和实验复现的参考范本。1. 编译原理课程设计在考什么字符流怎么变成一棵语法树西南交大编译原理课程设计词法分析器和语法分析器这个题目挂在课程页上只有十几个字但等你真正打开实现就会发现它考察的是两件完全不同的事词法分析器要把源代码的字符流切成一个个有类型的 token语法分析器再把这些 token 按文法拼成一棵合法的语法树。也就是说这个课设不是让你背正则表达式或者 FIRST 集定义而是让你亲手写两个能跑的程序把一个源文件从“字符串”变成“结构”。它适合正在准备验收的学生也适合那些想把编译原理前端原理真正串起来的人。一个反直觉结论是别迷信 flex / bison手写版本在答辩时反而更容易讲清楚因为每一行代码对应什么规则你一掀开就能说出来。2. 词法分析器怎么落地一张 Token 表和状态分支写出最小实现词法分析器的工作范围其实非常窄读字符、跳过空白、识别单词、返回带类型的 token。它不需要理解语义只需要回答“这一串字符是什么类别的词”。课设文档通常不规定你要实现完整的 C 语言而是实现一个子集常见的就是关键字、标识符、整数常数、运算符和界符这五类。子集没给全时我一般会自己定一份并写进报告这样验收时对方至少知道边界在哪。2.1 先定义 Token 分类把要识别的单词列成一张表动手写代码之前第一件事是把语言子集里所有单词分类列出来。这个表既是后续代码的骨架也是报告里最值得放的一张表。我通常按“分类 / 单词例子 / 模式”三列来列分类单词例子匹配模式关键字int char if else while return按单词表精确匹配标识符count _tmp var2[a-zA-Z_][a-zA-Z0-9_]*整数常数0 123 999[0-9]运算符 - * / ! 最长匹配先试两字符再试单字符界符; , ( ) { }单字符匹配这个表里有一个容易忽略的点种别码不需要一个单词编一个码。关键字可以一类一个码比如 TK_INT 和 TK_CHAR 分开但所有界符合成一个 TK_SEMI 就有点偷懒建议每个符号独立一个枚举值后续语法分析器写起来会清爽很多。我自己吃过这个亏一开始把(和)都算作 TK_PAREN结果语法分析器里被迫再比对 lexeme 才能区分左右括号代码一下子变丑。2.2 手写词法分析器核心循环与关键字查表确定了 Token 分类之后就可以写一个最小实现。下面是 C 版本的骨架核心思路是“每调用一次 get_token() 返回一个 token”词法分析器本身不保存状态调用方通过循环反复拿下一个 token。代码里把关键字查表集中放在一个函数里避免在识别分支里写一堆 if 比较。#include stdio.h #include ctype.h #include string.h typedef enum { TK_ID, TK_NUM, TK_INT, TK_CHAR, TK_IF, TK_ELSE, TK_WHILE, TK_RETURN, TK_PLUS, TK_MINUS, TK_STAR, TK_SLASH, TK_ASSIGN, TK_EQ, TK_NE, TK_LT, TK_LE, TK_GT, TK_GE, TK_SEMI, TK_COMMA, TK_LPAREN, TK_RPAREN, TK_LBRACE, TK_RBRACE, TK_EOF, TK_ERROR } TokenType; typedef struct { TokenType type; char lexeme[64]; int line; } Token; static int line_no 1; static TokenType keyword_type(const char *s) { if (!strcmp(s, int)) return TK_INT; if (!strcmp(s, char)) return TK_CHAR; if (!strcmp(s, if)) return TK_IF; if (!strcmp(s, else)) return TK_ELSE; if (!strcmp(s, while)) return TK_WHILE; if (!strcmp(s, return)) return TK_RETURN; return TK_ID; } Token get_token(void) { Token tok; int c; int i 0; tok.line line_no; tok.lexeme[0] \0; while ((c getchar()) || c \t) {} if (c \n) { line_no; return get_token(); } if (c EOF) { tok.type TK_EOF; return tok; } if (isalpha(c) || c _) { while (isalnum(c) || c _) { if (i 63) tok.lexeme[i] (char)c; c getchar(); } ungetc(c, stdin); tok.lexeme[i] \0; tok.type keyword_type(tok.lexeme); return tok; } if (isdigit(c)) { while (isdigit(c)) { if (i 63) tok.lexeme[i] (char)c; c getchar(); } ungetc(c, stdin); tok.lexeme[i] \0; tok.type TK_NUM; return tok; } tok.lexeme[0] (char)c; tok.lexeme[1] \0; switch (c) { case : tok.type TK_PLUS; return tok; case -: tok.type TK_MINUS; return tok; case *: tok.type TK_STAR; return tok; case /: tok.type TK_SLASH; return tok; case ;: tok.type TK_SEMI; return tok; case ,: tok.type TK_COMMA; return tok; case (: tok.type TK_LPAREN; return tok; case ): tok.type TK_RPAREN; return tok; case {: tok.type TK_LBRACE; return tok; case }: tok.type TK_RBRACE; return tok; case : if ((c getchar()) ) { tok.lexeme[1] ; tok.lexeme[2] \0; tok.type TK_EQ; } else { ungetc(c, stdin); tok.type TK_ASSIGN; } return tok; case !: if ((c getchar()) ) { tok.lexeme[1] ; tok.lexeme[2] \0; tok.type TK_NE; } else { ungetc(c, stdin); tok.type TK_ERROR; } return tok; case : if ((c getchar()) ) { tok.lexeme[1] ; tok.lexeme[2] \0; tok.type TK_LE; } else { ungetc(c, stdin); tok.type TK_LT; } return tok; case : if ((c getchar()) ) { tok.lexeme[1] ; tok.lexeme[2] \0; tok.type TK_GE; } else { ungetc(c, stdin); tok.type TK_GT; } return tok; default: tok.type TK_ERROR; return tok; } }这段代码的核心设计有两个。第一关键字和标识符走同一条识别路径先按[a-zA-Z_][a-zA-Z0-9_]*把完整单词读进 lexeme再交给 keyword_type 查表。这个顺序是词法分析器里最关键的约定先识别标识符再查关键字表能保证int不会被当成普通变量名。第二运算符分支统一使用“先读下一个字符尝试两字符运算符不匹配就 ungetc 退回”的写法保证不会裂成和。lexeme 长度限制 64对课设足够溢出时直接截断但你要知道这是个隐藏边界如果后面做符号表比较截断后的名字可能撞车。2.3 处理注释与非法字符词法错误也要有行号很多课设文档不会强制要求处理注释但测试用例里大概率会放一两个带注释的样例。我的建议是支持/* ... */块注释因为它能体现你在状态机上的考虑。实现不复杂在 get_token 的case /分支里读到下一个字符是*时进入一个循环不断读字符直到遇到*/或 EOF如果遇到 EOF 说明注释没闭合返回一个带行号的 TK_ERROR。这里有一个容易翻车的点注释里的换行也要计入 line_no否则后续所有报错行号都会偏。非法字符的处理更简单任何不在识别表里的符号比如、#都返回 TK_ERROR由上层语法分析器统一报告“第几行出现非法字符”。不要在词法分析器里 printf 直接输出错误把错误信息留给上层统一管理这样词法分析和语法分析的报错风格才能保持一致。2.4 正则、DFA 和手写状态分支的关系报告里怎么写才不露怯课设报告里通常要求写“词法分析器的设计原理”如果你直接说自己手写了一个分支循环老师可能会追问 DFA 的事。常见做法是在报告里把这张 Token 分类表映射成一张状态转换图然后说明手写分支就是状态转换图的直接翻译。比如标识符状态、数字状态、运算符状态各对应一个分支ungetc对应状态的“不消耗下一个字符”返回值。这样即没有用 flex 生成代码也能把词法理论和你手写实现之间的对应关系讲清楚。3. 语法分析器怎么选型递归下降比 LL(1) 表驱动更适合课设语法分析器的任务很简单拿到词法分析器给的 token 流判断它们是否满足文法。但这个“判断”有两种主流做法递归下降和 LL(1) 表驱动。我的结论是课设场景优先递归下降除非你的文档里明确要求必须提交预测分析表。递归下降的每个函数对应一个非终结符错误定位和调试都直观表驱动的好处是形式化味道更浓但查表、维护分析表的代码量不小一个测试样例挂掉你很难一眼看出是表算错了还是驱动代码写错了。3.1 课设语言的文法用 EBNF 定义天然避开左递归定义一个课设子集语言的文法我建议直接用 EBNF 风格而不是教科书式的 BNF原因很实际EBNF 里的*和?直接对应代码里的循环和条件而 BNF 里的左递归需要先改写才能翻译成递归下降函数。下面是我常用的一套最小文法program - stmt_list stmt_list - stmt stmt_list | ε stmt - if_stmt | while_stmt | decl_stmt | expr_stmt if_stmt - if ( expr ) { stmt_list } while_stmt - while ( expr ) { stmt_list } decl_stmt - (int | char) id ; expr_stmt - expr ; expr - term (( | - ) term)* term - factor (( * | / ) factor)* factor - id | num | ( expr )注意expr和term的写法。教科书上常见expr - expr term这种左递归文法直接翻译成代码会在函数第一行就无限调用自己栈溢出翻车。EBNF 里的(term (( | -) term)*)改写成了循环递归下降函数里对应一个 while 循环完全没有左递归问题。报告里建议把两版文法都写出来先写 BNF 版本再写消除左递归后的 EBNF 版本这正好是“语法分析器设计”这一节需要的内容。3.2 一个能跑的递归下降解析器match 与 advance 的配合递归下降的核心是三个函数advance() 负责推进 tokenmatch() 负责比对并报错每个非终结符一个函数。以下是一个最小可跑的解析结构Token lookahead; void advance(void) { lookahead get_token(); } void match(TokenType t) { if (lookahead.type t) { advance(); } else { printf(line %d: syntax error, expect token %d but got %d\n, lookahead.line, t, lookahead.type); synchronize(); // 错误恢复在第 4 章 4.3 展开 } } void parse_expr(void) { parse_term(); while (lookahead.type TK_PLUS || lookahead.type TK_MINUS) { advance(); parse_term(); } } void parse_term(void) { parse_factor(); while (lookahead.type TK_STAR || lookahead.type TK_SLASH) { advance(); parse_factor(); } } void parse_factor(void) { if (lookahead.type TK_NUM || lookahead.type TK_ID) { advance(); } else if (lookahead.type TK_LPAREN) { advance(); parse_expr(); match(TK_RPAREN); } else { printf(line %d: unexpected token in factor\n, lookahead.line); synchronize(); } } void parse_stmt(void) { switch (lookahead.type) { case TK_IF: advance(); match(TK_LPAREN); parse_expr(); match(TK_RPAREN); match(TK_LBRACE); parse_stmt_list(); match(TK_RBRACE); break; case TK_WHILE: advance(); match(TK_LPAREN); parse_expr(); match(TK_RPAREN); match(TK_LBRACE); parse_stmt_list(); match(TK_RBRACE); break; case TK_INT: case TK_CHAR: advance(); match(TK_ID); match(TK_SEMI); break; default: parse_expr(); match(TK_SEMI); break; } } void parse_stmt_list(void) { while (lookahead.type ! TK_EOF lookahead.type ! TK_RBRACE) { parse_stmt(); } } int main(void) { advance(); while (lookahead.type ! TK_EOF) { parse_stmt_list(); if (lookahead.type TK_EOF) break; } return 0; }这套代码有一个设计要点parse_stmt_list 没有用递归实现stmt_list - stmt stmt_list | ε而是用 while 循环效果和 EBNF 的*完全一致又规避了递归深度问题。每个函数只向前看一个 token 就决定走哪个分支这就是“预测分析”的含义。如果某一个 token 能同时进入两个分支文法就是有冲突的递归下降会写得很别扭这就是下面要说的 LL(1) 冲突检查。3.3 LL(1) 冲突检查为什么我的文法不会回溯递归下降能顺利写出来前提是文法是 LL(1) 的每个非终结符的每个候选产生式FIRST 集互不相交。以我上面的文法为例stmt 的四个候选分别以 TK_IF、TK_WHILE、TK_INT/TK_CHAR、以及 expr 的首个 tokenTK_ID/TK_NUM/TK_LPAREN开头两两没有交集所以 parse_stmt 里一个 switch 就能区分。如果不做这个检查你就会写出那种“先试一个分支不行再回头试另一个分支”的带回溯解析器运行慢且错误定位混乱。课设报告里建议手算一遍这组 FIRST 集列一个小表。比如expr的 FIRST 是 {TK_ID, TK_NUM, TK_LPAREN}stmt的 FIRST 是 {TK_IF, TK_WHILE, TK_INT, TK_CHAR, TK_ID, TK_NUM, TK_LPAREN}。如果将来扩展语言比如加一个for语句要重新检查它和现有候选是否冲突如果两个候选都以同一 token 开头就需要提取左公因子把公共前缀提到外面。3.4 表驱动 LL(1) 与递归下降怎么选答辩被追问时的答案如果你在文档里看到“用 LL(1) 分析法”的字样千万别慌。一种很稳妥的做法是报告里写 LL(1) 分析表预测分析表代码里用递归下降实现然后在文档里画出两者对应关系。表格驱动需要维护分析表二维数组和栈代码量反而更大而且表驱动的错误定位不如递归下降直观。真正被问到“为什么不用表驱动”时我一般这样答递归下降是预测分析的一种实现方式每个非终结符函数本质上就是分析表中的一行方向是等价的选择它是为了代码可维护性。这个回答比单纯说“好写”要硬气得多。4. 词法与语法怎么对接符号表、超前读与错误恢复的接口设计词法分析器和语法分析器单独写都很容易难的是对接。我第一次做这个课设时把词法分析器得到的 token 全部存进一个数组再交给语法分析器解析结果一个两百行的测试文件就把内存占了一大块而且报错行号全是乱的。后来我换成了“边读边解析”的方式语法分析器需要 token 时现场调用 get_token() 拿下一个。4.1 边读边解析一个 lookahead 就够用递归下降解析器永远只需要“当前 token”和“下一个 token”所以全局变量 lookahead 就足够。main 里第一步 advance() 把第一个 token 读进来之后每个 parse 函数通过 match 和 advance 消费 token。语法分析器从不需要回头重新看已经消费的 token这是递归下降的天然特性也让接口变得非常简单词法分析器暴露一个 get_token()语法分析器负责维护 lookahead。这种做法的好处是单遍扫描源文件再大内存也不怕代价是如果你想同时打印“token 流”和“语法树”就得在解析过程中边做边打印而不是先全部 token 化再慢慢分析。课设答辩时演示“输入一行代码输出 token 流和语法树”用边读边解析完全够。4.2 符号表登记时机、作用域和查找顺序符号表是热搜词里出现最多的概念也是词法分析和语法分析交汇的地方。课设里的符号表不需要做成复杂的哈希表一个数组加一个作用域深度标志就够了。常见的实现是“进入花括号块时 depth 加一退出时 depth 减一但符号条目不清除查找时从后往前找并且只认 depth 不超过当前深度的条目”。这样做的原因是同一个名字在内层作用域可以重新声明但查找时要先看到内层的而退出作用域后外层同名变量重新可见。#define MAX_SYMBOLS 256 #define MAX_NAME 64 typedef struct { char name[MAX_NAME]; int depth; } Symbol; static Symbol symtab[MAX_SYMBOLS]; static int sym_count 0; static int current_depth 0; void enter_scope(void) { current_depth; } void leave_scope(void) { current_depth--; } static int lookup_current(const char *name) { int i; for (i sym_count - 1; i 0; i--) { if (strcmp(symtab[i].name, name) 0 symtab[i].depth current_depth) { return 1; } } return 0; } int lookup(const char *name) { int i; for (i sym_count - 1; i 0; i--) { if (strcmp(symtab[i].name, name) 0 symtab[i].depth current_depth) { return 1; } } return 0; } void declare(const char *name) { if (lookup_current(name)) { printf(line %d: variable %s redeclared\n, lookahead.line, name); return; } strcpy(symtab[sym_count].name, name); symtab[sym_count].depth current_depth; sym_count; }登记时机要和语法分析器联动在 parse_stmt 的 TK_INT/TK_CHAR 分支里match(TK_ID) 之后立刻调用 declare(lexeme)在 parse_factor 里遇到 TK_ID 时调用 lookup查不到就报“未声明标识符”。这里的坑是词法分析器的 lexeme 是静态缓冲区下一次 get_token() 就会覆盖它所以声明和查找必须在拿到 token 的当下立刻使用 lexeme不要存到后面再用。4.3 错误恢复panic mode 是最简单的后悔药递归下降解析器最怕的就是遇到一个错误直接退出。测试脚本经常一次性喂十几个样例第一个样例挂了程序就停等于后面全白测。正确做法是“报错不退出跳到下一个安全位置继续解析”术语叫 panic mode。对语句级别的错误安全位置就是分号和右花括号它们是语句或块的自然边界。void synchronize(void) { while (lookahead.type ! TK_EOF) { if (lookahead.type TK_SEMI) { advance(); return; } if (lookahead.type TK_RBRACE) { advance(); return; } advance(); } }这里有一个容易忽略的细节遇到右花括号时要把这个 token 消费掉再返回。如果不消费外层块的 match(TK_RBRACE) 会看到同样的右花括号并再次消费导致块的边界错乱后续所有语句解析全部错位。还要在全局设置一个错误计数器连续报错超过比如 20 次就强制退出防止在极端坏输入下同步逻辑自身陷入死循环。4.4 调试输出把 token 流和行号对齐问题立刻少一半课设调试时最有用的是一个打印 token 的小函数。遇到语义错误时先打印当前 token 的类型和行号再打印它的 lexeme能快速定位是词法切错了还是语法规则写错了。我习惯在 main 里加一个命令行参数传-t就只打印 token 流不启动作语法分析传-p才进入解析。这样调试词法时不被打扰调试语法时又能随时看词法结果。5. 课设避坑与常见问题5 个让编译原理实验翻车的细节这里的每一条都是我实际写过之后才明白的。有些问题在课本习题里根本不会出现但测试用例一多就全暴露了。5.1 关键字被识别成标识符现象输入int a;词法分析器输出TK_ID(int) TK_ID(a) TK_SEMI语法分析器直接把 int 当成变量名后面的声明全乱套。原因识别标识符时先按字母规则读完整单词然后没有查关键字表就直接返回 TK_ID。解决在完成单词读取后必须调用 keyword_type 去查关键字表查到了就返回对应的关键字类型查不到才是 TK_ID。这个顺序千万不能颠倒。5.2 两字符运算符被拆成两个单字符现象输入a 1;词法输出变成TK_ID(a) TK_GT() TK_ASSIGN() TK_NUM(1)语法分析器在 factor 之后直接看到一个报文法错误。原因运算符分支只写了一个字符的 case遇到就立刻返回没有去尝试读下一个字符看是不是。解决在分支里先 getchar 试探下一个字符如果是就返回 TK_GE否则 ungetc 退回去返回 TK_GT。、、!三个符号都要同样处理。5.3 文法左递归导致递归下降栈溢出现象输入一个简单的表达式12;程序直接段错误。原因如果你把文法写成expr - expr term那 parse_expr 的第一行就会再次调用 parse_expr永远到不了终止条件栈直接爆掉。解决用前面写的 EBNF 循环版本或者先手工消除左递归。expr改成term (( | - ) term)*对应代码里的 while 循环。这个坑在换语言写 Java 版时也一样会出现Java 的栈深度虽然比 C 大但同样经不起无限递归。5.4 EOF 处理不当导致最后一条语句报错现象合法程序int a;被报告“缺少分号”。原因词法分析器在读到 EOF 后如果每次调用 get_token 都返回同一个 TK_EOF语法分析器可能在 EOF 之后再调用一次 advance()又拿到一个 TK_EOF如果 match 逻辑在 TK_EOF 上继续报错最后一条语句就会莫名其妙失败。解决get_token 里遇到 EOF 只返回一次 TK_EOF后续调用不再读文件。语法分析器里parse_stmt_list 的循环条件是lookahead.type ! TK_EOF lookahead.type ! TK_RBRACEmain 里也要在 TK_EOF 处停止解析。5.5 报错后直接退出测试脚本只过了第一个用例现象测试文件里有 10 个样例第一个样例有语法错误程序立即退出后面 9 个正确样例一个都没跑到测试结果非常难看。原因错误处理函数里直接调用了 exit()。解决把错误处理改成打印信息并计数然后调用 synchronize() 跳过错乱区域继续解析。只有错误数超过阈值比如 20才退出。这个简单策略能让单次运行覆盖几乎全部测试用例是课设验收时最加分的“健壮性”体现。6. 把课设从“能跑”做到“能答辩”三种自测与一个调试习惯6.1 准备五类回归样例用脚本一键跑完课设交之前我建议准备五类输入完全合法的程序、含非法字符的样例、运算符写错的样例、括号不匹配的样例、变量重复声明的样例。把这些样例存成独立文件再用一个 shell 脚本循环运行把输出和预期文本对比。每次改动词法或语法代码之后都跑一遍这个脚本实际效果比手动敲十条输入可靠得多。6.2 加一个调试开关让 token 流和语法树不再是黑匣子在 main 里用参数控制输出传-t时只打印 token 流传-p时打印“每次进入非终结符函数的名称”这相当于一个缩进版的语法树先序序列。答辩演示时先对同一段代码打印 token 流再打印解析过程整个分析过程一目了然老师就不需要盯着代码脑补程序在干什么了。代码组织上把 lexer、parser、symtab 拆成三个文件头文件里只暴露必要接口。报告里放 token 分类表、EBNF 文法和递归下降函数的对应关系这三样东西占一页纸就能讲清楚整个课设。我自己养成的一个习惯是每次只改一个文件然后立刻跑全部回归样例语法改动不碰词法用例词法改动不碰语法用例等全绿了再验证两者联调。这个习惯帮我少翻车很多次也希望帮到你。本文还有配套的精品资源点击获取