【笔记】编译原理 - note

zhyh's blog / 2023-05-11 / 原文

句型 $\in (V _T \cup V _N) ^ *$，句子 $\in V _T ^ *$
分析树
- 叶结点既可以是非终结符，也可以是终结符。从左到右排列叶节点得到的符号串称为是这棵树的产出或边缘
短语：句型的分析树中的每一棵子树的边缘
直接短语：某个只有父子两代结点的子树的边缘；一定是某产生式的右部
词法分析阶段的错误处理
查找已扫描字符串中最后一个对应于某终态的字符
- 如果找到了，将该字符与其前面的字符识别成一个单词，然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词；
- 如果没找到，则确定出错，采用错误恢复策略
  “恐慌模式(panic mode)”恢复：从剩余输入中不断删除开头字符，直到能够在剩余输入的开头发现一个正确的字符为止
最左推导，即总是替换句型的最左非终结符，最左句型
最右推导——规范推导，最左归约-规范归约，规范句型
S_ 文法，简单的确定性文法，形如：每个产生式的右部都以终结符开始，同一非终结符的各个候选式的首终结符不同，不含 ε 产生式
q_文法，每个产生式的右部或为 ε，或以终结符开始；具有相同左部的产生式有不相交的可选集
串首终结符 FIRST(α)
可以从文法符号串 α 推导出的所有串首终结符（为第一个符号且为终结符）的集合
非终结符的后继符号集 FOLLOW(A)
可能在某个句型中紧跟在非终结符 A 后边的终结符 a 的集合
产生式的可选集 SELECT(A→α)
可以选用产生式 A→α 进行推导时对应的输入符号的集合
LL(1) 文法
当且仅当文法 G 的同一非终结符的各个产生式的可选集互不相交
预测分析法
非递归，初始时栈为 S$]；输入缓冲区 w$
预测分析表：二维表，以当前非终结符和当前输入符号为表项，值为产生式
预测分析中的错误检测和恢复
- 栈顶终结符和当前输入符号不匹配：直接弹出栈顶的终结符
- 栈顶非终结符与当前输入符号不匹配：
  - M[A, a] 是空，忽略输入符号 a
  - M[A, a] 是 synch，弹出栈顶的非终结符 A
