标签：符号表 笔记 SDD 编译 地址 原理 quad 过程 属性

5 语法制导翻译

考虑语义分析——为 CFG 中的文法符号设置语义属性；在语法分析树上，语义属性值用与文法符号所在产生式（语法规则）相关联的语义规则来计算
语义规则同语法规则（产生式）相联系，涉及概念：

• 语法制导定义 (Syntax-Directed Definitions, SDD)
• 语法制导翻译方案 (Syntax-Directed Translation Scheme, SDT)

5.1 语法制导定义 SDD

语法制导定义 SDD，是对 CFG 的推广，具体而言，对于 CFG 的每个：

• 文法符号，即语法分析树上的一个节点 \(N\) 携带的符号 \(X\)，和一个 语义属性集合 相关联
  其中某个属性 \(a\) 表示为 \(X.a\)，分为：
  • 综合属性 (synthesized attribute)
    非终结符 \(A\) 的综合属性只能通过 \(N\) 的 子结点 或 \(N\) 本身 的属性值来定义
    终结符可以具有综合属性，值为词法分析器提供的词法值；因此没有对应语义规则
  • 继承属性 (inherited attribute)
    非终结符 \(A\) 的继承属性只能通过 \(N\) 的 父结点/兄弟结点 或 \(N\) 本身 的属性值来定义
    终结符没有继承属性
• 产生式，和一组 语义规则 相关联
  通过产生式关联的语义规则，在分析树上计算属性值
  语义规则为调用动作的，称为 “副作用”；对应节点属性称为 “虚属性”
  一个没有副作用的 SDD 称为属性文法
  语义规则通过 SDT 实现，见下

注释分析树 (Annotated parse tree)：每个节点都写有属性值的分析树

SDD 求值顺序

依赖图：由语义规则导出，描述分析树中结点的每个属性间依赖关系的有向图

• 分析树中每个 \(X.a\) 都对应着依赖图中的一个结点
• 如果属性 \(X.a\) 的值依赖于属性 \(Y.b\) 的值，则建立 \(Y.b \to X.a\) 有向边；　　
  特别地，对于来自自己的属性，画一个自环

依赖图可解的条件为其为 DAG，用得到的拓扑序列来计算
具体而言，序列 \(X_1 . a_1, X_2 . a_2,\dotsb\)，若有边 \(X_i . a_i\to X_j . a_j\)，则有 \(i<j\)

解决多元环：存在 SDD 的有用子类，能保证其语法树均为 DAG，而且还能和自顶向下、自底向上一起实现：

• S-属性定义 (S-Attributed Definitions, S-SDD)
• L-属性定义 (L-Attributed Definitions, L-SDD)

5.2 S-SDD，L-SDD

• S-SDD \(\sube\) L-SDD
• S-属性定义，S-SDD：仅使用 综合属性，可以 自底向上
• L-属性定义，L-SDD，若它的每个属性：
  • 要么是 综合属性
  • 要么是 继承属性，且满足继承自 父亲/先序兄弟节点/自身，具体来说：
    假设产生式为 \(A→X_1 X _2 \dotsb X _n\)，符号 \(X _i\) 仅具有继承属性，则其依赖：
    • \(A\) 的 继承属性（否则二元环）
    • \(X _1, X_2,\dotsb, X _{i-1}\) 的属性（向左依赖）
    • \(X _i\) 本身的属性

5.3 语法制导翻译方案 SDT

语法制导翻译方案 (SDT)，是在产生式右部中嵌入了程序片段（称为语义动作）的 CFG，表示各属性计算的时机，以 {} 括起
SDT 实现方法：LR 分析 + S-SDD、LL 分析 + L-SDD

LR 分析+S-SDD 实现 SDT（见 5.5）

1. S-SDD 转换为 SDT：将每个语义动作都放在产生式的最后
2. 实现 SDT：LR 分析过程中，当归约发生时执行相应的语义动作
   为栈增加综合属性值字段，对栈操作时顺带更新即可

