一、编译程序相关内容
代码生成与优化
- 中间代码是代码生成程序的输入，最终目标是将其转换为特定机器架构下的目标代码（机器代码或汇编代码）。
- 代码优化程序可插入在中间代码生成之后、目标代码生成之前。优化分为：
- 局部优化：如基本块内的公共子表达式消除、常量合并等；
- 全局优化：如循环不变代码外提、强度削弱、死代码删除等；
- 目标相关优化：利用目标机特性进行寄存器分配、指令调度等。
- 优化原则：保持程序语义不变，提升运行效率（时间/空间）或减小代码体积。
符号表管理
- 符号表是一种数据结构，用于存储源程序中每个标识符的相关属性信息，包括但不限于：
- 标识符名称
- 类型（int, float, array, struct 等）
- 作用域（全局、局部、块级）
- 存储类别（自动变量、静态变量、寄存器变量等）
- 内存地址或偏移量（由代码生成阶段确定）
- 参数和返回类型（对函数而言）
- 符号表支持的操作有：插入、查找、更新、作用域嵌套管理（如栈式符号表）。
- 多个编译阶段（词法分析、语法分析、语义分析、代码生成、优化）都会访问符号表以确保一致性与正确性。
错误处理
- 编译器需具备发现、报告和一定程度上恢复错误的能力，以便尽可能多地检测错误。
- 错误类型主要包括：
- 词法错误：非法字符、拼写错误的标识符（如
int a@;） - 语法错误：不符合语法规则（如缺少分号、括号不匹配）
- 语义错误：类型不匹配、未声明变量使用、函数调用参数不符等
- 词法错误：非法字符、拼写错误的标识符（如
- 错误处理策略：
- 报告错误位置（行号、列号）、类型和建议
- 使用同步记号法、插入/删除符号等方式尝试恢复解析流程，避免连锁报错
- 在某些情况下允许继续编译以发现更多错误
二、形式语言基础知识（字母表、符号串）
核心定义
- 字母表（Alphabet）：一个非空有限的符号集合，通常记作 Σ。例如：Σ = {a, b} 或 Σ = {0, 1}。
- 符号串（String）：由字母表中的符号组成的有限有序序列。例如：abba、0011。
- 长度（Length）：符号串中符号的个数。空串 ε 的长度为 0。
- 前缀（Prefix）：从字符串末尾删去零个或多个符号所得的结果。例如：“abc” 的前缀有：ε, “a”, “ab”, “abc”。
- 后缀（Suffix）：从字符串开头删去零个或多个符号所得的结果。例如：“abc” 的后缀有：ε, “c”, “bc”, “abc”。
- 子串（Substring）：连续的一段符号，通过删除前缀和后缀得到。包含空串和自身。例如：“abc” 的子串有：ε, “a”, “b”, “c”, “ab”, “bc”, “abc”。
- 子序列（Subsequence）：不要求连续，只要顺序一致即可。例如：“ace” 是 “abcde” 的子序列。
符号串运算
- 连接（Concatenation）：将两个符号串首尾相连。设 α = “ab”, β = “cd”，则 αβ = “abcd”。
- 单位元性质：αε = εα = α
- 幂运算（Power）：表示重复连接
- α⁰ = ε（任何串的 0 次幂为空串）
- α¹ = α
- α² = αα
- αⁿ = α 连接 n 次
此外，所有由字母表 Σ 上的所有符号串构成的集合称为Σ*（Kleene闭包），包含空串；而 Σ⁺ 表示不含空串的所有非空串集合。
中间代码是编译器在将源程序转换为目标代码过程中使用的一种介于高级语言与机器语言之间的中间表示形式。它有助于进行代码优化和目标代码生成，同时屏蔽了具体机器的细节。
常见的中间代码表示形式包括：
三地址码（Three-Address Code, TAC）
- 是一种线性表示，每条指令最多包含三个地址（两个源操作数、一个目标结果）。
- 形式：
x = y op z或x = op y（一元运算），或用于控制流如goto L、if x goto L、if x relop y goto L。 - 示例：
t1 = a + b t2 = t1 * c d = t2 - 特点：结构清晰，适合优化和后续翻译成目标代码。
四元组（Quadruple）
- 是三地址码的一种结构化表示，每个记录有四个字段：
(op, arg1, arg2, result)。 - 示例：
(+ , a, b, t1) (* , t1, c, t2) (= , t2, , d) - 优点：便于修改和优化，易于实现代码移动、公共子表达式消除等。
- 是三地址码的一种结构化表示，每个记录有四个字段：
三元组（Triple）
- 类似四元组，但只有三个字段：
(op, arg1, arg2)，结果用位置（序号）隐式表示。 - 示例：
(0: + , a, b) → 结果为第0个临时值 (1: * , (0), c) → 引用前一条的结果 (2: = , (1), d) - 缺点：重排困难（因依赖位置编号），不利于代码优化时的调整。
- 类似四元组，但只有三个字段：
抽象语法树（Abstract Syntax Tree, AST）
- 是语法分析后生成的树形结构，省略了冗余括号和语法单元（如终结符），仅保留计算结构。
- 每个内部节点表示一个操作符，叶子节点表示操作数（变量、常量）。
- 示例：表达式
(a + b) * c的 AST 为：* / \ + c / \ a b - 优点：直观反映程序结构，适用于语义分析、类型检查和高级优化。
后缀式（逆波兰表示，Postfix Notation）
- 又称后缀表达式，操作符位于操作数之后，无需括号即可唯一表示运算顺序。
- 示例：中缀表达式
a + b * c转换为后缀式为：a b c * + - 常用于栈式虚拟机（如 Java 字节码）的执行模型。
静态单赋值形式（Static Single Assignment Form, SSA）
- 一种增强型中间表示，在普通三地址码基础上要求每个变量只能被赋值一次。
- 对于多次赋值的情况，引入带下标的版本（如
x1,x2）并使用 φ 函数合并不同控制流路径的值。 - 示例：
x1 = ... ... x2 = ... x3 = φ(x1, x2) - 广泛用于现代编译器（如 GCC、LLVM）中的优化阶段，极大简化数据流分析。
这些中间表示各有优劣，实际编译器可能结合多种方式使用。例如：先生成 AST 进行语义分析，再转为三地址码或 SSA 形式进行优化，最后生成目标代码。
