本文档由notebookLM独家指导，尝试新时代速通路线。

词法分析

核心概念

词法单元 (Token)：由一个词法单元名和一个可选的属性值组成，通常用 <token name, token value> 的形式表示。它是词法分析器输出给语法分析器的逻辑符号。

模式 (Pattern)：描述了源语言中特定记号的构成规则。在编译器设计中，模式通常使用正则表达式来刻画，例如变量名的命名规则就是一个模式。(事实上翻译成模板你就理解是什么意思了，就是一堆东西应该长成什么样子)

词素 (Lexeme)：是源程序中的一个具体的字符序列。它与某个词法单元的模式相匹配，并被词法分析器识别为该词法单元的一个实例。

词法分析器根据模式（规则），在源代码中识别出词素（字符序列），并将其转化为词法单元（逻辑单元）传递给后续阶段

DFA：确定有穷自动机 NFA：不确定有穷自动机 二者区别在于NFA允许有多个出边，DFA所有状态、所有字符都必须有唯一转移，并不至少单纯的唯一输入唯一转移就可以，如果一个节点接受一个输入但是即不能终结也没有去处，那就还是NFA，满足不了DFA，

正则表达式

ϵ：匹配空串

字符 a：匹配字母表中的单个符号 a

选择 (r|s)：匹配 r 或 s 定义的语言。例如 a|b 匹配集合 {a,b}。

连接 (rs)：匹配 r 后面紧跟 s 的字符串。例如 ab 匹配 {ab}。

Kleene 闭包 ($r^*$)：匹配 r 出现 0 次或多次的情况。例如 a* 匹配 {ϵ,a,aa,…}。

优先级：闭包（*）优先级最高，其次是连接，最后是选择（|）。所有算符均为左结合

还有一些扩展语法我们通常在题目中不用，如正闭包 (r+)这种，因为做题不方便。不方便写状态机。但是是可以等价转换的。

  • $r^+$ 还原为 $rr^*$
  • $r?$ 还原为 $r | \epsilon$

RE转NFA

正则表达式 Regular Expression

非确定性有穷自动机 Non-Deterministic Finite Automata

选择 ($s|t$)：创建一个新起点和新终点。从起点画两条 $\epsilon$ 弧分别指向 $s$ 和 $t$ 的开始，再从 $s$ 和 $t$ 的结束各画一条 $\epsilon$ 弧指向新终点, 。

连接 ($st$)：将 $s$ 的接受状态与 $t$ 的开始状态合并（或者用一条 $\epsilon$ 弧连接） 。

闭包 ($s^*$)：增加新起点和新终点。新起点可直接跳到新终点（匹配空串），也可进入 $s$；$s$ 的终点画 $\epsilon$ 弧回跳到其起点（实现循环），同时也指向新终点。

唯一性：整个 NFA 只能有一个开始状态（用 start 箭头标出）和一个接受状态（用双圈表示）。

出口限制：接受状态不能有向外的转换弧。

弧的限制：每个状态要么发出一条字母表符号弧，要么最多发出两条 $\epsilon$ 弧。

推荐步骤：

  1. 先画出单个字母（如 $a, b$）的基础 NFA。
  2. 按照括号 > 闭包 > 连接 > 选择的优先级顺序逐步合并。
  3. 最后检查是否只有一个双圈状态，且该状态没有发出的弧。

NFA转DFA

子集构造法 (Subset Construction)，其核心思想是让 DFA 的每一个状态对应 NFA 的一个状态集合。

我们通过一个为Dtran的表格来实现，假设我们的语言只有ab两个字母。

NFA 状态 DFA状态 a b
{0,1,2,3,4,…..} A B C
{1,2,6,8,10,…} E B D

以上数据均为瞎编构造，仅用于说明NFA状态填入集合，DFA状态填入一个字母表示这个集合，当不存在新的集合出现时，证明已经转换完毕。

