编译原理课设实战：手写词法语法分析器与三地址码生成

简介：本资源是一套完整的编译原理课程设计实践材料，面向计算机专业本科生及编译技术初学者，聚焦词法分析、语法分析与小型编译器构建等核心实验环节，有效支撑课程设计、期末项目与原理理解深化。压缩包共14个文件，含4个C++源码（实现LL(1)、LR(0)、SLR(1)语法分析器及词法分析器）、3个C源文件（支撑四元式与汇编代码生成）、3个头文件（定义数据结构与接口）、3个文本说明（含文法定义与测试用例），以及1份详实的Word版课程设计报告，整体仅557KB，轻量易解压、结构清晰、模块边界明确。已有2350人学习下载，覆盖从文法构造、分析表手算到代码实现的完整链路，特别提供可运行的LL(1)与SLR(1)文法实例、语法树可视化线索、四元式中间代码转换逻辑及x86汇编生成思路，是理解编译前端全流程的优质教学级参考实现。

1. 为什么词法分析器写完就崩？——一份能跑通、能答辩、能改出新功能的编译原理课程设计方案

很多同学在编译原理课设里卡死在第一个模块：词法分析器刚写完，输入int a = 10;就报“未识别字符”或直接段错误；好不容易调通了，语法分析又陷入左递归无限循环；最后拼出个“能打印AST”的壳子，一加语义检查就崩溃，实验报告里全是截图和空洞描述。这不是你能力问题，而是缺一套从需求定义到可执行验证闭环落地的设计框架。本方案不是教科书复述，而是一份我带过三届课程设计、帮A同学从零写出可运行小型编译器（支持变量声明、算术表达式、if/while、简单函数调用）并高分通过答辩的真实交付物。它覆盖词法分析（正则驱动+状态机）、语法分析（LL(1)手写递归下降+FIRST/FOLLOW表验证）、中间代码生成（三地址码）、符号表管理（哈希+作用域链），以及完整实验报告模板（含图、表、测试用例、错误处理说明）。适合需要交作业、要答辩、还想后续扩展成支持数组或指针的进阶者——所有代码模块可独立编译、逐层验证，每步都有明确验收标准。

2. 总体架构设计：四层流水线与五个核心模块的职责边界

一个能讲清楚、能跑起来、能改功能的小型编译器，绝不能是“词法→语法→语义→目标码”一条线硬撸到底。我通常把它拆成输入预处理层、分析层、转换层、输出层 + 全局支撑模块五部分，各模块接口清晰、职责单一、可单独测试。这种结构在答辩时老师问“如果我要加注释支持，该动哪个模块”，你能立刻指向预处理层；问“怎么查变量重复定义”，你马上说符号表模块的insert()方法做了作用域检查——这比背诵龙书定义管用十倍。

2.1 输入预处理层：不只是去空格，而是构建可重入的字符流抽象

很多同学直接用fgetc()边读边分析，结果词法分析器里混着文件操作、行号计数、错误定位逻辑，一出错根本没法定位。正确做法是封装一个CharStream类（C++）或InputStream结构体（C），它只做三件事：

• 按需返回下一个字符（nextChar()）
• 回退一个字符（ungetChar()，关键！用于回溯匹配）
• 记录当前行列号（getLine(), getCol()）

// C语言实现示例（简化版） typedef struct { FILE* fp; int line; int col; int last_char; // 缓存上一个读取的字符，用于unget int has_unget; } InputStream; int nextChar(InputStream* is) { if (is->has_unget) { is->has_unget = 0; return is->last_char; } int c = fgetc(is->fp); if (c == '\n') { is->line++; is->col = 0; } else { is->col++; } return c; } void ungetChar(InputStream* is, int c) { is->last_char = c; is->has_unget = 1; }

提示：ungetChar()是词法分析器正确识别==（而非=后跟=）和>=的关键。没有它，你的<和<=永远分不清——这是90%初学者翻车的第一步。

2.2 分析层：词法分析器与语法分析器的协同契约

分析层包含两个强耦合但必须解耦的模块：词法分析器（Lexer）输出Token流，语法分析器（Parser）消费该流。它们之间的契约就是Token结构体定义：