LL 分析+L-SDD 实现 SDT（见 5.4）

回顾：LL 使用递归下降分析，可以递归，也可以栈维护非递归；这里一般指 LL(1)

1. L-SDD 转换为 SDT：
   • 将计算某个非终结符号 \(A\) 的继承属性的动作插入到产生式右部中紧靠在 \(A\) 的本次出现之前的位置上
   • 将计算一个产生式 左部符号 的 综合属性 的动作放置在这个产生式右部的 最右端
2. 实现 SDT：有三种
   • 在非递归的预测分析过程中进行（见 5.4.1）
   • 在递归的预测分析过程中进行（见 5.4.2）
   • 在 LR 分析过程中进行

5.4 LL + L-SDD 的自顶向下翻译

LL(1) 预测分析法，包括递归和非递归的方法

如图，从语法分析树上（包括动作虚属性）看，继承属性在调用之前插入继承动作，综合属性动作插在这个产生式的最后；按先序遍历

5.4.1 非递归的预测分析

回顾非递归的自顶向下：维护符号栈 \(A X _1 X _2\dotsb X _n \$]\) 和输入串 \(w\$\)，每次根据栈顶字符 \(A\) 和当前输入字符 \(a\)：若 \(A\) 为终结符且为 \(a\)，则抵消，否则查表运用产生式 \(A\to Y _1\dotsb Y _m\) 替换栈顶为 \(Y _1\dotsb Y _m X _1 X _2\dotsb X _n \$]\)，然后继续
现在维护新的同步运行的栈，用于保存属性值或动作；对每个符号 \(A\)：

• 若 \(A\) 为终结符，则直接在同步栈的同样位置存储其值（由词法分析得到，归为综合属性）
• 若 \(A\) 为非终结符，则
  • 在同步栈的同样位置存储其继承属性值
  • 在符号栈中 \(A\) 的底下放一个符号 \(Asyn\)，代表 \(A\) 的综合属性，并在同步栈的对应位置存储其综合属性值

在符号栈内，还可能有 \(Action\)（或以指针 \(\{a\}\) 表示）代表一些动作，并在同步栈的相同位置保存具体的内容（或其指针）

\[\begin{matrix} & \dotsb & \{a\} & A & Asyn & \{a'\} & \dotsb \$] & \text{符号栈} \\ & \dotsb & \text{指向动作的指针} & \text{A的继承属性} & \text{A的综合属性}& &\dotsb \$] & \text{同步栈} \end{matrix} \]

对初始状态，栈为 \(T, Tsyn, \$]\)
每次对于栈顶元素：

• 若其为非终结符 \(S\)，当前栈为 \(S, Ssyn,\dotsb,\$]\)，则由 SDT \(S\to A _1\{a _1\}A _2\{a _2\}\dotsb A _m\{a _m\}\)，在栈中替换 \(S\)：
  \[\begin{aligned} S, Ssyn,\dotsb,\$] \\ \implies A _1,\{a _1\},A _2,\{a _2\},\dotsb, A _m,\{a _m\}, Ssyn,\dotsb,\$]\end{aligned} \]

• 若其为终结符 \(a\)，则已获得综合属性值，当前即将出栈，则出栈前将 \(a\) 的属性值存到栈里需要 \(a\) 的属性值的那些动作 \(\{a\}\) 的槽里（形如 top±p，事先计算好）
• 若其为动作 \(\{a\}\)，则对槽里的值执行计算动作，然后将值送给 top±p 的位置（事先计算好），然后出栈；
  比如对于上面的 \(\{a _m\}, Ssyn,\dotsb\)，若 \(\{a _m\}\) 是计算综合属性值 \(Ssyn\) 的动作，则算完后将结果放入 top-1 位置（见下图第一行到第二行）