\n
最左归约-规范归约，规范句型
LR 文法：最大的、可以构造出相应移入-归约语法分析器的文法类
其中 L 表示对输入进行从左到右扫描、R 表示反向构造最右推导序列；一般 LR 默认指 LR(1)
移入-归约分析，初始时状态栈 [s0，符号栈（也叫分析栈）[$，输入串 w$
- 移入：将当前输入符号移到栈顶
- 归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
- 分析表，考察当前状态栈顶 s，输入缓冲区首字符 a
  - 动作表 ACTION[s, a]，执行移入或归约：
    - 移入 sx：将符号 a、状态 x 压入栈
    - 归约 rx：用第 x 个产生式 A→β 进行归约——同时使状态栈和符号栈的 |β| 个出栈，将 A 压入符号栈，并访问 GOTO
  - 转移表 GOTO[s, A]：将表项的状态压入状态栈
每次归约的符号串（某个产生式的右部）称为“句柄”
（整个串的）规范句型 = 符号栈 + 剩余输入串，也就是一些子树 + 待输入的一些叶子
（而符号栈是已输入字符串的规范句型）
“分析栈不能越过规范句型的句柄”，因为自动机上遇到句柄就得归约了
规范句型的活前缀：不含句柄右侧任意符号的规范句型的前缀
“不含句柄右侧任意符号的规范句型”就是分析栈
也就是分析栈的任意前缀
“LR自动机中从初始状态开始的每一条路径对应一个规范句型活前缀”，好理解的
LR(0)，$A→α⋅$
- A=S′，即此项目是 S′→S⋅，接受：$ACTION[i, \$]=acc$
- 否则，对任意 $a∈V _T∪ \{ \$ \}$ 都写上 $ACTION[i, a]=rj$，j 是 A→α 这个产生式的编号
SLR，$A→α⋅$
- A=S′，...
- 否则，对任意 $a∈ FOLLOW(A)$ 都写上 $ACTION[i, a]=rj$，j 是 A→α 这个产生式的编号
LR(1)
- 称项目 $[A→α⋅Bβ,a]$ 与 $[B→⋅γ,b]$ 等价，若 $B→γ∈P$，且 $b∈FIRST(βa)$
- $[A→α⋅,a]\implies ACTION[i, a]=rj$
LALR
如果除展望符外，两个 LR(1) 项目集是相同的，则称这两个 LR(1) 项目集是同心的
合并同心项，不会产生移进-归约冲突，但可能产生归约-归约冲突
分析能力：LR(0) < SLR < LALR < LR(1)
自动机大小：LR(0) = SLR ≈ LALR < LR(1)
LR 分析中的错误恢复：恐慌模式、短语层次
语法制导定义 SDD，是对 CFG（形如 $A\to \beta$）的推广
- 将文法符号和一个语义属性集合关联
  - 综合属性
    非终结符，子结点或本身
    终结符，可以具有综合属性
  - 继承属性
    非终结符，父结点/兄弟结点或本身
    终结符，没有继承属性
- 产生式和一组语义规则相关联
  语义规则为调用动作的，称为 “副作用”
  依赖图：由语义规则导出，描述分析树中结点的每个属性间依赖关系的有向图
- SDD 的有用子类：S-属性定义 S-SDD；L-属性定义 L-SDD
S-SDD：仅使用综合属性，可以自底向上
L-SDD，若它的每个属性：
- 要么是综合属性
- 要么是继承属性，且继承自父亲/先序兄弟节点/自身
语法制导翻译方案 SDT：产生式右部中嵌入了程序片段（称为语义动作）的 CFG
实现：
- LR 分析（总是归约）+ S-SDD（只继承）
  将每个语义动作都放在产生式的最后
- LL 分析（递归下降分析，可以递归，也可以栈维护非递归）+ L-SDD
LL + L-SDD，自顶向下
- 非递归的预测分析，开同步栈，符号栈初始为 T Tsyn $]
  在符号栈中 A 的底下放一个符号 Asyn，代表 A 的综合属性
  在同步栈的对应位置存储对应的值
  每次出栈前执行动作，将结果的值存到需要其的那些动作的槽里（top±p）
- 递归的预测分析
LR + L-SDD，自底向上
- 和 LL+L-SDD 的 SDT 的区别就是，将其修改成使得所有语义动作都位于产生式末尾（因为总是归约）
  做法：插入 M，M→ε + 末尾动作
声明语句翻译，全局 t, w 记录基础类型，用给数组的框框 []...；
T id;：enter(id.lexeme, T.type, offset), offset += T.width
赋值
lookup(name) 返回 name 对应的地址 addr
newtemp() 生成一个新的临时变量 t，返回 t 的地址
gen(code)
数组引用
L.type：L 做为数组元素的类型，可逐层剥离出嵌套的子类型 .elem
L.offset：指示一个临时变量，该临时变量用于累加公式中的 i×width，从而计算数组元素的偏移量
L.array：初始数组在符号表的地址（可调用 L.array.type.elem 得到第一层内的数组类型），从 id 那直接一路继承上来；用于最后生成语句 gen(L.array '[' L.offset ']' '=' 'E.addr')
控制语句
画出控制流图
newlabel(), label()
为了填写每个 goto 语句的目的地址，在进入 B 或 S 前必须定义好 B.true, B.false, S.next（但是在进入时可能还没有值，所以代码生成完还得回过头填一遍；而回填就是把这个过程也涵盖进去）；选择性定义 B/S.begin（若有自下而上的箭头）
记得控制流中可能需要插入 goto 语句
布尔表达式 B
已有 B.true, B.false，在底层布尔表达式（true, false, 判断式）生成 goto，其他情况继续递归，递归前赋予其 truelist, falselist
停一下，你想想上面的 true/false/next/begin 这些，只保证声明好就递归下放到叶节点生成的 goto，所以不得不生成代码完再填一遍；现在我们考虑从父亲处收集这些在叶节点生成 goto 代码并统一填写——这就是回填
回填，使用 list 从递归的节点中收集待填空的跳转指令
- makelist(i)：i 为某个跳转指令的标号（布尔表达式、控制流的 goto，还是两个地方）
- merge(p1,p2)
- backpatch(p,i)：回填
- nextquad：全局变量，存储下一条生成语句的标号
- 可以插入 M 以存储该处指令标号，有 M→ε
- 可以插入 N 以在该处生成一个跳转指令，有 N→ε
反正，你只要知道回填是从儿子那收集待填跳转指令，就知道该怎么写了
\n
程序每次执行该过程，称为一次“活动”，分配的连续存储区称为“活动记录”
活动记录一般形式（按记录的栈底到栈顶的顺序）
- 实参
- 返回值
- 控制链（“静态链”，存放调用者的 top_sp）
- 访问链（上一级嵌套定义的最近活动记录）
- 保存的机器状态：通常包括返回地址和一些寄存器中的内容（注意返回地址和控制链的 top_sp 区分）
- 局部数据：在该过程中声明的数据
- 临时变量：比如表达式求值过程中产生的临时变量
调用/返回序列
调用序列
- 调用者：修改被调用者：参数；返回地址（程序计数器的值）放入机器状态字段；top_sp 放到控制链；
  然后 top_sp 指向被调用者局部数据开始的位置
- 被调用者：保存寄存器值和其它状态信息
返回序列
- 被调用者：修改自身返回值；使用控制链、机器状态字段中的信息，恢复 top_sp 和其它寄存器；
  跳转到由调用者放在机器状态字段中的返回地址
- 调用者：使用被调用者返回值字段
访问链，指向其直接定义者的、在活动记录栈里最近的活动
Display 表，对每个嵌套深度 i，d[i] 按建立的先后顺序、维护嵌套深度为 i 的过程的活动记录
符号表，组织方式
- 基本属性，直接存放在符号表中
  如种属、类型、地址（偏移地址 offset）、扩展属性指针
- 扩展属性
对于多个过程，分别建立符号表
嵌套定义的，外围过程的符号表里有指向若干内部过程的序列，内部过程有指针指向外围过程
为每个符号表维护表项的宽度之和
/n
基本块划分 + 流图
优化：机器无关/相关——针对中间/目标代码；局部/全局——基本块内/外
- 基本块内优化，DAG，只有计算出口活跃变量的部分有用
  a[j]=y，创建一个 []= 结点，3 个子结点 a,j,y，没有定值变量表，而且杀死所有已经建立的、其值依赖于 a 的结点——不能再获得任何定值变量，因为从现在起 a 里的东西已经不确定了
- 删除公共子表达式、删除无用代码、代码移动、强度削弱
数据流分析
- 到达定值分析
  某个定值语句 d 能不能到达某个基本块 B 的开头：d ∈? IN[B]
  - 正向传函，倒着扫一遍基本块，当前的语句 d:u=∗ 如果还没被杀死，就将 d 加入 gen，然后杀死在场所有 d′:u=∗ 的语句——都将它们加入 kill；当前 d 已被杀死就跳过
  - 前驱取并，去掉自己 kill 掉的再加上 gen
  - 01 串做，做时可以标注一下当前哪个 OUT 变了
  - 引用（的）定值链，ud
    循环不变计算，检测变量是否未经定值就被引用，常量传播
- 活跃变量分析
  某个基本块 B 结尾出去后，能不能到达一个对变量 x 的引用：x ∈? OUT[B]
  - 逆向传函，正着扫一遍，对于当前 a=b+∗，如果 b 没见过，就放入 use；如果 a 没见过，就放入 def；特别地若 a=b，显然是放入 use
  - 后继取并，去掉自己 def 掉的再加上 use
  - 注意从后继来，就是找出边
  - 定值（的）引用链，du
    删除无用赋值，为基本块分配寄存器
- 可用表达式分析
  称某条代码的表达式可用，如果到它的所有来时之路上都计算过这个表达式，且从那时到现在没有对表达式的值进行修改（对表达式变量的定值）
  - 正向传函，初始 e_gen,e_kill 都为空，正着扫一遍：每次看 z=x op y，将 x op y 加入 gen，然后把 z 标注在 kill 上并划掉 gen 里所有带 z 的（可能就把刚加入的 z op y 划掉了），重复下去...扫完后，对于 kill 里标注的每个 z，将所有带 z 的表达式中除了还在 gen 的，都放入 kill
  - 初始除了ENTRY 的 OUT 都为表达式全集
    前驱取交，去掉 e_kill 加上 e_gen
  - 删除全局公共子表达式，复制传播
- 支配结点
  - 正向传函，加上自个就行
  - 前驱取交
  - 识别自然循环，找回边 n→d，d dom n，再反向找所有在 d 之后能到达 u 的
全局优化
- 删除全局公共子表达式
  前置：可用表达式
  对每个可用表达式，往前找到那些相同表达式的代码点，用同一个临时变量记一下，在这里使用它
- 删除复制语句
  前置：可用表达式，定值-引用链（活跃变量）
  站在当前的复制语句 x=y，
  - 往前看：这条复制语句得是可用的
  - 往后看：这个对 x 的定值在之后的所有引用前，有没有把 y 改了（肯定没改 x，不然这个定值在这个引用之前就被杀死了）
  - 都满足的话，du 链的所有对 x 的引用，替换成 y；删去 x=y
- 代码移动
  前置：引用-定值链（到达定值），自然循环
  先找到自然循环
  在循环里头找循环不变计算——通过 ud 链看看这个语句的定值点是不是在循环外头、或者常数；重复做
  代码外提：将这些循环不变计算，移动到前置首节点（需要满足支配、定值、引用条件）
  综上，人工操作可以：
  - 这个循环内，首先找的语句所属的块，它得是所有出口节点的必经之路（支配条件）；
  - 然后检测这个块里头的那个语句 x=∗：∗ 只能出现在循环外头或者为常数（循环不变计算，可能连锁反应）
  - x 不能在循环内的其他地方被定值（定值条件）
  - x=∗ 得是循环里头所有对 x 的引用的必经之路（引用条件）
- 作用于归纳变量的强度削弱
  前置：循环不变计算信息（到达定值+自然循环），到达定值
  - 检测归纳变量
    - 基础归纳变量看 j=j+* 的 ud 链——在循环里头除了它自己就没有定值 j，而且 * 是循环不变计算
    - 归纳变量，看 ud 链，在循环里头就定值了一次，而且是从基础归纳变量来的，k(j, c, d)
  - 强度削弱
    根据归纳变量信息，新建临时变量代替，这个你看图片吧懒得描述了
- 归纳变量删除
  前置：归纳变量（前面的一堆东西）+ 活跃变量
  归纳变量那边可能替换出复制语句，那就考虑可能复制语句删除
  尽量用临时变量代替，包括测试语句；如果基础归纳变量不活跃了，扔掉