在填充表格之前，必须定义两个操作：

  1. $\epsilon\text{-closure}(S)$：从状态集 $S$ 中的每个状态开始，只通过 $\epsilon$ 边（空移动）能够到达的所有状态的集合。
  2. $move(S, c)$：从状态集 $S$ 中的每个状态开始，通过消耗一个输入字符 $c$ 能够直接到达的状态集合。

初始的时候第一个NFA状态是start通过不限量个ε可达的节点。然后这个集合通过一个a/b进行状态转移，能到达什么地方，再计算这个几个通过不限量个ε可达的节点，也就是求$\epsilon_{closure}({T}) $（T为集合, T = move(A, a)）。

DFA最小化

DFA 最小化（通常采用 Hopcroft 算法）的核心是通过划分等价状态组，将行为完全一致的状态合并，从而得到状态数最少的等价 DFA。

核心步骤：

  1. 初始划分：将 DFA 的所有状态分为两个初始组：接受状态组（终态）和非接受状态组。检查可区分性：对于同一组内的状态，检查它们在输入相同符号 a 后，是否跳转到了不同的组。如果跳转目标不在同一个组，说明这些状态是“可区分”的，必须将它们拆分。
  2. 迭代与合并：重复上述拆分过程，直到所有组都不能再划分为止。最后，将每个组内的状态合并为一个代表状态。
  3. 区分标准：如果从状态 s 出发经路径 w 到达接受状态，而从 t 出发经相同路径 w 到达非接受状态，则 s 和 t 是不可合并的。

终态也叫接受状态就是完事了，非终态通常指自动机中的初始状态或中间状态。等价类就是对于任意输入他们跳转到同一个等价类并且它们两个本身必须同为“终态”或同为“非终态”。

语法分析

核心概念

语法分析的基础是上下文无关文法 (CFG)，它的任务是根据词法分析提供的记号（Token）流，构造出具有层次结构的语法分析树。

上下文无关文法（CFG）是用于描述程序设计语言语法的核心工具，它比正则表达式更强大，能够表达递归和嵌套结构（如配对的括号 (( ))）,。

它由一个四元组定义：

  1. 非终结符 ($V_N$)：表示语法范畴的逻辑符号，如“语句”或“表达式”。
  2. 终结符 ($V_T$)：语言的基本单元，即词法分析传来的记号（如 id, +, if）。
  3. 开始符号 ($S$)：文法中指定的唯一起始非终结符。
  4. 产生式 ($P$)：重写规则，形式为 $A \rightarrow \alpha$，表示左边的符号可以被右边的序列替换。

推导 (Derivation)：这是分析的核心过程。通过不断地用产生式的右部替换左部的非终结符，最终生成只包含终结符的字符串。

文法设计

  • 线性文法 (正则文法)：用于描述简单的重复或顺序结构。其产生式形式受限：
    • 右线性：$A \rightarrow aB$ 或 $A \rightarrow a$（非终结符只能在最右边）。
    • 左线性：$A \rightarrow Ba$ 或 $A \rightarrow a$。
    • 考试技巧：设计生成“被 3 除余 1 的二进制串”这类题目时，通常使用右线性文法，通过状态转换的思想来写。
  • 上下文无关文法 (CFG)：比线性文法更强大，左部只有一个非终结符，右部可以是任意符号串。
    • 应用：处理配对（如 $a^n b^n$）或嵌套结构（如括号匹配）时必须使用 CFG。

二义性与语法树

  • 定义：如果一个文法能为同一个句子构造出两棵不同的语法分析树（或两个不同的最左推导），它就是二义性的。
  • 证明方法：找一个简单的输入串（如真题中的 a+a+a 或 id*id+id），尝试画出两棵结构不同的树：一棵左结合，一棵右结合。
  • 消除方法：通过改写产生式来引入优先级和结合性。例如，先处理乘法再处理加法，从而强制生成的树只有一种形态。

构造等价无二义文法的核心在于引入运算符的优先级和结合性，通过将产生式分层来强制唯一的推导路径。