• 若其为综合属性 \(Ssyn\)，则和终结符一样，出栈前将其值存到需要其的那些动作的槽里（形如 top±p，事先计算好，可根据产生式计算，例如下图第二行到第三行）

上面提到的将 符号的值 送入 动作所在位置 都是事先计算好的的代码，怎么算呢？
注意：先执行语义动作（top 未变），再更新符号栈（改变 top）
对每一个 SDT 语句，考察其内部每一个符号 \(A\) 和该语句内需要 \(A\) 的值的动作，判断 \(A\) 为 top 时，这些动作在栈的什么位置（注意，计算时对于非终结符 \(S\)，需要计算 \(S, Ssyn\) 两个！）
比如 SDT \(T\to {\color{yellow} F}\{T'.val={\color{yellow} F}.val + T.val\}T'\)
对于 \(T\)，出栈 前 将其值送入 top+2 位置（\(T\) 出栈后 \(F,Fsyn,\{a\},T',T'syn\) 入栈，从右往左是 top,top+1,...）
对于 \(F\)，出栈前将其值送入 top-1 位置

5.4.2 递归的预测分析

这玩意就直接从语法树来看就行了，比非递归直观的多
沿用递归下降分析，为每个非终结符 \(A\) 构造的函数：\(A\) 的每个继承属性对应该函数的一个形参（回顾：L-SDD 要求继承自父亲或之前的兄弟节点，也就是 dfs 序小于其的节点，所以在调用时已知，自然可以作为形参传入），函数的返回值是 \(A\) 的综合属性值
在函数内，对每个产生式右部文法符号的每个属性都设置一个局部变量，用于后续使用，比如传入函数、写入动作的计算表达式

5.5 L-SDD 的自底向上翻译

我们在 5.4 讨论的是 LL 分析为基础的 L-SDD 的自顶向下翻译
如果我们考虑使用 LR 分析——自底向上时，我们总是归约——这意味在代码中我们只能在归约出一个产生式后才能执行动作，而不能将动作插入产生式。
所以现在我们得等价修改这个 SDT，使得所有语义动作都位于产生式末尾，从而能够在 LR 语法分析过程中计算

1. 首先由 5.4 已经完成 L-SDD 转换为 SDT（在非终结符之前放置语义动作来计算其继承属性，在产生式后端放置语义动作计算综合属性）
2. 现在对于每个内嵌的语义动作 \(\{a\}\)，向文法中引入一个“标记非终结符” \(M _i\) 来替换它；每个这样的语义动作都有一个不同的标记，并且对于任意一个标记 \(M\) 都有一个产生式 \(M→ε\)
   • 假设 \(M\) 对应的 \(\{a\}\) 所在的产生式为 \(A→α\{a\}β\)，替换后为 \(A→αMβ\)；且修改 \(a\) 为 \(a'\)，将 \(a'\) 关联到 \(M→ε\) 末尾
   • 修改：动作 \(a\) 需要的 \(A, α\) 中符号的任何属性，作为 \(M\) 的继承属性进行复制
   • 遵循 \(a\) 中的方法计算各个属性，但是将计算得到的这些属性作为 \(M\) 的综合属性
   • 从代码实现上，也需要考虑对于语义动作，其所需的属性值在栈的哪个位置

例如：\(T' → *F \{ T _1'.inh = T'.inh × F.val \} T _1' \{ T'.syn = T _1'.syn \}\)
用 \(N\) 替换后：
\(T' → *F\ N\ T _1' \{ T'.syn = T _1'.syn \} \\ N → ε \{ N.i _1 = T'.inh;\qquad \text{ 继承属性}\\ \qquad\quad N.i _2 = F.val;\qquad\quad\text{ 继承属性}\\ \qquad\quad N.s = N.i _1 × N.i _2\quad\text{ 综合属性}\\ \quad \text{代码其实就是（注意在 LR 中我们习惯符号栈底在左）：} \\ \qquad\quad stk[top+1].T1'.inh = stk[T'.inh 的位置，相关产生式未写出].T'.inh × stk[top].F.val; \\ \qquad\quad top = top + 1 \}\)

从代码上看，和 L-SDD 的非递归几乎一致，无非是加入了标记非终结符而已、把代码转移过去而已
再次强调：在符号栈执行 \(N\to ε\)（top+1，将 \(N\) 入栈） 前，先执行其动作语句

6 中间代码生成

6.1 声明语句

过程：收集标识符的类型等，并赋予其一个相对地址，保存在符号表记录中

类型表达式 Type Expressions

包括：

• 基本类型，如 \(int, real, char, type\_ error, void\)
• 为类型表达式命名的类型名
• 类型构造符 作用于 类型表达式
  • 数组：\(array(I, T)\)，\(I\) 为整数，\(T\) 为类型表达式，下同；表示 \(I\) 个 \(T\)
    int[3]：\(array(3, int)\)
    int[4][3]：\(array(4, array(3, int))\)
  • 指针：\(pointer(T)\)
  • 笛卡尔乘积构造符 \(\times\)，将每个名字和每个类型关联；函数构造符 \(→\)，记录构造符 \(record\)
  • 例如

    struct stype {
      char[8] name;
      int score;
    };
    stype[50] table;
    stype* p;
    

    \(record((name\times array(8, char))\times(score\times integer)) \\ array(50, stype) \\ pointer(stype)\)

局部变量分配

• 类型的宽度 \(width\)：该类型运行时所需存储单元数，从类型表达式可知；
• 符号表：表项为 \((name, type, offset)\)，符号名，类型，相对地址
  用函数 \(enter(name, type, offset)\) 创建新表项
• 在 SDT 实现过程中，在动作里插入相应代码
  • 先序遍历（可以在 LL(1) 时顺便做）
  • 维护全局变量 \(offset\)，存储下一个可用的偏移地址，被初始符号的产生式的动作赋值为 \(0\)
  • 维护全局变量 \(t,w\)，存储当前声明语句对应的 基本类型 的 \(type,width\)，用于计算其声明的符号的总宽度
  • 为树上每个符号（比如 int[3]），维护其综合属性 \(type, width\)
  • 在语义动作中，可能有：
    • 完成一个声明块（如 , ;）后，符号表 \(enter\) 增加新表项
    • 执行完 \(enter\) 后，更新 \(offset\) 更新
    • 识别出类型后，更新 \(t, w\)
    • 某个符号的综合属性 \(\larr t, w\) 或特定的 \(type, width\) 的表达式

6.2 赋值语句

6.2.1 简单赋值语句

过程：为若干表达式求值语句，生成对应的三地址码的指令序列（即指令都为三地址 addr1, addr2, addr3 进行某个基本运算并赋值，如 \(t _1 = t _2 + \#1\)）

• 对于表达式 \(E\)，需要维护其综合属性:
  • \(code\)：若干三地址码，对于儿子的 code 用 \(||\) 连接；用 \(gen(code)\) 生成新的 \(code\)
  • \(addr\)：地址，该地址用于存放变量、子表达式或表达式本身的（临时变量）值
• 为代码块 \(S\)，维护其代码 \(S.code\)
• 函数
  • \(lookup(name) = lookup(id.lexeme)\)：查询符号表（6.1 完成）返回 \(name\) 对应的地址 \(addr\)
  • \(newtemp()\)：生成一个新的临时变量 t，返回 t 的地址
  • \(gen(code)\)：生成三地址指令 \(code\)；并将其添加到已生成的指令序列后（“增量翻译”）
• 对变量符号本身，调用 \(lookup\) 查
• 对中间表达式，用 \(newtemp\) 新建
• 在识别出赋值语句后，调用 \(gen\) 生成代码

如下，其实就是实验三中对赋值语句的操作；
为 \(E\) 新建地址 \(addr\)，相当于实验中的为 Exp 建立 t1 = newtemp()
注意对于 \(id\) 需要在表中查找其地址 \(addr = lookup(id.lexeme)\) 而不是新建

6.2.2 数组引用

将数组引用翻译成三地址码的问题
考虑数组某个位置 \(a[i _1] [i _2] …[i _k]\)，记 \(w _1\) 为 \(a[i _1]\) 宽度，\(w _2\) 为 \(a[i _1][i _2]\) 宽度...其对应 \(type(a) = arr(i _1, arr(i _2, arr(\dotsb arr(i _k, int))))\) 逐层的 width：
数组元素 \(a[i _1] [i _2] …[i _k]\) 的相对地址是：

\[\begin{aligned} &base + i _1 w _1 + i _2 w _2 + \dotsb + i _k w _k \\=&base + i _1\times width[arr(i _2, arr(\dotsb arr(i _k, int)))]+\dotsb + i _k \times width[int]\end{aligned} \]

SDT，数组符号 \(L\)，表达式 \(E\)
其中为 \(L\) 维护综合属性：

• \(L.type\)：\(L\) 生成的数组元素的类型；如下图，从底层 a[3] 向上传递，逐层剥离出嵌套的子类型 \(.elem\)
• \(L.offset\)：指示一个临时变量，该临时变量用于累加公式中的 \(i _j × w _j\) 项，从而计算数组元素的偏移量
• \(L.array\)：数组名在符号表的地址，可以用于查找此数组名的基础类型 \(.type\)、基础类型的宽度 \(.type.width\) 等

最后的赋值语句直接写成 \(L.array [L.offset] = E.addr\)

6.3 控制语句

6.3.1 控制流语句

\[\begin{aligned} P \to &\quad S \\ S \to &\quad S _1 S _2 \\ S \to &\quad \text{id} = E\quad |\quad L = E ; \\ S \to &\quad {\rm if}\ B\ {\rm then}\ S _1 \\ &|\quad{\rm if}\ B\ {\rm then}\ S _1\ {\rm else}\ S _2 \\ &|\quad{\rm while}\ B\ {\rm do}\ S _1 \\ \end{aligned} \]

指令标号：对每条三地址指令，用其标号（就是序号）标识之，用于跳转

编写 SDT：看图写话

• 计算继承属性，一般在进入 \(B\) 或 \(S\) 前执行声明（和赋值）：
  • 为布尔表达式维护以下两者，且必须在调用前就已经声明好：
    • （必须）\(B.true\)：地址，存放布尔表达式 \(B\) 为真时控制流转向的指令标号
    • （必须）\(B.false\)：地址，存放布尔表达式 \(B\) 为假时控制流转向的指令标号
  • 为代码块维护：
    • （必须）\(S.next\)：地址，存放紧跟在 \(S\) 代码之后执行的指令的标号；一般继承得到，必须在调用前就已经声明好
    • （选择）\(S.begin\)：地址，代码开头，一般定义 \(newlabel()\) 完直接绑定 \(label()\)
• 设定跳转点的函数：组合技
  • \(newlabel()\)：生成一个用于存放指令标号的新的临时变量 \(L\)，返回其地址，提前为代码占坑，用于之后回填
  • \(label(L)\)：将下一条三地址指令的标号存放到变量 \(L\) 地址中
• 画出代码块的控制流
  • 代码结构图中非终结符对应的方框顶部若有导入箭头，调用 \(label()\) 函数
  • 上一个代码框执行完不顺序执行下一个代码框时，生成一条显式跳转指令——插入 \(goto\) 语句
  • 有自下而上的箭头时，设置对应 \(begin\) 用于 \(goto\) 跳转

6.3.2 布尔表达式

\[\begin{aligned} B \to&\quad B \text{ or } B \\ &|\quad B \text{ and } B \\ &|\quad \text{ not } B \qquad;\text{not > and > or}\\ &|\quad (B) \\ &|\quad E \text{ relop } E \\ &|\quad \text{true} \\ &|\quad \text{false} \end{aligned} \]

将 &&、||、! 翻译成跳转指令，通过跳转位置体现其含义；
由 6.3.1，已经得到当前布尔表达式的 \(B.true, B.false\)

此外针对如下冗余 goto 的情况，我们可以考虑精简上述 STD，将左边优化成右边
具体做法需要引入 \(fall\) 做为地址的一种值

1: if a < b goto 3      1: if False a < b goto 11
2: goto 11
3: some code            2: some code

6.4 回填

每个跳转指令都有一个跳转地址；生成一个跳转指令时，先将其放入某个列表，其含义可能为 \(B.truelist, B.falselist, S.nextlist\)：
同一列表内的指令具有相同目的跳转地址；等到能够确定正确的目标标号时，才去填充这些指令的目标标号

函数：

• \(makelist(i)\)：\(i\) 为某个跳转指令的标号，创建新列表并放入 \(i\)，返回指向列表的指针
• \(merge(p _1, p _2)\)：将 \(p _1\) 和 \(p _2\) 指向的列表进行合并，返回合并列表的指针
• \(backpatch(p, i)\)：回填，将 \(i\) 作为目标标号插入到 \(p\) 所指列表中的各指令中

用 \(nextquad\) 存储下一条生成语句的标号，一般在 SDT 中插入 \(\color{grey}{M}\) 以存储该处指令标号，且有 \(M\to \varepsilon\{ M.quad = nextquad; \}\)

布尔表达式
为每个布尔表达式 \(B\) 生成综合属性（用于之后的控制流）：

• \(B.truelist\)：以 \(B\) 为真 为条件跳转的跳转指令的标号 的序列
• \(B.falselist\)：以 \(B\) 为假 为条件跳转的跳转指令的标号 的序列

对于布尔表达式 \(B\)，生成初始 \(truelist, falselist\)，分别存放生成的 \(goto\) 指令
对于布尔表达式的与或非，生成 \(truelist, falselist\) 继承子语句的 \(list\)，并考虑回填

控制语句
为每个控制语句 \(S\) 生成综合属性：

• \(S.nextlist\)：以 \(S\) 代码后的指令标号（\(S.next\)）为目的的跳转指令的标号 的序列

每个控制语句回溯前执行动作：计算综合属性，回填 跳到语句内指令位置 的 \(list\)

6.5 Switch 语句

6.6 过程调用

\[\begin{aligned} S \to&\quad \text{call id} (Elist) \\ Elist \to&\quad Elist,E \\ &|\quad E \end{aligned} \]

7 运行存储分配

7.1 存储组织

存储分配策略

• 静态存储分配：在编译时刻就可以确定大小的数据对象，在编译时刻就为它们分配存储空间
  要尽可能多的进行静态分配，这些对象的地址可以被编译到目标代码中
• 动态存储分配：运行时刻，动态地分配数据对象的存储空间
  • 栈式存储分配
  • 堆式存储分配
    

活动记录
编译器通常以过程（或函数、方法）为单位分配存储空间
程序每次执行该过程，称为一次“活动”，分配的连续存储区称为“活动记录”
活动记录一般形式（按记录的栈底到栈顶的顺序）

• 实参：调用过程提供给被调用过程的参数
• 返回值：被调用过程返回给调用过程的值
• 控制链：指向调用者的活动记录（静态链）
• 访问链：用来访问存放于其它活动记录中的非局部数据
• 保存的机器状态：通常包括返回地址和一些寄存器中的内容
• 局部数据：在该过程中声明的数据
• 临时变量：比如表达式求值过程中产生的临时变量

7.2 静态存储分配

对于某些过程中的名字，这些名字的存储地址可以被编译到目标代码中
过程每次执行时，它的名字都绑定到同样的存储单元

7.3 栈式存储分配

维护活动记录的栈：当一个过程被调用时，该过程的活动记录被压入栈；当过程结束时，该活动记录被弹出栈

活动树

用来刻画运行时进入/离开各个活动的情况
每个结点对应于一个活动；根节点为 main 过程的活动；子结点对应于这次活动调用的各个过程的活动

活动记录的位置设计

• 在调用者和被调用者之间传递的值（参数、返回值）一般被放在被调用者的活动记录的开始位置，尽可能地靠近调用者的活动记录
• 固定长度的项（控制连、访问链、机器状态字）被放置在中间位置
• 在早期不知道大小的项（临时变量）被放置在活动记录的尾部
• 栈顶指针寄存器 \(top\_ sp\) 指向活动记录中局部数据开始的位置，以该位置作为基地址

调用、返回序列

过程调用和返回，需要管理活动记录栈，保存或恢复机器状态；
由调用者和被调用者分别执行一部分代码实现

• 调用序列（实现调用的代码段）
  • 调用者：
    计算实际参数的值；放入被调用者的对应字段
    将返回地址（程序计数器的值）放到被调用者的机器状态字段中：将原来的 \(top\_sp\) 值放到被调用者的控制链中
    然后，增加 \(top\_sp\) 的值，使其指向被调用者局部数据开始的位置
  • 被调用者：
    保存寄存器值和其它状态信息
    初始化其局部数据并开始执行
• 返回序列
  • 被调用者：
    将返回值放到与参数相邻的位置
    使用控制链、机器状态字段中的信息，恢复 \(top\_sp\) 和其它寄存器，然后跳转到由调用者放在机器状态字段中的返回地址
  • 调用者：
    调用者（仍然知道返回值相对于当前 \(top\_sp\) 的位置）使用该返回值

变长数据的存储分配

在编译时刻不能确定大小的对象：将被分配在堆区；或者如果是过程的局部对象（只作用于这个过程，退出过程后不再使用），也可以分配在运行时刻栈中（可避免垃圾回收、减小开销）

7.4 非局部数据的访问

考虑一种语法：过程嵌套声明，也就是过程的声明具有嵌套关系，下文的“嵌套”都是指声明的嵌套，而非运行时过程调用者与被调用者的关系
非局部数据，不属于当前过程声明的局部数据：全局数据、外围过程定义的数据（即过程嵌套声明这种）
访问非局部数据：访问链（静态链）、display 表（嵌套层次显示表）

访问链

静态作用域规则：只要过程 b 的声明嵌套在过程 a 的声明中，过程 b 就可以访问过程 a 中声明的对象
访问链：指针，建立在相互嵌套的过程的活动记录之间，使得内嵌的过程可以访问外层过程中声明的对象；

建立访问链：
注意，声明的嵌套，和运行时调用产生的活动树，是两个概念
访问链指向其直接定义者的、在活动记录栈里最近的活动
具体而言：假设嵌套深度为 \(n _x\) 的过程 \(x\) 调用嵌套深度为 \(n _y\) 的过程 \(y\)，记作 \(x\to y\)

• \(n _x < n _y\) 的情况（外层调用内层），根据语法，\(y\) 一定是直接被 \(x\) 定义的，必有 \(n _y = n _x +1\)
  则在 调用代码序列 中增加一个步骤：在 \(y\) 的访问链中放置一个指向 \(x\) 的活动记录的指针
• \(n _x = n _y\)（同层调用），两者访问链相同，直接赋值即可
• \(n _x > n _y\)（内层调用外层），则顺着 \(x\) 的访问链找到直接定义 \(y\) 的那个即可——沿着链从 \(x\) 走 \(n _x - n _y + 1\) 步就是

Display 表

是一个指针数组 \(d\)
对每个嵌套深度 \(i\)，\(d[i]\) 维护该深度下最新建立的嵌套深度为 \(i\) 的过程的活动记录（在运行栈中可能存在多个嵌套深度为 \(i\) 的过程的活动记录）
如果要访问某个嵌套深度为 \(i\) 的非局部名字 \(x\)，只要沿着指针 \(d[i]\) 找到 \(x\) 所属过程的活动记录，再根据已知的偏移量就可以在活动记录中找到 \(x\)
维护 display 表：

• 每个活动的调用、返回时都需要更新
• 调用某个嵌套深度为 \(i\) 的函数时，其访问链指向 \(d[i]\)，\(d[i]\) 再指向此函数的地址
• 退出某个嵌套深度为 \(i\) 的函数前，将 \(d[i]\) 赋为此函数的访问链指向的地址

7.5 参数传递

不表

7.6 符号表

存放标识符的属性信息，具体可能包括：

• 名称 (Name)
• 种属 (Kind)，变量、数组、过程等，不同种属要存的属性不一样
• 类型 (Type)，整型、实型、字符等
• 存储位置、长度
• 作用域
• 参数和返回值信息（对于过程、函数等）

单个符号表的组织方式：

• 基本属性，直接存放在符号表中
  如种属、类型、地址（偏移地址 offset）、扩展属性指针
• 扩展属性，动态申请内存

对于多个过程，分别建立符号表，组织方式：

• 需要考虑过程间的嵌套关系（作用域信息，对于 c 语义，即花括号括出的代码块）、重名问题
• 对于嵌套定义，外围过程的符号表里有指向若干内部过程的序列，内部过程有指针指向外围过程（见下图的箭头）
• 为每个符号表维护表项的宽度之和（见下图每个表的右上角）

符号表建立（对于嵌套/被嵌套，用相互指针实现）

• 声明语句，若允许嵌套声明，则进入嵌套过程时，应暂时挂起外围过程的声明处理
• 函数：
  • \(mktable(pre)\)
    创建新表，返回新符号表的指针，传入外围过程的符号表指针 \(pre\)
  • \(addwidth ( table, width )\)
    将 \(table\) 指向的符号表中所有表项的宽度之和 \(width\) 记录在符号表的表头
  • \(enter( table, name, type, offset )\)
    在 \(table\) 指向的符号表中，为名字 \(name\) 建立一个新表项
  • \(enterproc(table, name, newtable )\)
    在 \(table\) 指向的符号表中，为过程 \(name\) 建立一条记录，\(newtable\) 指向过程 \(name\) 的符号表
• 建立的同时，同步维护符号表指针栈 \(tblptr\)、对应偏移地址栈 \(offset\)（里面的每个元素，都是某个过程的当前偏移地址，\(tblptr\) 和 \(offset\) 是一一对应的；对于每个过程，内部局部变量的 offset 都是相对过程开头的位置，都是从 0 开始的；过程地址+offset 才是实际运行时的变量地址）

操作：

• 声明语句，对于遇到的某个标识符声明：查 + 填
  先在本层的符号表里查询；若查到，报重复错误
  否则登记新表项
• 执行语句：查
  从该层符号表开始，查找符号信息；未找到则向指向外围的过程符号表查

display 表示

• \(display\) 表：记录下各块所在的层号，沿着该表可以找到当前正在分析的块的各个外层
• \(btab\) 表：块表，对每个块，成对记录 \((lastpar, last)\)，lastpar 指向本过程体中最后一个形参在 nametab 中的位置、last 指向本过程体中最后一个名字在 nametab 中的位置（两者都类似前向星）
• \(nametab\) 表：记录 \(name\) + \(link\)，记录符号名，link 指向同一过程体中定义的上一个名字在 nametab 中的位置（每个过程体在 nametab 中登记的第一个名字的 link 为 0）

标签：符号表,笔记,SDD,编译,地址,原理,quad,过程,属性
From： https://www.cnblogs.com/zhyh/p/17385998.html