C语言词法分析器与语法分析器课程设计：从状态机到递归下降

简介这是一份《编译原理课程设计》报告书围绕C语言词法分析器和C-语言语法分析器的设计与实现展开。文档从实验目的与意义切入详细梳理C语言保留字、符号、标识符等词法特点给出正则表达式定义、Token类型及类型代码并结合DFA状态转换图讲解词法分析器的工作流程。内容包含注释DFA与词法分析DFA等状态图可帮助读者直观理解自动机如何识别数字、标识符、字符串和运算符同时说明语法分析器的工作原理适合计算机专业学生完成编译原理课程设计、撰写实验报告或复习相关考点时参考。资源包为单个doc文档大小约379KB目录结构完整兼具报告模板与实现思路参考价值已有274人学习下载对想快速理清DFA构造、Token分类和语法分析整体框架的学习者尤为实用。1. 从一个答辨现场翻车说起刚拿到“C语言词法分析器和C语言语法分析器编译原理课程设计报告书”这个题目时多数人第一反应是去网上找一份现成的代码改一改但我见过太多人代码跑起来了、报告却答不上来。老师指着状态转移图问“为什么这个状态遇到字母会跳到标识符状态”你不说清楚报告写得再厚也白搭。这篇笔记就是为准备做这个课程设计的你写的——我把词法分析器和语法分析器的最小可运行实现、报告书该怎么组织、以及最容易让程序“看着能跑、答辩就翻车”的坑都摊开讲。前半部分适合新手照步骤搭后半部分适合熟手核对设计边界。核心目标很简单让代码和报告书互相对得上答辨时心里有底。2. 词法分析器把字符流切成 token 才是编译的第一关2.1 为什么要手写状态机正则表达式只是思路不是交付物词法分析器要解决的第一个问题是把 C 语言源代码这个超长字符串切成有意义的“单词”。int a 42;在编译前端眼里不是五个字符而是五个 token关键字int、标识符a、赋值运算符、数字常量42、分号;。每个 token 至少要带两类信息类别是什么、原始文本是什么。常见做法是维护一个TokenType枚举加一个字符缓冲区类别决定后续语法分析怎么消费文本用于报错和生成符号表。你完全可以靠正则表达式把规则写出来然后用 flex 自动生成分析器但课程设计的评估重点往往不是“能不能跑”而是“有没有把状态转移的逻辑说清楚”。手写词法分析器通常意味着用一个有限自动机DFA来扫描字符流每读一个字符就依据当前状态决定下一个状态状态标到某个“接受态”时输出一个 token。这样一个switch (state)或者二维状态转移表就能画成老师最爱看的状态转移图也方便你在答辩时直接指出“这个分支对应图上的哪条弧”。C 语言词法上的坑其实很固定空白字符要跳过但必须记录换行标识符能包含数字但不能以数字开头关键字本质上是“已经被预留的标识符”数字常量不能写成12abc运算符有、、这种最长匹配问题。手写状态机时我会把字符先分类再喂给状态迁移逻辑而不是每个状态堆几十个if否则代码会膨胀到难维护。字符分类可以简单定义为字母或下划线、数字、空白、运算符、界符。这样状态转移表的规模可以被压得很小。2.2 用状态转移表实现一个能跑的最小词法分析器下面这段代码是我常用的最小骨架它只覆盖标识符、数字和几个运算符但结构是完整的读一个字符按当前状态决定迁移到达接受态后回退一个字符再返回 token。这里的“回退一个字符”很关键因为很多 token 的结尾要靠读到不属于它的字符才能判断出来不把那个字符放回去就会丢字符。#include stdio.h #include string.h #include ctype.h #define TOKEN_MAX 128 typedef enum { T_EOF, T_ID, T_NUM, T_ASSIGN, T_ADD, T_SUB, T_MUL, T_DIV, T_LP, T_RP } TokenType; typedef struct { TokenType type; char text[TOKEN_MAX]; int line; } Token; typedef enum { ST_START, ST_ID, ST_NUM, ST_DONE } State; static Token make_token(TokenType t, const char *text, int line) { Token tk; tk.type t; tk.line line; strncpy(tk.text, text, TOKEN_MAX - 1); tk.text[TOKEN_MAX - 1] \0; return tk; } Token next_token(FILE *fp, int *line) { int ch; char buf[TOKEN_MAX]; int len 0; State st ST_START; while ((ch fgetc(fp)) ! EOF) { switch (st) { case ST_START: if (isspace(ch)) { if (ch \n) (*line); continue; } if (isalpha(ch) || ch _) { buf[len] (char)ch; st ST_ID; } else if (isdigit(ch)) { buf[len] (char)ch; st ST_NUM; } else { switch (ch) { case : return make_token(T_ASSIGN, , *line); case : return make_token(T_ADD, , *line); case -: return make_token(T_SUB, -, *line); case *: return make_token(T_MUL, *, *line); case /: return make_token(T_DIV, /, *line); case (: return make_token(T_LP, (, *line); case ): return make_token(T_RP, ), *line); default: fprintf(stderr, 无法识别的字符: %c\n, (char)ch); return make_token(T_EOF, , *line); } } break; case ST_ID: if (isalnum(ch) || ch _) { if (len TOKEN_MAX - 1) buf[len] (char)ch; } else { ungetc(ch, fp); st ST_DONE; } break; case ST_NUM: if (isdigit(ch)) { if (len TOKEN_MAX - 1) buf[len] (char)ch; } else { ungetc(ch, fp); st ST_DONE; } break; default: break; } if (st ST_DONE) break; } buf[len] \0; if (st ST_ID) return make_token(T_ID, buf, *line); if (st ST_NUM) return make_token(T_NUM, buf, *line); return make_token(T_EOF, , *line); }这段代码的逻辑说明ST_START是初始状态遇到空白就跳过并统计换行遇到字母或下划线跳入ST_ID遇到数字跳入ST_NUM遇到运算符直接返回单字符 token。ST_ID状态下持续吸收字母、数字、下划线直到读到一个不属于标识符的字符这时用ungetc把它退回输入流再标记ST_DONE。ST_NUM同理只吸收数字。最后ST_DONE触发循环结束返回 token。这个代码的参数和边界有几个要留意的地方TOKEN_MAX是缓冲区上限防止超长标识符溢出但这里只是静默截断实际课程设计里最好在截断时报错ungetc只能回退一个字符所以不能把已经读入的多个字符倒回去line用指针传进来是因为 token 结构体里要记录行号后续报错时能指出位置。要支持关键字也很简单ST_ID吸收完标识符后查一张关键字表如果命中就把类型改成对应的关键字类型。常见的做法是建立一个const char *keywords[]数组用strcmp线性查量不大时性能完全够。2.3 词法分析报告书的核心素材token 类别表、状态转移图和测试输出报告书的词法部分不是让你堆代码而是要让老师一眼看到“你设计了哪些 token、状态怎么流转、测试覆盖了什么”。我会在报告里放三样东西token 类别表、状态转移图、一组带截图的测试用例。token 类别表用表格列得非常具体。类别类型枚举样例说明关键字T_IF, T_ELSE, T_INT 等if, else, int在标识符识别后查表得到标识符T_IDfoo, _x, a1字母或下划线开头后跟字母/数字/下划线数字常量T_NUM0, 42, 007至少一位数字赋值运算符T_ASSIGN单字符运算符算术运算符T_ADD, T_SUB, T_MUL, T_DIV - * /单字符运算符界符T_LP, T_RP( )单字符界符状态转移图可以手画也可以用 Graphviz 的 dot 语法生成但不建议在报告里贴太复杂的图。只要画出ST_START - ST_ID - ST_DONE和ST_START - ST_NUM - ST_DONE这两条主路径再加上空白跳过和错误状态即可。老师问得最多的反而是“如果输入是 123abc你的分析器怎么处理”因为很多实现会把数字吸收完再遇到字母时报错或者直接输出两个 token这个边界你要先想清楚然后在报告里写“123abc 属于非法词法单元遇到数字后紧跟字母应报错”。测试输出建议用真实命令行截图不要贴那种在 IDE 里跑出来的杂窗口。我一般会准备三段输入一段是普通表达式一段是含空行、制表符和注释如果有的代码一段是故意出错的123abc。词法分析器只需要把每个 token 的类型和文本打印出来例如T_ID: a、T_NUM: 123截图放在报告里就能验证工作量。3. 语法分析器把 token 流按要求组合成语法结构递归下降最稳3.1 文法设计先消除左递归再写分析函数词法分析器把int a 42;切成了六个 token语法分析器要做的是判断这个序列是否符合 C 语言的语法规则并且构建出一棵语法树。课程设计里最常见的实现是递归下降分析因为它思路直白、代码量可控而且报告书里可以画 LL(1) 分析表来配合说明。如果选 LR 类分析工具报告书会显得像黑匣子答辨时反而难讲清楚。递归下降要求文法最好是 LL(1) 的也就是每个非终结符在展开时要能根据当前 token 唯一决定走哪个产生式。因此第一步是先定义一个小型 C 语言子集文法然后消除左递归。下面这个文法是我常用的版本它覆盖赋值语句、表达式、括号和四则运算足够支撑一个课程设计演示。program : stmt_list stmt_list : stmt stmt_list | ε stmt : assign_stmt assign_stmt: id expr ; expr : term expr_tail expr_tail : term expr_tail | - term expr_tail | ε term : factor term_tail term_tail : * factor term_tail | / factor term_tail | ε factor : id | num | ( expr )注意这里的expr_tail和term_tail都是从右递归描述的因为expr产生式已经改写了原始的左递归形式expr : expr term会让递归下降掉进无限循环。为什么左侧递归会死循环因为parse_expr()函数进去第一件事还要调parse_expr()token 一个都没消费栈很快就溢出了。所以“消除左递归”不是可有可无的包装而是必须落实的代码约束。报告书里写文法时最好用产生式列表加一段说明的方式不要只贴一个 ebnf 文件。我会为每个非终结符标出 First 集合因为 First 集合决定了递归下降函数用什么 token 作为入口判断。例如expr的 First 是{ id, num, ( }那么在parse_stmt里看到这三种 token 之一就知道该进入表达式解析。Follow 集合则用来处理空产生式比如expr_tail遇到;或)时要停止继续吃运算符。3.2 递归下降核心代码能检查赋值语句并打印错误位置的最小实现下面这段代码实现了对赋值语句和表达式的语法检查。它没有真正生成语法树节点而是把关注点放在“能不能匹配成功、出错位置在哪”这是课程设计最稳的起点。你可以在它的基础上扩展 if/else 或 while也可以把每个函数改成返回节点指针来构造 AST。#include stdio.h #include stdlib.h typedef enum { T_EOF, T_ID, T_NUM, T_ASSIGN, T_ADD, T_SUB, T_MUL, T_DIV, T_LP, T_RP, T_SEMI } TokenType; typedef struct { TokenType type; char text[128]; int line; } Token; static Token current; static int parse_error 0; static void next_token(void) { // 这里替换成上一章实现的 next_token并从全局 FILE* 中读取 } static void error(const char *msg) { if (!parse_error) { fprintf(stderr, 第 %d 行 语法错误: %s\n, current.line, msg); parse_error 1; } } static int match(TokenType t) { if (current.type t) { next_token(); return 1; } return 0; } static void parse_factor(void) { if (current.type T_ID || current.type T_NUM) { next_token(); } else if (current.type T_LP) { next_token(); parse_expr(); if (!match(T_RP)) error(缺少右括号); } else { error(表达式里出现了意外的 token); } } static void parse_term_tail(void) { if (current.type T_MUL || current.type T_DIV) { next_token(); parse_factor(); parse_term_tail(); } } static void parse_term(void) { parse_factor(); parse_term_tail(); } static void parse_expr_tail(void) { if (current.type T_ADD || current.type T_SUB) { next_token(); parse_term(); parse_expr_tail(); } } static void parse_expr(void) { parse_term(); parse_expr_tail(); } static void parse_assign_stmt(void) { if (current.type T_ID) { next_token(); if (match(T_ASSIGN)) { parse_expr(); if (!match(T_SEMI)) error(赋值语句缺少分号); } else { error(标识符后面缺少赋值符号); } } else { error(语句必须以标识符开头); } } static void parse_program(void) { while (current.type ! T_EOF) { parse_assign_stmt(); } }这段代码的函数调用链对应了文法parse_program循环消费语句parse_assign_stmt先看T_ID再吃赋值号和表达式parse_expr调parse_term再调parse_expr_tailparse_expr_tail遇到加号或减号就再吃一个parse_term并递归。parse_error是个保险开关一旦出错就不再叠加报错避免输出几十条噪声。老师追问“为什么没有考虑优先级”时你就可以回答expr_tail只处理加减、term_tail只处理乘除天然保证了乘除先于加减。这个实现里最容易忽视的是“没有 token 消耗的死循环”。如果把expr_tail写成if (current.type T_ADD) parse_term();而忘了递归调用expr_tail那么在遇到连续两个加号时就会漏分析。另一个隐藏问题是next_token的实现要跳过空格和注释否则current会停留在空白 token 上。常见做法是词法分析器遇到空白直接跳过不在 token 流里产生空白类型这样语法分析器就不需要处理。3.3 报告书中的 First 和 Follow 集合手算的过程比结论更值钱语法分析部分的报告书不能只放代码至少要有一节叫“预测分析表的构造”里面写出几个关键非终结符的 First 和 Follow 集合。计算过程其实不复杂但很多同学喜欢直接抄网上的结论导致和代码不一致。比如上面这个文法expr的 First 集合来自term而term的 First 集合来自factor所以First(expr) First(term) { id, num, ( }。expr_tail的 First 是{ , - }但因为存在ε产生式Follow(expr_tail) 还需要看谁能在它后面出现。非终结符First 集合Follow 集合program{ id }{ EOF }assign_stmt{ id }{ EOF, id }expr{ id, num, ( }{ ;, ) }expr_tail{ , - }{ ;, ) }term{ id, num, ( }{ , -, ;, ) }term_tail{ *, / }{ , -, ;, ) }factor{ id, num, ( }{ *, /, , -, ;, ) }报告书里写这张表的时候我会附一句“手算方式是非终结符产生式右部首符号如果是终结符就收入 First如果是非终结符就递归求其 FirstFollow 则从开始符号加$然后扫描所有产生式把某个非终结符后面的符号收入跟随集合”。不要小看这句话答辨时老师很可能让你现场算一个。计算完后还可以画出一个简化的 LL(1) 预测分析表横轴是终结符纵轴是非终结符表里填产生式编号这样就和递归下降函数一一对应。4. 课程设计报告书把代码过程变成老师看得懂的逻辑链4.1 报告书的标准结构不是流水账而是设计证据链这门课程的报告书一般要求 Word 文档标题里那份“报告书.doc”通常包含封面、摘要、需求分析、总体设计、详细设计、测试结果和总结。很多同学把“详细设计”写成大段源代码这是报告书最常犯的错误。老师的阅读预期不是 read the code而是“你遇到了什么问题、用什么方案解决、最终效果如何”。所以每个章节都应该服务于一条逻辑链输入是什么、输出是什么、中间经历了哪些阶段。我写报告书时会在“需求分析”一节先明确输入输出格式。例如输入是任意一个.c文件输出是两份结果词法分析输出 token 列表语法分析输出“语法正确”或错误行号。这里不要用含糊的“支持 C 语言大部分语法”要精确说“支持变量赋值、表达式、变量声明、if/else如果做了”。把范围写小一点没有坏处老师看到你能自觉限定子集反而会觉得你有工程意识。总体设计一节建议画一张分层的模块图输入源程序 → 词法分析器 → token 流 → 语法分析器 → 分析结果。这个图用 Word 里的文本框画就行不需要炫技。每一层之间用箭头标出传递的数据结构比如“Token 数组”或“出声生成器回调”。课程设计的规模不大一张图就能讲清楚架构。详细设计是最厚的一章我习惯拆成“词法分析设计与实现”“语法分析设计与实现”“错误处理设计与实现”三小节。每小节先写数据结构定义再写算法步骤最后贴关键代码片段。代码不要整段贴只贴核心状态转换或递归调用链并紧跟一段文字说明为什么这样写。比如贴ST_ID分支时说明“这里用 ungetc 回退字符避免丢 token”。这种细节比代码块本身更让老师放心。4.2 测试用例怎么设计才能覆盖“正常、边界、错误”三类报告书的测试部分是最容易凑字数的但也是老师判断你有没有真正运行过的地方。我会设计一个测试用例表格每条用例包含“输入片段、预期输出、实际输出、是否通过”。正常用例是像a 1 2 * (3 - 4);这样的普通表达式边界用例包括连续多个空格、空行、以关键字开头的标识符比如int2 3;其中int2应该是标识符而不是关键字错误用例包括a b;缺少分号、a (b;缺少右括号、123abc词法错误。这些用例不要只放在报告里还要在验收现场跑一遍。我通常准备一个test_cases/目录每个文件只装一个用例然后写一个批处理脚本逐个调用分析器把输出重定向到results/目录。报告书里放一个汇总表就行具体运行截图放两张一张全对过一张故意报错。报错截图反而更显真实因为没有任何分析器能处理所有非法输入。这里还有一个细节输出格式要稳定。词法分析器每行输出(行号, 类型, 文本)语法分析器出错时输出Error at line N: ...。这样测试用例表格里可以方便地贴预期输出。不要用 IDE 自带的可视化界面做演示因为答辩电脑上的调试环境不一定一样。命令行输出最保险。4.3 报告里的图与截图状态转移图、语法树、调试痕迹状态转移图和语法树是这门课程设计最强的视觉证据。我建议至少画两幅图词法分析器的状态转移图和a 1 2;对应的语法分析树。状态转移图可以手工画节点和箭头但要保证和代码分支一致。比如代码里有ST_START、ST_ID、ST_NUM三个状态图里就不能多画一个ST_STRING。老师很喜欢在图上找一个代码里不存在的状态这是送分题也是送命题。语法分析树的画法更简单把产生式展开过程画成树形结构即可。比如表达式1 2 * 3的树根是expr左子树term - factor - 1右子树expr_tail - term - factor 2嵌套term_tail - * factor 3。如果你在代码里实现了抽象语法树节点截图打印节点时可以用括号表示法(expr (term (factor 1)) (expr_tail (term ...)))报告里贴这个输出不会再被质疑“你到底建树没有”。调试截图方面我用得最多的不是断点截图而是给词法分析器加一个-debug参数用它打印 token 流和语法分析栈。比如运行./parser -debug test.c时输出token: T_ID texta token: T_ASSIGN text token: T_NUM text1 ... parse assign_stmt at line 1 parse expr at line 1这种输出比内存视图更直白也更容易在报告书里排版。如果你要用 GDB 调栈也可以截一张bt命令的图但要有注释解释清楚调用栈对应哪些递归函数。报告书里不要放没有说明的截图每张图下面写“这张图说明了什么”。5. 避坑指南词法语法分析器课程设计最常见的五个坑5.1 现象关键字和标识符串门输入int main时词法分析器把int输出成T_ID导致语法分析器把声明语句当成赋值语句处理报错位置莫名其妙。原因通常是关键字表匹配时机错了。如果先判断“以字母开头就返回标识符”那么int永远来不及查关键字表。解决方法是先把整个标识符吸收进缓冲区闭包后再查关键字表。也就是说所有以字母或下划线开头的字符都走同一条ST_ID状态吸收完后再统一分类是关键字就返回关键字类型否则返回T_ID。这条规则在报告书里用一句话写清楚就能避免答辩时被指出设计缺陷。5.2 现象递归下降遇到表达式就死循环很多同学写完parse_expr后一运行就卡死或者栈溢出。原因几乎都是文法没有消除左递归。expr : expr term看起来很美但代码里parse_expr()第一行又调用parse_expr()token 一个没吃编译器只会给我们一个 segmentation fault。解决方法是把左递归改写为右递归也就是前面那套expr_tail方案。另外还要检查每个非终结符函数是否至少消费了一个 token如果没有进入下一层递归前就要判断当前 token 是否能匹配产生式的开头否则即使是右递归也可能互相空转。5.3 现象报告中的 First/Follow 表和代码不一致报告书上写First(expr) { id }但代码里明明允许表达式以(开头答辩时老师翻到这一页就把你温柔地敲打一顿。原因通常是先写了代码再倒推手算集合时算错或抄了别人的表。解决办法是在代码里写一个调试函数根据已实现的产生式现场输出 First 集合然后把输出截图作为报告书的依据。至少要在报告里写清楚“表中只列出关键非终结符完整结果见附录”不要硬撑一个看起来完整的表。5.4 现象遇到注释或预编译指令直接乱掉C 语言源代码里几乎都会有//、/* ... */和#include。如果词法分析器没有处理注释遇到//时会把第二个/误解为除号然后再把整行注释内容当成一堆未知 token语法分析必然翻车。解决方法是给状态机加两个注释状态ST_LINE_COMMENT和ST_BLOCK_COMMENT。遇到/时偷看一眼下一个字符如果是/就进入行注释状态读到换行返回ST_START如果是*就进入块注释状态直到遇到*/。#include这类预编译指令不在大多数课程设计范围内最简单的处理是在需求分析里声明“只支持普通函数体内的语句不支持预处理指令”但这会让测试输入受限。建议至少在词法分析器里把#开头的一整行跳过这样你就可以拿简单的测试文件而不至于崩掉。5.5 现象token 缓冲区越界导致报错位置不准当源代码里出现一个超长标识符比如连续 200 个字符没有空格缓冲区buf[TOKEN_MAX]会越界。现象不是立刻崩溃而是后续 token 文本乱掉最后语法分析器在错误的位置报错。原因很简单写缓冲区时没有检查长度len超过了TOKEN_MAX。解决方法是像前面代码那样在每次写buf[len]之前判断len TOKEN_MAX - 1并在越界时打印错误“标识符长度超过上限”。不要忽略这种看似边缘的输入老师最爱拿一个 200 字符的变量名来测试你的边界意识。其实这背后就是 C 语言基本功里的数组和指针边界问题你可以在报告书的“错误处理”一节专门提属于加分项。6. 进阶验证在答辩现场让程序“说清楚”自己做了什么6.1 用 GDB 调出 token 流打给老师看如果你已经把代码跑通最推荐的验收前做法是给程序加一个调试开关把词法分析和语法分析的内部过程打印出来。不要临时在答辩时开 GDB 单步那样太慢而且老师可能不耐烦。我习惯的做法是在main函数里用环境变量或命令行参数控制输出级别传-v时打印每个 token传-p时打印语法分析进入和退出的非终结符名。这样你只要提前跑一遍把-v输出保存下来报告书和 PPT 里都能用同一份数据。如果老师现场问“你这个 token 流里面为什么没有空格类型”你就打开命令行当场跑给他看答案自然就有了。6.2 扩展一个小目标加上 if/else 的作用域判断完成基础赋值语句后再花半天给语法分析器加一个if语句课程设计档次会明显不一样。文法只需要加stmt : if ( expr ) stmt递归下降函数则是在parse_stmt里先判断current.type T_IF然后吃掉(、解析表达式、吃掉)再递归调用parse_stmt()。这里最大的坑是else的悬挂二义性你可以直接规定“每个if都必须有else”或者实现“就近匹配”。报告书里把这个问题写出来本身就是很好的讨论素材。变量作用域可以先不实现但可以在符号表里预留一个保存变量类型的字段词法分析器遇到int、float这些关键字时记录当前声明的变量名供语法分析器做重复声明检查。6.3 验收前十分钟把报告书里的图与代码逐行对齐最后一次检查时我会把报告书里的每一张状态转移图、每一条 First/Follow 记录和代码里的对应函数列一张对照表。图上有ST_ID状态代码里就必须有对应的case ST_ID:报告里写Follow(expr_tail) { ;, ) }代码里就必须保证parse_expr_tail遇到分号和右括号时能够正常返回而不是报错。以前我总把报告书放在最后写结果图和代码对不上答辩前熬夜改非常痛苦。后来我改成先写测试用例再实现代码最后填报告返工少很多。这个顺序你如果还没开始很值得试一试。希望帮到你。本文还有配套的精品资源点击获取