2022秋季学期 编译原理 期末复习笔记

编译/assets/2022Fall-compile-final

算法集合

• 自上而下LL
  • 针对所有，求first · 范围：初始化 放空 分割 产生式检查
  • 针对所有，求follow 初始化 右端A后缀first 可选左端follow
  • 针对所有产生式，求PS预测集合 first右+可选follow左
  • 消除直接、间接左递归（排序、对每个终结符替代比他序号小的左递归用产生式）
  • 消除左公因子
  • 根据预测集合判断是否是LL1文法
  • 递归下降 ParseX
  • 表驱动 借助栈，开口向左的栈，初始化放#。根据栈顶和向前查看来不断推导
  • 错误处理——表驱动：跳过直到同步符号即followA，检测firstA出现的时候恢复分析A
  • 递归下降：补救集合？？？
• 符号表：哈希；全局符号表；作用域+单独符号表…
• 自下而上LR
  • 短语、直接短语和句柄（rm），活前缀（句柄之前的所有前缀）
  • 向右开口的栈（状态栈+符号栈），输入序列#，分析表，（分析引擎）
  • 注意reduce的时候，弹出整个一层然后压入符号再压入状态。即被弹出的老状态无用。
  • LR0
    • 增广文法 项目（归约、移进、接受、待归）
    • 构造CLOSURE
    • 构造LR0 FSM，通过转移边
    • 构造分析表
    • ——归约就是一个归约，不含移进和其他归约
  • SLR1
    • 解决一部分冲突，通过归约后VN的Follow来区分，移进就看移进什么东西，不相交就好
  • LR1
    • 新项目 = 项目+搜索符
    • 构造CLOSURE：搜索符的传递，是βa的first
    • 构造LR1 FSM 通过转移边，初始化的搜索符为#
    • 构造分析表，搜索符只在归约项目中使用
  • LALR1
    • 没那么复杂，合并同芯状态
    • 合并同芯状态的后继状态也同芯…合并之
  • 二义文法限制给定优先级比较简单，如算符匹配
  • 错误处理技巧
• 语义计算
  • 属性文法：语义规则都在最后
    • 树遍历
      • 构造分析树
      • 标记节点——节点是属性
      • 标记依赖关系
      • 拓扑排序
      • 计算标注
    • 借助语法分析的单遍
      • S属性文法：自下而上，在LR分析中增加语义栈，根据栈顶的几个元素计算。注意lexval
      • L属性文法：要求综合属性+只使用产生式左边的继承属性。
        • 深度后续遍历即可，dfs每个节点都先继承给孩子属性。然后访问每一个孩子。最后再从计算完的孩子身上获得综合属性。
  • 翻译模式：语义规则在符号前，综合在P后。都是单遍
    • 做限制：
      • 类似S 全综合
      • 类似L 继承属性使用的只能是左边的东西，且如果用左端则只能用继承。
    • 自上而下：熟悉的parseX，通过参数传递继承属性，返回值传递综合属性。每个Parse内就按照产生式往下写就好。记得给好继承，保存好综合。
      • 消除左递归，消除的同时需要变换语义规则集。
    • 自下而上：
      • 首先消除除了最后之外的奇奇怪怪东西，包括数字赋值，print，以及复杂函数。通过引入变量把他们都换成简单复写
      • 然后在转化成栈形式，只转化句子末尾的综合属性。如果需要访问继承属性，就一直向前倒到综合属性。不一致就引入调整到一致。
      • 注意数栈的时候的推空式，以及跨箭头top不变。
