90-常见概念定义

前端

词法分析

定义：编译器的第一个阶段，其主要任务是将源代码转换为一系列记号（tokens）。这些记号是编程语言的最小有意义单位，如关键字、标识符、运算符、分隔符和字面量等。
好处
- 简化语法分析器的任务：将源代码转为 tokens，使得后续的语法分析（Parser）只需处理 token 流，而无需直接处理字符，降低复杂度。
- 提高编译器模块化和可维护性：词法分析与语法分析分离，各自专注于不同任务，代码结构更清晰。
- 更容易进行错误检测：在词法阶段可及早捕捉非法字符、未闭合的字符串等错误，提供更早期的反馈。
- 便于支持语法高亮、代码补全等功能：在 IDE 中，词法分析的结果可用于标识关键字、变量等，辅助开发者编程。

DFA

定义：确定性有限自动机，对于每个状态和输入字符，只有一个状态转移
- $M = (Q, \Sigma, \delta, q_0, F)$
- $Q$ ：状态集合
- $\Sigma$ ：输入字母表
- $\delta$ ：状态转移函数， $\delta: Q \times \Sigma \mapsto Q$
- $q_0 \in Q$ ：初始状态
- $F \subseteq Q$ ：接受状态集合
- $\delta^*: Q \times \Sigma^* \mapsto Q$ ：状态转移函数的扩展，接受多个输入字符
特点：确定性、有限状态、起始状态唯一、无 $\epsilon$ 转移
好处：实现简单，高效运行，每个输入字符都有唯一的状态转移，易于实现和优化。

NFA

定义：非确定性有限自动机，对于一个输入字符，可以有多个状态转移，只要有一个状态转移成功，就可以接受
- $M = (Q, \Sigma \cup \{\epsilon\}, \delta, q_0, F)$
- $\delta: Q \times (\Sigma \cup \{\epsilon\}) \mapsto 2^Q$ ( $2^Q$ 表示 $Q$ 的幂集，所有的子集)

正则语言

定义：若存在一个 DFA/NFA 能够匹配所有这个语言的字符串，拒绝所有不属于这个语言的字符串，那么这个语言就是正则语言。
优点
- 计算效率高：可以用 DFA 实现匹配，匹配时间是线性时间 O(n)，且不需回溯。
- 结构简单：定义方式直观、规则有限，易于理解与实现。
- 自动机支持：可以用 DFA/NFA 精确识别，用于编译器、文本处理等任务。
- 封闭性好：对多个操作封闭：并、交、补、连接、闭包、差集、逆等等。
- 可转换为等价自动机：任意正则表达式都可以转换为 NFA，再转为 DFA。

上下文无关文法

定义：四元组 $G=(N,T,S,P)$
- $N$ 非终结符的有限集合：还能继续推导的符号
- $T$ 终结符的有限集合：不能继续推导的符号
- $S\in N$ 开始符号
- $P$ 产生式的有限集合，格式为 $A\to\alpha$ ，其中 $A\in N$ ， $\alpha\in(N\cup T)^*$
优点
- 强表达能力：可以描述嵌套、配对、递归等结构（正则语言无法处理）
- 通用性强：几乎所有实用语言都能用 CFG 建模
- 构造系统性强：有明确的推导规则和结构，可自动生成语法分析器
- 形式化程度高：有助于语法验证、语法树构造、语义分析
- 支持递归定义：可自然表达函数调用、括号嵌套、表达式嵌套等
作用
- 描述编程语言的语法结构
- 用于编译器的语法分析阶段，将源代码转换为语法树

LL1

定义
- L：从左到右扫描
- L：从最左推导
- 1：使用 1 个符号的前瞻，决定使用哪个产生式
特点：没有左递归、没有歧义
优点
- 实现简单：可以直接手写分析器（递归函数表示每个非终结符）也可以构造简单的预测分析表进行语法判断
- 无需回溯：对于每个非终结符，根据前瞻符号唯一确定一条产生式，效率高、逻辑清晰
- 分析速度快：线性时间复杂度O(n)，每个输入符号只处理一次
- 容易调试和维护：结构清晰，每个非终结符对应一个函数，便于调试错误或添加规则
- 适合教学和学习：是初学语法分析和编译器实现时最常见的文法类型