以真题文法 $S \rightarrow a \mid S+S \mid SS \mid S^* \mid (S)$ 为例，构造步骤如下：

  1. 确定优先级：通常顺序为括号 $(S)$ 和原子 $a$ > 闭包 $S^*$ > 连接 $SS$ > 选择 /运算符$S+S$。
  2. 处理结合性：
    • 左结合（如 $+$ 和连接）：采用左递归形式（$A \rightarrow A\alpha \mid \beta$）。
    • 右结合：采用右递归形式。
  3. 分层改写：
    • $S \rightarrow S + A \mid A$ （处理优先级最低的 $+$，左结合）
    • $A \rightarrow AB \mid B$ （处理连接，左结合）
    • $B \rightarrow B^ \mid C$* （处理闭包）
    • $C \rightarrow (S) \mid a$ （处理最高优先级的括号和原子）

补充：引入的东西在于不同层级的非终结符只能推导出一种优先级的运算，每一级非终结符，只能包含它自己这一级以及比它优先级更高的运算，严格排斥更低优先级的运算。

引入的非终结符 代表含义 负责的运算符 关键特征
F (Factor) 原子/因子 ( ) , id 不可分割的最小单元，不包含任何二元运算符
T (Term) 项 * 只能生成连乘的结构，不允许在此层直接生成 +
E (Expr) 表达式 + 最外层，只能生成连加的结构，加法的右侧必须是 T

左递归消除

  • 为什么要消除：自顶向下的 LL(1) 分析器不能处理左递归（如 $A \rightarrow A\alpha$），否则会陷入死循环。

  • 固定公式 (直接左递归)：

  • 若有 $A \rightarrow A\alpha \mid \beta$，改写为：

  1. $A \rightarrow \beta A'$
  2. $A’ \rightarrow \alpha A’ \mid \epsilon$

进一步还有隐式左递归消除

隐式左递归（间接左递归）是指文法产生式中没有直接的 $A \rightarrow A\alpha$，但经过两步或多步推导后，会出现以自身开头的符号串（例如 $S \Rightarrow Aa \Rightarrow Sda$）。

消除步骤（算法 4.1）：

  1. 非终结符排序：将文法中的所有非终结符按一定顺序排列，如 $A_1, A_2, \dots, A_n$。
  2. 代入转化：按照排序依次检查每一个 $A_i$。如果 $A_i$ 的产生式右部以排在它前面的非终结符 $A_j$ ($j < i$) 开头，则将 $A_j$ 的所有定义代入到 $A_i$ 的产生式中。
  3. 消除直接左递归：完成代入后，若 $A_i$ 出现了直接左递归，则应用标准公式：$A \rightarrow \beta A’, A’ \rightarrow \alpha A’ \mid \epsilon$ 进行消除。 实例演示

已知文法：$B \rightarrow Sa \mid a$，$A \rightarrow Bb \mid b$，$S \rightarrow Ac \mid c$。

  • 代入：将 $B$ 的定义代入 $A$，得到 $A \rightarrow Sab \mid ab \mid b$。
  • 再代入：将 $A$ 的新定义代入 $S$，得到 $S \rightarrow Sabc \mid abc \mid bc \mid c$。
  • 消除：此时 $S$ 变为了直接左递归，应用公式改写为 $S \rightarrow (abc \mid bc \mid c) S’$ 和 $S’ \rightarrow abc S’ \mid \epsilon$ 即可。

LL（1）分析

LL(1) 分析是考试中分值最高的大题（约 20-30 分），它代表：L（从左向右扫描）、L（产生最左推导）、1（每步只向前看一个输入符号）。

掌握这个专题需要按以下三个核心步骤走：

第一步：计算 First 集和 Follow 集

这是构造分析表的依据。

  • First(X)：从 $X$ 推导出的字符串中第一个终结符的集合。

  • Follow(A)：可能紧跟在非终结符 $A$ 后面的终结符集合。

  • 必考点：开始符号 $S$ 的 Follow 集初始必包含 $。

这三条规则的核心逻辑是：找出在所有可能的推导序列中，哪些终结符可能紧跟在非终结符 $B$ 的右边。