• 静态语义检查
• 中间代码生成
  • 偏移量标注：width子树规模，综合上去；offset从头部继承下来；在底部声明的时候使用enter函数在符号表中标注偏移。函数局部标注也差不多，注意参数也占位置。
  • 内情向量
    • 静态数组放在符号表：每个维度上下界；类型；首地址；维数；C；
    • 动态数组放在运行时组织栈|堆
    • 地址计算：行优先时，从第一维开始往后乘…索引减去下标，乘后续维度的空间。addr - C + V
  • TAC生成“声明数组”、翻译各种语句等等。
    • 大致过程：place申请Temp；计算子语句；code = 子code||gen（某句Temp）
    • 翻译TAC时候，本句Code可以并上需要的子句code
    • place是存储位置
    • arglist 实参列表 makelist创建实参地址节点 append往这个列表中添加节点
  • 布尔表达式翻译
    • 直接求值
      • 逻辑运算：先取子code，然后放上去
      • 关系比较：用0和1表示取值，用goto nextstat+x表达跳几条语句
    • 控制流语句中布尔的语义——短路
      • 生成目标：按照or and等等往下顺序写，如果随时能判断整个正误就直接跳转。
      • 相当于每个E都有true和false的继承属性。需要我们得到子表达式xxx就能马上判断父亲的正误。随时能判断就gengoto。
      • rop：两句，都是跳转
      • 且：如果E1错就赶紧跳E错。所以E1错=E错，E1对=newlabel；E2错也可以跳E错，E2对才是E对。code部分，先E1，这样可能短路跳走了，然后E1truelabel，然后E2一定跳走
      • 非：全相反
      • 括号：不变
  • 条件语句翻译
    • 先条件code，再label，再中间code，再label…
  • 顺序复合
    • 用到next属性都表示整块紧邻的下一句
  • break continue
    • 能产生break的地方，特意标注break。比如while中的内部S…
• 运行存储组织
  • 默认float8
  • 栈结构
    • 临时单元
    • 动态数组
    • 动态数组（动态数组的存储位置，比如float的话就是2N的空间）
    • 固定局部数据（动态数组：底下放内情向量4B，然后addr ptr4B指向上面的动态区）
    • 过程参数（先参数个数）
    • （reg保存）
    • 控制数据（SL DL RA ）
    • （返回值）
  • 嵌套过程语言，区别于函数递归。
  • 动态链：一定指向caller即上一层
  • 静态链：指向嵌套过程的直接外层
  • Display
    • 保存全部在栈帧中
    • 保存被自己替换的那条
• 基本块流图和循环
  • 划分基本块
    • 三入三出条件
  • 支配（必过） 回边——循环
• 数据流分析
  • 经典方程
  • 到达定值分析，方程
    • 过程
  • 活跃变量分析，方程
    • 标记
  • UD和DU链
  • 待用信息和活跃信息
• DAG局部优化
  • 三种子图
  • 重复利用，可确定常数直接创建，不知道初值需要标0
  • 拓扑排序翻译
• 寄存器分配
  • Ershov 和 Sethi：针对表达式，从底层往上标记
  • 相干图
    • 变量（伪寄存器）为节点
    • 定值点紧随的活跃变量集合，和定值连线
  • K着色…

Lec0 考试信息

a）语法分析 + 词法分析 + 编译基础知识 40%左右
（slide01 + slide02 + slide 03 + slide05）

​ b）语法制导的语义计算 + 静态语义分析与中间代码生成 30%左右
​ （slide 06 + slide07）

​ a）和 b）共计70%

​ c）符号表+运行时存贮组织 10~15%
​ （slide04 + slide08）

​ d）代码生成 + 代码优化 15~20%
​ （slide09）

​ c）和 d）共计30%

2）不出题范围

​ a）Slide或Lecture文件中所有标有“选讲”的内容

​ b）Lecture09 中 3.1, 3.3 和 3.4

​ c）Lecture09 中 4.1 和 4.2

Lec1

分析，综合 两大阶段

编程语言范型

命令语言 描述问题如何实现 有状态并改变

陈述声明语言 描述问题做什么，没有状态

OO

并发、分布式语言

同步、数据库、脚本

• 前端 分析，首次生成中间代码
• 中端 中间代码生成优化
• 后端 综合，生成优化目标代码

字符流-单词流-AST语法分析树-中间代码1~n-目标代码和优化

词法、语法、语义，中间代码生成与优化，目标代码生成与优化

辅助以符号表管理和错误处理

pass|Phase 从头到尾扫描一遍，单或多遍，常有逻辑先后

有Interpreter 不产生目标程序，不区别翻译执行，直接翻译完就执行，解释程序一直守候，直接出结果，用于实现虚拟机。区别于编译程序。

预处理程序，处理掉扩展信息再送进编译程序。

