从零开始的编译原理速成#

串和语言#

字母表：符号的有限非空集合，通常用 $\Sigma$ 表示。

串：字母表上有限个符号的有限序列，如 abc，$\varepsilon$（空串）。

语言：字母表上的串的集合，如 {abc, ab, a, $\varepsilon$}，$\emptyset$。

串的运算#

• 连接：将两个串连接在一起，记为 $s_1 s_2$。

• 幂：将一个串重复连接多次，记为 $s^n$。

语言的运算#

• 和：两个语言的并集，记为 $L_1 \cup L_2$。

• 连接：两个语言的连接，记为 $L_1 L_2$。

• 幂：一个语言的幂，记为 $L^n$。

• 闭包：一个语言的闭包，记为 $L^*$。

• 正闭包：一个语言的正闭包，记为 $L^+$。有 $L^+ = L L^*$。

NFA 的定义#

NFA 是一个五元组 $(S, \Sigma, move, s, F)$，其中：

• $S$：状态的有限集合

• $\Sigma$：输入符号的有限集合（字母表）

• $move$：状态转移函数，$S \times (\Sigma \cup \{\varepsilon\}) \rightarrow P(S)$

• $s$：唯一的初始状态，$s \in S$

• $F$：接受状态的集合，$F \subseteq S$

注意到 NFA 与 DFA 的区别只在于 $move$ 函数：

• NFA 的状态转移函数允许有 $\varepsilon$ 转移

• NFA 的状态转移函数的值是状态的集合，而不是单个状

即 DFA 的 $move$ 函数为 $S \times \Sigma \rightarrow S$。

正则表达式可以作为 NFA 中的某个元素存在，此时记改正则表达式为 $r$ 的 NFA 为 $N(r)$。

NFA 转 DFA#

NFA 可以通过子集构造法转换为等价的 DFA。

1. 初始状态：在只走 $\varepsilon$ 转移的情况下，从 NFA 的初始状态 $s$ 出发，得到的状态集合，作为 DFA 的初始状态。

2. 状态转换：对于 DFA 的每个状态 $T$ 和每个输入符号 $a$，计算 NFA 中从状态集合 $T$ 中每个元素出发经过输入符号 $a$ 以及任意个 $\varepsilon$ 转移能到达的所有状态的集合（不包含每个元素自身），作为新的 DFA 状态。

3. 接受状态：DFA 的接受状态为包含 NFA 接受状态的所有状态集合。

通过子集构造法，可以将 NFA 转换为等价的 DFA，从而实现正则表达式到 DFA 的转换。

DFA 的化简#

DFA 的化简是将一个 DFA 转换为状态数最少的等价 DFA 的过程。

化简步骤：

1. 去除不可达状态：从初始状态出发，找出所有可达状态，删除不可达状态。

2. 合并等价状态：将等价状态合并为一个状态。等价状态是指对于任意输入字符串，两个状态经过相同的输入字符串后，最终到达的状态要么都是接受状态，要么都是非接受状态。

3. 重命名状态：为化简后的 DFA 中的状态重新命名，使其更易读。

具体在实现中，首先去除不可达状态，这是显然的。

然后可以通过迭代的方法来合并等价状态：

• 初始划分：将状态集合划分为接受状态集合和非接受状态集合。

• 迭代划分：对于每个划分中的状态，对于每个输入符号，检查其转移到的状态是否在同一划分中。如果不在同一划分中，则将该状态划分为不同的子集。如果没有对应的转移，则视为转移到一个特殊的“死状态”，该死状态与其他状态不等价，但是都转移到死状态的状态是等价的。

• 终止条件：当划分不再变化时，停止迭代。

最后，重命名状态，使其更易读。重命名后的状态的转移关系与原 DFA 保持一致。

重写文法#

通过引入新的非终结符和调整产生式的结构，可以消除二义性。例如，可以将上述二义性文法重写为：

1
T -> T * F | F
2
F -> ( E ) | id

这样，乘法运算的优先级高于加法运算，从而消除了二义性。

