Brandon Zhang
October 27, 2020
Semantic Analysis & Runtime Environment
语法分析
知识点：
运行环境
知识点：
- 活动记录、控制栈
- 栈式存储分配
- 非局部名字的访问
- 参数传递方式
7.1 程序运行时的存储组织
7.1.1 程序运行空间的划分
活动与过程的概念 过程：静态概念 活动：一次过程的每次执行，是动态概念 两者可以为1:1或1:m的关系，递归过程中可能一若干个活动活着。
活动的生存期 活动的生存期要么是不重叠的，要么是嵌套的(区别于进程的地方！活动不可以并发执行！)
对于一个程序，它会向操作系统申请一块内存空间：
活动记录会在控制栈中根据栈式存储分配策略来实现。
7.1.2 活动记录与控制栈
- 控制栈
- 局部数据的安排
- 编址限制的影响(padding)
7.1.3 名字的作用域及名字绑定
名字的作用域： 最近嵌套原则
名字绑定： note: 对于递归程序中定义的名字，即使是同一个名字也可能映射到不同的存储空间。
- 左值：存储空间的地址
- 右值：存储空间的内容
7.2 存储分配策略
7.2.1 静态存储分配
- 条件：源程序中声明的各种数据对象所需存储空间的大小在编译时都可以确定。
- 存储分配：编译时,为他们分配固定的存储空间。
- 地址绑定：程序装入内存时进行。
- 运行期间：名字的左值保持不变
不允许递归调用和建立动态数据结构
7.2.2 栈式存储分配(重点)
递归调用：同一个过程在不同存储位置出现。
调用序列
返回序列
其中top_sp = top_ep' - C1 - C2;
P是通过top_sp找到返回值并放入局部数据域中。
7.2.3 堆式存储分配
当活动记录的释放不需要遵循先进后出的原则
控制链代表着调用与被调用者的关系，无需出栈操作。这种存储分配用于动态创建或撤销一个数据结构使用。
7.3 非局部名字的访问
对非局部名字的访问通过访问链实现，关键在于如何创建、使用、维护访问链。
7.3.1 静态作用域规则
非嵌套过程 引用的名字只有两类：
- 局部的：放入局部数据域中，通过top_ep访问
- 全局的：放入静态数据区中(不在活动记录)
嵌套过程
嵌套关系：嵌套深度的概念
访问链：被调用过程活动记录的访问链指向其直接外层过程的最新活动的活动记录
- 过程p引用非局部名字a，则$n_a < n_p$；
- 符号表中，变量名字的目标地址变为： <嵌套深度，偏移量>
访问链的建立：
- q直接嵌套在p中：$n_q = n_p + 1$
- q不嵌套在p中：$n_q \le n_p$
- display表 为了减少指针操作，提高访问非局部名字的速度。
组织形式：
- d[i]指向嵌套深度为i的过程的最新活动的活动记录
- 前i-1个元素指向按静态规则包围过程P的那些过程的最新的活动记录
维护：
- 过程调用时，调用序列中 将q的最新活动记录压入栈顶，并将其插入到$d[n_q]$所指链表中，使其成为该链表的首结点。(插在链首)
- 活动结束时，返回序列中 删除$d[n_q]$链表的首结点。
7.4 参数传递机制
传值调用 在过程中，参数和局部变量一样可以被赋值，但其结果不影响过程体之外的变量的值。
引用调用 调用过程把实参存储单元的地址（即一个指向实参存储单元的指针）传递给被调用过程的相应形参。 被调用过程执行时，通过形参间接地引用实参。
复制恢复 传值调用和引用调用的一种混合形式。效率高
- 过程调用时，调用过程对实参求值，将实参的右值传递给被调用过程，写入其活动记录的参数域中(copy in)，并记录与形参相应的实参的左值。
- 被调用过程执行时，对形参的操作在自己的活动记录的参数域空间上进行。
- 控制返回时，被调用过程根据所记录的实参的左值把形参的当前右值复制到相应实参的存储空间中(copy out) 。当然，只有具有左值的那些实参的值被复制出来。
传名调用 直接换名字。
中间代码生成
知识点：
- 三地址代码
- 语句的翻译
- 布尔表达式的翻译
- 回填技术
中间代码作为过渡的优点：便于编译程序的建立和移植。
8.1 中间代码形式
8.1.1 图形表示
语法树
dag图
8.1.2 三地址代码
三地址语句的一般形式：x := y op z
- x可以是名字、临时变量
- y、z 可以是名字、常数、或临时变量
- op 代表运算符号，如算数运算符、或逻辑运算符等
- 语句中，最多有三个地址。
- 四元式
- 三元式
- 间接三元式
8.2 赋值语句的翻译
8.2.1 仅涉及简单变量的赋值语句
8.2.2 涉及数组元素的赋值语句
8.2.3 记录结构中域的访问
8.3 布尔表达式的翻译
8.3.1 数值表达式
类似于算术表达式的求值：
- 与或非运算与加法、乘法、负号运算一致；
- 关系表达式有固定的三地址代码形式：
8.3.2 控制流表达式
关心程序应该跳转到的位置。
布尔表达式被翻译为一系列条件转移和无条件转移三地址语句。
继承属性：
- E.true：为真时转移到的三地址语句的标号
- E.false：为假时转移到的三地址语句的标号
短路运算
测试目的：找错 对测试有很大影响：可以控制测试代码的部分
- 黑盒测试：功能测试
- 白盒测试：结构测试
- 条件组合测试：针对短路代码
- E1：真，E2：真
- E1：真，E2：假
- E1：假，E2：真
- E1：假，E2：假
- 条件组合测试：针对短路代码
用控制流表示法翻译布尔表达式时，在一遍扫描中： 当生成某些转移指令时，目标地址可能还不知道
8.3.4 回填技术
- 先产生没有填写目标标号的转移指令；
- 建立一个链表，把转向这个目标的所有转移指令的标号填入该链表；
- 目标地址确定后，再把目标地址填入该链表中记录的所有转移指令中；
- 记录未填地址的语句的地址序号，并标注真假.t / .f；
- 填完以后从链表删除。删除以后对链表进行合并，合并出只有.t / .f 两个表项