装入与链接程序，用来对可重定向的机器语言程序修改，合并多个并加入库，以产生最终可执行的低级程序。

调试程序，接受编译出的调试信息以及程序，来给出更多运行时的信息

T型图

用底下的程序把左编译成右。

本地编译器指的是，用M把A编译成M

交叉编译器，用M把L编译成N

如果想用已有语言A实现新语言B，则相当于已有M下A编M的编译器。我需要拿A设计一个把B编译成M的编译器，并编译成M。就得到了在M下把B编译成M的编译器。

A的L语言移植到B机器，需要用L写L转B。然后来回编译

用编译器编译就是把T放到右下

Lect2 词法分析

识别单词 返回Token流（Token和属性值），或者错误信息。

经常由语法分析程序调用，不断获取下一个单词记录

单词描述工具

扩展巴克斯EBNF 类似正规表达式的形式表示单词类别

用::= {表示0个及以上个} <非终结符>

{}0或多次 []0或一次

状态转移|有限状态机 来表示词法分析过程，结束态是识别完当前单词给出的类别。

正规表达式 有限状态机

标识符vs保留字，保留字表。

字符退还 读取<下一个不是=，则一定是小于号单词，但是下一个已经读取的要退还。

• 每一类词法单元都对应正规表达式
• 转换成有限自动机，比如Thompson构造成ε-NFA
• 增加一个开始状态，转移到每一个初态
• 可以使用子集构造法得到确定化的DFA
• 可能会最小化，等价获得小状态DFA
• 如果没有连一起的自动机，则分别依次模拟运行每一个词法单元的自动机。

Lect3 自顶向下语法分析 91

基本思想

识别和解析，对于任意CFG和句子，判断这句是否在语言中。如果在给出分析树或者最左推导，否则报错。

从文法开始符号S出发来推导，每一步都获得句型，最终句子正好是终结符串。即每一步都是用产生式换一个非终结符。

非确定 非终结符的不确定 所用产生式的不确定

改进 一定替换最左边的非终结符，产生式不确定，则一定产生最左推导。

更加确定 产生式选择是确定的，所以无回溯。怎么选？向前查看lookahead一定量的单词。这样很爽但对文法有限制。

限制文法

• 不含左递归

  • 直接左递归 P-P1|2

    • 最后最左边肯定是2，引入P-2Q Q-1Q|ε

      

  • 间接左递归 P-Aa A-Pb

    • 

• 不含左公因子？？ S-aAb|aAc 或者A-a|aA

  • 引入新的VT替换掉公因子右边

不含左递归和左公因子也不一定是LL1文法捏

但是不是LL1如果有有限产生式也可以使用LL1来分析

LL1文法

左到右扫描单词，最左推导，向前查看1个即可

First集合

first(某短语) = 这个短语能推出的所有最左终结符，包括ε

计算First

• 范围是所有产生式右端的所有后缀，ε和单字符。

• 包括ε的所有终结符都放上自己。

• LOOP

  • 【放空】非终结符可以推ε，把ε放入。

  • 【分割】对所有后缀（两个以上字符）的集合，考虑

    其实是找第一个不含空的，并到它。如果都含就全并加上ε

    • 存在一个i位置的first不含ε，但它之前字符的first都含ε。则这个后缀的first为1~i的广义并去掉ε。
    • 否则，如果所有字符first都含ε，直接广义并。

  • 【产生式检查】对所有产生式左边的VT，都加入右边整个的first。

Follow集合

Follow（非终结符A）= 合法句型中所有可能跟在这个A后面的非终结符或者结束符#

计算

• S放入#
• LOOP
  • 【检查尾缀，放入first，可能放入左边的Follow】对所有产生式右端中的每一个VN B。把他后面后缀部分的First集合去ε之后加入FollowB。如果有空，就把产生式左边的Follow加入

预测集合

PS（产生式P）

• 如果ε不在右端的first，则就是first
• 否则是first去空加上follow

LL1判断

每个非终结符的任何两个不同产生式，其预测集合不相交。

LL1分析

递归下降LL1

每个VT对应子程序（函数），根据语法描述来明确：根据下一个符号选择产生式处理。产生式处理就是非终结符调用子程序，终结符读入字符判断合规与否。