引入优先级和结合性规则#

通过定义运算符的优先级和结合性，可以指导解析器选择正确的语法结构。例如，可以规定乘法运算的优先级高于加法运算，并且两者都是左结合的。

通过这些方法，可以有效地消除二义性文法，提高解析器的准确性和效率。

消除左递归#

如果文法中存在推导 $A \implies^+ A \alpha$，则称该文法具有左递归。

可以通过重写产生式来消除直接左递归：

对于产生式 $A \rightarrow A \alpha | \beta$，可以重写为：

$A \rightarrow \beta A^{'}$ $A^{'} \rightarrow \alpha A^{'} | \varepsilon$

可以理解为，原本 $A$ 可以推导出任意多个 $\alpha$，现在通过引入新的非终结符 $A^{'}$ 来表示这种重复的结构。

注意到此处 $\varepsilon$ 不可省略。

对于间接左递归，则需要先进行消除直接左递归，再进行重写：

对于产生式 $A \rightarrow B \alpha$ 和 $B \rightarrow A \beta | \gamma$，可以重写为：

$A \rightarrow \gamma \alpha A^{'}$ $A^{'} \rightarrow \beta \alpha A^{'} | \varepsilon$

提取左公因子#

如果文法中存在多个产生式 $A \rightarrow \alpha \beta_1 | \alpha \beta_2$，则称该文法具有左公因子。

可以通过提取左公因子来重写产生式：

$A \rightarrow \alpha A^{'}$ $A^{'} \rightarrow \beta_1 | \beta_2$

LL(1) 文法#

LL(1) 文法：是一种适合自上而下分析的文法类型。LL(1) 文法要求在每一步推导中，能够根据当前输入符号和栈顶非终结符唯一确定下一步的产生式。

我们首先需要定义两个集合：first 集和 follow 集。

• first 集：对于任意符号串 $\alpha$，first($\alpha$) 是能够出现在 $\alpha$ 推导出的字符串开头的终结符的集合。如果 $\alpha$ 能够推导出 $\varepsilon$，则 $\varepsilon$ 也包含在 first($\alpha$) 中。

  计算 first 集的规则如下：

  1. 如果 $X$ 是终结符，则 first($X$) = {$X$}。

  2. 如果 $X$ 是非终结符，且存在产生式 $X \rightarrow Y_1 Y_2 ... Y_k$，则将 first($Y_1$) 中的所有非 $\varepsilon$ 符号加入 first($X$)。

     • 如果 first($Y_1$) 包含 $\varepsilon$，则继续将 first($Y_2$) 中的所有非 $\varepsilon$ 符号加入 first($X$)，以此类推，直到遇到一个不包含 $\varepsilon$ 的 first 集，或者处理完所有 $Y_i$。
     • 如果所有 $Y_i$ 的 first 集都包含 $\varepsilon$，则将 $\varepsilon$ 加入 first($X$)。

  3. 如果存在产生式 $X \rightarrow \varepsilon$，则将 $\varepsilon$ 加入 first($X$)。

• follow 集：对于任意非终结符 $A$，follow($A$) 是能够出现在某个句子中 $A$ 后面的终结符的集合。如果 $A$ 能够出现在句子的末尾，则 \ $（输入结束符）也包含在 follow($A$) 中。

  计算 follow 集的规则如下：

  1. 将 \ $加入 follow($S$)，其中$S$ 是开始符号。

  2. 如果存在产生式 $B \rightarrow \alpha A \beta$，则将 first($\beta$) 中的所有非 $\varepsilon$ 符号加入 follow($A$)。如果 first($\beta$) 包含 $\varepsilon$，则将 follow($B$) 中的所有符号也加入 follow($A$)。

  3. 如果存在产生式 $B \rightarrow \alpha A$，则将 follow($B$) 中的所有符号加入 follow($A$)。

然后我们其实可以定义 select 集：

• select 集：对于任意产生式 $A \rightarrow \alpha$，select($A \rightarrow \alpha$) 是能够触发该产生式的输入符号的集合。

  计算 select 集的规则如下：

  1. 如果 $\varepsilon \notin$ first($\alpha$)，则 select($A \rightarrow \alpha$) = first($\alpha$)。

  2. 如果 $\varepsilon \in$ first($\alpha$)，则 select($A \rightarrow \alpha$) = (first($\alpha$) - {$\varepsilon$}) $\cup$ follow($A$)。

感性理解即，select 集表示在分析过程中，当栈顶非终结符为 $A$，若 $A$ 能推导出 $\alpha$，则下一个终结符必须在 first($\alpha$) - {$\varepsilon$} 中；若 $\alpha$ 还能推导出 $\varepsilon$，则下一个终结符还可以在 follow($A$) 中。

LL(1) 文法判定的充要条件是 select($A \rightarrow \alpha$) $\cap$ select($A \rightarrow \beta$) = $\emptyset$。

递归下降预测分析#

递归下降预测分析：是一种基于 LL(1) 文法的自上而下分析方法。它使用一组递归函数来模拟分析栈的操作，每个非终结符对应一个递归函数。

具体的，对于每个非终结符 $A$，定义一个递归函数 $parse\_A()$。在该函数中，根据当前输入符号和 $A$ 的产生式的 select 集，选择合适的产生式进行推导。

伪代码示例：

1
function parse_A():
2
    switch (current_input_symbol):
3
        case in select(A -> alpha):
4
            // 推导 A -> alpha
5
            for each symbol in alpha:
6
                if symbol is terminal:
7
                    match(symbol)
8
                else:
9
                    call parse_symbol()
10
            break
11
        case in select(A -> beta):
12
            // 推导 A -> beta
13
            ...
14
            break
15
        ...
16
        default:
17
            error("Unexpected input symbol")

非递归预测分析表驱动法#

非递归预测分析表驱动法：是一种基于 LL(1) 文法的自上而下分析方法。它使用一个分析栈和一个预测分析表来指导分析过程。

预测分析表：是一个二维表格，行表示非终结符，列表示终结符。表格中的每个单元格包含对应非终结符和终结符的产生式。

以下为示例：

假设有如下文法和 SELECT 集：

根据 SELECT 集来构建分析表 $M$：

用表分析输入串：id + id * id $

1. 初始化

• 栈: [ $ , E ] (\$$ 是栈底， E$ 是开始符号在栈顶)

• 输入: id + id * id $ (指向 id)

2. 分析

规约#

规约（Reduction）：是自下而上分析中的一个基本操作。它是将输入串中的一部分符号替换为对应的非终结符，从而逐步构建分析树的过程。

在一步规约中，选择输入串中的一个子串，该子串与某个产生式的右部匹配，然后将该子串替换为该产生式的左部非终结符。

本质上，规约是推导的逆过程。在推导中，我们从非终结符出发，通过应用产生式将其替换为终结符串；而在规约中，我们从终结符串出发，通过应用产生式将其替换为非终结符。

句柄#

句柄（Handle）：是在自下而上分析中，当前输入串中可以进行规约的最右侧子串。换句话说，句柄是句型的一个子串，它与某个产生式的右部匹配，并且在当前分析状态下，可以被规约为该产生式的左部非终结符。

句柄的性质：

1. 句柄的右侧仅含有终结符。

2. 若文法二义，则句柄可能不唯一。

例：

考虑以下文法：

$A \rightarrow \beta$

则 $\alpha \beta \omega$ 的句柄为 $\beta$，注意不是 $\beta \omega$（句柄必须是产生式的右部）。

用栈实现移进-规约分析#

分析器的基本动作有两种：移进（Shift）和规约（Reduce）。实际还可能会有接受（Accept）和出错（Error）两种动作。

移进：将当前输入符号移入栈中。

规约：将栈顶的若干符号根据某个产生式进行规约。

接受：当栈中只剩下开始符号，且输入串已全部处理完毕时，表示分析成功。

出错：当无法进行移进或规约时，表示分析失败。

移进-规约分析的基本步骤：

1. 初始化：将栈初始化为空，输入串指向第一个符号。

2. 分析循环：

   1. 检查栈顶符号和当前输入符号，决定进行移进还是规约。

   2. 如果可以规约，则执行规约操作，将栈顶的若干符号替换为对应的非终结符。

   3. 如果不能规约，则执行移进操作，将当前输入符号移入栈中，并将输入指针向后移动一位。

   4. 如果栈中只剩下开始符号，且输入串已全部处理完毕，则执行接受操作，分析成功。

   5. 如果无法进行移进或规约，则执行出错操作，分析失败。

3. 重复步骤 2，直到分析成功或失败。

在每一步中的动作，都是基于当前栈顶符号和输入符号来决定的下一步操作。

移进-规约分析的冲突#

在移进-规约分析中，可能会遇到两种类型的冲突：移进-规约冲突和规约-规约冲突。

1. 移进-规约冲突（Shift-Reduce Conflict）：当分析器在某个状态下，既可以进行移进操作，也可以进行规约操作时，就会发生移进-规约冲突。这种冲突通常发生在文法中存在二义性或者优先级不明确的情况下。

例如，考虑以下文法：

1
E -> E + E
2
E -> E * E
3
E -> id

对于输入串 id + id * id，在分析过程中，当栈顶为 E + E 时，分析器既可以选择移进下一个符号 *，也可以选择规约 E + E 为 E。这就导致了移进-规约冲突。

2. 规约-规约冲突（Reduce-Reduce Conflict）：当分析器在某个状态下，存在多个产生式可以用于规约时，就会发生规约-规约冲突。这种冲突通常发生在文法中存在二义性或者产生式重叠的情况下。

例如，考虑以下文法：

1
S -> A
2
S -> B
3
A -> a
4
B -> a

对于输入串 a，在分析过程中，当栈顶为 a 时，分析器既可以选择规约 a 为 A，也可以选择规约 a 为 B。这就导致了规约-规约冲突。

为了解决这些冲突，可以采取以下方法：

• 优化文法：通过重写文法，消除二义性和重叠的产生式。

• 引入优先级和结合性规则：为运算符定义优先级和结合性，指导分析器选择正确的操作。

• 使用更强大的分析方法：如 LR 分析器，可以处理更广泛的文法类型，减少冲突的发生。

活前缀#

活前缀（Viable Prefix）：是在自下而上分析中，当前栈中的符号串，它是某个右句型的前缀，并且可以通过一系列规约操作从输入串中得到。该前缀不超过最右句柄，最多包含最右句柄。

LR(0) 项目#

LR(0) 项目：是文法产生式的一种扩展形式，用于表示分析器在某个状态下的分析情况。LR(0) 项目由一个产生式和一个点（·）组成，点表示当前分析的位置。

例如，考虑产生式 $A \rightarrow XYZ$，则对应的 LR(0) 项目有以下几种形式：

• $A \rightarrow \cdot XYZ$：表示还没有分析任何符号。

• $A \rightarrow X \cdot YZ$：表示已经分析了符号 $X$，正在分析符号 $Y$。

• $A \rightarrow XY \cdot Z$：表示已经分析了符号 $X$ 和 $Y$，正在分析符号 $Z$。

• $A \rightarrow XYZ \cdot$：表示已经分析完了符号 $X$、$Y$ 和 $Z$。

如果产生式为 $A \rightarrow \varepsilon$，则对应的 LR(0) 项目为 $A \rightarrow \cdot$。

项目分为四类：

• 规约项目：点的后继符号为空。

• 移进项目：点的后继符号为终结符。

• 待约项目：点的后继符号为非终结符。

• 接受项目（唯一）：项目左部为拓广文法的开始符号的规约项目。

LR(0) 项目集规范族#

LR(0) 项目集规范族：是 LR(0) 分析器的核心概念，用于表示分析器在不同状态下的分析情况。LR(0) 项目集规范族由一组 LR(0) 项目集组成，每个项目集表示分析器在某个状态下可能的分析情况。

构建 LR(0) 项目集规范族的步骤：

1. 拓广文法：从文法的开始符号出发，构建初始项目集 $I_0$，包含项目 $S' \rightarrow \cdot S$，其中 $S'$ 是新的开始符号。

2. 闭包操作：对于每个项目集 $I$，执行闭包操作，添加所有可能的项目。对于每个项目 $A \rightarrow \alpha \cdot B \beta$，如果 $B$ 是非终结符，则将所有产生式 $B \rightarrow \gamma$ 添加到项目集中，形式为 $B \rightarrow \cdot \gamma$。

3. 转移操作：对于每个项目集 $I$ 和每个符号 $X$（终结符或非终结符），计算转移项目集 $goto(I, X)$。对于每个项目 $A \rightarrow \alpha \cdot X \beta$，将其转换为 $A \rightarrow \alpha X \cdot \beta$ 并添加到新的项目集中。

4. 重复步骤 2 和 3，直到不再有新的项目集产生。

通过构建 LR(0) 项目集规范族，可以为 LR(0) 分析器提供状态机的基础，从而实现对输入串的分析和处理。

SLR(1) 分析器#

SLR(1) 分析器：是一种基于 LR(0) 项目集规范族的自下而上分析器。它通过引入 follow 集来解决 LR(0) 分析器中的移进-规约冲突，从而能够处理更广泛的文法类型。

SLR(1) 分析器的构建步骤：

1. 构建 LR(0) 项目集规范族：按照前述方法构建 LR(0) 项目集规范族。

2. 计算 follow 集：对于文法中的每个非终结符，计算其 follow 集。

3. 构建分析表：对于每个项目集 $I$ 和每个项目 $A \rightarrow \alpha \cdot$（规约项目），如果 $A$ 不是拓广文法的开始符号，则对于每个终结符 $a$ 在 follow($A$) 中，将规约操作 $A \rightarrow \alpha$ 添加到分析表的对应位置。

4. 处理移进操作：对于每个项目集 $I$ 和每个项目 $A \rightarrow \alpha \cdot a \beta$（移进项目），将移进操作添加到分析表的对应位置。

通过引入 follow 集，SLR(1) 分析器能够更准确地决定何时进行规约操作，从而减少移进-规约冲突的发生，提高分析器的能力。

LR(1) 分析器#

LR(1) 分析器：是一种更强大的自下而上分析器，它通过引入向前看符号（lookahead symbol）来解决移进-规约冲突和规约-规约冲突，从而能够处理更广泛的文法类型。

LR(1) 分析器的构建步骤：

1. 构建 LR(1) 项目集规范族：与 LR(0) 项目类似，但每个项目还包含一个向前看符号。对于每个项目 $A \rightarrow \alpha \cdot B \beta, a$，如果 $B$ 是非终结符，则将所有产生式 $B \rightarrow \gamma$ 添加到项目集中，形式为 $B \rightarrow \cdot \gamma, b$，其中 $b$ 属于 first($\beta a$)。

• 关于 first($\beta a$) 的计算：

  1. 如果 $\beta$ 能推导出 $\varepsilon$，则 first($\beta a$) = first($\beta$) - {$\varepsilon$} $\cup$ { $a$ }。

  2. 如果 $\beta$ 不能推导出 $\varepsilon$，则 first($\beta a$) = first($\beta$)。

2. 构建分析表：对于每个项目集 $I$ 和每个项目 $A \rightarrow \alpha \cdot$（规约项目），对于每个向前看符号 $a$，将规约操作 $A \rightarrow \alpha$ 添加到分析表的对应位置。对于每个项目 $A \rightarrow \alpha \cdot a \beta$（移进项目），将移进操作添加到分析表的对应位置。

通过引入向前看符号，LR(1) 分析器能够更准确地决定何时进行规约操作，从而进一步减少冲突的发生，提高分析器的能力。

LALR(1) 分析器#

LALR(1) 分析器：是一种介于 SLR(1) 和 LR(1) 之间的自下而上分析器。它通过合并具有相同核心的 LR(1) 项目集来减少状态数量，从而在保持较高分析能力的同时，提高分析器的效率。

LALR(1) 分析器的构建步骤：

1. 构建 LR(1) 项目集规范族：按照前述方法构建 LR(1) 项目集规范族。

2. 合并项目集：对于具有相同核心（即忽略向前看符号后相同）的 LR(1) 项目集，将它们合并为一个 LALR(1) 项目集。合并后的项目集包含所有原始项目集的项目，但向前看符号为它们的并集。

3. 构建分析表：与 LR(1) 分析器类似，但使用合并后的 LALR(1) 项目集来构建分析表。

通过合并项目集，LALR(1) 分析器能够显著减少状态数量，从而提高分析器的效率，同时仍然能够处理大部分 LR(1) 文法。

但是，LALR(1) 分析器由于合并项目集，可能会引入规约-规约冲突，因此在某些情况下，其分析能力可能略低于 LR(1) 分析器。

翻译方案#

翻译方案：是在文法产生式中嵌入语义动作的一种方法。语义动作通常用大括号 {} 包围，表示在语法分析过程中执行的操作。

例如，考虑以下产生式和嵌入的语义动作：

1
E -> E1 + T { E.val = E1.val + T.val }

在这个例子中，语义动作 { E.val = E1.val + T.val } 表示在分析过程中，当应用该产生式时，计算表达式 E 的值。

本质上，翻译方案是对语法制导定义的一种实现性改进或具体化。

L 属性定义的自上而下计算#

当只需要综合属性时：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。

如果既有综合属性又有继承属性，在建立翻译模式时就必须保证：

1. 产生式右边的符号的继承属性必须在先于这个符号的动作中计算出来。

2. 一个动作不能引用这个动作右边的符号的综合属性。

3. 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。

可以感性理解：非终结符为函数，则其继承属性为函数的参数，综合属性为函数的返回值。S 属性定义的自下而上本质上就是 AST 的后序遍历，而 L 属性定义的自上而下就涉及到函数的递归问题，为了不要发生无限递归，我们就需要消除左递归。

通过改写文法用综合属性代替继承属性#

通过改写文法用综合属性代替继承属性：是一种将 L 属性文法转换为 S 属性文法的方法。该方法通过引入新的非终结符和产生式，将继承属性转换为综合属性，从而简化属性计算过程。

一个常见的例子是 Pascal 语言中的类型声明。假设有以下产生式：

1
D -> L : T
2
T -> type
3
L -> L, id | id

该产生式中的 L 非终结符有一个继承属性 type，用于传递类型信息。我们可以改写文法，将继承属性转换为综合属性：

1
D -> id L
2
L -> , id L | : T
3
T -> type

在改写后的文法中，L 非终结符的类型信息作为综合属性传递，从而避免了继承属性的使用。通过这种方法，可以将 L 属性文法转换为 S 属性文法，简化属性计算过程。

L 属性定义的自下而上计算#

在自下而上计算中，我们常使用一个辅助栈来存储继承属性的值。在规约操作时，将继承属性从栈中弹出，并将其传递给相应的非终结符。

对于不需要进行属性计算的翻译方案，可以新建一个语法记号并让其产生 $\varepsilon$，然后把不需要计算属性的动作放在这个新记号的产生式中。

对于需要进行属性计算的翻译方案，我们可以考虑确定栈中所需要的继承属性的位置，然后在规约时直接可以从栈中取出这些属性进行计算。

需要注意的情况是，有时候可能会出现栈中所需要的继承属性位置不唯一的情况，这时可以通过在翻译方案中增加一些辅助记号来解决这个问题，从而确保每个继承属性的位置是唯一确定的。

例如，考虑以下产生式：

1
A -> B D
2
A -> B C D

假设 D 有一个继承属性 type，D.type = B.type。

• 在规约 A -> B D 时，栈中 B 的位置是唯一的，可以直接取出 B.type 进行计算。

• 在规约 A -> B C D 时，D.type 仍然等于 B.type，但此时无法唯一确定 B 的位置。

为了解决这个问题，我们可以引入一个新的辅助记号 X，使文法变为：

1
A -> B D
2
A -> B C X D
3
X -> ε

这样，在规约 A -> B C X D 时，X 的位置是唯一的，可以通过 X 来间接确定 B 的位置，从而正确计算 D.type。

名字的作用域#

名字的作用域（Scope of a Name）：是指在程序中一个名字（变量、函数等）可以被访问和使用的范围。作用域决定了名字的可见性和生命周期。

感性理解可以理解为变量的作用域。

即使一个名字在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象。

注意到作用域和生存期是两个概念，作用域指的是什么时候可以访问一个名字，而生存期指的是什么时候一个数据对象存在于内存中。

名字（变量）的作用域和绑定#

名字到存储单元的绑定：

• 环境把名字映射到左值（存储单元），而状态把左值映射到右值（值）。

• 赋值改变状态，但不改变环境。

• 如果环境将名字 x 映射到存储单元 s，就说 x 被绑定到 s。

活动记录#

活动记录（Activation Record）：是用于存储过程活动信息的数据结构。它包含了过程执行所需的各种信息，如参数、局部变量、返回地址等。

被编译程序每次运行时，编译器从操作系统获得一块存储区（内存）。其内容包括：

• 编译后的目标代码（可执行程序.exe）

• 数据对象（各种静态变量和动态变量）

• 用于管理过程活动的控制栈（活动记录）

被编译程序每次运行时，编译器从操作系统获得一块存储区（内存）。其空间安排大概为：

一般的活动记录的布局：

局部数据的安排#

• 字节是可编址内存的最小单位。

• 一个过程所声明的局部变量，按这些变量声明时出现的次序，在活动记录的局部数据区中依次分配空间。

• 局部数据的地址可以用相对于某个位置（本过程对应的活动记录的起始位置）的偏移来表示。

• 数据对象的存储安排深受目标机器寻址方式的影响，存在对齐问题。例如，要求整数（int，long）的相对地址可以被 $4$ 整除。

• 由于对齐而引起的无用空间称为衬垫空白区。

这里涉及结构体的对齐问题，结构体的对齐方式通常是按照其最大成员的对齐方式进行对齐。

程序块#

程序块（Block）：是指一组语句的集合，这些语句在逻辑上被组织在一起。程序块可以包含变量声明、控制结构、函数调用等。

程序块的作用域通常是从块的开始到块的结束。在程序块内声明的变量只能在该块内访问。

分配策略#

分配策略：是指在运行时存储空间中为数据对象分配内存的策略。常见的分配策略包括静态分配、堆式分配和栈式分配。

静态分配#

静态分配：

• 名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。

• 绑定的生存期是程序的整个运行时间。

• 控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。

• 每个活动记录的大小是固定的。

• 过程调用时保存信息的地址在编译时也是已知的。

静态分配的限制：

• 递归过程不被允许

• 数据对象的长度和它在内存中位置，必须是在编译时可以知道的

• 数据结构不能动态建立

栈式分配#

静态分配：

• 主要用于管理过程的活动记录。

• 局部变量的生存期是过程活动的时间。

• 控制进入该过程时，局部变量绑定到存储单元，过程活动结束后，局部变量的空间释放。

活动树：是表示程序中过程调用关系的树状结构。每个节点表示一个过程活动，边表示过程调用关系。描绘控制进入和离开活动的方式。

运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）

调用序列#

调用序列（Call Sequence）：是指在程序执行过程中，过程调用和返回的顺序。调用序列反映了程序的控制流和过程间的调用关系。

过程调用序列：过程调用时执行的分配活动记录，把信息填入它的域中，使被调用过程可以开始执行的代码

过程返回序列：被调用过程返回时执行的恢复机器状态，释放被调用过程活动记录，使调用过程能够继续执行的代码