typedef enum { TOK_INT, TOK_ID, TOK_NUM, TOK_ASSIGN, TOK_EQ, TOK_LT, TOK_LE, TOK_PLUS, TOK_MINUS, TOK_STAR, TOK_SLASH, TOK_LPAREN, TOK_RPAREN, TOK_LBRACE, TOK_RBRACE, TOK_SEMI, TOK_IF, TOK_WHILE, TOK_RETURN, TOK_EOF, TOK_ERROR } TokenType; typedef struct { TokenType type; char* lexeme; // 原始字面量，如"while" int line; // 错误定位用 int col; union { int int_val; // 数字字面量值 char* id_name; // 标识符名 } value; } Token;

关键点在于：Lexer不负责判断while是不是关键字，只按规则切出字符串；Parser在遇到TOK_ID时，查保留字表决定是否转为TOK_WHILE。这样设计，Lexer可复用于其他语言（只需换保留字表），Parser也能清晰看到“这里本应是标识符，但被识别为关键字”。

2.3 转换层：从AST到三地址码的确定性映射

语法分析器产出的是抽象语法树（AST），但直接生成目标码太难。中间插入三地址码（Three-Address Code, TAC）层是课程设计最务实的选择。每个AST节点对应1~3条TAC指令，例如：

注意：TAC不是最终目标码，而是为后续优化（如常量折叠）和目标平台生成留出接口。课程设计阶段，能稳定输出带标签的四元式（op, arg1, arg2, result）就已达标。

2.4 输出层：文本化IR与可验证的目标码格式

输出层不追求生成.exe，而输出两种可人工验证的格式：

• AST Graphviz DOT文件：用dot -Tpng ast.dot -o ast.png一键生成树图，答辩时展示结构清晰；
• TAC汇编风格文本：每行一条指令，含行号、操作码、操作数，例如：

  1: t1 = 10 2: t2 = a + t1 3: b = t2

  这种格式让老师一眼看出计算顺序是否符合预期，比二进制或内存dump直观十倍。

2.5 全局支撑模块：符号表与错误处理器的健壮性设计

符号表（SymbolTable）不是简单的char* → type哈希表。它必须支持：

• 作用域嵌套：{ int a; { int b; a = b; } }中内层b不污染外层；
• 重定义检查：同一作用域内int a; float a;报错；
• 类型推导缓存：a = 1 + 2.0时，自动将a类型升为float（可选，但加分项）。

错误处理器（ErrorHandler）拒绝printf("error!")式粗暴处理。它维护一个ErrorList，每条记录含：错误类型（LEXICAL/SYNTAX/SEMANTIC）、位置（line,col）、消息、严重等级（WARNING/ERROR/FATAL）。最终统一输出为表格：

提示：答辩时老师常问“错误恢复怎么做？”。答“遇到语法错误，Parser跳过直到下一个;或}”比“我还没实现”强十倍——哪怕只是伪代码。

3. 词法分析器实现：正则到DFA的手动构造与状态机编码

词法分析器是编译器第一道关卡，也是最容易因“小细节”全盘崩溃的模块。别迷信Flex自动生成——课程设计要求你理解过程。本方案采用手写确定性有限自动机（DFA），用switch-case状态跳转实现，完全可控、易调试、可画状态图答辩。

3.1 关键字与标识符：为什么不能先匹配关键字？

常见错误：Lexer先查"if"、"while"等字符串，匹配成功就返回TOK_IF；否则当TOK_ID。这会导致ifstream被识别为TOK_IF（因为前2字符匹配），余下stream变成非法字符。正确策略是：所有标识符统一走ID规则，Parser再查保留字表。ID的正则是[a-zA-Z_][a-zA-Z0-9_]*，状态机如下：

S0 --letter/_--> S1 S1 --letter/digit/_--> S1 S1 --other--> ACCEPT(ID)

3.2 数字字面量：整数、浮点、十六进制的分层识别

数字不能只写[0-9]+。需区分：

• 整数：[0-9]+
• 浮点：[0-9]+\.[0-9]*([eE][+-]?[0-9]+)?
• 十六进制：0[xX][0-9a-fA-F]+