void parseS

{

如果需要查看则看lookahead，可以switch来选择产生式，根据PS集合来判断

matchtoken表示终结符

ParseXXX表示非终结符

}

表驱动

预测分析表+下推栈

分析表为VT*VN，即非终结符+向前查看（PS）得到产生式右端。

• 开始时候栈中有#
• S入栈，S#
• 终结符则读入消除
• 非终结符则查表对应产生式，换成产生式

推广

大胆并First…

错误处理

表驱动 Aa查表没有产生式可用，跳过输入串一些符号直到同步符号为之。

• FollowA中所有作为A的同步符号，遇到了之后弹出A，大概表示A已经过去
• 把FirstA加入A的同步符号集合，出现时候根据A恢复分析

递归下降

进入parse的时候检查下lookahead，补救集合定义为Begin∪End

如果没有合法的非终结符，则跳过所有单词直到合法符号或者EndSym

出parse的时候再检查下matchtoken，如果不在endsym，就跳过等待开始符号

LLk文法结论

• 可判定：CFG是不是LLK文法；两个LLK是否相等
• 不可判定：一个CFG是否存在K，使得LLK；或者说存在等价的LLK
• LLK无二义，不存在左递归
• 不含ε产生式的话，LLK一定在LLk+1里面

Lect4 符号表 17 7

作用

静态语义检查、中间代码生成

常见属性

名、类别和类型、储存类别和分配、作用域、其他（内情、结构成员、形参）

实现

线性表、有序表、二叉搜索树、Hash

全局符号表+作用域各自符号表

作用域和可见性

当前作用域，开闭。

某一点的开作用域中声明的名字才可访问。

单符号表：一个大符号表，所有嵌套作用域共用

多符号表：作用域栈，每个作用域维护自己的符号表 在

Lect5 自底向上语法分析 113 1

自底向上分析思想

识别与解析

自顶向下是从S开始，相当于推导分析。而自底向上就是从终结符串开始规约到S，P右到P左，找不到就回退。

改进 选择可归约串 归约

减少回溯，句型来说，可规约串一定是短语

从S开始推导的过程中，任何一个非终结符A能产生的串β就是短语。是句型αβγ相对于A的短语。

在树里看，就是以非终结符为节点下面的东西随便拼出来就好。

直接短语 短语里能被一步推出的。就是所有产生式的右端？

千万注意空字符。特殊判断一下这个句型里有没有空字符存在，是否属于直接短语。

句柄 S最右推导出（右句型）αAw且A一步到β。就是说最右推导到这里右边已经推出一些终结符了，下一个马上该一步可归约的串。

短语是可归约性串，不一定一步不一定在哪

直接短语是一步可规约串，不一定在哪

句柄是在最靠左的一步可规约串，因为是最左推导中出现的A

句柄不一定唯一，可能有多个（二义文法）

移进-规约分析

功能强大，推导的时候只观察可推导出的输入串的部分，归约时候输入全部出现。

利于出错处理：输入符号查看后移进

构造复杂

输入序列#+下推分析栈+有限状态引擎+分析表，对应rm推导（规范推导）

根据引擎状态、下推栈内容、剩余序列来确定动作和新状态

reduce 归约 shift 移进 error错误 accept成功

移进归约冲突

不确定移动还是归约

归约归约冲突

多于一个短语可以归约

借助分析表查询，LR分析表or算符优先分析表

LR分析

基础

从左到右扫描，最右推导。以下四种共享分析表。

分析栈中存在的是各种状态。

分析表ACTION表是横坐标是当前输入串，纵坐标当前栈顶状态。表内有s r acc，由栈顶和输入串找动作。

不带符号栈

有移进新状态和归约并转到两种操作。

移进新状态就是把状态压入栈顶。

归约并转到就是输入串消除一部分然后根据得到的非终结符替换状态。

带符号栈

移入的时候把符号也移入

归约的时候弹出几个符号和状态

LR0

向前查看0个

增广文法

增加一个开始符号的开始符号。

活前缀

β是右句型的句柄，则αβ的所有前缀（包括epsilon）都是G的活前缀。