1. 开始符号规则：若 $A$ 是开始符号，则 $$ \in FOLLOW(A)$

  • 总结：文法的起始目标是匹配整个输入串，而输入串的逻辑终点由 $$$ 标记。
  • 证明：根据句法分析的设计，完整的推导序列表现为 $S$ \Rightarrow w$$，因此 $$$ 必然存在于起始符号的后继集合中。

2. 右邻居规则：若 $A \rightarrow \alpha B \beta$，则 $FIRST(\beta) - {\epsilon} \subseteq FOLLOW(B)$

  • 总结：$B$ 的“右手边邻居”能推导出的所有开头字符，都是 $B$ 的追随者。
  • 证明：在推导序列 $A \Rightarrow \alpha B \beta$ 中，如果 $\beta$ 推导出的字符串以终结符 $a$ 开头（即 $a \in FIRST(\beta)$），则序列变为 $\dots \alpha B a \dots$，证明 $a$ 可以紧跟在 $B$ 之后。

3. 左部继承规则：若 $A \rightarrow \alpha B$ 或 $A \rightarrow \alpha B \beta$（且 $\beta \Rightarrow \epsilon$），则 $FOLLOW(A) \subseteq FOLLOW(B)$

  • 总结：如果 $B$ 位于产生式末尾，或者它后面的所有符号都能消失（推导出空串），那么凡是能跟在左部符号 $A$ 后面的，也一定能跟在 $B$ 后面。
  • 证明：
    • 针对 $A \rightarrow \alpha B$：假设 $a$ 跟在 $A$ 后面，推导为 $Aa \Rightarrow \alpha Ba$，此时 $a$ 显然也跟在 $B$ 后。
    • 针对 $\beta \Rightarrow \epsilon$：若 $Aa \Rightarrow \alpha B \beta a$，由于 $\beta$ 可以变为空，推导最终变为 $\alpha B a$，证明 $a$ 也是 $B$ 的追随者。

第二步：构造预测分析表 $M$

根据产生式 $A \rightarrow \alpha$ 填表：

  1. 对 $First(\alpha)$ 中的每个终结符 $a$，把 $A \rightarrow \alpha$ 放入 $M[A, a]$。
  2. 若 $\epsilon \in First(\alpha)$，则对 $Follow(A)$ 中的每个终结符 $b$，把 $A \rightarrow \alpha$ 放入 $M[A, b]$。
  3. 判定：如果表中任何单元格都没有重定义（即一个格子里只有一条产生式），该文法就是 LL(1) 文法。

第三步：显式栈模拟句法分析

在考试中，通常要求你演示对输入串（如 babbb 或 adccd）的分析过程：

  • 初始化：栈底为 $，栈顶为开始符号 $S$；输入串末尾加 $。

  • 操作：

    • 若栈顶是终结符且与输入匹配，则弹出并前进。
    • 若栈顶是非终结符，查表 $M$，将栈顶替换为对应产生式的右部逆序入栈。
    • 若栈顶与输入都是 $，则分析成功。

恍若隔世

此时已经忘了期中考了什么，之前学了什么。

所以先回忆 正则和NFA和DFA的转来转去 还有最小化这一块

最左/右推导，是从S->SS* 这个视角看的，把S这个串的最左侧/右侧的非终结符替换掉，而不是看串的最终形态。

然后就是 左递归、语法树 和 LL(1)，然后就没了

自底向上分析

归约：推导的逆过程，把串逐步还原成起始推导式子的过程。

移进：把输入的串压入分析栈的过程

句柄：归约时候的栈里面的与产生式匹配的那一段内容。也就是最有推导到这一步产生的内容

LR(0) / SLR(1)

LR(0) 分析法是自底向上（Bottom-up）语法分析家族的基础。“L”代表自左向右（Left-to-right）扫描输入串，“R”代表最右推导的逆过程（Rightmost derivation in reverse），“0”则表示在做分析决策时不参考任何向前看符号。

