C语言实现编译原理课设：词法分析、语法分析到四元式生成全解析

C语言实现编译原理课设：词法分析、语法分析到四元式生成全解析

发布时间：2026/10/10 8:55:29
C语言实现编译原理课设：词法分析、语法分析到四元式生成全解析 简介基于C语言实现小型编译程序的完整课程设计资源包面向编译原理课程设计与对编译器底层机制感兴趣的学习者。资源围绕将高级语言源码转换为四元式中间表示这一核心任务完整演示词法分析、语法分析、语义分析、四元式生成等关键环节并提供相应的C/C源码实现与配套说明文档。压缩包共4个文件以C源代码、C主程序、Markdown说明文档和License授权文件为主整体仅14KB代码精简、结构清晰适合快速研读与二次修改。目前已有288人学习下载可用于辅助理解编译程序的分阶段构造也可作为课程设计报告与答辩的参考素材帮助读者掌握有限状态自动机、递归下降分析、类型检查及常量折叠等核心知识。1. 用 C 语言写编译程序一份能产出四元式的课程设计源码从a 3 5 * 2;这样一条赋值语句到控制台打印出(*, 5, 2, t1)这行四元式中间要跨过词法分析、语法分析和语义分析三座山。这份用 C 语言实现的小型编译程序课程设计源码正好把这三段路线完整走了一遍读入简化高级语言代码输出一张四元式中间代码表。四元式作为编译器的中间表示IR核心是一个四元组(操作符, 操作数1, 操作数2, 结果)有了这张表后面做优化、生成汇编都有了一个干净入口。适合正在做编译原理课设的学生、想搞懂词法分析和递归下降到底怎么落地的开发者以及第一次面对 C 语言字符串、指针、文件缓冲区组合拳的新手。2. 先搭数据结构四元式、Token、符号表的结构设计写编译程序最大的教训是数据结构没想清楚就动手写词法分析器后面一定返工。Token 流要传给语法分析器语法分析器要输出四元式表符号表又要被语法分析和语义分析同时查这三者的结构体如果定义得不对代码写到最后就是靠strcmp和全局变量硬撑翻车只是时间问题。我一般先把三个核心结构体定死再开始写逻辑。2.1 四元式结构体中间代码的最小单元四元式的形式是(OP, A, B, C)OP 是操作符A 和 B 是操作数C 是结果。在 C 语言里最直接的表现就是一串结构体数组#define MAX_QUADS 1024 #define MAX_NAME 32 typedef struct { char op[8]; /* 操作符ADD、SUB、MUL、DIV、ASSIGN 等 */ char arg1[MAX_NAME]; /* 第一个操作数变量名或常量字符串 */ char arg2[MAX_NAME]; /* 第二个操作数单目运算或赋值时留空 */ char result[MAX_NAME]; /* 接收结果的变量或临时变量 t1、t2... */ } Quad; Quad quads[MAX_QUADS]; int quad_count 0;操作数字段用char数组而不是int这是我当时纠结最久的地方。表达式a 1生成的四元式是(ADD, a, 1, t1)其中a是变量名、1是常量二者都要以字符串形式存。如果强行把操作数解析成数值后面语法分析就需要反复做字符串到整数的转换还会丢失变量名这个关键信息。常量可以后续用atoi取出来变量名却没法从数值还原。这份资源里的四元式操作符集合覆盖了课设最常用的一批课程设计里的表达式求值、赋值语句、if-else控制流都靠它们撑起来。下面是四元式表的标准命名约定我在写emit函数之前先列了一张表放在代码注释里避免写一半把SUB写成MINUS操作符含义四元式示例ASSIGN赋值(ASSIGN, a, 空, b)ADD加法(ADD, a, b, t1)SUB减法(SUB, a, b, t1)MUL乘法(MUL, a, b, t1)DIV除法(DIV, a, b, t1)NEG取负单目(NEG, a, 空, t1)GOTO无条件跳转(GOTO, 空, 空, label)生成四元式的动作封装成一个emit函数所有语义动作都走这一个入口。这样做的好处是后续想统计四元式条数、打印调试信息只需要改这一个函数void emit(const char* op, const char* arg1, const char* arg2, const char* result) { if (quad_count MAX_QUADS) { fprintf(stderr, 四元式表溢出请增大 MAX_QUADS\n); exit(1); } strcpy(quads[quad_count].op, op); strcpy(quads[quad_count].arg1, arg1 ? arg1 : ); strcpy(quads[quad_count].arg2, arg2 ? arg2 : ); strcpy(quads[quad_count].result, result ? result : ); quad_count; }2.2 Token 与符号表连接词法分析和语法分析的契约词法分析器的产物是 Token 流。Token 结构体里必须带着原始字符串和行号因为语法分析只需要 type但报错和调试需要行号和词面值typedef enum { TOKEN_IDENT, TOKEN_NUMBER, TOKEN_KEYWORD, TOKEN_OPERATOR, TOKEN_EOF } TokenType; typedef struct { TokenType type; /* 枚举类型标识符、数字、关键字、运算符 */ char lexeme[MAX_NAME]; /* 原始字符串用来查符号表和生成四元式操作数 */ int line; /* 行号语法报错时直接打印 */ } Token; Token tokens[MAX_TOKEN_COUNT]; int token_count 0;语法分析器拿到tokens数组之后通过tokens[pos].type来决定下一步动作。这里有一个关键约定TOKEN_IDENT类型的 Token其lexeme就是变量名之后生成四元式时直接用这个字符串作为操作数。所以在词法分析阶段把标识符完整截取出来比什么优化都重要。符号表在这个课设里不需要哈希表线性数组加strcmp遍历就够用。它的作用是在语义分析阶段查变量有没有声明过、类型是否一致typedef struct { char name[MAX_NAME]; int type; /* 变量类型INT、REAL */ double value; /* 解释执行时使用的值 */ } Symbol; Symbol sym_table[MAX_SYMBOLS]; int sym_count 0; Symbol* lookup_symbol(const char* name) { for (int i 0; i sym_count; i) { if (strcmp(sym_table[i].name, name) 0) { return sym_table[i]; } } return NULL; }符号表的设计思路是所有变量的插入、查找都走lookup_symbol一个入口不允许别的函数直接操作sym_table数组。因为语法分析器一边解析一边调用emit如果每个函数都自己遍历符号表代码会散得到处都是后期加类型检查时根本无从下手。2.3 主流程三遍扫描如何在 main 函数里串联这套资源的主流程是典型的三段式读入源文件、词法分析、语法分析加四元式生成三个段落之间通过 Token 数组衔接。main 函数短小但逻辑上把编译器的前端串起来了int main(int argc, char* argv[]) { if (argc 2) { printf(用法: %s test.c\n, argv[0]); return 1; } FILE* fp fopen(argv[1], r); if (!fp) { perror(打开源文件失败); return 1; } read_source(fp); /* 把整个文件读入全局缓冲区 */ fclose(fp); while (next_token() ! NULL) { /* 不断从缓冲区识别 Token存入全局 tokens 数组 */ } parse_program(); /* 递归下降分析同时生成四元式 */ print_quads(); /* 输出四元式表验证结果 */ return 0; }read_source负责把源文件整块读入字符缓冲区next_token是词法分析器的主循环parse_program是语法分析的入口。这三段之间的数据传递全部依赖全局变量课设规模下这是最实用的方案不需要为了模块化去封装一堆结构体指针。但全局变量多了一个副作用如果词法分析器和语法分析器都叫了error函数命名冲突就来了。我当时在源码里统一了错误处理函数名词法层叫lex_error、语法层叫parse_error打印内容和行号各自维护。3. 词法分析器从字符流到 Token 流的实现与边界处理词法分析器是整套代码里第一个真正动手写的模块。它的任务很单纯读字符、识别 Token、把 Token 存入数组。但越单纯的任务越容易在边界上翻车。文件末尾丢字符、标识符截断、运算符识别错误这些问题在这一层全部会暴露出来。3.1 手写词法分析器为什么不用 Flex课程设计里main.cpp的代码走的是手写路线没用 Flex。这个选择不是技术上的落后而是课设答辩场景下的务实考虑。Flex 根据正则表达式自动生成词法分析器生成的代码是一大坨状态表驱动的 C 文件你很难在答辩时跟老师解释清楚那几百行状态转移是怎么回事。手写有限自动机就完全不一样每个if分支对应一个状态迁移逻辑一目了然。手写词法分析器的核心是三重判断数字、标识符、运算符。前两者有明确的首字符区分规则运算符则需要做最长匹配。比如和如果只读一个字符就返回遇到会被错误拆成两个 Token。我一般先读入可能的双字符运算符再回退。下一步真正动手写next_token函数。这个函数每调用一次就返回一个 Token 指针内部用全局的current_pos记录当前位置Token* next_token(void) { while (source[current_pos] || source[current_pos] \t || source[current_pos] \n) { current_pos; /* 跳过空白字符 */ } if (source[current_pos] \0) { return NULL; /* 整个缓冲区扫描完毕 */ } char ch source[current_pos]; if (isalpha(ch) || ch _) { int start current_pos; while (isalnum(source[current_pos]) || source[current_pos] _) { current_pos; } strncpy(token.lexeme, source start, current_pos - start); token.lexeme[current_pos - start] \0; token.type lookup_keyword(token.lexeme); /* 关键字优先匹配 */ return token; } if (isdigit(ch)) { int start current_pos; while (isdigit(source[current_pos])) { current_pos; } strncpy(token.lexeme, source start, current_pos - start); token.lexeme[current_pos - start] \0; token.type TOKEN_NUMBER; return token; } /* 运算符分支这里省略双字符匹配细节 */ return NULL; }lookup_keyword的逻辑是先查一张关键字表if、else、while、int等匹配不到就返回TOKEN_IDENT。这里有一个顺序上的坑必须先查关键字表再返回标识符因为if同时也是合法标识符的字母组合不查表就会把关键字当作普通变量。数字识别的时候只处理了整数没有处理小数点和科学计数法。课设要求里如果明确写了3.14这种浮点常量就需要在数字分支里加一个小数点状态。识别浮点数的核心判断是读到小数点时必须确保小数点后面还有数字否则要回退。3.2 运算符的最长匹配双字符运算符的处理单字符运算符比较简单 - * / ( ) { } ; 各归各。双字符运算符比较常见的是、、、!、、||。如果不做最长匹配a b会被拆成和两个赋值运算符语法分析直接乱套。处理方案是预读一个字符匹配成功就消费两个字符失败就回退一个char* match_operator(void) { char cur source[current_pos]; char next source[current_pos 1]; if (cur next ) { current_pos 2; return GE; } if (cur next ) { current_pos 2; return LE; } if (cur next ) { current_pos 2; return EQ; } if (cur ! next ) { current_pos 2; return NE; } /* 单字符运算符 */ switch (cur) { case : current_pos; return ADD; /* 返回内部助记符后面查表映射 */ case -: current_pos; return SUB; case *: current_pos; return MUL; case /: current_pos; return DIV; case : current_pos; return ASSIGN; case (: current_pos; return LPAREN; case ): current_pos; return RPAREN; case ;: current_pos; return SEMICOLON; default: return NULL; } }这段代码把运算符映射成内部助记符而不是直接返回char是为了和四元式的操作符字段共用一套命名。ADD、SUB这些字符串直接写进四元式表词法分析器、语法分析器、四元式表三者的命名一致调试时grep一下就能串起来。3.3 文件缓冲区边界为什么读文件会丢末尾字符这个坑是 C 语言初学者必踩的。用fgets或fgetc逐字符读文件时缓冲区大小没留够、读取循环条件写错、字符串末尾的\0没处理都会造成最后一个字符丢失或者数组越界。我在这份课设里直接把整个文件读进一个固定大小的字符数组再在数组末尾手动补\0#define MAX_SOURCE 8192 char source[MAX_SOURCE]; int current_pos 0; void read_source(FILE* fp) { size_t len fread(source, 1, MAX_SOURCE - 1, fp); source[len] \0; /* 手动补结束符否则词法分析器无法判断文件结束 */ }如果源文件超过 8192 字节fread会截断内容这时候读进缓冲区的内容是不完整的。我后来在read_source里加了检查len MAX_SOURCE - 1时直接报错“源文件过大”避免词法分析器在截断的代码上跑出一堆莫名其妙的错误。这个检查对课设规模的代码完全够用真要支持超大文件再改成动态扩容。缓冲区相关的另一个坑是feof的使用。很多人写while (!feof(fp))逐字符读结果发现文件内容读完了还多读了一次因为feof在读取操作之后才设置标志。用fread一次性读入可以完全绕开这个问题这也是我推荐这种方式的原因。4. 递归下降语法分析与语义动作在解析过程中产出四元式语法分析器是这个编译程序的灵魂。词法分析产物是一串 Token语法分析器要把这串 Token 按照文法组织成结构并在每一步归约时顺手生成四元式。递归下降是最适合手写的分析方法C 语言函数天然支持递归一个非终结符对应一个函数代码结构和 BNF 文法几乎一一对应。4.1 表达式文法如何消除左递归表达式求值是课设的核心。一个常规的算术表达式文法长这样E - T { (|-) T } T - F { (*|/) F } F - id | num | ( E )这个文法已经做了左递归消除。原始文法里常见写法是E - E T这种写法直接用于递归下降会陷入无限递归因为E的第一个字符还没看就再次调用parse_E永远出不来。消除左递归的办法是改成循环结构先解析一个T再看下一个 Token 是不是或-是就继续循环解析下一个T。{ ... }这个记号表示“重复零次或多次”在代码里就是while循环。选择这套文法的理由是它完整覆盖了课设要求的表达式能力乘法除法优先级高于加减法括号可以改变优先级。F层处理最基础的因子包括标识符、数字和带括号的表达式。这个层级关系对应了四元式生成时的操作顺序后面写parse_T时不会出现优先级错乱。4.2 递归下降函数与语义动作的插桩语法分析函数本身只做结构判断生成四元式要依靠emit和newtemp两个工具函数。newtemp负责生成临时变量名每调用一次就返回一个新的t1、t2int temp_count 0; char* newtemp(void) { static char name[MAX_NAME]; snprintf(name, sizeof(name), t%d, temp_count); return name; }parse_E和parse_T的代码结构完全一样只是操作符不同。以parse_E为例void parse_E(void) { char* op1 parse_T(); /* 先解析第一个项 */ while (tokens[pos].type TOKEN_OPERATOR (strcmp(tokens[pos].lexeme, ) 0 || strcmp(tokens[pos].lexeme, -) 0)) { char op tokens[pos].lexeme[0]; pos; char* op2 parse_T(); char* result newtemp(); if (op ) { emit(ADD, op1, op2, result); } else { emit(SUB, op1, op2, result); } op1 result; /* 关键把结果当作下一次运算的操作数 */ } return op1; /* 这里返回给上层实际代码里用全局变量或指针传递 */ }parse_T的结构完全相同只是把/-换成*//调用的下一层换成parse_F。每解析出一个新运算就生成一个临时变量下一次运算的操作数就是这个临时变量。拿a b * c举例parse_T在解析到*时先生成(MUL, b, c, t1)然后parse_E生成(ADD, a, t1, t2)最终的四元式序列顺序是完全正确的。parse_F的逻辑更短但是含金量最高它直接面对标识符、数字和括号char* parse_F(void) { if (tokens[pos].type TOKEN_NUMBER) { char* name strdup(tokens[pos].lexeme); pos; return name; /* 常量直接作为操作数返回 */ } if (tokens[pos].type TOKEN_IDENT) { if (lookup_symbol(tokens[pos].lexeme) NULL) { parse_error(未声明的变量); } char* name strdup(tokens[pos].lexeme); pos; return name; } if (tokens[pos].type TOKEN_OPERATOR strcmp(tokens[pos].lexeme, () 0) { pos; char* expr parse_E(); if (tokens[pos].type ! TOKEN_OPERATOR || strcmp(tokens[pos].lexeme, )) ! 0) { parse_error(缺少右括号); } pos; return expr; } parse_error(表达式语法错误); return NULL; }这里的语义检查藏在标识符分支在生成四元式之前先查符号表如果变量没有声明过就直接报错。这个设计把语义分析前置到了语法分析过程中虽然混合了阶段但课设规模下完全可行而且报错信息能精确到变量名。4.3 赋值语句与控制流的四元式生成赋值语句的语法动作比较简单但控制流需要用到跳转四元式。if-else的翻译模式是在条件判断后先发射一个条件跳转四元式跳转到else标签然后接着翻译then分支最后再发射一个无条件跳转跳出整个if。这个实现里标签用L1、L2这种字符串表示本质上就是GOTO的目标地址void parse_if(void) { pos; /* 跳过 if 关键字 */ char* cond parse_E(); /* 解析条件表达式 */ char* l_else newlabel(); emit(GOTO_FALSE, cond, , l_else); /* 条件为假跳到 else */ parse_stmt(); /* then 分支 */ char* l_end newlabel(); emit(GOTO, , , l_end); /* 完成后跳出 */ strcpy(labels[more_label_count], l_else); /* 这里做标签地址回填 */ strcpy(labels[more_label_count], l_end); }标签地址回填是控制流实现的难点。四元式表的长度是动态增长的GOTO指令发射时目标标签可能还没生成所以先在labels表里占个位置所有四元式生成完毕后再扫描一遍四元式表把GOTO的目标从标签名改成具体四元式下标。这套机制不难但第一次写的时候很容易忘记最后的回填步骤导致解释器执行时跳到一个不存在的四元式下标。递归下降解析器的调试方式很直接在parse_F里打印当前 Token跑一个简单表达式看解析路径是否符合预期。最常见的错误是pos倒退或者重复消费 Token这类问题的根源几乎都是某个分支忘记自增pos。5. 常见问题与排查缓冲区丢字、优先级错位、数组越界课设代码跑通不难难的是跑通之前的排查过程。这里列几个我在拆这份源码时实际遇到的坑每条都按“现象 → 原因 → 解决”说清楚照着查能省不少时间。5.1 源文件最后一个字符总是被吞掉现象test.c里写的a 1;词法分析器只识别出来a 1结尾的分号消失了语法分析直接报错。原因读文件时用了fgets或者while (!feof(fp))的写法文件末尾的换行符和EOF标志没有正确处理缓冲区里的字符串没有以\0结尾词法分析器读到最后越过了数组末尾。解决换成fread一次性读入手动在source[len]处写\0。判断文件结束不要依赖feof而是检查fread的返回值。改完之后用printf(%s, source)验证一下缓冲区内容确认末尾分号在。5.2 表达式a b * c的四元式顺序反了现象生成结果是(ADD, a, b, t1)在前(MUL, b, c, t2)在后乘法反而先算完了加法的操作数。原因文法设计时没有区分优先级层parse_E和parse_T都直接调用了同一个解析函数导致乘法没有被强制先归约。递归下降的优先级是靠函数调用层级实现的parse_E调parse_T、parse_T调parse_F这个层级一旦打破优先级全乱。解决严格按照文法分层写。parse_E只处理/-parse_T只处理*//parse_F处理因子。写完以后用a b * c和(a b) * c各测一遍重点看四元式里临时变量的先后顺序。5.3 临时变量编号和四元式数组一起增长越界了现象程序跑到一半崩溃打印四元式表时发现下标跑到 1200 多超过MAX_QUADS。原因newtemp和emit各自维护计数器如果某个表达式嵌套层数很深临时变量暴增四元式表溢出。这个崩溃不会立刻出现往往在语法分析器处理复杂表达式时才暴露。解决emit里已经加了溢出检查quad_count MAX_QUADS时报错退出。在调试阶段把MAX_QUADS临时调到 4096先保证逻辑跑通最后再调回来。注意区分temp_count和quad_count是两个不同的东西临时变量编号是无限递增的不能拿它当四元式下标用。5.4 标识符abc123被识别成abc和123两个 Token现象符号表里存了abc后面的数字常量123被当作独立的TOKEN_NUMBER语义分析报“未声明的变量 abc123”。原因词法分析器的标识符分支写成了while (isalpha(source[current_pos]))没有把数字字符包含进去。C 语言标识符的合法字符是字母、数字和下划线且不能以数字开头。解决识别条件改为while (isalnum(source[current_pos]) || source[current_pos] _)。同时用isalpha判断首字符确保123abc这种情况走数字分支而不是标识符分支。5.5main.cpp文件用 C 编译器编译报错现象源码包里的入口文件叫main.cpp但是代码风格完全是 C 语言。用gcc编译时报了一堆语法错误。原因gcc根据文件扩展名选择编译器.cpp后缀会触发 C 编译规则而代码里用的malloc不转型、printf隐式声明这些写法在 C 里是严格报错的。解决用gcc -stdc11 main.cpp可以强制按 C 语言标准编译或者在命令行加-x c参数。更省事的办法是把文件复制一份改成main.c再用gcc main.c编译。这个坑很坑不是代码逻辑问题纯粹是文件命名习惯造成的。6. 用 40 行解释器验证四元式把中间表示真正跑起来四元式表生成出来以后怎么证明它是对的光看打印结果容易有盲区。我更建议写一个几十行的四元式解释器直接遍历quads数组执行一遍拿到最终变量值来验证。这一步能把代码生成和代码执行两个问题彻底分开如果是四元式错了解释器输出的结果会跟手算不一致如果是解释器错了那问题就出在取值逻辑上。这样调试时目标明确很多。解释器的核心逻辑很直接维护一个变量表保存变量当前值遍历四元式按操作符执行对应操作。代码长度控制在 40 行以内就能跑通算术表达式和赋值语句void interpret_quads(void) { Symbol* a; Symbol* b; double v; for (int i 0; i quad_count; i) { Quad* q quads[i]; if (strcmp(q-op, ASSIGN) 0) { a get_or_create_symbol(q-result); a-value atof(q-arg1); } else if (strcmp(q-op, ADD) 0) { a get_or_create_symbol(q-result); a-value atof(q-arg1) atof(q-arg2); } else if (strcmp(q-op, MUL) 0) { a get_or_create_symbol(q-result); a-value atof(q-arg1) * atof(q-arg2); } /* SUB、DIV 同理 */ } }get_or_create_symbol负责在符号表里查找或创建变量。这里用atof直接把操作数字符串转成数值是因为四元式里已经区分了变量名和常量字符串常量的操作数一定是合法的数字格式。如果算出来的t1值是 13四元式的(ADD, a, 1, t1)就是正确的。我在验证阶段的习惯是一边改文法一边跑解释器改了语法分析逻辑就重新生成四元式立刻用解释器跑一遍再和手算结果比对。这个方法帮我抓到了至少两个隐蔽问题一个是parse_E里忘记把临时变量更新到op1另一个是减法操作数和顺序反了。从那以后我每次写完一个递归下降函数都强制跑一遍解释器验证四元式而不是只看打印出的表格。希望这个验证习惯能帮到你尤其是面对那些看起来样板但藏着逻辑错的四元式输出时跑一遍比盯三分钟屏幕有效得多。本文还有配套的精品资源点击获取