大概是在最左归约句型的句柄（下一步要被归约的部分），前面连起来的部分就是活前缀。即最左归约的时候所有不要被归约的前面的东西？

增广文法的活前缀 S 是 G’ 的活前缀

活前缀一定是右句型的前缀且不超过句柄。

活前缀含有句柄的所有符号：产生式右部完全到栈顶

一部分符号：右子部到了，期待左子部

没有，期待全部右部

LR0 FSM

任何CFG都对应一个，由增广构造。看做一个字母表的DFA

是特殊的LR0项目（产生式右边加. ，标志着已经分析过的串和产生式匹配的位置）集，分为

每个状态都是项目集的闭包CLOSURE，计算CLOSURE I

• 每一个J中的待约项目和B的产生式，把B的产生式加进来并把点放在最左边。
• 循环直到没有新项目

构造方法

• 初态为增广CLOSURE（{S’ -> .S}）
• 状态转移函数为 GO(状态I，符号X) = CLOSURE J，J是I的状态中走一个X。即从初态0开始，尝试把里面每个状态都往后走来构造新的闭包状态。值得一提的是走的一样的符号状态算一起的。

这个FSM是根据VTVN转移的自动机，每个状态都是终态。

这个DFA的语言是G’所有活前缀的集合。 即通过构造增广文法的FSM，找到了G’的所有活前缀的语言。所以我们不会错过任何最右推导。

增广文法的每个活前缀都对应其中的一个状态，从初态开始就好。

从这个FSM构造LR0分析表

• 所有状态即为栈顶的状态，作为纵坐标放在左边。所有字符（包括#）放在上面。
• 根据项目的不同标记字符即可
  • 先在增广接受项目的状态上标注#acc
  • 然后根据每个状态的转移边标记s，根据归约项目把所有VT标记r，这样归约的状态相当于不查看无脑归约。
  • 每一格子动作都唯一的就是LR0文法，其每个状态都：
    • 不同时含有归约和移进，即.a和x.不同时出现——移进归约冲突
    • 最多有一个归约——归约归约冲突

SLR1

FSM中有状态有归约同时还有移进。即不止含有一个点在最后的状态。

向前查看，根据下一个输入符号是否是归约后VN的follow来解决冲突。

归约归约：所有归约后VT的follow不相交即可。

移进归约：归约VTFollow和移进符号集不相交即可。

修改为，对所有含有归约项目的状态。求出Follow后只在follow内标归约即可。

LR1

SLR不能解决的，移进归约冲突。只考虑了归约VT的follow，也应该考虑是否是句柄的Follow。

修改项目格式，增加向前搜索符 表示产生式右端完整匹配后允许在余留符号串中的下一个终结符或者#。 用逗号分隔，

这样的归约项目，只有后面是a才能归约，相当于进一步强化条件缩小可归约范围。

LR1FSM

1. 闭包构造
   1. 闭包补全中，新加入的产生式的搜索符为First βa。即老产生式后面东西的first集。
2. 状态转移构造
   1. 开始状态为S‘到S，搜索符号是#。
   2. 状态转移方法不变。
3. 构造分析表
   1. 注意向前搜索符只在归约的时候用。

LALR1

LookAhead LR1

合并LR1中的同芯状态，得到和LR0FSM相同的状态，但保留更强的能力。芯指的是不包含向前搜索符的部分。

合并同芯状态后如果没有归约-归约冲突，就是LALR1文法。只需检查新合并状态即可。

• 构造LR1FSM
• 合并同芯，搜索符号用斜杠/合并
• 合并之后的GO后继，也把原来的后继状态合并。

二义文法在LR分析

二义文法一定不是LR文法，但是可能人为限定之后相当高效。

在一些冲突状态中，人为规定优先级

左结合的相同符号，优先归约

不同符号，优先级高的先归约，优先级低的等待高的移进。

LR分析出错处理

根据堆栈状态和输入符号设置报错信息。恢复措施？

应急恢复：从符号栈和剩下的输入前端找一块能被某个VN最右推导出来的句型，且VN的follow包含输入符号串后面的符号。然后符号栈强行归约换成VN，状态栈弹出一定状态后根据归约的VN GOTO。

即兴恢复：对于每个error都确定场景。。

