编译原理名词解释
可以点击这里使用名词解释小工具
一、基础语法与形式语言
- LHS / Left-Hand Side：产生式左侧，通常为单个非终结符
- RHS / Right-Hand Side：产生式右侧，由终结符与非终结符组成的序列
RL / Regular Language：正则语言，可由有限自动机识别的语言类
CFL / Context-Free Language：上下文无关语言，可由下推自动机识别
CFG / Context-Free Grammar：上下文无关文法，用于描述 CFL
DFA / Deterministic Finite Automaton：确定有限自动机，每个状态对同一输入有唯一转移
NFA / Non-deterministic Finite Automaton：非确定有限自动机，存在 ε 转移或多条路径
PDA / Pushdown Automaton：下推自动机，带栈的有限自动机，识别 CFL
NPDA / Non-deterministic Pushdown Automaton：非确定下推自动机
DPDA / Deterministic Pushdown Automaton：确定下推自动机，识别确定性 CFL
二、语法分析相关
LL(n) / LL(n) Parser：从左到右、最左推导、向前看 n 个符号的语法分析器
LR(n) / LR(n) Parser：从左到右、最右推导、向前看 n 个符号的语法分析器
SLR / Simple LR：简单 LR 分析法，使用 Follow 集解决移进/归约冲突
AST / Abstract Syntax Tree：抽象语法树，忽略分隔符等语法细节，保留结构信息
DAG / Directed Acyclic Graph（Syntax DAG）：语法有向无环图，共享公共子表达式
SDD / Syntax-Directed Definition：语法制导定义，将属性与文法符号关联
SDT / Syntax-Directed Translation：语法制导翻译，在产生式中嵌入语义动作
三、中间表示与优化
IR / Intermediate Representation：中间表示，编译器中位于前端与后端之间的代码形式
TAC / Three-Address Code：三地址码，每条指令最多三个地址的 IR
ASM / Assembly：汇编代码，机器指令的符号形式
SSA / Static Single Assignment Form：静态单赋值形式，每个变量只赋值一次，便于数据流分析
IDF / Iterated Dominance Frontier：迭代支配边界，用于计算 SSA 中 φ 函数插入位置
EBB / Extended Basic Block：扩展基本块，由多个基本块组成但仅有单一入口
CG / Call Graph：调用图，描述函数/过程之间的调用关系
四、数据流与程序分析
DFA / Data-Flow Analysis：数据流分析，通过程序结构推导各点的变量取值信息
IFDS / Inter-procedural Finite Distributive Subset Problem：过程间有限可分子集问题，一种过程间数据流分析框架
CS-DDA / Context-Sensitive Demand-Driven Analysis（常见缩写之一，未标准化）：上下文敏感的按需分析
五、逻辑与约束系统
PL / Propositional Logic：命题逻辑，由命题变量与逻辑连接词（与、或、非等）构成
NNF / Negation Normal Form：否定范式，否定操作仅出现在原子命题前
DNF / Disjunctive Normal Form：析取范式，若干合取项的析取
CNF / Conjunctive Normal Form：合取范式，若干析取项的合取
SAT / Boolean Satisfiability Problem：布尔可满足性问题，判断是否存在真值赋值使命题公式为真
六、工具与系统
- ANTLR / Another Tool for Language Recognition：语言识别生成器，可生成词法/语法/树分析器
- LLVM / Low Level Virtual Machine：底层虚拟机，一套模块化编译基础设施，以 SSA 型 IR 为核心