SSA

变量只能被定义（赋值）一次
使用 $\phi$ 函数在分支合并点合并不同路径的变量
优点
- 简化数据流分析：每个变量只有一个定义，易于追踪变量的值和使用情况
- 提高优化效果：编译器可以更容易地进行常量传播、死代码消除等优化

后端

寄存器分配的目的

提高寄存器利用率，避免浪费
减少溢出带来的内存访问，提高程序执行效率
避免指令间数据依赖，提升指令并行度
溢出：寄存器数量不够，将变量存入内存

指令调度的目的

提高指令级并行：在不改变程序语义的前提下，让更多无依赖的指令同时执行，避免因数据依赖、结构冲突或控制冲突造成的阻塞
隐藏指令延迟：将长延迟操作（如访存、乘法）与其他指令交错调度，使得处理器可以在等待期间执行其他指令

中端

Dataflow Analysis

名称

定义

分析目的

Dataflow Analysis

编译器静态分析的一种，用于在不执行程序的情况下，描述 Data Flow Facts 如何在程序中转移

提供语义信息以支持优化（如常量传播、死代码删除、寄存器分配等）

Reaching Definitions（可达定义分析）

某条语句 s 是否能“到达”另一条语句 t，即在 s 定义一个变量后，没有被其他定义覆盖而到达 t

用于消除冗余赋值、进行变量替换（如常量传播）、插入 φ 函数

Available Expressions（可用表达式分析）

在程序的某一点，某个表达式（如 a + b）是否已经被计算且其中的操作数自那时以来未更改

用于公共子表达式消除（CSE），避免重复计算

Live Variables（活跃变量分析）

在程序的某一点，某变量是否可能在将来被使用，且在那之前其值不会被覆盖

用于寄存器分配、死代码删除（消除不会被用到的赋值）

符号执行

Symbolic Execution（符号执行）
- 一种程序分析技术，将输入视为符号变量，而不是具体值，沿着程序的不同路径执行，生成路径条件（path conditions），以探索程序行为和查找潜在错误（如断言失败或漏洞）。
Path Sensitivity（路径敏感性）
- 分析区分程序中不同的执行路径，分析器会分别考虑不同路径下的
- 优点：更精确，能发现路径特有的错误。
- 示例：if (x > 0) { y = 1; } else { y = 2; } —— 分析会分别考虑 x > 0 和 x ≤ 0 两种路径。
Flow Sensitivity（流敏感性）
- 分析程序中语句的执行顺序，识别变量值随语句执行的变化，避免状态混淆。
- 或在动态类型语言中，变量在不同执行点的类型可能不同，也可使用流敏感分析。
- 示例：
  int x = 0; x = x + 1; // 分析知道 `x` 先是 0，再是 1。
Context Sensitivity（上下文敏感性）：在分析函数（或方法）时，能够区分不同调用上下文（call context）对函数行为的影响。
- 会根据调用路径的不同，为同一个函数构建不同的分析结果。
- 相同的函数在不同调用上下文中可能表现不同
- 示例：foo(1) 和 foo(2) —— 分析分别处理，而不是统一分析 foo。

符号执行为何使用 CNF

SAT/SMT 求解器的标准输入形式：现代符号执行核心依赖 SAT/SMT 求解器，而它们通常要求输入 CNF。
CNF 可通过 Tseitin 转换，将复杂公式线性规模地转为等价可满足形式。
CNF 转换效率 vs DNF 指数级爆炸
- 任意布尔公式可多项式时间转为 CNF（借助桥接变量）。
- 与之相比，转为 DNF 往往会导致指数级的增长（2^n 子句），不具可行性。
DNF 求满足性虽简单，但构造代价太高，生成 DNF 本身是 NP 难的。

生成可满足等价性好：Tseitin 转换使 CNF 大小仅线性增长。
兼容性强：几乎所有 SAT/SMT solver 都以 CNF 为标准输入。
构造成本低：相对 DNF 而言，生成效率更高。
求解技术成熟：有 CDCL、布尔消解等高效算法。

指针分析

别名 Alias：两个符号指向同一个内存地址
指针分析 Pointer Analysis：分析程序中指针的别名关系
目的：确定哪些指针可能指向同一内存位置，以便进行优化

最后更新于1个月前