比如多了个右括号，没有左括号可以匹配了，就删了它

Lect6 语法制导的语义计算 81 2

语义计算：语义检查，中间代码生成等

属性文法

在CFG上扩展：文法符号可以有属性Attr，产生式有语义动作，是语义规则的集合。

常见动作，赋值:= ，特定语义函数，可以很灵活

继承和综合

综合|继承：自底向上传递，被赋值的属性属于产生式左边的VNA还是右边的符号。

综合属性：可以自底向上后序遍历，得到求值过程。

继承属性：同时存在继承和综合属性的话，需要深度优先遍历？反复上下？自下而上综合，自上而下继承，可能多变和多遍。。。

属性文法的语义计算——树遍历

• 构造语法分析树
• 依赖图
  • 对树里每个节点的属性都建立一个节点。如果有非赋值的函数，但是也有依赖的属性，则也建立虚节点。
  • 根据依赖关系标记有向边，前驱为先计算的值。
• 无圈图的拓扑排序来遍历分析树，计算所有属性
  • 拓扑排序：取绝对前驱进行排序…
  • 标注|修饰 来表示计算结果

有圈不可这么算，不是良定义（规则集合能为所有分析树中的属性集确定唯一的值集）

属性文法的语义计算——单遍，语法分析的同时

S属性文法——只包含综合属性

自下而上，LR分析正好也是，扩展分析栈的域（语义栈来存放综合属性）计算综合属性正好就是每一步归约之前

状态、符号和语义栈。计算的时候靠栈顶计算即可。

注意有些lexval是自带的，压入栈的时候就带着了，是lex词法的时候准备好的。

L属性文法——可综合可继承

右边文法符号属性的计算只取决于左边文法符号的属性，不依赖其他。

左边属性当然是综合。即要么综合，继承就只继承VNA

自上而下 深度优先后序遍历的方法，其实是先深搜到底，把继承属性传递下去，再自底向上计算综合属性。

对每个节点而言，先传给孩子继承属性并深度访问孩子，最后通过孩子综合自己。一定注意递归返回的时候的综合计算。

procedure dfvisit (Node n)

for m in n.children 左到右:

​ calc m继承属性

​ visit m

calc n综合属性

翻译模式的语义计算

语法制导语义计算的另一种描述，类似属性文法但是{}语义规则集出现在任何地方。显示表达动作和运算次序。

必须受限 才能保证访问的时候存在

类似S属性文法

仅需要综合的翻译模式 放在右端末尾即可

类似L属性文法

1. 右端符号的继承属性计算位于该符号之前——所以压入的时候一定计算完成
2. 继承属性的动作不访问右边符号的属性，只依赖左边（如果用P左的VN属性只能用其继承，不能用其综合）。——所以要压入自己的时候，使用的东西都已经在了。
3. 左边综合属性放在最后，大家都算完了之后，放在产生式尾部。

单遍——自上而下的预测分析

经典的ParseX模式，参数是继承属性，返回值为其综合值。

函数中按照查看来选择产生式，根据产生式慢慢parse，产生式里面说白了就是给他继承属性，保存好他的综合属性。

• 对于终结符，保存（绑定）其综合属性，调用matchtoken和nexttoken
• 对于非终结符，把他要的东西给他去parse并保存综合属性

如何在带有语义规则时候消除左递归？

原来：从下往上套

现在：从上往下套，从下往上传

用R.i一步步嵌套继承下来，最后翻转成综合属性R.s，一步步综合上去。

原来最后一步的综合，变成第一步的继承。

原来左递归的综合，变成右递归的继承。

最后的戛然而止，把继承转换为综合开始上传。

单遍——自下而上的移进归约分析

1. 去掉中间的语义动作——除了复写规则以外的语义规则都在P的末端，方便计算综合属性。

   1. 单纯函数，没有保存值。——引入新VN A->ε，A代替原来的这个函数，print函数放在A后面。
   2. （不急）保存值了——引入新VN A->ε，A代替原来的这个函数，函数放在A后面。增加一些复写规则（单纯复制值）。

