期末复习¶

四¶

开作用域与闭作用域¶

• 这里其实就是静态结构嵌套

六¶

• 综合属性：自下而上，从右部到左部
• 继承属性：自上而下，从左部到右部（注意，不一定只有左边的符号参与贡献）

基于树遍历的计算¶

• 想法是显然的：先建树，找出每个节点对应的属性，再找出计算关系即可。
• 最后根据 DAG 求值

S-属性文法¶

• 只有综合属性，每次属性计算发生在归约时
• 因此比较适合自下而上的语义计算

L-属性文法¶

• 深度优先的后序遍历：也是很显然的方式

自上而下的翻译模式¶

• 这也是很显然的，继承属性是进入 A 之前知道的，综合属性是 A 处理完之后知道的

• 这也是显然的，即进入新的 B 时，先计算继承属性作为形参，再通过综合属性作为返回值
• 如例子：

自上而下消除左递归¶

• 其实就是把一个自底向上过程，改为了自顶向下先传递，再从底部综合

翻译模式自下而上¶

• 关键：如何引入空产生式？在哪里？为什么？

• 关于继承属性：

  • 在 LR 分析中，我们希望继承属性是通过栈上的综合属性==直接==得到的
  • 这就要求，用到的综合属性，其在栈上的相对位置要固定

• 比如：

• 为什么会出现 top + 1 ？

  • 归约空产生式，从空变为 M/P，相当于新增了一个栈顶元素

七¶

L-翻译 布尔表达式¶

• 会意即可，相当于：true or false 的跳转标签是继承属性，code 则是综合属性
• 最大的 E 的跳转标签由外层决定，与 bool 关系无关

• 如果含 break，让 break 指向 next 即可：

拉链与代码回填¶

• 想法也是很直观可以理解的

八¶

DL SL 和 display 表¶

• DL：指向调用该过程的最新活动记录（即指向栈中的上一块区域）

• SL：指向直接外层的最新活动记录（指向定义该过程的过程的最新活动记录）

• Display 表：看各个嵌套层的当前过程的活动记录的位置

  • 这里的嵌套指的不是调用的嵌套
  • 指的是定义的嵌套

• 如例子：

• main 是 0 层

• P、S 是 1 层
• Q 是 2 层
• R 是 3 层

• D[i] 存的是第 i 层的最新活动记录的基地址

• 每个活动记录里面保存的 Display 表项：

  • 该过程所占用的原 display 表的值

• 如例子：

• 每次新过程，如果该过程的嵌套深度的对应表中原来就有值

• 则保存这个值，而将表里的值更新为当前过程基地址

• 静态作用域和动态作用域对比：（这两者对代码的解释不同）

• 静态作用域：
  • 找变量看静态结构的上一层，不看调用的上一层
• 动态作用域：
  • 找变量看调用的上一层，而不是静态结构的上一层

九¶

基本块¶

• 这里注意一下块的划分：
  • 这里 3 要分开了，因为 3 是一个入口语句

自然循环¶

到达-定值数据流¶

• 定制点 d：赋值或可能赋值的语句
• d 到达 p：d 可以到 p 且中间未被重新定值

• 其中，GEN 和 KILL 是可以预先算得的
• 初始 IN = 空，OUT = GEN
• 按方差不断迭代即可得到 IN 和 OUT

活跃变量数据流¶

• 这里 LiveUse 是：定值前要引用的变量
• 同理：LiveUse 和 Def 是可以先被求出的
• 初始：LiveIn = LiveUse ，LiveOut = 空

UD 链和 DU 链¶

• 显然的：如果引用前本块有定值，则就是最近的定值点；如果没有，则是 IN 里面的定值点。

• 注意：变量的 DU 链集合是引用点

基本块的 DAG¶

寄存器相干图¶

• 关键：定值点与最近的活跃点，连一条边（不止是：同时活跃点相互连边）