简介这份《编译原理名词解释》完整版PDF面向计算机专业学生与备考期末、考研的学习者系统梳理编译原理课程中的核心概念与高频考点帮助读者在复习阶段快速建立知识框架、查漏补缺。资源为单个PDF文件压缩包约406KB内容按基础概念、翻译程序分类、编译过程、辅助数据结构、编译程序结构、文件格式、编译流程及高级概念等模块编排涵盖源语言与目标语言、编译与解释程序、词法分析与语法分析、中间代码与目标代码生成、符号表与常数表、前端与后端划分等条目并延伸至正规式、左递归消除、提取左因子、First集与Follow集、LL(1)与LR(0)、SLR分析表构造及LR语法分析器控制程序等进阶知识点条目释义简洁、便于背诵与对照理解。目前已有93人学习下载适合需要集中记忆名词定义、梳理编译流程脉络的读者使用。1. 编译原理名词解释从一份 PDF 到能上手改词法分析器很多人第一次翻开编译原理的课程资料看到满页的“正规式”“NFA 到 DFA 的确定化”“SLR 项目集闭包”第一反应是背下来应付考试。但真正做过编译器前端的人知道这些名词解释不是用来背的而是用来查的——当你的词法分析器在某个输入上卡死或者语法分析器报了一个莫名其妙的移进/归约冲突能救你的往往就是对这些名词的准确理解。这份“编译原理名词解释”资料的价值不在于它列了多少词条而在于它能不能帮你把“符号表”“语法制导翻译”“运行时存储组织”这些概念对应到一段能跑起来的代码上。这篇文章面向的是正在做编译原理实验、或者想自己写一个小型编译器前端的开发者我会把这份资料里最常被查的名词拆开讲清楚每个概念在代码里长什么样、参数怎么设、哪里最容易翻车。2. 词法分析核心名词正规式、NFA、DFA 与词法分析器生成2.1 正规式到 NFAThompson 构造法的代码落地名词解释里对“正规式”的定义通常是一种用于描述正则语言的代数表达式由字符、连接、选择、闭包等运算构成。但光看定义没用你得知道它在代码里怎么变成状态机。常见做法是用 Thompson 构造法把每个正规式片段转成一个带 ε 转移的 NFA 片段再拼起来。下面是一个简化版的 Thompson 构造实现支持连接、选择和闭包三种基本运算class NFAState: def __init__(self): self.epsilon [] # ε 转移目标状态列表 self.transitions {} # 字符 - 目标状态列表 self.is_end False def build_nfa_for_char(c): 为单个字符构造 NFA 片段 start NFAState() end NFAState() start.transitions[c] [end] end.is_end True return start, end def build_nfa_concat(nfa1, nfa2): 连接把第一个的接受状态通过 ε 连到第二个的起始状态 start1, end1 nfa1 start2, end2 nfa2 end1.is_end False end1.epsilon.append(start2) return start1, end2 def build_nfa_union(nfa1, nfa2): 选择新建起止状态用 ε 分支 start NFAState() end NFAState() start.epsilon.extend([nfa1[0], nfa2[0]]) nfa1[1].epsilon.append(end) nfa2[1].epsilon.append(end) nfa1[1].is_end False nfa2[1].is_end False end.is_end True return start, end def build_nfa_star(nfa): 闭包允许跳过或重复 start NFAState() end NFAState() start.epsilon.extend([nfa[0], end]) nfa[1].epsilon.extend([nfa[0], end]) nfa[1].is_end False end.is_end True return start, end这段代码的关键在于epsilon列表和transitions字典的配合。epsilon存的是不需要消耗输入字符就能跳过去的状态transitions存的是必须匹配某个字符才能走的状态。参数上唯一需要注意的是is_end标记它在拼接过程中会被反复改写如果忘记在连接时把前一个片段的is_end置为False最终 NFA 会有多个接受状态确定化时就会多出不必要的终态。2.2 NFA 到 DFA 的确定化子集构造法与状态爆炸名词解释里“确定化”通常一笔带过但实际写代码时子集构造法的核心是计算 ε-闭包和 move 集合。ε-闭包指的是从某个状态集合出发只走 ε 转移能到达的所有状态move 则是消耗一个字符后能到达的状态集合。def epsilon_closure(states): 计算状态集合的 ε-闭包 stack list(states) closure set(states) while stack: s stack.pop() for next_s in s.epsilon: if next_s not in closure: closure.add(next_s) stack.append(next_s) return closure def move(states, char): 从状态集合出发消耗字符 char 后到达的状态集合 result set() for s in states: if char in s.transitions: result.update(s.transitions[char]) return result def nfa_to_dfa(nfa_start): 子集构造法主流程 start_closure frozenset(epsilon_closure({nfa_start})) dfa_states {start_closure: 0} queue [start_closure] transitions {} while queue: current queue.pop(0) # 收集所有可能的输入字符 chars set() for s in current: chars.update(s.transitions.keys()) for c in chars: next_set frozenset(epsilon_closure(move(current, c))) if not next_set: continue if next_set not in dfa_states: dfa_states[next_set] len(dfa_states) queue.append(next_set) transitions[(dfa_states[current], c)] dfa_states[next_set] return dfa_states, transitions这里用frozenset作为 DFA 状态的身份标识是因为普通set不可哈希没法当字典键。参数上最需要注意的是chars的收集范围——如果只从当前状态集合里收集字符可能会漏掉某些转移导致 DFA 不完整。实际工程中词法分析器的 DFA 通常还会补一个“死状态”把所有未定义的转移都指向它避免运行时空指针。2.3 词法分析器生成工具从名词到可执行文件如果你不想手写 NFA/DFA常见做法是用 flex 或 ANTLR 这类工具。以 flex 为例你写的是正规式规则它帮你生成 C 代码。但名词解释里不会告诉你的是flex 的规则匹配遵循“最长匹配”和“最先出现优先”两条原则。这意味着如果你把关键字规则写在标识符规则后面if会被当成标识符匹配掉。# 一个最小 flex 规则示例 %% if { return IF; } else { return ELSE; } [0-9] { yylval atoi(yytext); return NUMBER; } [a-zA-Z_][a-zA-Z0-9_]* { yylval strdup(yytext); return ID; } [ \t\n] { /* 跳过空白 */ } . { return yytext[0]; } %%这段规则里if和else必须写在标识符规则前面否则永远不会被匹配到。yytext是 flex 提供的当前匹配文本指针yylval用来往语法分析器传值。参数上唯一要调的是缓冲区大小和YY_DECL宏默认栈大小在极端长标识符场景下会溢出。3. 语法分析核心名词上下文无关文法、推导与语法树3.1 上下文无关文法与推导从产生式到语法树名词解释对“上下文无关文法”的定义是一个四元组 (V, T, P, S)其中 V 是非终结符集合T 是终结符集合P 是产生式集合S 是开始符号。但真正写语法分析器时你关心的是推导方向最左推导对应自顶向下分析最右推导的逆过程对应自底向上分析。class Grammar: def __init__(self, productions, start): self.productions productions # dict: 非终结符 - 产生式右部列表 self.start start def leftmost_derivation(self, target, max_steps100): 最左推导每次替换最左边的非终结符 sentential [self.start] steps [list(sentential)] for _ in range(max_steps): # 找到最左边的非终结符 idx None for i, sym in enumerate(sentential): if sym in self.productions: idx i break if idx is None: break nonterminal sentential[idx] # 尝试每个产生式 for rhs in self.productions[nonterminal]: new_sentential sentential[:idx] list(rhs) sentential[idx1:] steps.append(list(new_sentential)) if new_sentential list(target): return steps sentential new_sentential break return steps这段代码演示了最左推导的搜索过程。参数max_steps是防止无限递归的后悔药因为左递归文法会让推导永远停不下来。实际写递归下降分析器时必须消除左递归否则栈会直接爆掉。3.2 LL(1) 与 LR(1)FIRST 集、FOLLOW 集与预测分析表名词解释里“FIRST 集”和“FOLLOW 集”的定义通常很抽象。FIRST(α) 是从 α 出发能推导出的所有终结符开头的集合FOLLOW(A) 是在某个句型中紧跟在 A 后面的终结符集合。这两个集合是构造 LL(1) 预测分析表的基础。def compute_first(grammar): 计算所有符号的 FIRST 集 first {sym: set() for sym in grammar.productions} for sym in grammar.productions: first[sym] set() changed True while changed: changed False for nonterminal, rhs_list in grammar.productions.items(): for rhs in rhs_list: if not rhs: continue # 如果右部第一个是终结符直接加入 if rhs[0] not in grammar.productions: if rhs[0] not in first[nonterminal]: first[nonterminal].add(rhs[0]) changed True else: # 否则把第一个非终结符的 FIRST 集加入 for sym in first[rhs[0]]: if sym not in first[nonterminal]: first[nonterminal].add(sym) changed True return first这段代码的迭代终止条件是changed变为False因为 FIRST 集的计算是单调递增的最多迭代到不动点。参数上要注意空产生式ε 产生式的处理如果某个非终结符能推导出空串那么它的 FIRST 集要包含 ε并且计算 FOLLOW 集时要特殊处理。3.3 语法树与抽象语法树从解析到中间表示名词解释里“语法树”和“抽象语法树”经常被混在一起。语法树保留了所有推导细节包括括号和冗余的非终结符抽象语法树则去掉了这些只保留运算结构和操作数。实际编译器里语法分析器输出的是 AST因为后续的语义分析和代码生成不需要知道当初是怎么推导的。class ASTNode: def __init__(self, kind, childrenNone, valueNone): self.kind kind # 节点类型binary_op, number, identifier self.children children or [] self.value value # 叶子节点的值 def build_ast_from_parse_tree(parse_node): 从语法树节点构建 AST 的简化示例 if parse_node.kind expr: # 如果 expr 只有一个子节点直接透传 if len(parse_node.children) 1: return build_ast_from_parse_tree(parse_node.children[0]) # 否则认为是二元运算 left build_ast_from_parse_tree(parse_node.children[0]) op parse_node.children[1].value right build_ast_from_parse_tree(parse_node.children[2]) return ASTNode(binary_op, [left, right], op) elif parse_node.kind number: return ASTNode(number, valueparse_node.value) elif parse_node.kind identifier: return ASTNode(identifier, valueparse_node.value) return None这段代码的关键在于kind字段的语义约定。binary_op节点的children固定为两个元素value存运算符number和identifier是叶子节点没有子节点。参数上唯一要小心的是运算符优先级——如果语法分析器输出的语法树没有正确处理优先级AST 构建时就会得到错误的结合顺序。4. 语义分析与符号表类型检查、作用域与属性文法4.1 符号表的数据结构从线性表到哈希表名词解释对“符号表”的定义是用于存储程序中标识符及其属性的数据结构。但实际实现时符号表的设计直接决定了编译器的性能。最简单的是线性表插入 O(1)、查找 O(n)常见做法是用哈希表加作用域链。class SymbolTable: def __init__(self): self.scopes [{}] # 栈式作用域索引 0 是全局作用域 def enter_scope(self): self.scopes.append({}) def exit_scope(self): if len(self.scopes) 1: self.scopes.pop() def insert(self, name, symbol_info): 在当前作用域插入符号重复定义报错 current self.scopes[-1] if name in current: raise Exception(f重复定义: {name}) current[name] symbol_info def lookup(self, name): 从内到外查找符号 for scope in reversed(self.scopes): if name in scope: return scope[name] return None def lookup_current_scope(self, name): 只在当前作用域查找用于判断重复定义 return self.scopes[-1].get(name)这段代码用列表模拟作用域栈enter_scope和exit_scope对应进入和离开一个块。参数上要注意的是insert只在当前作用域检查重复lookup则从内到外遍历。如果语言支持“先声明后使用”那么lookup在遇到未声明标识符时应该报错而不是返回None让调用方自己判断。4.2 类型检查与类型系统从简单类型到类型推导名词解释里“类型检查”通常分为静态检查和动态检查。静态检查在编译期完成需要类型环境来记录每个表达式的类型。下面是一个简单的类型检查器框架class TypeChecker: def __init__(self, symbol_table): self.symbol_table symbol_table self.type_env {} # 表达式节点 - 类型 def check(self, node): 递归检查 AST 节点返回类型 if node.kind number: self.type_env[id(node)] int return int elif node.kind identifier: sym self.symbol_table.lookup(node.value) if sym is None: raise Exception(f未声明标识符: {node.value}) self.type_env[id(node)] sym[type] return sym[type] elif node.kind binary_op: left_type self.check(node.children[0]) right_type self.check(node.children[1]) if left_type ! right_type: raise Exception(f类型不匹配: {left_type} vs {right_type}) self.type_env[id(node)] left_type return left_type return unknown这段代码用id(node)作为类型环境的键因为 AST 节点是可变对象不能直接哈希。参数上要注意的是binary_op的类型规则——这里简化成左右类型必须相同实际语言里还要考虑隐式类型转换和运算符重载。4.3 属性文法与语法制导翻译从综合属性到继承属性名词解释对“属性文法”的定义是在上下文无关文法基础上为每个产生式附加一组属性等式。综合属性从子节点往父节点传继承属性从父节点往子节点传。实际写语义分析器时你不需要显式构造属性文法但需要知道哪些信息是自底向上算的哪些是自顶向下传的。class SDTNode: def __init__(self, kind): self.kind kind self.synthesized {} # 综合属性 self.inherited {} # 继承属性 def evaluate_sdt(node, inherited_attrsNone): 语法制导翻译的简化求值过程 if inherited_attrs: node.inherited.update(inherited_attrs) # 先递归处理子节点传入继承属性 for child in node.children: evaluate_sdt(child, node.inherited) # 再根据子节点的综合属性计算当前节点的综合属性 if node.kind add: node.synthesized[value] ( node.children[0].synthesized[value] node.children[1].synthesized[value] ) elif node.kind num: node.synthesized[value] node.inherited.get(value, 0) return node.synthesized这段代码展示了综合属性和继承属性的求值顺序继承属性在递归下降前传入综合属性在子节点处理完后计算。参数上要注意的是inherited字典的传递方向——如果某个属性既不是纯综合也不是纯继承就需要多遍扫描。5. 避坑与排查编译原理实验里最容易翻车的五个地方5.1 词法分析器把关键字识别成标识符现象输入if (x 0)词法分析器返回的 token 序列是ID LPAREN ID GT NUMBER RPARENif被当成普通标识符。原因flex 或手写词法分析器里标识符规则的正规式覆盖了关键字。因为标识符规则[a-zA-Z_][a-zA-Z0-9_]*也能匹配if而规则匹配遵循“最长匹配”两者长度相同于是按“最先出现优先”决定如果标识符规则写在前面关键字就永远匹配不到。解决把关键字规则写在标识符规则前面或者在标识符匹配成功后查关键字表命中则返回关键字 token。手写词法分析器时常见做法是先按标识符规则读出整个单词再查保留字表。5.2 递归下降分析器遇到左递归直接栈溢出现象语法规则写成expr - expr term | term递归下降分析器一调用就报RecursionError。原因递归下降是自顶向下的expr的产生式右部第一个符号又是expr导致无限递归。名词解释里“左递归”的定义就是产生式右部最左符号等于左部非终结符。解决消除左递归把expr - expr term | term改写成expr - term expr和expr - term expr | ε。改写后递归下降分析器就能正常工作了。如果不想改文法可以用 Earley 或 CYK 这类通用分析算法但性能会差很多。5.3 SLR 分析表出现移进/归约冲突现象用 SLR 方法构造分析表时某个状态里同时存在移进动作和归约动作分析器不知道该走哪条路。原因SLR 只用了 FOLLOW 集来判断归约时机粒度太粗。如果某个非终结符的 FOLLOW 集里包含了一个字符而这个字符在当前状态下又可以移进就会冲突。解决升级到 LR(1) 或 LALR(1)。LR(1) 为每个项目附加展望符精度更高LALR(1) 合并同心项目集表的大小和 SLR 差不多但冲突更少。实际工程里 yacc/bison 默认用 LALR(1)遇到冲突会报出来你可以手动给运算符指定优先级和结合性来消解。5.4 符号表作用域退出时忘记恢复现象在某个块里定义的变量退出块之后还能被查到导致“未声明标识符”检查失效。原因enter_scope和exit_scope没有成对调用或者exit_scope里没有正确弹出作用域。常见于语法分析器在错误恢复时跳过了exit_scope。解决用 try/finally 保证exit_scope一定执行或者在 AST 遍历时用访问者模式进入块节点时enter_scope离开时exit_scope。符号表本身可以用栈式结构退出时直接 pop不需要逐个删除。5.5 类型检查时把 AST 节点当字典键导致哈希失败现象用type_env[node] int存类型信息运行时报TypeError: unhashable type。原因AST 节点是自定义类的实例默认没有实现__hash__和__eq__Python 里可变对象默认不可哈希。解决用id(node)作为键或者给 AST 节点加一个唯一的node_id字段。如果需要在类型环境里按结构查找可以序列化节点为字符串再哈希但性能会差一些。常见做法是直接在节点对象上挂一个type属性避免额外的字典查找。6. 从名词解释到能跑的编译器前端一个最小验证方法学完这些名词怎么验证自己真的懂了我的习惯是拿一份“编译原理名词解释”资料随机挑十个词条每个词条写一段不超过 50 行的代码来演示它。如果写不出来说明还停留在背诵阶段。比如“语法制导翻译”这个词你可以写一个计算器在语法分析的同时算出表达式值“符号表”这个词你可以写一个支持嵌套作用域的变量查找器。下面是一个最小验证框架把词法、语法、语义串起来输入一个算术表达式输出计算结果# 最小编译器前端验证支持 - * / 和括号 import re TOKEN_RE re.compile(r\s*(?:(\d)|([\-*/()]))) def tokenize(text): tokens [] pos 0 while pos len(text): m TOKEN_RE.match(text, pos) if not m: raise Exception(f词法错误: {text[pos:]}) if m.group(1): tokens.append((NUM, int(m.group(1)))) elif m.group(2): tokens.append((m.group(2), m.group(2))) pos m.end() tokens.append((EOF, None)) return tokens class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def consume(self, expectedNone): tok self.tokens[self.pos] if expected and tok[0] ! expected: raise Exception(f语法错误: 期望 {expected}得到 {tok[0]}) self.pos 1 return tok def parse_expr(self): expr - term ((|-) term)* left self.parse_term() while self.peek()[0] in (, -): op self.consume()[0] right self.parse_term() left left right if op else left - right return left def parse_term(self): term - factor ((*|/) factor)* left self.parse_factor() while self.peek()[0] in (*, /): op self.consume()[0] right self.parse_factor() if op *: left left * right else: if right 0: raise Exception(运行时错误: 除以零) left left / right return left def parse_factor(self): factor - NUM | ( expr ) tok self.peek() if tok[0] NUM: self.consume() return tok[1] elif tok[0] (: self.consume(() val self.parse_expr() self.consume()) return val else: raise Exception(f语法错误: 意外的 token {tok[0]}) def evaluate(text): tokens tokenize(text) parser Parser(tokens) result parser.parse_expr() if parser.peek()[0] ! EOF: raise Exception(语法错误: 表达式末尾有多余内容) return result # 测试 print(evaluate(1 2 * (3 - 1))) # 输出 5这个框架里tokenize对应词法分析Parser的三个parse_*方法对应递归下降语法分析每个方法里直接算值对应语法制导翻译。参数上唯一要调的是TOKEN_RE的正则如果要支持更多运算符改这个正则和对应的parse_*方法就行。我自己的习惯是每学一个新名词就往这个框架里加一个特性比如加变量支持就要引入符号表加类型检查就要在 AST 上挂类型属性。这样积累下来名词解释就不再是纸上的定义而是你调试过的代码。希望帮到你。本文还有配套的精品资源点击获取