2. 分析栈继承属性访问和模拟求值

   1. 指的是所有继承属性的访问，在任何位置。

   2. 继承属性是简单复写，且使用P右端前面的综合属性是OK的。

   3. 继承属性访问通过已有符号的综合属性间接进行（往前倒，总能找到但是可能不唯一），保证总可以通过某个符号的综合属性来体现

   4. 常常增加新的符号和规则来达到目的——针对不唯一情况

      1. 引入新推空VN，来把位置造到相对栈顶相同。把前面有用的值继承下来，然后综合上去。

         

      2. 非简单复写，如1.2中所述。把需要的参数继承下来，在推空计算中综合后，给到后面的继承。

3. 用综合属性代替继承属性

4. 把print和单独赋值的继承单拿出来，即不是两边有数的。

5. 复杂函数单拿出来做成简单复写——中间的语义规则全是简单复写

6. 在翻译成栈语言的过程中，只管综合而忽略其他。综合属性放在左端位置，访问的属性一直向前倒直到综合，如果不一致访问，就做成唯一的。

注意空字符的top位置。

注意往前数top的时候，箭头是不减一的。

有时候，自己想用的属性不在自己的子树里，就没法综合。可能还要用后面的继承。试试变换等价文法，把这些东西放到自己的子树里。。。

Lect7 静态语义分析与中间代码生成 66 2

静态语义分析

静态检查：类型；作用域；控制流；唯一性；上下文相关性

类型检查

借助翻译模式，将类型表达式作为属性赋给程序部分。

大概是，在最底层通过lex确认字面值和type类型。然后需要赋值的语句进行检查。利用子节点的ok或者指定类型来判断合法与否。

typeerr。变量一直标记type。

声明语句需要addtype(id.entry, T.type)，即添加符号表。ident也可以lookuptype来查找类型。Expression是带着类型属性的。

Call则要检查参数数量、类型是否一直。所以para里面是ok而不是具体type。

Statement中 Stype多为ok，由下层s和E的合法得到。

• 检查break和continue在内部：在非循环的时候，S传承inloop或者初始化0.循环的inloop为 1.在break中检查S是不是inloop。相当于继承属性

中间代码生成

利于重定向，缩小跨度，利于优化 AST也是中间代码

有向无圈DAG 只考虑计算，把AST分析树中相同结构子树合并

语法制导AST

采用产生式时，构造VN节点，同时VT节点也构造好。

offset：存储区变量偏移地址

width 占用字节数

enter(id.name, Decl.offset) 符号表中id的偏移量设置为..

保存偏移信息

全局空间：P在不断生成D和F。每个东西有width和offset参数。F不占空间，offset是继承属性，width是综合属性。

所以width从声明底层T D获取标注好之后一直向上传递，则P的width就是自己这课子树的整个width字数规模。一直向上综合。

然后通过继承属性向下分配偏移，继承就好了。右P偏移为父亲加左孩子偏移

Lect8 运行时存储组织 43 3

基本类型：char1 integer4 float8 boolean1 pointer4

array struct object

表达式计算 栈区or专门运算数栈

低地址：保留——code——静态数据（Initdata、bss0）——共享库——堆++ ++栈——保留——OS

静态分配

编译可确定大小，有些语言只支持这样，如static const global

栈分配

递归、活动记录（栈帧）

frame pointer指向帧底（高） sp指向栈顶（低）

offset以word为单位

• 临时单元
• 动态数组（动态数组的存储位置，比如float的话就是2N的空间）
• 固定局部数据（动态数组：底下放内情向量4B，然后addr ptr4B指向上面的动态区）
• 过程参数（先参数个数）
• （reg保存）
• 控制数据（SL DL RA ）
• （返回值）

堆分配

不限时间次序，需要显式释放delete new，用户清理，野指针

java隐释放，用户不清理

分配算法：最佳适应、最先适应、循环最先、碎片整理

嵌套过程语言的栈分配

解决对非局部量的引用、存取

注意区别于函数递归，嵌套可以访问外层的活动记录。而R call R后并不算嵌套，还是同一空间

解决：Display表+活动记录静态链

链都指向底，毕竟是base+offset模式

动态链DL

指向调用该过程前的最新活动记录地址，就是caller

静态链SL