LR(0) 项目是在文法产生式的右部某个位置标有“·”的产生式。

  • “·”的含义： 表示分析过程中的状态。“·”之前的子串表示已经出现在分析栈顶的部分，“·”之后则是下一步希望看到的符号。

  • 项目分类：

    • 归约项目： 如 $A \to \alpha\cdot$，表示产生式右部已全部识别，可以进行归约。
    • 待约项目（基本项目）： 如 $A \to \alpha\cdot B\beta$，表示后面紧跟的是非终结符。
    • 移进项目： 如 $A \to \alpha\cdot a\beta$，点后面紧跟的是终结符。

  • 特殊情况： 对于 $\epsilon$ 产生式（如 $A \to \epsilon$），其对应的项目仅有一个，即 $A \to \cdot$。

增广文法（Augmented Grammar）

为了让分析器能明确知道何时成功接受输入串，通常会对文法 $G[S]$ 增加一个产生式 $S’ \to S$。

  • 初始项： $S’ \to \cdot S$。
  • 接受状态： 当状态中包含 $S’ \to S\cdot$ 且输入符号为 $ 时，执行 accept。

闭包（Closure）与转向（Goto）

  • 闭包运算 (closure)： 如果项目集 $I$ 中包含 $A \to \alpha\cdot B\beta$，且文法中有产生式 $B \to \gamma$，则必须将 $B \to \cdot\gamma$ 加入到项目集中，直到不再增加为止。
  • 转向函数 (goto)： 定义了状态之间的转换。$goto(I, X)$ 表示当前状态为 $I$，当吃进文法符号 $X$（可以是终结符或非终结符）后，转到的新状态是所有 $A \to \alpha X \cdot\beta$ 项目及其闭包的集合。

LR(0) 的局限性：冲突

LR(0) 分析法功能较弱，容易在分析表中产生冲突，导致文法不是 LR(0) 文法：

  • 移进-归约冲突： 某个状态既包含移进项目（如 $S \to d\cdot c$），又包含归约项目（如 $A \to d\cdot$），且无法仅凭栈顶状态决定动作。
  • 归约-归约冲突： 某个状态包含两个及以上的归约项目，分析器无法决定用哪条产生式进行归约。

LR0总结构造过程：

  1. 先增广一个初始产生式，然后把所有的或都拆开成单独的推导，把所有的产生式编号为0,1,2,3…
  2. 先把S‘->S 写入 作为状态 0，注意，如果点后面是非终结符那么需要把这个非终结符的所有初始项目（推导式最开始的状态）写在这个状态里面，这也就是闭包运算
  3. 下一步就是如何转移到其它状态，可以看前面的goto运算，就是吃进了终结符或者非终结符后的下一个状态，把点向右移动（移进），注意也要进行闭包操作
  4. 整体状态的编号类似bfs的顺序
  5. 最后画表格，列分别为状态、ACTION（终结符和$）、GOTO（非终结符），ACTION 下面表中sn表示状态，rn表示规约（n = 0,1,2,3…），acc表示接受，然后对于处于归约的状态，需要把这一行全部写上r，n就是产生式的编号，GOTO 下面只有数字表示状态，因为ACTION表示规约/移进动作，GOTO不执行只跳转

将LR0扩展为SLR1：

  1. 把所有非终结符的Follow集合列出来
  2. 对于LR0表格中的rn，如果相应推导式的Follow集合里面没有 ACTION 上面的终结符，那么就把它删掉，相当于不规约

LR(1) / LALR(1)

LR(k) 就相当于, A->ab, x1,x2,x3..,xk 这个推导式逗号后面有k个终结符

