简介这份资源是电子科技大学编译原理课程的实验代码合集面向正在学习编译原理、需要动手实现词法分析与语法分析的高校学生及自学者。内容围绕编译器前端核心模块展开包含词法分析器与语法分析器的完整实现涉及正则表达式、有限状态自动机、LL/LR解析策略以及抽象语法树构建等关键知识点并配有运行说明文档与可执行程序便于对照验证理论到实践的落地过程。压缩包共21个文件约203KB以cpp与h源码为主另有pas示例、docx说明文档及vcxproj、sln等工程文件目录涵盖输入处理、词法分析、语法分析等模块结构清晰。目前已有2111人学习下载适合作为课程实验参考、满分代码研读与编译器开发入门的实践素材帮助读者理解token流生成、语法规则解析及工程组织方式。1. 电子科技大学编译原理实验代码从词法分析到代码生成的完整复现路线如果你正在搜“电子科技大学编译原理实验代码”大概率不是想找一份能直接交差的压缩包而是卡在了某个具体环节词法分析器的正则表达式写不对语法分析树的节点结构设计混乱或者语义分析里的符号表越写越像一锅粥。电子科技大学的编译原理实验通常以 C 或 C 为宿主语言要求从零实现一个能跑通微型语言子集的编译器前端部分年份还会延伸到三地址码生成。这套实验的核心价值不在于“写一个编译器”这个结果而在于让你亲手处理正则到 NFA 到 DFA 的转换、LL(1) 或 LR(1) 分析表的构造、语法制导翻译的落地。适合已经学过编译原理理论课、但面对空白源文件不知道第一行写什么的人。下面按实际动手顺序拆开讲每一步都给可抄的骨架和参数。2. 词法分析器从正则表达式到可运行的 DFA 扫描器2.1 为什么先手写 DFA 而不是直接上 Lex很多同学第一反应是用 flex 或 lex 生成词法分析器但电子科技大学的实验检查通常要求你展示状态转移表或转移图直接调库会被追问“DFA 最小化怎么做的”。我一般建议先用 Python 脚本把正则转 NFA、NFA 转 DFA、DFA 最小化跑一遍把中间结果打印出来再用 C 手写一个基于状态表的扫描器。这样既理解了原理又能应对检查。核心参数是状态数一个支持标识符、整数、浮点数、四则运算符和括号的微型语言最小化后的 DFA 状态通常在 15 到 25 之间。如果超过 30说明你的正则写得太碎合并一下字符类。2.2 用 Python 生成 DFA 转移表并导出为 C 数组下面这段脚本把一组正则规则转成 DFA 转移表输出成 C 数组格式。它不依赖第三方库纯手写 Thompson 构造和子集构造方便你对照课本。# regex_to_dfa.py # 输入规则列表 [(token名, 正则串), ...] # 输出C 格式的二维转移表和一维接受状态表 EPSILON class NFAState: def __init__(self): self.trans {} # char - [next_state_id] self.eps [] # epsilon 闭包 self.accept None def build_nfa(rules): # 简化版每个规则独立构造 NFA 片段最后用新起点 epsilon 连接 states [] def new_state(): s NFAState() states.append(s) return len(states) - 1 start new_state() for token, pattern in rules: # 这里只处理单字符和连接、或、闭包完整实现需递归下降解析正则 # 实际实验里建议直接手写每个 token 的 NFA 片段 pass return states, start # 更实用的做法直接手写状态表因为实验语言的正则很简单 # 状态 0 为起点接受状态用负数或单独数组标记 TRANS [ # 状态: [字母, 数字, ., , -, *, /, (, ), 其他] [1, 2, -1, 3, 4, 5, 6, 7, 8, -1], # 0 起点 [1, 1, -1, -1, -1, -1, -1, -1, -1, -1], # 1 标识符 [2, 2, 9, -1, -1, -1, -1, -1, -1, -1], # 2 整数 [9, 9, -1, -1, -1, -1, -1, -1, -1, -1], # 9 浮点小数部分 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 3 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 4 - [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 5 * [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 6 / [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 7 ( [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 8 ) ] ACCEPT {1: ID, 2: INT, 9: FLOAT, 3: PLUS, 4: MINUS, 5: STAR, 6: SLASH, 7: LPAREN, 8: RPAREN}这段代码的关键在于TRANS表的列索引映射0 到 9 分别代表字母、数字、小数点、加、减、乘、除、左括号、右括号、非法字符。-1表示死状态。ACCEPT字典把状态映射到 token 类型。实际写 C 版本时把TRANS展平成一维数组用state * 10 char_class索引速度更快。参数调整如果你的语言支持下划线开头的标识符把第 1 列在状态 0 和 1 的转移都改成 1 即可如果支持科学计数法需要在状态 9 后增加一个处理e或E的状态。2.3 C 语言扫描器骨架与缓冲区管理拿到转移表后C 端的扫描器就是一个循环读字符、查表、跳状态、记录 token 起止位置。这里给一个最小可运行骨架重点看next_token函数。// lexer.c #include stdio.h #include ctype.h #include string.h #define MAX_TOKEN 256 static const int TRANS[10][10] { /* 填入上面的表 */ }; static const char *ACCEPT[] { NULL, ID, INT, FLOAT, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN }; int char_class(int c) { if (isalpha(c) || c _) return 0; if (isdigit(c)) return 1; if (c .) return 2; if (c ) return 3; if (c -) return 4; if (c *) return 5; if (c /) return 6; if (c () return 7; if (c )) return 8; return 9; } // 返回 token 类型字符串token 文本写入 buf const char* next_token(const char **input, char *buf) { const char *p *input; while (*p isspace(*p)) p; // 跳过空白 if (!*p) return NULL; int state 0; const char *start p; int last_accept -1; const char *last_pos NULL; while (*p) { int cls char_class(*p); int ns TRANS[state][cls]; if (ns 0) break; state ns; p; if (ACCEPT[state]) { last_accept state; last_pos p; } } if (last_accept 0) { fprintf(stderr, 词法错误非法字符 %c 在位置 %ld\n, *start, start - *input); *input start 1; return ERROR; } int len last_pos - start; strncpy(buf, start, len); buf[len] \0; *input last_pos; return ACCEPT[last_accept]; }逻辑说明last_accept和last_pos实现最长匹配——即使当前状态不是接受状态只要之前遇到过接受状态就回退到那个位置。这是处理123.这种输入的关键读到小数点后状态 9 是接受状态但继续读不到数字就回退把123作为 INT 返回小数点留给下一个 token。参数注意MAX_TOKEN要大于最长标识符长度实验里设 256 足够char_class对非法字符返回 9对应转移表最后一列全是-1保证不会误吞。3. 语法分析LL(1) 分析表的构造与递归下降的取舍3.1 用 FIRST 和 FOLLOW 集生成预测分析表电子科技大学实验通常要求实现 LL(1) 或 LR(1)。LL(1) 的代码量小适合在有限时间内跑通。核心步骤对每个非终结符求 FIRST 集对每个产生式求 FOLLOW 集然后填表。下面用 Python 演示一个微型表达式文法的分析表生成。# ll1_table.py grammar { E: [[T, E]], E\: [[, T, E], [ε]], T: [[F, T]], T\: [[*, F, T], [ε]], F: [[(, E, )], [id]] } nonterms list(grammar.keys()) terms {, *, (, ), id, $} FIRST {nt: set() for nt in nonterms} FOLLOW {nt: set() for nt in nonterms} FOLLOW[E].add($) def first_of_seq(seq): if not seq: return {ε} if seq[0] in terms: return {seq[0]} res set() for sym in seq: if sym in terms: res.add(sym) return res res | (FIRST[sym] - {ε}) if ε not in FIRST[sym]: return res res.add(ε) return res changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: f first_of_seq(prod) if not f FIRST[nt]: FIRST[nt] | f changed True changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: for i, sym in enumerate(prod): if sym in nonterms: rest prod[i1:] f first_of_seq(rest) add f - {ε} if ε in f: add | FOLLOW[nt] if not add FOLLOW[sym]: FOLLOW[sym] | add changed True table {} for nt, prods in grammar.items(): for prod in prods: f first_of_seq(prod) for t in f - {ε}: table[(nt, t)] prod if ε in f: for t in FOLLOW[nt]: table[(nt, t)] prod for k in sorted(table, keylambda x: (x[0], x[1])): print(k, -, table[k])运行后会输出(E, id) - [T, E]这样的条目。参数注意ε用字符串表示实际 C 实现里可以用空产生式标记。如果表中有冲突同一个(nt, t)对应多个产生式说明文法不是 LL(1)需要提取左公因子或消除左递归。实验里常见的表达式文法经过消除左递归后都能满足。3.2 递归下降 vs 预测分析表实验检查的偏好递归下降写起来快每个非终结符一个函数代码可读性强。但电子科技大学的检查老师往往要求你展示分析栈的变化过程这时候预测分析表更直观。我的做法是先用递归下降快速跑通语义动作再补一个基于栈的预测分析版本用于演示。递归下降的坑在于回溯——如果文法不是 LL(1)你可能需要写try_parse函数保存和恢复位置。实验语言通常设计成 LL(1)所以不需要回溯。下面是一个递归下降的片段// parser.c // 全局变量当前 token 类型和文本 extern const char *cur_token; extern char cur_text[MAX_TOKEN]; void match(const char *expected) { if (strcmp(cur_token, expected) 0) { advance(); // 读下一个 token } else { fprintf(stderr, 语法错误期望 %s实际 %s\n, expected, cur_token); exit(1); } } // E - T E void parse_E() { parse_T(); parse_E_prime(); } void parse_E_prime() { if (strcmp(cur_token, PLUS) 0) { match(PLUS); parse_T(); parse_E_prime(); } // 否则 ε直接返回 }逻辑说明match负责消耗 token 并推进parse_E_prime根据当前 token 决定是否展开。参数注意advance()要处理词法错误如果next_token返回ERROR直接报错退出。递归深度等于表达式嵌套深度实验输入不会太深不用担心栈溢出。4. 语义分析与符号表语法制导翻译的落地细节4.1 符号表的数据结构选择符号表是语义分析的核心。实验里通常需要支持变量声明、类型检查、作用域嵌套。我一般用哈希表加作用域栈每个作用域一个哈希表查找时从栈顶往下找。C 语言里可以用简单的链表数组哈希函数用(hash hash * 31 c)。关键参数是桶的数量实验规模下 64 或 128 足够。下面是一个最小实现// symtab.c #define HASH_SIZE 128 typedef struct Symbol { char name[MAX_TOKEN]; char type[16]; // int 或 float int scope_level; struct Symbol *next; } Symbol; Symbol *symtab[HASH_SIZE]; int current_scope 0; unsigned int hash(const char *s) { unsigned int h 0; while (*s) h h * 31 *s; return h % HASH_SIZE; } void insert_symbol(const char *name, const char *type) { unsigned int idx hash(name); Symbol *sym malloc(sizeof(Symbol)); strcpy(sym-name, name); strcpy(sym-type, type); sym-scope_level current_scope; sym-next symtab[idx]; symtab[idx] sym; } Symbol* lookup_symbol(const char *name) { unsigned int idx hash(name); Symbol *p symtab[idx]; while (p) { if (strcmp(p-name, name) 0 p-scope_level current_scope) return p; p p-next; } return NULL; } void enter_scope() { current_scope; } void exit_scope() { // 删除当前作用域所有符号 for (int i 0; i HASH_SIZE; i) { Symbol **pp symtab[i]; while (*pp) { if ((*pp)-scope_level current_scope) { Symbol *tmp *pp; *pp (*pp)-next; free(tmp); } else { pp (*pp)-next; } } } current_scope--; }逻辑说明insert_symbol头插法插入lookup_symbol从当前作用域往下找。exit_scope遍历所有桶删除当前层符号。参数注意scope_level从 0 开始全局作用域为 0。如果实验要求支持函数参数可以在Symbol里加一个is_param标志。4.2 类型检查与三地址码生成语义分析阶段要做的第二件事是类型检查。对于int a 1.5;这种需要报错或隐式转换。我一般用一张类型兼容表int和float运算结果为float赋值时右边类型必须能隐式转到左边。三地址码生成可以在语法分析的回调里做每个表达式节点返回一个临时变量名。下面是一个表达式节点的结构typedef struct ExprNode { char *place; // 存放结果的临时变量或变量名 char *type; // int 或 float struct ExprNode *left, *right; char op; // - * / } ExprNode; ExprNode* make_binop(ExprNode *l, char op, ExprNode *r) { ExprNode *node malloc(sizeof(ExprNode)); node-left l; node-right r; node-op op; node-place new_temp(); node-type type_join(l-type, r-type); printf(%s %s %c %s\n, node-place, l-place, op, r-place); return node; }逻辑说明new_temp()生成t1、t2这样的临时变量名。type_join返回float如果任一操作数是float。参数注意临时变量编号要全局唯一可以用静态计数器。如果实验要求生成四元式把printf改成输出(op, arg1, arg2, result)即可。5. 避坑与排查编译原理实验里最容易翻车的五个地方5.1 词法分析吞掉换行导致行号错乱现象报错信息里的行号总是比实际少 1 或多 1。原因next_token跳过空白时把\n也跳过了但没有更新行号计数器。解决在跳过空白循环里判断if (*p \n) line;并且把行号作为全局变量暴露给语法分析器。5.2 LL(1) 分析表出现多重入口现象填表时同一个(非终结符, 终结符)被赋值两次。原因文法存在左递归或左公因子导致 FIRST 集和 FOLLOW 集重叠。解决先消除左递归A - Aα | β改成A - βAA - αA | ε再提取左公因子。检查方法打印 FIRST 和 FOLLOW 集看是否有非终结符的 FIRST 集包含ε且 FOLLOW 集与另一个产生式的 FIRST 集相交。5.3 符号表作用域退出时误删外层符号现象进入内层作用域后声明同名变量退出内层后外层变量也找不到了。原因exit_scope删除条件写成了scope_level current_scope。解决严格用判断只删除当前层的符号。另外如果同名变量在不同层查找时应该返回最近声明的那个所以lookup_symbol要从栈顶往下找找到第一个匹配就返回。5.4 三地址码临时变量命名冲突现象生成的代码里出现两个t1导致后续优化或解释执行时结果错误。原因临时变量计数器在递归下降的每个函数里局部定义没有全局共享。解决把temp_count定义为static int或全局变量new_temp每次递增并返回格式化字符串。注意sprintf写入的缓冲区要足够大建议char buf[16]。5.5 浮点数词法分析回退错误现象输入123.时词法分析器返回FLOAT但值为123.后续语法分析报错。原因状态 9 是接受状态但小数点后没有数字时不应该接受。解决在ACCEPT表里把状态 9 标记为接受但在next_token里增加判断如果last_accept对应FLOAT且last_pos[-1] .则回退到状态 2 的接受位置。更简单的做法是修改转移表状态 2 读到小数点后进入状态 9状态 9 只有读到数字才保持读到其他字符返回死状态这样123.会在小数点后无法继续而回退到状态 2。6. 用差分测试验证你的编译器前端写完词法、语法、语义三部分后怎么确认没有隐藏 bug我习惯用差分测试准备一组输入文件同时用你的编译器和一份参考实现比如 Python 的ast模块或手写的解释器跑比较输出。对于电子科技大学的实验参考实现可以是一个简单的 Python 脚本用eval计算表达式结果你的编译器生成三地址码后用一个栈式解释器执行两者结果应该一致。具体做法写一个run_tests.sh遍历tests/目录下的.txt文件每个文件一行表达式。你的编译器输出三地址码再用一个 20 行的 Python 解释器执行三地址码把结果和eval的结果对比。#!/bin/bash # run_tests.sh for f in tests/*.txt; do expr$(cat $f) expected$(python3 -c print($expr)) actual$(./compiler $f | python3 tac_interp.py) if [ $expected ! $actual ]; then echo FAIL: $f expected$expected actual$actual else echo PASS: $f fi donetac_interp.py是一个极简的三地址码解释器按行解析t1 3 4这样的语句用字典存变量值。这个差分测试能抓住大部分语义错误比如运算符优先级搞反、类型转换遗漏。参数注意eval对浮点数的精度和你的解释器可能不同比较时用abs(expected - actual) 1e-6。最后一个习惯每次改完语法或语义代码先跑一遍全部测试用例再手动测三个边界输入——空输入、只有空白字符的输入、超长标识符比如 300 个字符。这三个能暴露缓冲区溢出和空指针问题。希望帮到你。本文还有配套的精品资源点击获取
电子科技大学编译原理实验代码：从词法分析到代码生成的完整复现路线
简介这份资源是电子科技大学编译原理课程的实验代码合集面向正在学习编译原理、需要动手实现词法分析与语法分析的高校学生及自学者。内容围绕编译器前端核心模块展开包含词法分析器与语法分析器的完整实现涉及正则表达式、有限状态自动机、LL/LR解析策略以及抽象语法树构建等关键知识点并配有运行说明文档与可执行程序便于对照验证理论到实践的落地过程。压缩包共21个文件约203KB以cpp与h源码为主另有pas示例、docx说明文档及vcxproj、sln等工程文件目录涵盖输入处理、词法分析、语法分析等模块结构清晰。目前已有2111人学习下载适合作为课程实验参考、满分代码研读与编译器开发入门的实践素材帮助读者理解token流生成、语法规则解析及工程组织方式。1. 电子科技大学编译原理实验代码从词法分析到代码生成的完整复现路线如果你正在搜“电子科技大学编译原理实验代码”大概率不是想找一份能直接交差的压缩包而是卡在了某个具体环节词法分析器的正则表达式写不对语法分析树的节点结构设计混乱或者语义分析里的符号表越写越像一锅粥。电子科技大学的编译原理实验通常以 C 或 C 为宿主语言要求从零实现一个能跑通微型语言子集的编译器前端部分年份还会延伸到三地址码生成。这套实验的核心价值不在于“写一个编译器”这个结果而在于让你亲手处理正则到 NFA 到 DFA 的转换、LL(1) 或 LR(1) 分析表的构造、语法制导翻译的落地。适合已经学过编译原理理论课、但面对空白源文件不知道第一行写什么的人。下面按实际动手顺序拆开讲每一步都给可抄的骨架和参数。2. 词法分析器从正则表达式到可运行的 DFA 扫描器2.1 为什么先手写 DFA 而不是直接上 Lex很多同学第一反应是用 flex 或 lex 生成词法分析器但电子科技大学的实验检查通常要求你展示状态转移表或转移图直接调库会被追问“DFA 最小化怎么做的”。我一般建议先用 Python 脚本把正则转 NFA、NFA 转 DFA、DFA 最小化跑一遍把中间结果打印出来再用 C 手写一个基于状态表的扫描器。这样既理解了原理又能应对检查。核心参数是状态数一个支持标识符、整数、浮点数、四则运算符和括号的微型语言最小化后的 DFA 状态通常在 15 到 25 之间。如果超过 30说明你的正则写得太碎合并一下字符类。2.2 用 Python 生成 DFA 转移表并导出为 C 数组下面这段脚本把一组正则规则转成 DFA 转移表输出成 C 数组格式。它不依赖第三方库纯手写 Thompson 构造和子集构造方便你对照课本。# regex_to_dfa.py # 输入规则列表 [(token名, 正则串), ...] # 输出C 格式的二维转移表和一维接受状态表 EPSILON class NFAState: def __init__(self): self.trans {} # char - [next_state_id] self.eps [] # epsilon 闭包 self.accept None def build_nfa(rules): # 简化版每个规则独立构造 NFA 片段最后用新起点 epsilon 连接 states [] def new_state(): s NFAState() states.append(s) return len(states) - 1 start new_state() for token, pattern in rules: # 这里只处理单字符和连接、或、闭包完整实现需递归下降解析正则 # 实际实验里建议直接手写每个 token 的 NFA 片段 pass return states, start # 更实用的做法直接手写状态表因为实验语言的正则很简单 # 状态 0 为起点接受状态用负数或单独数组标记 TRANS [ # 状态: [字母, 数字, ., , -, *, /, (, ), 其他] [1, 2, -1, 3, 4, 5, 6, 7, 8, -1], # 0 起点 [1, 1, -1, -1, -1, -1, -1, -1, -1, -1], # 1 标识符 [2, 2, 9, -1, -1, -1, -1, -1, -1, -1], # 2 整数 [9, 9, -1, -1, -1, -1, -1, -1, -1, -1], # 9 浮点小数部分 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 3 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 4 - [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 5 * [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 6 / [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 7 ( [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 8 ) ] ACCEPT {1: ID, 2: INT, 9: FLOAT, 3: PLUS, 4: MINUS, 5: STAR, 6: SLASH, 7: LPAREN, 8: RPAREN}这段代码的关键在于TRANS表的列索引映射0 到 9 分别代表字母、数字、小数点、加、减、乘、除、左括号、右括号、非法字符。-1表示死状态。ACCEPT字典把状态映射到 token 类型。实际写 C 版本时把TRANS展平成一维数组用state * 10 char_class索引速度更快。参数调整如果你的语言支持下划线开头的标识符把第 1 列在状态 0 和 1 的转移都改成 1 即可如果支持科学计数法需要在状态 9 后增加一个处理e或E的状态。2.3 C 语言扫描器骨架与缓冲区管理拿到转移表后C 端的扫描器就是一个循环读字符、查表、跳状态、记录 token 起止位置。这里给一个最小可运行骨架重点看next_token函数。// lexer.c #include stdio.h #include ctype.h #include string.h #define MAX_TOKEN 256 static const int TRANS[10][10] { /* 填入上面的表 */ }; static const char *ACCEPT[] { NULL, ID, INT, FLOAT, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN }; int char_class(int c) { if (isalpha(c) || c _) return 0; if (isdigit(c)) return 1; if (c .) return 2; if (c ) return 3; if (c -) return 4; if (c *) return 5; if (c /) return 6; if (c () return 7; if (c )) return 8; return 9; } // 返回 token 类型字符串token 文本写入 buf const char* next_token(const char **input, char *buf) { const char *p *input; while (*p isspace(*p)) p; // 跳过空白 if (!*p) return NULL; int state 0; const char *start p; int last_accept -1; const char *last_pos NULL; while (*p) { int cls char_class(*p); int ns TRANS[state][cls]; if (ns 0) break; state ns; p; if (ACCEPT[state]) { last_accept state; last_pos p; } } if (last_accept 0) { fprintf(stderr, 词法错误非法字符 %c 在位置 %ld\n, *start, start - *input); *input start 1; return ERROR; } int len last_pos - start; strncpy(buf, start, len); buf[len] \0; *input last_pos; return ACCEPT[last_accept]; }逻辑说明last_accept和last_pos实现最长匹配——即使当前状态不是接受状态只要之前遇到过接受状态就回退到那个位置。这是处理123.这种输入的关键读到小数点后状态 9 是接受状态但继续读不到数字就回退把123作为 INT 返回小数点留给下一个 token。参数注意MAX_TOKEN要大于最长标识符长度实验里设 256 足够char_class对非法字符返回 9对应转移表最后一列全是-1保证不会误吞。3. 语法分析LL(1) 分析表的构造与递归下降的取舍3.1 用 FIRST 和 FOLLOW 集生成预测分析表电子科技大学实验通常要求实现 LL(1) 或 LR(1)。LL(1) 的代码量小适合在有限时间内跑通。核心步骤对每个非终结符求 FIRST 集对每个产生式求 FOLLOW 集然后填表。下面用 Python 演示一个微型表达式文法的分析表生成。# ll1_table.py grammar { E: [[T, E]], E\: [[, T, E], [ε]], T: [[F, T]], T\: [[*, F, T], [ε]], F: [[(, E, )], [id]] } nonterms list(grammar.keys()) terms {, *, (, ), id, $} FIRST {nt: set() for nt in nonterms} FOLLOW {nt: set() for nt in nonterms} FOLLOW[E].add($) def first_of_seq(seq): if not seq: return {ε} if seq[0] in terms: return {seq[0]} res set() for sym in seq: if sym in terms: res.add(sym) return res res | (FIRST[sym] - {ε}) if ε not in FIRST[sym]: return res res.add(ε) return res changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: f first_of_seq(prod) if not f FIRST[nt]: FIRST[nt] | f changed True changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: for i, sym in enumerate(prod): if sym in nonterms: rest prod[i1:] f first_of_seq(rest) add f - {ε} if ε in f: add | FOLLOW[nt] if not add FOLLOW[sym]: FOLLOW[sym] | add changed True table {} for nt, prods in grammar.items(): for prod in prods: f first_of_seq(prod) for t in f - {ε}: table[(nt, t)] prod if ε in f: for t in FOLLOW[nt]: table[(nt, t)] prod for k in sorted(table, keylambda x: (x[0], x[1])): print(k, -, table[k])运行后会输出(E, id) - [T, E]这样的条目。参数注意ε用字符串表示实际 C 实现里可以用空产生式标记。如果表中有冲突同一个(nt, t)对应多个产生式说明文法不是 LL(1)需要提取左公因子或消除左递归。实验里常见的表达式文法经过消除左递归后都能满足。3.2 递归下降 vs 预测分析表实验检查的偏好递归下降写起来快每个非终结符一个函数代码可读性强。但电子科技大学的检查老师往往要求你展示分析栈的变化过程这时候预测分析表更直观。我的做法是先用递归下降快速跑通语义动作再补一个基于栈的预测分析版本用于演示。递归下降的坑在于回溯——如果文法不是 LL(1)你可能需要写try_parse函数保存和恢复位置。实验语言通常设计成 LL(1)所以不需要回溯。下面是一个递归下降的片段// parser.c // 全局变量当前 token 类型和文本 extern const char *cur_token; extern char cur_text[MAX_TOKEN]; void match(const char *expected) { if (strcmp(cur_token, expected) 0) { advance(); // 读下一个 token } else { fprintf(stderr, 语法错误期望 %s实际 %s\n, expected, cur_token); exit(1); } } // E - T E void parse_E() { parse_T(); parse_E_prime(); } void parse_E_prime() { if (strcmp(cur_token, PLUS) 0) { match(PLUS); parse_T(); parse_E_prime(); } // 否则 ε直接返回 }逻辑说明match负责消耗 token 并推进parse_E_prime根据当前 token 决定是否展开。参数注意advance()要处理词法错误如果next_token返回ERROR直接报错退出。递归深度等于表达式嵌套深度实验输入不会太深不用担心栈溢出。4. 语义分析与符号表语法制导翻译的落地细节4.1 符号表的数据结构选择符号表是语义分析的核心。实验里通常需要支持变量声明、类型检查、作用域嵌套。我一般用哈希表加作用域栈每个作用域一个哈希表查找时从栈顶往下找。C 语言里可以用简单的链表数组哈希函数用(hash hash * 31 c)。关键参数是桶的数量实验规模下 64 或 128 足够。下面是一个最小实现// symtab.c #define HASH_SIZE 128 typedef struct Symbol { char name[MAX_TOKEN]; char type[16]; // int 或 float int scope_level; struct Symbol *next; } Symbol; Symbol *symtab[HASH_SIZE]; int current_scope 0; unsigned int hash(const char *s) { unsigned int h 0; while (*s) h h * 31 *s; return h % HASH_SIZE; } void insert_symbol(const char *name, const char *type) { unsigned int idx hash(name); Symbol *sym malloc(sizeof(Symbol)); strcpy(sym-name, name); strcpy(sym-type, type); sym-scope_level current_scope; sym-next symtab[idx]; symtab[idx] sym; } Symbol* lookup_symbol(const char *name) { unsigned int idx hash(name); Symbol *p symtab[idx]; while (p) { if (strcmp(p-name, name) 0 p-scope_level current_scope) return p; p p-next; } return NULL; } void enter_scope() { current_scope; } void exit_scope() { // 删除当前作用域所有符号 for (int i 0; i HASH_SIZE; i) { Symbol **pp symtab[i]; while (*pp) { if ((*pp)-scope_level current_scope) { Symbol *tmp *pp; *pp (*pp)-next; free(tmp); } else { pp (*pp)-next; } } } current_scope--; }逻辑说明insert_symbol头插法插入lookup_symbol从当前作用域往下找。exit_scope遍历所有桶删除当前层符号。参数注意scope_level从 0 开始全局作用域为 0。如果实验要求支持函数参数可以在Symbol里加一个is_param标志。4.2 类型检查与三地址码生成语义分析阶段要做的第二件事是类型检查。对于int a 1.5;这种需要报错或隐式转换。我一般用一张类型兼容表int和float运算结果为float赋值时右边类型必须能隐式转到左边。三地址码生成可以在语法分析的回调里做每个表达式节点返回一个临时变量名。下面是一个表达式节点的结构typedef struct ExprNode { char *place; // 存放结果的临时变量或变量名 char *type; // int 或 float struct ExprNode *left, *right; char op; // - * / } ExprNode; ExprNode* make_binop(ExprNode *l, char op, ExprNode *r) { ExprNode *node malloc(sizeof(ExprNode)); node-left l; node-right r; node-op op; node-place new_temp(); node-type type_join(l-type, r-type); printf(%s %s %c %s\n, node-place, l-place, op, r-place); return node; }逻辑说明new_temp()生成t1、t2这样的临时变量名。type_join返回float如果任一操作数是float。参数注意临时变量编号要全局唯一可以用静态计数器。如果实验要求生成四元式把printf改成输出(op, arg1, arg2, result)即可。5. 避坑与排查编译原理实验里最容易翻车的五个地方5.1 词法分析吞掉换行导致行号错乱现象报错信息里的行号总是比实际少 1 或多 1。原因next_token跳过空白时把\n也跳过了但没有更新行号计数器。解决在跳过空白循环里判断if (*p \n) line;并且把行号作为全局变量暴露给语法分析器。5.2 LL(1) 分析表出现多重入口现象填表时同一个(非终结符, 终结符)被赋值两次。原因文法存在左递归或左公因子导致 FIRST 集和 FOLLOW 集重叠。解决先消除左递归A - Aα | β改成A - βAA - αA | ε再提取左公因子。检查方法打印 FIRST 和 FOLLOW 集看是否有非终结符的 FIRST 集包含ε且 FOLLOW 集与另一个产生式的 FIRST 集相交。5.3 符号表作用域退出时误删外层符号现象进入内层作用域后声明同名变量退出内层后外层变量也找不到了。原因exit_scope删除条件写成了scope_level current_scope。解决严格用判断只删除当前层的符号。另外如果同名变量在不同层查找时应该返回最近声明的那个所以lookup_symbol要从栈顶往下找找到第一个匹配就返回。5.4 三地址码临时变量命名冲突现象生成的代码里出现两个t1导致后续优化或解释执行时结果错误。原因临时变量计数器在递归下降的每个函数里局部定义没有全局共享。解决把temp_count定义为static int或全局变量new_temp每次递增并返回格式化字符串。注意sprintf写入的缓冲区要足够大建议char buf[16]。5.5 浮点数词法分析回退错误现象输入123.时词法分析器返回FLOAT但值为123.后续语法分析报错。原因状态 9 是接受状态但小数点后没有数字时不应该接受。解决在ACCEPT表里把状态 9 标记为接受但在next_token里增加判断如果last_accept对应FLOAT且last_pos[-1] .则回退到状态 2 的接受位置。更简单的做法是修改转移表状态 2 读到小数点后进入状态 9状态 9 只有读到数字才保持读到其他字符返回死状态这样123.会在小数点后无法继续而回退到状态 2。6. 用差分测试验证你的编译器前端写完词法、语法、语义三部分后怎么确认没有隐藏 bug我习惯用差分测试准备一组输入文件同时用你的编译器和一份参考实现比如 Python 的ast模块或手写的解释器跑比较输出。对于电子科技大学的实验参考实现可以是一个简单的 Python 脚本用eval计算表达式结果你的编译器生成三地址码后用一个栈式解释器执行两者结果应该一致。具体做法写一个run_tests.sh遍历tests/目录下的.txt文件每个文件一行表达式。你的编译器输出三地址码再用一个 20 行的 Python 解释器执行三地址码把结果和eval的结果对比。#!/bin/bash # run_tests.sh for f in tests/*.txt; do expr$(cat $f) expected$(python3 -c print($expr)) actual$(./compiler $f | python3 tac_interp.py) if [ $expected ! $actual ]; then echo FAIL: $f expected$expected actual$actual else echo PASS: $f fi donetac_interp.py是一个极简的三地址码解释器按行解析t1 3 4这样的语句用字典存变量值。这个差分测试能抓住大部分语义错误比如运算符优先级搞反、类型转换遗漏。参数注意eval对浮点数的精度和你的解释器可能不同比较时用abs(expected - actual) 1e-6。最后一个习惯每次改完语法或语义代码先跑一遍全部测试用例再手动测三个边界输入——空输入、只有空白字符的输入、超长标识符比如 300 个字符。这三个能暴露缓冲区溢出和空指针问题。希望帮到你。本文还有配套的精品资源点击获取