指向静态直接外层（能访问外层数据来说，有过程嵌套语言）最新活动记录地址，用来访问非局部数据,在动态链底下

（全局）Display表

嵌套层活动记录在运行栈上的基地址，主层次为0，当前层次为K，display有K+1单元。

1. 在每个活动记录存入完整表，每次call时候从caller抄几个再加自己
2. 存一个表项即保存被替换的Dn。在静态存储or专用reg维护全局display表
3. 用静态链，指向自己的直接外过程。更容易实现，但是效率低

对于动态块的非局部量 1要么类似函数单独有活动记录 2单个活动记录内随时扔，作用域结束即无用可覆盖。

动态作用域 变量被认为是最近的调用中声明的，类似动态链的效果。之前有就行。

Lect9 目标代码生成和优化 70 3

独立于不断变化的主过程，从TAC开始有流图并不断改进和优化

基本块 流图 循环

基本块

顺序执行的语句序列，只有一个出入口，只有入口label和出口转移or停止

入口：程序第一句or转移的目标句or条件转移紧挨着的

划分基本块

• 找到每个入口
• 根据入口构造：从入口到下一入口or转移or停
• 没在基本块的是无法到达的

流图：CFG，基本块为节点，连线条件：

1 条件转移连两条线

2 转移连一条线

3 顺序出口连一条线

循环

支配 首节点到n的任意通路都过m，则m支配n。m dom n，domn = 所有支配节点，即所有必过点。

回边 d dom n但是n指向d。我可以回到我的必经之路。

（自然）循环 回边两端+能够不过d到n的节点。显然d可以到循环的任何点——直观理解，如果这些点不能由d到达，则d不是domn了

数据流分析基础

典型方程

out = gen∪（in - kill）

出口信息 = 内部新生信息+（进来的信息-已死亡信息）

到达-定值分析

定值语句，可能给A赋值

定值点到达：流图中从定值点d有路径到p且过程中没有被重新定值

outB = genB ∪ (inB - killB), inB = ∪outb

1. gen是定值且能到出口的所有定值点

2. kill B B外能到B入口，但是定值变量在B内被重新定值

3. in为所有前驱out信息的并

算法

• 标注gen，out=gen
• 标注kill：找定值变量的其他定值点，看看那个能“到达”此块，即中间没有被kill。
• 一直循环到不变
  • 从1开始对节点
  • newin = 前驱out，如果和老in不一样
    • 改变，更新老in
    • 更新out = gen+in-kill

活跃变量分析

活跃变量——从某点p开始后面用过A在p的值，A在p是活跃的。如果存在路径在变量被重新定值之前还要被引用

方程：livein = liveuse用的前面的 ∪ (liveout - def)，out = 后继In的并

其实是从后向前，入口活跃 = 用了的+（出口活跃-定值且之前没被用）

• 标注use，in = use
• 标注def，定值且之前没被引用
• 一直循环到不变，从1开始对节点
  • newout = 后继in
  • 如果不同，则更新newout；按照方程更新in

UD链和DU链

ud：u的全部d点。借助到达-定值：本块自己有定值orIN中的所有A的定值

DU：D的所有U点，那就是？？

待用信息：D的待用信息，DU链最近引用点

活跃信息

基本块的DAG表示 局部优化

有向无圈图

叶节点是变量名或者常数，x0代表x初值

内部节点是运算符号

只考虑赋值 单双目运算三种子图

画图就好

• 可确定的常数，就直接写成新节点赋值
• 没被赋值直接使用的，假设初值为A0
• 最后拓扑排序，写出优化代码

寄存器分配

Ershov数——SethiUllman

表达式求值，从底层开始，孩子相等加一，孩子不等取大？ 写汇编

图着色分配

1. 假定无限reg，完成指令选择和生成
2. 物理寄存器指派到伪寄存器。不足时伪寄存器泄露到内存，尽量减少

寄存器相干图

伪寄存器（变量）为节点

如果节点在程序某点被定义，而另一个节点在紧靠该定值之后的点是活跃的，则连线？

即，定值之后活跃的所有变量，连接这个节点。需要知道每句之间的活跃变量。

着色 启发算法

选一个颜色数k，一个一个节点删除度数小于k的节点即可。