LR(1) 解决的是LR(0)中Follow集合可能过大的问题，即在某些前缀下Follow集合中的符号根本不可能出现。

  1. 前置处理：和之前完全一样，先增广一个初始产生式 S'→S，把所有 “或” 拆开成单独推导，所有产生式编号为 0,1,2,3…（增广产生式必须是 0 号）

  2. 核心差异：LR (1) 项目

  • 格式：A→α·β, a（a 是单个终结符或 $，叫展望符）
  • 含义：我已经识别了 α，接下来要识别 β；等我把 β 也识别完（圆点到末尾），只有当下一个输入符号正好是 a 时，我才用 A→αβ 归约
  • 对比：LR (0) 项目没有展望符，相当于对所有符号都归约；SLR (1) 用全局 Follow (A) 当展望符；LR (1) 每个项目有自己的专属展望符
  1. 闭包运算（重点）
  • 初始：把给定的 LR (1) 项目全部加入状态
  • 规则：如果状态里有项目 A→α·Bβ, a（B 是非终结符）（α和β是什么都无所谓）
    • 把 B 的所有产生式的初始项目 B→·γ 全部加进来（γ是什么也无所谓）
    • 关键：给这些新项目计算展望符 = First (βa)：这个相当于如果β推不出空就是First(β) 可以推出空就是First(β) + a
  • 递归：直到没有新项目可以加入为止
  • 注意：为什么LR(1)这么傻逼就是因为这个First可能算出多个展望符，由于是LR(1)，逗号后面只能有一个，所以它竟然每一个展望符都要写到新的一行里面，这就是所谓的分裂出一坨，但是作业解析中的写法是展望符之间用/分割开就可以，这样看起来没那么占地方
  1. goto 转移运算
  • 第一步：和 LR (0) 完全一样，找到状态中所有圆点后是 X 的项目，把圆点向右移动一位
  • 关键：移动后，原来的展望符原封不动保留
  • 第二步：对移动后的所有项目，做上面的 LR (1) 闭包运算
  • 结果就是转移后的新状态
  1. 构造所有状态
  • 初始状态 0 = closure ({S'→·S, $})（注意初始展望符必须是 $！）
  • 整体状态编号完全按照 BFS 顺序，和之前一模一样
  • 去重规则：只有当两个状态的所有项目（包括展望符）都完全相同时，才认为是同一个状态
  1. 表格（只有归约规则变了）

  • 表格结构完全不变：列是状态、ACTION（终结符和 $）、GOTO（非终结符）

  • ACTION 表符号含义完全不变：sn= 移进，rn= 归约，acc= 接受

  • 移进规则：和 LR (0)/SLR (1) 完全一样

  • 归约规则）：

    • 如果状态里有归约项目 A→α·, a（产生式编号 k）

  • 只在 ACTION [i,a] 这一个格子里写 rk，其他格子什么都不写（对比：LR (0) 整行写 r；SLR (1) 给 Follow (A) 里的所有符号写 r）

显然LR(1)太繁琐了，所以LALR(1)诞生了：

项目核心：LR (1) 项目去掉其展望符部分后剩余的 LR (0) 项目

同心集：LR (1) 项目集规范族中，项目核心完全相同，仅展望符集合不同的项目集。

合并规则：

  1. 核心合并规则：同心集的项目核心集完全一致，合并后新的项目核心集与原核心集相等，无新增核心项目。
  2. 展望符合并规则：对同一核心项目在各同心集中的展望符集合取并集，作为合并后该核心项目的展望符集合。
  3. GOTO 函数合并规则：若状态 I、J 合并为 I’，则对任意文法符号 X，goto(I', X) 为 goto(I, X) 与 goto(J, X) 的合并结果（由同心集的同态性保证其目标必为同心集）。

总结

特性 LR(0) SLR(1) LR(1) LALR(1)
项目格式 A→α·β A→α·β A→α·β, a A→α·β, {a1,a2,...}
状态数量 少 和 LR (0) 相同 多（通常是 LR (0) 的 2-3 倍） 和 LR (0) 相同
归约依据 全局归约 全局 Follow (A) 局部单个展望符 局部展望符集合
冲突解决能力 无 解决大部分移进 - 归约冲突 解决所有合理冲突 解决大部分冲突，可能引入归约 - 归约冲突

语法制导翻译

这一块的内容就是语法分析后，加上语义操作

语法制导定义(Syntax-Directed Definitions, SDD)

语法制导翻译方案(Syntax-Directed Translation schemes， SDT)：

综合属性：结点 N 的属性值由其子结点或其自身的属性计算得出

继承属性：结点 N 的属性值由其父结点、兄弟结点或其自身的属性计算得出

lexval: 它是一个关联在终结符号（Terminals）上的综合属性。其具体数值是由**词法分析器（Lexical Analyzer）**在扫描源程序并识别出Token时提供的，类似字符串转实际的值

如果一个SDD的每个属性都是综合属性，则它是S属性的。可以按照分析树的自底向上顺序来计算各属性值

一个语法制导定义是L属性定义，如果任意一条产生式A → X1X2 … Xj… Xn，其右部符号Xj的继承属性仅依赖于

  1. 产生式中Xj的左边的符号X1, X2 ,… Xj-1的属性；

  2. A的继承属性。

L属性定义对综合属性没有限制。显然，所有的S属性定义都是L属性定义

SDD 的语义规则是无顺序的，需要你自己画注释语法分析树来找拓扑排序

SDT 则是把{xxxx}这种代码插入产生式中间，这样就自带顺序，SDD转SDT要注意，插入的式子中所有用到的的属性一定要已经得出。

中间代码生成

DAG：相比于注释语法分析树更加化简，体现在如果有相同的元素被用到那就用之前的而不是新建一个

后缀表示：如 a + b -> a b +

三地址码：

L 为行号或者标记

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

x = y op z        // arithmetic and logical (算术与逻辑运算)
x = op y         // negation and conversion (一元运算与类型转换)
x = y            // copy (复制赋值)

goto L           // unconditional jump (无条件跳转)
if x goto L      // conditional jump (条件为真跳转)
ifFalse x goto L // conditional jump (条件为假跳转)
if x op y goto L // relational operation (关系运算条件跳转)

param x1         // parameter passing (参数传递)
param x2
...
param xn
call p, n        // procedure call (过程调用，无返回值)
y = call p, n    // function call (函数调用，有返回值)
return y         // return a value (返回值)


x = y[i]         // indexed copy, i is the offset (数组元素读取，i为偏移量)
x[i] = y         // 数组元素写入

x = &y           // address and pointer assignment (取地址与指针赋值)
x = *y           // 指针解引用读取
*x = y           // 指针解引用写入

三地址码的具体表现存储形式：

四元式：(op, arg1, arg2, result)

序号 op arg1 arg2 result
0 * b c t1
1 + a t1 t2
2 / d e t3
3 - t2 t3 t4
4 = t4 null x

三元式：每条指令由3 个字段组成，没有专门的 result 字段 (op, arg1, arg2)

序号 op arg1 arg2
0 * b c
1 + a (0) // (0) 表示引用序号为 0 的三元式的结果
2 / d e
3 - (1) (2)
4 = x (3) // 赋值运算的 arg1 是目标变量，arg2 是源

间接三元式：为了解决三元式的位置相关性问题，增加了一个间接码表

如果代码中出现两次b * c，三元式表中只需要存储一次：

序号 三元式序号
0 0 // 第一次计算 b*c
1 1
2 0 // 第二次直接引用已有的三元式 0
3 2
序号 op arg1 arg2
0 * b c // 只存一次
1 + a (0)
2 + d (0)

回填：是一种在中间代码生成过程中，用于处理跳转地址未知的指令的技术。它主要为了实现一遍扫描（One-pass）翻译。

“回填”不使用继承属性，只使用综合属性！

回填技术依赖于三个核心操作：

makelist(i)： 创建一个新列表，其中只包含指令序号 i。返回指向该列表的指针。

merge(p1, p2)： 将两个回填列表 p1 和 p2 合并为一个，返回合并后的列表指针。

backpatch(p, i)： 核心回填操作。将具体的语句地址 i 填入列表 p 中所有指令的跳转目标域。

关键属性与变量truelist 和 falselist： 布尔表达式 B 的两个综合属性，分别记录当 B 为真或为假时，需要回填的跳转指令列表。

nextlist： 语句 S 的综合属性，记录在该语句执行完后，需要跳过后续代码的跳转指令列表。

nextinstr： 全局变量，记录下一条即将生成的四元式指令序号。

标记非终结符 M： 用于在产生式中捕获当前指令序号。规则为M→ϵ{M.instr=nextinstr;}。