简介面向编译原理课程设计的完整报告书聚焦C语言词法分析器与C语言语法分析器的设计与实现能够帮助计算机专业学生完成课程设计报告撰写、掌握编译器前端核心原理。资源共1个doc文档压缩包约379KB内容覆盖实验目的与意义、C语言词法特点、正则表达式描述以及Token定义、Token类型代码、DFA状态转换设计等核心章节。其中词法分析器设计部分系统展示了如何利用确定性有限自动机识别数字、标识符、算术运算符、比较运算符、字符串与字符等Token也给出了保留字与特殊符号的完整分类语法分析器部分则阐述了编译器词法分析的工作流程方便读者理解从源码字符流到Token序列再到语法结构分析的整个过程。报告保留了清晰的章节层次和源码级枚举定义既可作为课程设计参考资料也可用于复习编译原理中的正则表达式、DFA等考点。已有274人学习浏览适合正在准备此类课程设计或希望系统梳理词法分析、语法分析实现思路的本科生下载学习。1. 编译原理课程设计怎么落到代码一份C语言词法分析器和语法分析器的完整报告很多人的编译原理课程设计卡在「DFA画出来了代码却不知道从哪一行开始写」。这份报告书的好处是它把词法分析器和语法分析器的实现路径整个串起来了先用正则表达式界定token再把token转化成DFA状态转移然后在scan.c里用getToken()把这个状态机变成真正的C代码语法分析部分则把C-语言的EBNF文法逐条映射成递归下降函数最终输出一棵TreeNode语法树。它解决的是课设最磨人的三件事——词法边界怎么定、语法树怎么建、测试用例怎么设计。适合正在做编译原理课设的同学也适合想快速找回词法/语法分析全流程的从业者翻一翻。2. 词法分析器拆开看正则、DFA与getToken()的落地学编译原理的时候教材会告诉你词法分析有三种实现手写、正则转DFA、用lex生成。课程设计里用lex一把梭当然省事但答辩老师大概率会追问DFA状态图在哪、状态转移怎么对应到代码。这份报告选的是最扎实的一条路手写状态机把每个转移条件都落到getToken()的switch或者if判断里代码量和DFA状态数一一对应老师问起来每一个状态都能指给ta看。2.1 词法边界保留字、符号和正则表达式怎么定词法分析的第一步不是写代码是给「什么样的字符流算一个token」划界。报告把C的token分成四类保留字、特殊符号、其它tokenID/NUM/CHARACTER/STRING以及文件结束和错误两大类标志位。保留字清单是完整的32个ANSI C关键字从AUTO到WHILE一个没少。AUTO BREAK CASE CHAR CONST CONTINUE DEFAULT DO DOUBLE ELSE ENUM EXTERN FLOAT FOR GOTO IF INT LONG REGISTER RETURN SHORT SIGNED SIZEOF STATIC STRUCT SWITCH TYPEDEF UNION UNSIGNED VOID VOLATILE WHILE特殊符号就比较有讲究了。报告里列的是C语言运算符号和分隔符的最小集合 - * / -- - * ! ; , ( ) [ ] { } /* */ :注意这两组符号的关键点单字符运算符和多字符运算符是混在一起的和能不能正确区分取决于DFA在设计时有没有把「读到之后再看下一个字符」这个动作想清楚。报告后面给的INOPERATE状态就是干这个的。正则表达式部分报告给的是带文法的简化版whitespace (newline | blank | tab | comment) digit 0|..|9 nat digit signedNat (|-)? nat NUM signedNat (. nat)? /* 支持整数、小数、符号数 */ letter a|..|z|A|..|Z ID letter (letter | digit | _) CHAR other STRING other 这组正则看起来朴素但每个符号都有它的用意。NUM允许多一个小数部分INT、FLOAT这种数字常量就能一次性吃掉ID要求必须以字母开头数字开头的字符串不会被误判成标识符CHAR和STRING里的other表示「引号内除引号外的任意字符」。注意它省略了转义字符也就是说\n这种写法在这个词法器里会被拆成多个token这是个已知的边界后面避坑章节会展开说。2.2 两套DFA注释的5状态和词法的10状态报告的DFA是分两个画的这个拆分很实用。第一套是注释DFA只有5个状态状态1START读入/进入状态2状态2读入*进入状态3否则判定这不是注释回退状态3注释中读入*进入状态4否则继续留在状态3状态4可能结束读入/进入状态5结束否则回退重新判断状态5结束状态注释token完成第二套是词法分析的DFA10个状态START、INNUM、INNUM1、INNUM2、INID、INCOMPARE、INOPERATE、INSTRING、INCHAR、DONE。核心转移规则一句话就能概括START时根据首字符决定进入哪个状态各个中间状态里「下个字符属于这个token」就原地踏步「不属于」就转DONE并生成token。状态输入下一状态说明STARTdigitINNUM可能是数字STARTletterINID可能是标识符START ! INCOMPARE可能是比较运算符START - * /INOPERATE可能是算术运算符STARTINCHAR字符常量STARTINSTRING字符串常量INNUMdigitINNUM继续吃数字INNUM.INNUM1小数点点号INNUM1digitINNUM2小数点后必须有数字INNUM2digitINNUM2继续吃小数部分INIDletter/digit/_INID标识符字符INCOMPAREDONE形成 !INOPERATEDONE形成 - *这套DFA唯一的麻烦在INCOMPARE和INOPERATE读到之后如果下一个字符不是那这个单独就是一个token但下一个字符已经被读上来了必须退回输入流。这就是报告里ungetNextChar()函数存在的意义也是后面所有「字符被吞」bug的根源。2.3 TokenType枚举先把token全部编号再写代码词法分析器的输出是什么不能是字符串得是「类型值」的结构。报告用了一个超长的枚举把所有token类型编号我用去掉重复项的版本还原一下typedef enum { ENDFILE, ERROR, /* 文件结束、错误 */ /* 保留字 */ AUTO, BREAK, CASE, CHAR, CONST, CONTINUE, DEFAULT, DO, DOUBLE, ELSE, ENUM, EXTERN, FLOAT, FOR, GOTO, IF, INT, LONG, REGISTER, RETURN, SHORT, SIGNED, SIZEOF, STATIC, STRUCT, SWITCH, TYPEDEF, UNION, UNSIGNED, VOID, VOLATILE, WHILE, /* 其他 token */ ID, NUM, CHARACTER, STRING, /* 特殊符号 */ PLUS, MINUS, TIMES, OVER, SELFPLUS, SELFMINUS, PLUSASSIGN, MINUSASSIGN, TIMESASSIGN, LT, LEQ, GT, GEQ, EQ, NEQ, ASSIGN, SEMI, COMMA, LPAREN, RPAREN, LBRACKET, RBRACKET, LCBRACKET, RCBRACKET, LCOMMENT, RCOMMENT, COLON } TokenType;这个枚举的排列顺序隐含了词法分析的处理逻辑保留字和普通标识符共用INID状态读到完整单词后先查保留字表命中就返回AUTO、INT这种枚举没命中才返回ID。另外每个token的实际文本会被copyString()复制到tokenString里因为源代码缓冲区的数据随时可能被下一行覆盖不复制就丢。读这份报告的时候有个细节要注意原文档的枚举粘贴时把LT到LPAREN之间的项重复了一遍我在上面已经去掉了。看到重复项别慌说明原报告是手工整理的读代码时留意别顺着抄错就行。2.4 scan.c骨架getToken()与字符缓冲/回退机制词法分析的代码集中在scan.c和scan.h配套的util.c、util.h负责printToken、copyString这些工具函数global.h放全局变量声明。主函数只干两件事打开源文件、循环调用getToken()直到返回ENDFILE。getToken()这个名字容易让人以为它每次读一个token实际上它背后有一个整行缓冲机制报告里这几个成员变量都写明了char tokenString[MAXTOKENLEN 1]; /* token文本缓冲区 */ int lineno 0; /* 当前行号 */ char lineBuf[BUFLEN]; /* 整行代码缓冲区 */ int linepos 0; /* 当前行的读取位置 */ int bufsize 0; /* 缓冲区已用大小 */ int EOF_flag FALSE; /* 文件结束标志 */配套的两个字符级函数机理是每次读一行到lineBuf然后从lineBuf里逐字符吐给DFAstatic int getNextChar(void) { if (linepos bufsize) { /* 当前行读完了 */ lineno; if (fgets(lineBuf, BUFLEN, sourceFile) NULL) { EOF_flag TRUE; return EOF; } linepos 0; bufsize strlen(lineBuf); } return lineBuf[linepos]; } static void ungetNextChar(void) { if (linepos 0) linepos--; /* 只回退一个字符 */ }getNextChar()每次取一个字符并推进linepos遇到行尾就用fgets()加载下一行并递增行号。ungetNextChar()则是DFA里「多读了一个字符」的后悔药只能退一个位置。###这种无效字符怎么处理START状态下直接进入DONE并返回ERROR但不会因为一个错误就终止整个分析这样test.c开头的###int才能正确输出错误token再继续读后面的合法代码。3. 语法分析器拆开看EBNF文法与递归下降函数怎么互相照应语法分析这部分报告的切入点是C-语言简化版C不是完整ANSI C。这个选择很聪明完整C的文法规则多到能写满十页A4纸而C-保留核心语法结构正好覆盖语句嵌套、变量声明、函数声明、表达式优先级这些课设考察点递归下降函数也能控制在十几个以内。3.1 先有文法再写代码C-语言的EBNF规则递归下降分析器的每个函数几乎都是从EBNF文法的某一条规则翻译过来的。报告给的文法是一棵清晰的树从program开始逐层展开program → declaration_list declaration_list → declaration { declaration } declaration → var_declaration | fun_declaration var_declaration → type_specifier ID ; | type_specifier ID [ NUM ] ; type_specifier → int | void fun_declaration → type_specifier ID ( params ) compound_stmt params → param_list | void param_list → param { , param } param → type_specifier ID { [ ] } compound_stmt → { local_declarations statement_list } local_declarations → empty { var_declaration } statement_list → { statement } statement → expression_stmt | compound_stmt | selection_stmt | iteration_stmt | return_stmt expression_stmt → [ expression ] ; selection_stmt → if ( expression ) statement [ else statement ] iteration_stmt → while ( expression ) statement return_stmt → return [ expression ] ; expression → var expression | simple_expression simple_expression → additive_expression { relop additive_expression } additive_expression → term { addop term } term → factor { mulop factor } factor → ( expression ) | var | call | NUM call → ID ( args )这套文法的写法是「自顶向下、逐层细化」每条规则右侧第一项基本就是递归下降函数的调用顺序。{ ... }表示「零到若干个重复」翻译成代码就是while循环或sibling链。[ ... ]表示「可选」翻译成代码就是一次if判断。比如selection_stmt → if ( expression ) statement [ else statement ]对应函数里就是匹配if和(之后调expression()和statement()再看当前token是不是ELSE是就再跟一个statement()。3.2 TreeNode一棵四个子节点加兄弟指针的语法树语法分析的输出不是打印「语法正确」就完事它要生成一棵语法树。报告的TreeNode结构设计得比较节省typedef struct treeNode { struct treeNode * child[4]; /* 最多四个子节点 */ struct treeNode * sibling; /* 兄弟节点指针 */ int lineno; /* 所在行号 */ NodeKind nodekind; /* 节点种类 */ union { TokenType op; /* 运算符 */ int val; /* 数值 */ const char * name; /* 标识符名 */ } attr; ExpType type; /* 表达式类型 */ } TreeNode;child[4]够不够对照节点类型表看最复杂的节点是FunK需要返回类型、函数名、参数列表、函数体四个子节点刚好四个。Selection_StmtK要if条件、IF体、ELSE体三个子节点。表达式里的OpK需要左值、运算符、右值三个。所以child[4]是「按最坏情况设计」的结果。sibling指针则用来处理declaration_list → declaration { declaration }这种并列结构——多个声明用兄弟链串起来不在同一层级硬塞进child数组。这里有个细节值得注意attr是union而不是struct。也就是说一个节点要么是运算符、要么是数值、要么是名字三者不会同时出现。这符合语法树的语义一个常量节点不需要名字一个ID节点不需要数值设计上是合理的。3.3 declaration()向前探测一个token决定是函数还是变量整个递归下降里最有技巧性的函数是declaration()。declaration → var_declaration | fun_declaration而var_declaration和fun_declaration的开头都是type_specifier ID光看前两个token区分不了。报告的处理方法是匹配完类型和ID之后向前探测第三个token——是(就是函数声明是[就是数组声明是;就是普通变量声明。TreeNode * declaration(void) { TreeNode * t NULL, * p NULL, * q NULL, * a NULL, * s NULL; if (token INT) { p newNode(IntK); match(INT); } else if (token VOID){ p newNode(VoidK); match(VOID); } else syntaxError(type error); if (p ! NULL token ID) { q newNode(IdK); q-attr.name copyString(tokenString); match(ID); if (token LPAREN) { /* 函数声明 */ t newNode(FunK); t-child[0] p; /* 返回类型 */ t-child[1] q; /* 函数名 */ match(LPAREN); t-child[2] params(); /* 参数表 */ match(RPAREN); t-child[3] compound_stmt(); /* 函数体 */ } else if (token LBRACKET) { /* 数组声明 */ t newNode(Var_DeclK); a newNode(Arry_DeclK); t-child[0] p; t-child[1] a; match(LBRACKET); s newNode(ConstK); s-attr.val atoi(tokenString); /* 数组大小 */ match(NUM); a-child[0] q; a-child[1] s; match(RBRACKET); match(SEMI); } else if (token SEMI) { /* 普通变量 */ t newNode(Var_DeclK); t-child[0] p; t-child[1] q; match(SEMI); } else { syntaxError(); } } return t; }三个分支的顺序在实现上有讲究。LPAREN函数声明必须最先判断因为C-文法里函数声明是最复杂的结构后面要跟大括号语句块LBRACKET和SEMI的顺序问题不大因为[和;互斥。数组声明里int a[10]的10存在ConstK节点里用atoi(tokenString)把字符串转成整型——这意味着词法分析器返回NUM token时tokenString里必须有完整的数字文本否则atoi会得到0。这个小细节说明词法分析和语法分析的数据约定是隐式的语法分析器信任词法分析器提供的tokenString。3.4 statement()到expression_stmt递归下降的调用链statement是语法分析的分叉点五种语句类型靠开始token就能区分。报告用一个switch实现了这个分发TreeNode * statement(void) { TreeNode * t NULL; switch (token) { case IF: t selection_stmt(); break; case WHILE: t iteration_stmt(); break; case RETURN: t return_stmt(); break; case LCBRACKET: t compound_stmt(); break; case ID: case SEMI: case LPAREN: case NUM: t expression_stmt(); break; default: syntaxError(); token getToken(); break; } return t; }这个switch把每个token映射到唯一的语法结构只有ID、SEMI、LPAREN、NUM四种情况归到表达式语句。空语句;也属于expression_stmt函数里对SEMI的处理相当于「可选的表达式加上分号」所以空语句能合法通过。这里递归下降的结构特别清晰statement调用expression_stmtexpression_stmt调用expressionexpression再去调simple_expression、additive_expression、term、factor一层层往下钻运算符优先级就在这个调用层级里体现出来了。还有一个值得看的地方是params()对void的处理。C-文法里params → param_list | void报告的处理是匹配VOID之后再看下一个token如果是)说明这就是无参函数参数表只有一个VoidK节点如果后面跟的是ID说明参数列表包含一个void类型的参数直接把VoidK节点传给param_list()做第一个参数。这种「边读边判定」的小技巧处理标准库常见的int f(void)写法非常顺。4. 把两份代码跑起来文件组织、编译命令与test.c设计文档里的代码分散在几个文件里第一次照着敲的人容易在文件划分上犹豫。我把报告里的文件结构和常见做法对齐了一下这部分不用带脑子直接抄目录就行。4.1 文件组织scan.c、util.c、global.h和语法分析文件各管什么文件职责关键内容global.h全局变量与公共类型声明TokenType枚举、tokenString、linenoutil.h / util.c工具函数printToken()、copyString()scan.h / scan.c词法分析getToken()、getNextChar()、ungetNextChar()、reservedLookup()parse.c常见命名语法分析parse()、declaration()、statement()等递归下降函数词法部分报告里写得清清楚楚scan.c和scan.h是主体。语法部分报告只给了函数实现思路和TreeNode定义没给文件名常见做法是单独放一个parse.c再写一个main.c做入口。main函数里打开源文件、调用parse()、关闭文件、打印语法树结构上和词法部分的主函数是对称的。4.2 编译与调试gcc参数和gdb看回退编译命令没什么玄学把词法和语法两个部分的文件一起编gcc -Wall -g -o parser scan.c util.c parse.c main.c-Wall打开所有警告语法分析器这种递归下降代码最容易出现「函数声明了没定义」「switch漏了break」的警告开着能少踩不少坑。-g保留调试符号后面排查「字符被吞」的问题要用gdb单步看linepos的变化。如果用的是vscode本质也是配一条tasks.json把这条命令跑起来命令行写法不变。调试的时候我习惯在getNextChar()和ungetNextChar()两个函数上打断点。词法分析出问题十有八九发生在回退不该回退的时候退了token就少字符该回退的时候没退下一个token就多了字符。gdb里看linepos在return前后怎么变一眼就能定位。4.3 test.c测试设计注释、数字、字符串、错误输入全覆盖测试文件是这样一段刻意设计的代码后半段留了点「小动作」/*test.c*/ int main(void){ ###int a 0; float b 20.1; char c[]abcdefg; char d h; if(a2){ b0.1 a; }}这段测试覆盖得相当全开头有注释int是保留字20.1是小数NUMmain、a、b是一般标识符、、是特殊符号双引号包着字符串单引号包着字符###是故意放进去的错误输入。词法分析器对###的行为是每遇到一个#就进入DONE并返回一个ERROR token然后继续处理后面的int不会因为遇到非法字符就崩掉整个分析。运行时gdb parser然后在parse()入口下断点能看到词法错误和普通token一起进入语法分析器。这里要注意的一点是词法错误和语法错误的边界。###是词法层能发现的错误因为#根本不在任何token的起始字符集合里而b0.1后面缺分号这类问题词法分析器完全看不出来它只会老老实实输出b、、0.1这三个token等语法分析器在statement这一层发现到达不了SEMI才报错。测试结果把两者分开处理输出行号、token类型、取值错误输入单独标ERROR这个输出格式也是答辩时最好讲的部分。5. 避坑指南词法分析和语法分析最常见的五个翻车点这章写的都是实际跑这份代码会撞上的问题每一条我都标了现象、原因和解决办法。5.1 词法和语法的职责边界混在一起现象词法分析器报了「缺少分号」或者「括号不匹配」错误。 原因写代码的时候把语法检查顺手做进了词法分析。报告作者自己也在小结里承认一开始总把这两层混淆。词法分析只做「把字符流切成token流」这一件事分号缺失、括号不配对是语句结构问题必须等语法分析器拿到token序列之后才能判断。 解决词法分析遇到无法识别的字符时返回ERROR token但继续往下走语法分析才负责在token序列里检查结构合法性。判断标准很简单——这条错误能不能不看源码只看token序列就发现能就是语法层的事。5.2 超前读了一个字符忘了退回去现象int a20;被切成了int、a、、20但下一个token的开头字符丢了或者被拆成和两个token。 原因DFA在INCOMPARE状态读到之后会先读下一个字符判断是不是。如果下一个字符是a说明这个token就是单独的但a已经被读进来了不退回就会被吞。 解决任何「多读一个字符再决定当前token归属」的状态在确定当前token结束时都必须调一次ungetNextChar()。建议在扫描函数里做一次自查每个进入DONE状态的分支问自己「当前字符是否已经不属于本token」。5.3 注释结束判定状态4遇到非/要回退现象/* a */ b词法分析结果里b不见了或者整个文件后半段全被当成注释。 原因注释DFA的状态4是「可能结束」读到*之后要等下一个字符。如果下一个是/注释结束如果不是/这个字符是有效代码必须退回输入流重新处理。漏掉回退就把注释后面的第一个有效字符吃了。 解决实现上在状态4遇到非/时先ungetNextChar()再回退到状态3。用/* ab **/这种连续星号的用例专门测一遍。5.4 保留字被当成普通标识符现象int a;里的int被输出为ID而不是INT语法分析时declaration()匹配不到INT直接报type error。 原因DFA的INID状态只负责把字母开头的字符串收完它并不知道int、if这些词是保留字。词法分析必须在INID结束、准备返回ID之前查一次保留字表。 解决reservedLookup()函数做这件事——把tokenString和保留字表逐一比对命中就返回对应的TokenType枚举没命中才返回ID。这个查表是词法分析返回前最后一步不能省。5.5 字符串里的转义字符没处理现象char c[]a\b;在\处词法分析器报错或者字符串提前在处结束。 原因报告里的正则明确写的是STRING other other是「除引号外的任意字符」转义序列里的引号不属于这个集合。报告作者也承认省略了转义字符是时间所限。 解决如果要把这条路补完整需要在INSTRING和INCHAR状态里加一个判断读到\时无条件把下一个字符也消费掉再继续正常状态转移。这是完整C词法必备的能力改起来也就几行但DFA图需要加一个「转义中」的状态。6. 从那以后我拿到词法分析器代码先做这三件事不管是自己写还是读别人的词法/语法分析器我现在的习惯是固定跑一遍验证流程三件事十分钟以内。第一件构造最小正例。从int a;这种单变量声明开始每加一种语法结构就重跑一次加函数、加if、加while、加数组、加嵌套复合语句。每次只动一个变量token流和语法树的变化一目了然。第二件构造最小反例。故意塞一个###在文件头故意在b0.1后面去掉分号看错误是在词法层报还是在语法层报。这一条最能暴露词法和语法边界有没有分清楚。第三件把token流打出来和预期做diff。我一般会在词法分析器里加一个dumpToken()函数把每次getToken()返回的枚举名和tokenString输出成一行文本然后跟预期结果逐行比对错误马上现形。语法树的前序遍历打印也一样能看出树结构和预期是否一致。这三件事听着基础但我真吃过亏。有一回图省事只跑了正例没跑反例词法分析器把##这种垃圾输入后面的第一个合法字符吞了答辩演示的时候现场翻车被老师指着输出问「这个字符去哪了」。从那以后我每次跑词法/语法分析器都强制走一遍「最小正例最小反例token流diff」的流程几分钟换一个稳的演示效果不亏。希望帮到你。本文还有配套的精品资源点击获取