状态机必须支持最长匹配（Longest Match Rule）。例如123.45e6必须整体识别为浮点，而非123（整数）+.45e6（非法）。实现时，在每个接受态（ACCEPT）记录当前最长匹配长度，仅当新路径更长时才更新。

// 伪代码：浮点数识别核心逻辑 state = START; int start_pos = stream->col; int max_len = 0; TokenType best_type = TOK_ERROR; while (1) { char c = nextChar(stream); switch(state) { case START: if (isdigit(c)) { state = INT_PART; } else if (c == '.') { state = DOT_FIRST; } else return TOK_ERROR; break; case INT_PART: if (isdigit(c)) continue; else if (c == '.') { state = FRAC_PART; } else if (c == 'e' || c == 'E') { state = EXP_START; } else { ungetChar(stream, c); max_len = stream->col - start_pos; best_type = TOK_INT; break; } // ... 其他状态 } } return best_type;

3.3 字符串与注释：规避回溯地狱的工程技巧

字符串字面量"hello\nworld"需处理转义序列\n、\t、\"。若用while(c != '"')会跳过换行导致行号错乱。正确做法：逐字符解析，遇\则读下一个字符做转义映射：

case '"': while (1) { c = nextChar(stream); if (c == '"') break; // 结束引号 else if (c == '\\') { c = nextChar(stream); switch(c) { case 'n': append('\n'); break; case 't': append('\t'); break; case '"': append('"'); break; default: error("Unknown escape \\%c", c); } } else if (c == '\n') { error("Unterminated string literal"); return TOK_ERROR; } else { append(c); } } return TOK_STRING;

提示：单行注释//和多行注释/* */必须在预处理层过滤掉，绝不传给Lexer。否则int x = 1; // comment会被切为TOK_INT, TOK_ID, TOK_ASSIGN, TOK_NUM, TOK_SEMI, TOK_COMMENT，Parser无法处理TOK_COMMENT。

3.4 状态机编码规范：让老师一眼看懂你的设计

手写DFA最怕写成“意大利面条代码”。我强制要求：

• 每个状态用enum State { S0, S1, S2, ... }明确定义；
• 主循环用while(1)，每个case只处理一个字符，无嵌套if；
• 接受态用ACCEPT(token_type)宏封装，统一做ungetChar()和return；
• 所有错误分支走REJECT()宏，记录错误位置。

这样，老师扫一眼switch(state)就能确认你理解了DFA本质，而不是堆砌条件判断。

3.5 避坑：词法分析器五大翻车现场与血泪修复

现象：输入a==b，Lexer输出TOK_ID('a'), TOK_ASSIGN('='), TOK_ID('b')，而非TOK_ID('a'), TOK_EQ('=='), TOK_ID('b')。
原因：=和==的正则存在前缀关系，DFA未按最长匹配设计，遇到第一个=就立即接受。
解决：在=状态后，必须尝试读下一个字符；若为=则走==分支，否则回退并接受单个=。代码中体现为if (nextChar() == '=') { accept(TOK_EQ); } else { ungetChar(); accept(TOK_ASSIGN); }。

现象：数字0x1A被识别为TOK_NUM(0)+TOK_ID("x1A")。
原因：十六进制规则0[xX][0-9a-fA-F]+未优先于整数规则匹配，Lexer在读到0时就接受了整数。
解决：调整规则优先级——所有以0开头的字面量，先尝试十六进制/八进制，失败再试整数。状态机中S0读到0后，进入HEX_START状态，而非直接ACCEPT(TOK_NUM)。

现象：字符串"hello\"world"解析错误，报“未知转义”。
原因：转义处理未覆盖\"，或ungetChar()后未重置列号，导致后续字符位置错乱。
解决：在case '"'分支内，nextChar()后立即更新stream->col；转义表必须包含\"、\'、\\、\n、\t、\r六种，其余一律报错。

现象：注释/* comment */跨多行，Lexer未更新stream->line，导致后续错误行号显示为1。
原因：预处理层未在跳过/* ... */时调用nextChar()并计数换行。
解决：注释处理循环中，每读到\n必须stream->line++，且stream->col=0。

现象：标识符_private被当作关键字拒绝，但规范允许以下划线开头。
原因：保留字表硬编码了"_private"，或ID正则未包含_。
解决：ID正则必须为[a-zA-Z_][a-zA-Z0-9_]*；保留字表只存"if"、"while"等真关键字，不含任何以下划线开头的词。

4. 语法分析器实现：LL(1)递归下降的确定性构造与FIRST/FOLLOW验证

语法分析器是课程设计的核心难点。很多同学抄龙书的递归下降代码，却不知为何要消除左递归、为何要计算FIRST集。本方案聚焦可验证的LL(1)构造——每条产生式都对应一个函数，每个函数调用前都用lookahead预测，全程无回溯、无猜测，答辩时可逐行解释控制流。

4.1 文法改造：从自然文法到LL(1)兼容文法

原始文法（含左递归）：

Expr → Expr + Term | Term Term → Term * Factor | Factor Factor → ( Expr ) | ID | NUM

消除左递归后（必须做！否则无限递归）：

Expr → Term Expr' Expr' → + Term Expr' | ε Term → Factor Term' Term' → * Factor Term' | ε Factor → ( Expr ) | ID | NUM

提示：ε（空产生式）不是摆设。Expr'函数必须能处理+不存在的情况，即直接返回——这是if (lookahead == '+') { ... } else { return; }的理论依据。

4.2 FIRST/FOLLOW表：手算验证与代码级映射

FIRST集决定函数入口的if判断条件，FOLLOW集决定ε产生式的触发时机。以Expr'为例：

• FIRST(+ Term Expr') = {'+'}
• FOLLOW(Expr') = {')', ';', '$'}（$表示输入结束）
  因此Expr'()函数逻辑为：

def Expr_prime(): if lookahead == '+': match('+') Term() Expr_prime() elif lookahead in [')', ';', '$']: # FOLLOW(Expr')成员 return # 推导ε else: error("Expected '+' or end of expression")

注意：match(token)函数必须校验lookahead是否匹配，并调用nextToken()推进。漏掉nextToken()会导致无限循环——这是第二大翻车点。

4.3 递归下降代码骨架：每个非终结符一个函数

所有函数遵循统一模式：

1. 检查lookahead是否在FIRST集中，是则匹配并递归；
2. 若存在ε产生式，检查lookahead是否在FOLLOW集中，是则返回；
3. 否则报错。

// C语言示例：Factor → ( Expr ) | ID | NUM void Factor() { if (lookahead.type == TOK_LPAREN) { match(TOK_LPAREN); Expr(); match(TOK_RPAREN); } else if (lookahead.type == TOK_ID) { match(TOK_ID); // 插入符号表：checkIdDeclared(lookahead.value.id_name); } else if (lookahead.type == TOK_NUM) { match(TOK_NUM); } else { error("Expected '(', ID or number, got %s", tokenTypeToString(lookahead.type)); } }

4.4 AST节点构造：在语法分析过程中实时生成

不要等Parser跑完再遍历一遍。在每个match()成功后，立即创建AST节点。例如Expr → Term Expr'中：

• Term()返回term_node；
• Expr_prime()返回expr_prime_node；
• 合并为BinaryOpNode("+", term_node, expr_prime_node)。

这样，Parser结束时AST已就绪，无需额外遍历。

4.5 避坑：语法分析器四大玄学故障与排查口诀

现象：if (x > 0) { y = 1; }解析到y = 1;时报错“Expected '}'”，但代码明显有}。
原因：StatementList规则未正确处理Statement后的分号，或match(TOK_SEMI)在y = 1后未执行，导致lookahead停在';'，而'}'分支未被触发。
解决：检查Statement()函数末尾是否有match(TOK_SEMI)；若语句本身含if/while（无分号），则StatementList必须用while (lookahead != '}' && lookahead != EOF)循环。

现象：a = b + c * d计算顺序错误，生成a = b + c; a = a * d而非a = b + (c * d)。
原因：文法未体现运算符优先级，Expr → Expr + Term和Term → Term * Factor层级正确，但代码中Expr_prime()调用Term()后未将结果作为右操作数绑定。
解决：Expr_prime()返回的节点必须是BinaryOpNode("+", left, right)，其中left是上层Term()结果，right是本次Term()结果——确保AST结构反映优先级。

现象：while (x < 10) x = x + 1;中x = x + 1被解析为while体，但x < 10的括号未被消耗。
原因：Condition规则未调用match(TOK_LPAREN)和match(TOK_RPAREN)，或match()函数有bug未推进lookahead。
解决：在Condition()函数开头match(TOK_LPAREN)，结尾match(TOK_RPAREN)，并在match()内打印调试日志printf("matched %s at %d:%d\n", ...)。

现象：空程序$（仅EOF）报错“Expected program start”。
原因：起始符号Program的FOLLOW集未包含'$'，或main()中未初始化lookahead为首个token。
解决：Program()函数首行必须是if (lookahead.type == TOK_EOF) return;（因FOLLOW(Program) = {'$'}）；main()中务必调用nextToken()获取首个token。

5. 语义分析与中间代码生成：符号表驱动的类型检查与三地址码落地

语义分析不是“锦上添花”，而是课程设计能否得高分的分水岭。它让编译器从“能解析”升级为“懂含义”。本方案采用符号表驱动的单遍语义分析，在语法分析同时完成变量声明检查、类型匹配、作用域管理，并实时生成三地址码（TAC）。

5.1 符号表设计：哈希表+作用域链的工业级实践

符号表（SymbolTable）必须支持嵌套作用域。我采用栈式作用域链：全局作用域在底，每次进入{}或if/while体时pushScope()，退出时popScope()。每个作用域是独立哈希表：

typedef struct Symbol { char* name; Type type; // INT, FLOAT, VOID, etc. int is_function; // 1 if function, 0 if variable int scope_level; // 用于调试 struct Symbol* next; } Symbol; typedef struct Scope { Symbol* symbols; struct Scope* parent; // 指向外层作用域 } Scope; typedef struct { Scope* current; int scope_level; } SymbolTable; SymbolTable* st_create() { SymbolTable* st = malloc(sizeof(SymbolTable)); st->current = malloc(sizeof(Scope)); st->current->parent = NULL; st->current->symbols = NULL; st->scope_level = 0; return st; }

5.2 声明与引用检查：在AST遍历中实时拦截错误

语义分析在AST生成后进行（也可在Parser中嵌入，但分离更清晰）。遍历AST时：

• 遇VarDecl节点：调用st_insert(st, node->name, node->type)，若返回失败则报“重复声明”；
• 遇IdNode节点：调用st_lookup(st, node->name)，若返回NULL则报“未声明”；
• 遇AssignNode：检查左右操作数类型是否兼容（INT = FLOAT警告，VOID = INT错误）。

// 类型兼容检查伪代码 bool typeCompatible(Type left, Type right) { if (left == right) return true; if (left == TYPE_INT && right == TYPE_FLOAT) return true; // 隐式转换 if (left == TYPE_FLOAT && right == TYPE_INT) return true; return false; }

5.3 三地址码生成：AST节点到TAC的确定性映射表

每个AST节点类型对应固定的TAC生成规则。关键原则：子节点先生成，父节点用其结果。例如BinaryOp("+", left, right)：

1. 生成left的TAC，得到临时变量t1；
2. 生成right的TAC，得到t2；
3. 输出t3 = t1 + t2，返回t3。

// 生成TAC的通用函数签名 char* generateCode(ASTNode* node, SymbolTable* st); // BinaryOp节点生成示例 char* generateBinaryOp(ASTNode* node, SymbolTable* st) { char* left_temp = generateCode(node->left, st); char* right_temp = generateCode(node->right, st); char* result_temp = newTemp(); // 生成新临时变量，如"t1" fprintf(tac_out, "%s = %s %s %s\n", result_temp, left_temp, opToString(node->op), right_temp); return result_temp; }

5.4 函数调用与参数传递：栈帧模拟的轻量实现

课程设计不必实现真实栈帧，但需模拟参数传递。函数调用f(a, b)生成：

param a param b call f

函数定义int f(int x, int y)在进入时生成：

x = param0 y = param1

这样，TAC层面就体现了参数绑定，为后续目标码生成打下基础。

5.5 避坑：语义分析与TAC生成的三大黑匣子与破局点

现象：int a; float a;未报错，或int a = 3.14;静默截断。
原因：st_insert()未检查同名符号是否已存在，或类型检查未启用（typeCompatible()未被调用）。
解决：st_insert()中，若st_lookup()已存在同名符号，立即error("Redeclaration of %s", name)；赋值节点必须调用typeCompatible(left_type, right_type)并根据返回值报错或警告。

现象：if (x) { ... }中x是float，但条件表达式要求int，未报类型错误。
原因：条件语句的语义规则未定义——if的条件必须是标量类型（INT或FLOAT），但代码未校验。
解决：在IfStmt节点的语义分析中，对condition子节点调用getType()，检查返回值是否为TYPE_INT或TYPE_FLOAT，否则报错“Condition must be scalar”。

现象：a = b + c生成a = b + c（正确），但a = b + c * d生成a = b + c; a = a * d（错误）。
原因：TAC生成未遵循AST结构，而是按文本顺序线性扫描。BinaryOp节点的generateCode()未递归生成子节点，而是直接拼接字符串。
解决：严格遵循“子节点先生成”原则。generateCode()对每个子节点递归调用，并用其返回值（临时变量名）参与父节点运算。

6. 实验报告撰写与答辩通关：从代码到文档的交付闭环

实验报告不是代码的说明书，而是你作为工程师的交付证明。老师看的不是你写了多少行，而是你是否建立了完整工程思维：需求是否明确？设计是否合理？实现是否可验证？问题是否可追溯？本方案提供一套可直接套用的报告结构，重点突出“我如何思考、如何决策、如何验证”。

6.1 报告核心四要素：问题定义、设计权衡、验证证据、反思迭代

一份高分报告必须回答四个问题：

1. 问题定义：用一句话说清你要解决什么。例如：“实现一个支持整型变量、算术表达式、if/while控制流的小型编译器，能将源程序编译为三地址码，并检测基本语法与语义错误。”
2. 设计权衡：解释关键选择。例如：“选用递归下降而非LR(1)，因LL(1)文法更易手写调试，且课程设计规模下性能足够；放弃Flex/Yacc，因需深入理解词法/语法分析本质。”
3. 验证证据：用数据说话。提供测试用例表，含输入、期望输出、实际输出、是否通过：

4. 反思迭代：坦诚不足与改进。例如：“当前未实现数组访问，因指针运算复杂度超出课设范围；若扩展，将在SymbolTable中增加isArray字段，并在AST中添加ArrayAccessNode。”

6.2 答辩话术设计：用“场景-动作-结果”代替技术名词堆砌

老师问：“你的词法分析器怎么处理转义字符？”
❌ 错误答法：“我用了状态机，遇到反斜杠就读下一个字符，然后查表映射。”
✅ 正确答法：“比如用户写printf("Hello\tWorld");，我的Lexer在字符串状态中，读到\就触发转义处理分支，接着读t，查转义表映射为ASCII 9（Tab），最终存入字符串字面量。这样生成的AST中，"Hello\tWorld"的内部表示就是Hello+Tab+World，后续语义分析能正确计算长度。”

老师问：“语法分析怎么保证不回溯？”
✅ 答：“我严格按LL(1)文法实现，每个非终结符函数开头都用lookahead预测。比如Factor()函数，只在lookahead是'('、ID或NUM时才执行，否则直接报错。这意味着它永远不猜、不试、不回退——就像交通灯，红灯停、绿灯行，没有黄灯犹豫。”

6.3 验收自查清单：答辩前最后一遍强制检查

在提交前，用此清单逐项核对，确保无低级失误：

从那以后我每次交课设，都强制走一遍这个清单——哪怕只剩一小时，也先跑TC01到TC05。因为答辩时老师随手敲的，往往就是清单里最基础的用例。希望帮到你。

本文还有配套的精品资源，点击获取