期末开卷笔记

编译原理 期末开卷笔记

第一部分 基础知识

词法分析

1.【题型】构造最小化DFA
·第一步：根据Thompson法则，构造NFA。
·第二步：构造等价DFA，具体方法是：先找初始状态的\(\epsilon\)-闭包，再依次找各个\(\epsilon\)-闭包接受不同字符输入时，进入的新状态的\(\epsilon\)-闭包，确定各个\(\epsilon\)-闭包的转化关系。
·第三步：DFA最小化。
2.DFA最小化方法：状态集合细分法。
·首先，将所有状态分成两个集合：接受状态集合、非接受状态集合。
·然后，针对每个集合，分别使用字符表中各个字符\(\alpha \in \Sigma\)尝试对每个集合进行细分。
·直到每个集合均无法被任一字符继续细分，则得到的每个状态集合就对应于一个equivalence class，完成了最小化DFA的状态寻找。

语法分析

一、上下文无关文法

1.自顶向下分析：\(S \Rightarrow^* w\)
·两个选择：替换当前句型中的哪个非终结符、用该非终结符的哪个产生式进行替换。
·最左推导：总是选择每个句型的最左非终结符进行替换；与最右归约相对应。
·最右推导：总是选择每个句型的最右非终结符进行替换；与最左归约相对应。
·自底向上分析总是采用最左归约；自顶向下语法分析采用的是最左推导。
2.歧义文法及其解决方案
·歧义文法：不同语法分析树对应于同一个token序列，但不同语法分析树含义不同（如：符号优先级不同）。
·符号优先级：在语法分析树中，距离树根越远的操作优先级越高。
·解决方案：改造文法/声明优先级（实际做法，不降低文法可读性）。

二、递归向下分析法

1.定义：由一组过程组成，每个过程对应于一个非终结符及其所有产生式。
2.预测分析法与递归下降分析法
·预测分析法：向前看固定个数的符号，选择正确的产生式；是递归下降分析法的特例。
·预测分析法确定、无需回溯；递归下降分析法可能需要回溯。
·向前看\(k\)个输入符号的分析法，称为\(LL(k)\)分析法。

三、文法转换

1.回溯问题及其解决方案
·回溯问题：同一非终结符的多个产生式存在共同前缀，则导致回溯问题。
·解决方案：尽可能延迟决策时间（即：左公因子提取），如\(S \rightarrow aA | aB\)改为\(S \rightarrow aS', S' \rightarrow A | B\)。
2.左递归问题及其解决方案
·直接左递归问题：含有\(A \rightarrow Aw\)形式的产生式，即为直接左递归。
·间接左递归问题：经\(\geq 2\)步的推导，产生终结符本身，即为间接左递归。
·直接左递归消除：原始形式\(A \rightarrow A\alpha_1 | A\alpha_2 | \cdots | A\alpha_n | \beta_1 | \cdots | \beta_m\)改为\(A \rightarrow \beta _1A'|\beta_2 A'| \cdots \beta_mA', A'\rightarrow \alpha_1A'|\alpha_2A'|\cdots|\alpha_nA' | \epsilon\)
·间接左递归消除：首先将间接左递归替换为直接左递归，再消除直接左递归。

四、\(LL(1)\)语法分析

1.\(FIRST/FOLLOW\)集合与\(LL(1)\)分析表
·如果\(FOLLOW(B) = \{a, c\}, B\rightarrow bC|dB|\epsilon\)，那么\(B\)遇到\(a\)或\(c\)时，表项应填充规则\(B \rightarrow \epsilon\)。
·需注意：若\(B\)是可空的，则\(FIRST(B)\)应该包含\(\epsilon\)。
2.\(LL(1)\)文法的等价判定条件
①文法不含左递归。
②对任意两个产生式\(A\rightarrow\alpha, A\rightarrow\beta\)：\(FIRST(\alpha) \cap FIRST(\beta) = \empty\).
③若\(A \rightarrow \epsilon\)，则\(FIRST(A) \cap FOLLOW(A) = \empty\)。
3.\(LL(1)\)含义：从左向右扫描输入、进行最左推导、向前看\(1\)个输入符号。
4.\(LL(1)\)分析表的填充
·\(\forall t \in FIRST(A)\)，选择能够得到\(A \Rightarrow^* tw\)的产生式\(A \rightarrow \alpha\)进行填充。
·若\(t \in FOLLOW(A)\)且\(A\)可空，选择能够得到\(A \Rightarrow ^* \epsilon\)的产生式\(A \rightarrow \alpha\)进行填充。
·概括：对于每个表项\((X, \alpha)\)，需同时考虑“可空导出”、“非空导出”两种情形，“可空导出”对应于\(\alpha \in FOLLOW(X)\)，“非空导出”对应于\(\alpha \in FIRST(X)\)。
5.\(LL(1)\)分析表的匹配
·非终结符：匹配、出栈；终结符：根据前瞻字符查询分析表，进行产生式替换，替换所得符号序列倒序进栈。
6.自顶向下语法分析的错误恢复
·若栈顶为\(A\)时，前瞻符号为非预期符号（对应于文法分析表中\(A\)的空白表项），则跳过该符号，直到后续的token落入\(FOLLOW(A)\)，再退出\(A\)函数。
·做法的目的：使得后续的处理过程不受到A()函数中错误的影响。

五、\(LR\)语法分析

1.基本方法与操作
·基本方法：最左归约（反向构造最右推导）。
·基本操作：shift，token依次进栈；reduce，栈顶的若干个终结符、非终结符组成的序列恰好与某产生式右端匹配，全部出栈，替换为产生式左端非终结符。
2.\(LR(0)\)分析表
·item：点号左侧为已完成分析的符号序列，右侧为即将分析的符号序列。
·点号在最右侧的complete item，下一步是归约操作；点号尚未到达最右侧的incomplete item，下一步是移入操作。
·每个状态要不断对点号右边的非终结符进行展开，直到规则无法增加，形成闭包为止。
·在\(LR(0)\)分析表中，只包含complete item的状态，无论遇到的下一个符号是什么，都会直接发生归约。
3.\(LR(0)\)分析法
·引入item，但是每条规则没有前瞻符号。
4.\(SLR\)分析法
·DFA的构建过程与\(LR(0)\)分析法完全相同。
·表达能力强于\(LR(0)\)，原因是对归约添加了约束，只有遇到的下一终结符在将要归约到的非终结符的\(FOLLOW\)集合中，归约动作才能执行。 5.\(LR(1)\)分析法
·每条规则后增加终结符，如\(A \rightarrow \alpha.X\beta, z\)中，对\(X\)展开时，\(X\)产生式的规则后应添加\(w \in FIRST(\beta z)\)的终结符作为限制。
·起始状态：\((S' \rightarrow .S\$, ?)\)的闭包。
6.\(LALR\)分析法（一些著名编译器实际采用的分析法）
·构造方法与\(LR(1)\)类似，但是进行了同类项合并，更为简洁，但表达能力有所下降。
·\(LALR/LR(1)\)表达能力的区别：在于是否能解决reduce-reduce冲突。
·同类项合并：包含点号的规则相同，终结符不同的状态合并为一个等价状态。
7.冲突问题
·\(LR\)分析法只存在shift-reduce和reduce-reduce冲突。
·\(LR(1)\)分析法不存在reduce-reduce冲突。
·\(LR(0), SLR, LALR\)分析法可能存在reduce-reduce和shift-reduce冲突。
8.冲突解决方案
·shift-reduce冲突：优先shift（Yacc的默认选择），reduce优先级更低。
·reduce-reduce冲突：位置优先，选择第一条产生式进行归约。

抽象语法树

1.作用：语法分析树去除无意义符号得到抽象语法树，从而简化语法树。
2.Yacc自底向上分析：值栈、文法分析栈进行并行操作，计算各个非终结符、终结符的语义值。

语义分析

1.符号表：建立标识符及其属性（位置、类型等）的映射，与语法树并行存在，使用binding。
2.原始符号表\(S_0\) + 新增规则\(\{a \rightarrow int\}\)，加号两侧不可颠倒，原因是若新增规则与原始符号表中相同标识符的规则冲突，则新规则会覆盖旧的规则。
3.函数式风格：新增规则时，对旧表作拷贝，针对旧表的copy进行修改；命令式风格：直接针对符号表进行更改，退出作用域后通过撤销更改得到之前的符号表。
4.符号表：插入binding时使用头插法，越靠近bucket头部的binding，距离当前所处作用域也越近。
5.类型检查：基于抽象语法树的递归函数。

活动记录

一、函数调用基本概念

1.函数调用与栈帧变化过程
（1）函数g调用函数f
①栈指针(sp)：指向函数g给函数f传递的第一个参数的位置。
②函数f申请一个帧的空间，范围是sp - frame_size ~ sp。
（2）进入函数f
①新的帧指针fp用sp进行赋值，即指向static link位置；旧的fp保存在内存中。
②此时，fp和sp指向的位置相同。
（3）函数f执行
sp指针随着空间分配，可能不断往低地址增长；fp不变。
（4）退出函数f
①栈指针sp设为fp，恢复到进入f前的状态。
②从内存中，将保存的fp值恢复给fp。
2.寄存器与参数传递
①叶子过程（不再调用其他过程的过程）：无需将incoming arguments写入内存，而是直接放入寄存器，从而节约内存，提高效率。
②一些优化过的编译器，采用过程间寄存器分配。
③函数f调用h函数时，若位于寄存器r1中的变量x已经成为死变量，则可以直接覆盖该寄存器r1。
④寄存器窗口：存在于部分体系结构之中。
3.返回地址保存
·叶子过程可直接将返回地址保存在寄存器中，非叶子过程需将返回地址写入内存栈保存。
·若采用过程间寄存器分配技术，则非叶子过程可能无需将返回地址写入内存。

二、静态链接

1.block feature：某些语言中，内部函数可能用到外部函数定义的一些变量。
2.静态链接：调用函数f时，给函数f传递父函数(caller)的帧指针，父函数的帧指针即为静态链接。
3.lambda lifting：子函数实际访问的父函数中的每个变量，都作为一个额外的参数传递给子函数。
4.注意：进行递归调用时，假设prettyprint->show->show为调用关系，则show->show调用时，传递的static link并非父show函数的static link，而是prettyprint的static link。
5.结构体：定义时无需申请空间，真正进入结构体时再作申请；结构体可以视为函数定义，为其申请活动记录，但该方法不高效；可视为临时表达式。

三、参数传递的分类

1.传值(pass by value)：实参的数值传递给形参。
2.传引用(pass by reference)：传递变量的地址。
3.双向值传递(pass by value-result)：函数调用时，实参的值传给形参；函数返回时，形参的值也会返回给实参。
4.命名传递(pass by name)

中间表示

1.中间语言表达形式：提高编译器的模块化程度和可移植性。
2.前端：词法分析、语法分析、语义分析、中间表达生成；后端：中间表达优化、机器代码生成。
3.三地址码：复合表达式拆分成基本表达式；可使用四元组（三个地址、一个操作符）进行表示。

活动记录

1.活动记录：与函数调用一一对应，存储于栈中。
2.函数嵌套定义-特殊变量：在父函数中定义的变量，子函数也能看到，该变量既不是局部变量，也不是全局变量。
3.栈帧与堆栈
①栈指针：仅在函数入口处，堆栈向低地址增长，用一个新的栈帧存储函数调用信息。
②栈帧：存储函数参数、局部变量、返回地址，以及其他临时变量。
③栈帧：高地址，位于frame pointer上方为caller函数的outgoing arguments，亦即当前函数的incoming arguments，以及caller函数的static link；current frame存储返回地址、临时变量等；靠近低地址的区域为当前函数的outgoing arguments和static link，用于传给被当前函数调用的子函数。
4.函数调用与指针变化
①函数\(g\)调用函数\(f\)：栈指针SP指向\(g\)的第一个outgoing argument（即：static link）；函数\(f\)申请sp ~ sp - FRAMESIZE范围，一个帧的空间。
②进入函数\(f\)：FP旧值放入内存，更新为旧的SP，即\(g\)函数的static link位置。此时，FP和SP都指向函数\(g\)的static link。
③函数\(f\)执行：SP可能向低地址移动，FP保持不变。
④函数\(f\)退出：将FP放入SP，即令SP指向g的static link，然后从内存中恢复出FP旧值。
5.函数调用和寄存器保存：caller-save/callee-save；前\(k\)个参数使用寄存器直接传递，剩余参数使用内存传递。
6.传参过程优化：①叶子过程：不调用其他函数，incoming arguments无需写入内存，而是直接放入寄存器。②过程间寄存器分配。③\(f\)调用\(h\)时，死变量占用的寄存器可以直接被覆盖，无需保存。④寄存器窗口机制。
7.返回地址：call指令的下一地址，被存放到指定的寄存器(ra)中。除非应用过程间寄存器分配技术，非叶子过程需要将返回地址写入栈帧，但叶子过程只需将其保留在寄存器中。
8.静态链接——块特征(block feature)：函数嵌套定义中，内部函数可能用到外部函数定义的变量。
9.静态链接：若函数\(f\)(father)调用嵌套定义的子函数\(c\)(child)，则会给子函数\(c\)传递（静态包围\(c\)的函数）\(f\)的帧指针FP，该FP即为Static Link。
10.Display：维护全局数组，保存各个函数层次的指针关系。
11.Lambda Lifting：若\(g\)函数嵌套定义\(f\)函数，则\(f\)中实际访问的每一个\(g\)中变量，都作为一个额外的参数传递给\(f\)。
12.函数的嵌套调用和递归调用：①嵌套调用（非递归）：若show函数调用indent函数，将show函数的帧指针作为静态连接，放在outgoing arguments的最低地址处，传递给indent函数；②递归调用：prettyprint中嵌套定义了show函数，父show函数调用子show函数，则并非将父show函数的FP传递给子show函数，而是将父show函数栈帧中，incoming arguments的static link（即prettyprint函数的FP）传给子show函数.
13.子函数调用叔叔函数的过程：prettyprint函数嵌套定义write/show函数，show函数嵌套定义indent函数。若indent函数需调用write函数，则indent函数先在incoming arguments找到show的帧指针，然后从show的incoming arguments中找到prettyprint函数的帧指针，之后才能进行write函数的调用。
14.基于栈的运行时环境（无嵌套定义/局部过程）①帧指针FP：指向当前的活动记录。②动态链接/控制链接：存储调用者的FP，即指向调用者的活动记录。③栈指针SP：指向当前的栈顶位置。
15.局部变量访问：帧指针 - 偏移量。
16.结构体空间：①函数中，结构体的定义无需分配空间，真正进入结构体才分配空间。②结构体可能视为函数定义，即对进入每个结构体，新申请一个活动记录，离开时释放；但往往不高效。③常见处理：视为临时表达式。
17.参数传递机制：①pass by value：实参传值给形参。②pass by reference：传递变量对应的内存地址，比如数组的起始地址。③pass by value-result：双向值传递，即函数调用时实参的值传给形参，且函数返回时，形参的值返回给实参，实参被更新。④pass by name：参数估值延迟，指导被程序用到的时候，才会被计算。
18.举例——pass by name

a[i]在正式使用前，只是一个名称，不知道它的值，被传入函数p；首先进行++i操作，i变为2；之后到达++x语句，a[i]才被计算，此时i = 2，a[2] = 2，令a[2]自增，结果为3，因此a[2]被更新为3，a[1]不变。

中间表示

1.三地址码：三个地址（常数、源程序中的名字、编译器生成的临时变量名） + 一个操作符。
2.中间表示树：CONST(i)：整形常量i；NAME(n)：符号常量n，相当于汇编语言中的label；TEMP(t)：临时变量；BINOP(o, e1, e2)：对子表达式e1, e2进行二元运算，其中e1表达式优先估值；MEM(e)：开始于内存地址e，长度为wordSize字节的内容，可能对应于读、写操作。
3.ESEQ(s, e)：先计算语句s，形成副作用，然后计算表达式e，将其结果作为ESEQ表达式的结果。
4.副作用：ESEQ(a = 5, a + 5)的结果为10。有两种副作用：①改变内存。②改变寄存器。
5.【中间表示绘制注意事项】①函数调用：CALL结点返回函数调用的return value，左分支为NAME--print，右分支为SEQ表示传入参数列表。②数组元素访问：MEM--+，左分支为数组基地址MEM--e，右分支一般是操作符为MUL的BINOP表达式，表示索引偏移量\(\times\)字长。③副作用语句：使用TEMP--r新建临时变量，存储表达式运算结果。④显式声明：n为循环语句块之后，第一条待执行语句的label；显式规定变量相对于函数帧指针TEMP--fp的偏移量为k。

基本块、轨迹

一、规范树改造

1.IRTree和目标机器汇编代码的不匹配问题：①CJUMP：目标机器一般是条件成立则跳转，否则继续执行。②ESEQ指令：先执行语句s（可能产生副作用，更改内存/寄存器变量的值），再执行语句e，二者执行顺序不应颠倒。③CALL指令：一个CALL指令的返回值，作为另一个CALL指令的参数时，可能发生传参寄存器覆盖问题。
2.IRTree改造步骤：①改写IRTree，消除SEQ/ESEQ结点成为标准化树。②标准化树分组为基本块。③基本块按照执行顺序排列为轨迹；令紧跟CJUMP的语句块均为False label对应的语句块。
[注]基本块内部：既不包含标签（只允许从块的起始处开始顺序执行，不能有其他任何入口），也不包含跳转语句（只能顺序执行完整个块再前往其他基本块，不能中途退出）。
3.规范树改造——ESEQ结点提升
①父ESEQ作为子ESEQ的第二子节点——右倾树改为左倾树，ESEQ改为SEQ

②ESEQ作为BINOP第一子结点——ESEQ、BINOP结点换位

③ESEQ作为BINOP第二子节点——ESEQ上提、创建临时变量保存第一子节点（原因：执行表达式s可能影响第一操作数e1的结果）

4.表达式交换（ESEQ作为BINOP第二子节点）
①常数和副作用语句s可交换。②空语句可以和任何表达式e进行交换。③其余情况认为不可交换。

5.根据表达式可交换性对IR语句进行改写

6.规范树改造——CALL指令即时保存返回值：①注意到：BINOP(PLUS, CALL(func1, args1), CALL(func2, args2))会产生传参寄存器被覆盖（第二个CALL的返回值覆盖第一个CALL的返回值）的问题。②改造：CALL(func, args)改造为ESEQ(MOVE(TEMP t, CALL(func, args)), TEMP t)。
7.语句的线性链表：SEQ(SEQ(a, b), c) = SEQ(a, SEQ(b, c))，考虑语句s1, ..., sn组成线性链表，其中各statement均不包含SEQ/ESEQ子结点。

二、基本块和迹

1.条件分支：①改造目的：false label对应语句块，恰好位于CJUMP语句之后。②具体转换步骤：规范树划分为基本块 -> 基本块按照执行顺序，排列为traces。
2.基本块：①单一入口：第一条语句为LABEL语句，无LABEL则手动添加。②单一出口：最后一条语句为JUMP/CJUMP，若无则手动添加。③无其余LABEL/JUMP/CJUMP。
3.基本块算法：①从头到尾扫描规范树列表。②遇LABEL表明：新的基本块开始，旧的基本块结束。③遇JUMP/CJUMP表明：当前基本块结束，之后新的基本块开始。④手动为部分基本添加LABEL开头、无条件JUMP结尾。
4.基本块性质与操作：①排列不变性：各基本块之间，使用LABEL + JUMP/CJUMP跳转，故基本块的排列顺序不影响程序执行结果。②操作：让FALSE LABEL基本快紧跟CJUMP；让无条件JUMP的目标基本块紧随其后，从而删除无条件JUMP，加快程序运行速度。
5.迹：①可以连续执行的一组基本块构成的序列，称为一个trace。②基本目标：生成一组trace完全覆盖所有基本块，每个基本块恰好处于一个trace中。③额外目标：希望尽量减少trace数量。
6.Trace生成算法概述：①从某个基本块开始执行，不断跟随基本块末尾跳转语句，得到可能的迹。若为CJUMP结束，则只能选择true/false label之一对应的基本块，纳入当前的迹中；未被选择的基本块将属于另一个trace。②迭代直到所有基本块被覆盖。
7.【基本块划分技巧】①跳转语句下方画分割线，表明当前基本块结束。②目标语句上方画分割线，表明开启一个新的基本块。
8.优化：①CJUMP后紧跟false label基本块。②若CJUMP紧跟true label基本块，则需否定CJUMP判断条件，进行CJUMP真假标签互换。③后续无任何指令的CJUMP：把CJUMP(cond, a, b, t, f)改造为CJUMP(cond, a, b, t, f'), LABEL f', JUMP(NAME f)，以实现每个CJUMP后紧跟着false label。④频繁执行的指令序列，应尽量放在同一个trace中，以减少无条件跳转次数。

指令选择

1.指令选择：①使用tree pattern覆盖整个IR Tree，从而选择出对应的机器指令。②一个TEMP实现为一个寄存器。③某种指令可能对应于多种Tree Pattern。④自顶向下进行tiling（即IRTree覆盖），自底向上生成目标代码。
2.理论最优覆盖(Optimum)：使用时钟周期量化各指令运行时长，求出瓦片对应机器指令运行之和的理论最小值，对应的tiling方式称为最优覆盖。
3.实际最佳覆盖(Optimal)：不存在两个相邻瓦片可以合并为一个瓦片，使得指令运行的总时钟周期数减小。
4.指令选择——Maximal Munch算法：从树根开始，选择最大（覆盖结点数目最多）的瓦片进行覆盖，然后对子树进行最大覆盖操作（贪心思想），以相反顺序生成机器指令。
5.指令选择——动态规划算法：①对于多种覆盖方式同时匹配IRTree的情况，每种方案的覆盖总代价 = 左子树执行代价 + 右子树执行代价 + 当前瓦片执行代价。②自底向上进行动态规划，逐步选择以+/MEM等结点为根结点的子树，进行覆盖的最小代价。
6.指令发射算法：先对根结点所在瓦片的每一个子树，调用Emission(leaf)，最后再对当前根节点所在的瓦片，生成对应指令。
7.算法复杂度分析：①设\(T\)为瓦片种类数，\(K\)为每个瓦片包含的平均树结点个数，\(T'\)表示每个树结点至多有多少中匹配的瓦片，\(K'\)为最大结点数量，\(N\)表示IRTree的结点个数。②最大匹配算法：时间复杂度为\(O(\frac{(K' + T')N}{K})\)，原因是每次进行瓦片覆盖后，平均\(K\)各结点从IRTree中摘除。③动态规划：\((K' + T')N\)。④由于\(K, K', T'\)均为常量，因此上述两种算法均为线性时间算法。
8.①RISC：32个寄存器，只有一类整数/指针寄存器，仅能在寄存器间完成算术操作，三地址指令形式，Load/Store只有Mem[reg + const]的形式，指令长度相同，每条指令只有一个结果。②CISC：寄存器更少，某些操作只能通过特定寄存器实现，算术操作可以通过寄存器/Mem执行，只支持两地址模式即r1 <- r1 op r2，寻址模式更多，变长指令，可能有指令副作用。
9.CISC的一些问题及其解决方案：①寄存器数量更少。可任意产生TEMP结点，假设寄存器分配工作可以顺利解决数量问题。②寄存器有指定分类。可改写规则，解决诸如乘法左操作数必须是eax寄存器等问题。③二地址指令：增加额外的MOME指令，将结果转存到目标寄存器中。④算术运算可以访问内存：执行算术运算前，取操作数到寄存器；执行运算后，再把寄存器数值写回内存。⑤更多寻址模式、可变长指令：不是问题。⑦指令副作用：r2 <- Mem[r1]，可能副作用为r1 <- r1 + 4，如需r1不变则应添加SUB指令。

活性分析

1.活性：变量在将来被定义前还需被使用，则称变量活跃。
2.活性范围：按照指令流，确定活性范围，如1->2, 2->3等。
3.活性分析：①绘制控制流图(control flow graph)，确定语句的执行流情况。②使用回溯方法，从后往前分析变量活性。（找出最后一次在哪里被使用->逐步向前分析，直到变量被定义为止）
[注]注意：使用、定义可能同时出现在一个语句中，此时在该语句前，变量是活跃的。
4.变量的定义集合、使用集合。
5.变量活跃性的严谨定义
①变量的“活跃路径”：若控制流图中，某路径重点为use(v)，并且路径上无节点进行def(v)，则称该变量在路径上活跃。
②入口活跃：若变量在某节点的任何in-edge上都是活跃的，则称该变量在该结点“入口活跃”。
③出口活跃：若变量在某节点的任何out-edge上都是活跃的，则称该变量在该结点“出口活跃”。
6.变量活跃性的判断
①若变量\(a \in use[n]\)，则在结点\(n\)，变量入口活跃。
②若变量在\(n\)结点入口活跃，则对于任意\(m \in pred[n]\)，变量在结点\(m\)出口活跃。
③若变量\(a\)在结点\(n\)出口活跃，且\(a \notin def[n]\)，则变量\(a\)在结点\(n\)入口活跃。
7.变量活跃性求解公式
\(in[n] = use[n] \cup (out[n] - def[n])\)
\(out[n] = \cup_{s \in succ[n]}in[s]\)
8.变量活跃性迭代算法（前向）

·in[n]更新：use[n]∪out[n] - def[n]。
·out[n]更新：（根据控制流图）寻找n的后继结点s，对它们的in结点取并集。
·注意：逐个结点按照顺序计算，不能颠倒次序。 9.变量活跃性迭代算法（反向）——收敛速度加快
·结点反向；先计算out，再计算in。
10.基本块合并：若某节点只有一个前驱结点，则该结点可与其前驱结点进行合并；若某节点只有一个后继节点，则该结点可与其后继节点进行合并。
11.静态活性分析

·注意到\(c \geq b\)必定成立，因此右侧分支无效，判断条件恒为真。
·故左侧的false label必定不会执行，即\(a\)在第2语句使用后，失去活性。
·c和a的活性范围刚好不产生冲突，因此足够“聪明”的策略，应该把变量a/c分配至统一寄存器中。
12.停机理论与活性分析
①停机理论：不存在程序\(H'\)，输入程序\(X\)和label L，若\(X\)执行时到过\(L\)则返回真；若不能到\(L\)，则返回假。
②结论：不能完全分析出某个标签/路径是否一定会被访问，但是可以通过特定算法，进行保守估计。
13.动态活性与静态活性
①动态活性：对于结点\(n\)，若从\(n\)结点到某个使用\(a\)的结点的实际执行过程中，从未经历过定义\(a\)的结点，则称变量\(a\)在结点\(n\)处具有动态活性。
②静态活性：若从\(n\)开始，存在一条通往使用\(a\)的结点的路径，该路径上不对\(a\)进行定义，则称\(a\)在该路径上具有静态活性。
③性质：动态活性\(\Rightarrow\)静态活性。
14.干涉图
（1）干涉(interference)：变量不能分配到同一个寄存器，即存在干涉。
（2）干涉边的定义：①若非MOVE指令定义变量a，且live-out变量为b1, b2, b3，则添加干涉边(a, b1), (a, b2), (a, b3)。②若为MOVE指令\(a \leftarrow c\)，live-out变量为b1, b2, ...，则对于\(b_i \neq c\)，添加干涉边\((a, b_i)\)。
[注]即对MOVE指令的干涉边进行特殊分析。

寄存器分配

1.线性时间近似算法（寄存器个数为\(K\)）：①构造：识别各结点的live-in/live-out活性变量，构造干涉图。②简化：若某节点\(m\)的邻居个数小于\(K\)，则该结点可从图上移动到栈中。③溢出：若简化后的图中仅剩重度结点，则可能某个结点需要放入内存，也可能仍然可以染色。④选择：从空图开始，每次从栈中弹出一个结点，着色。若某重度结点无法着色，则需将其放入内存，四个步骤全部重新执行。
2.合并：如果\(j \leftarrow b\)，且二者不产生干涉，则两者可以合并为一个结点，删除MOVE指令。
3.合并的副作用：直接合并两个轻度结点，可能导致重度结点的产生。
4.两种保守合并策略：①Briggs：若合并后，结点\(ab\)的重度邻居结点少于\(K\)个，则可以合并。②George：\(a\)的每个邻居要么与\(b\)干涉，要么是轻度结点，则可以进行合并。
5.完整的寄存器分配算法

垃圾回收

一、Mark and Sweep算法

1.手动内存管理的问题：内存泄露（不断malloc没有free）、多重释放、释放后使用。
2.自动内存管理：①由系统完成。②垃圾回收属于自动内存管理。③垃圾：已经分配，但不再被使用的空间。④垃圾判定：不可判定，实际使用保守方法进行近似。
3.垃圾的近似判定：在堆中申请，但是unreachable的对象，即为垃圾。②对象reachable\(\Leftrightarrow\)存在一个寄存器，保留指向\(x\)的指针，或存在一个reachable对象，保留指向\(x\)的指针。
4.reachable对象标记算法（深度优先搜索）：①若x是指向堆空间的指针，标记它指向的记录（对象），并对该对象的每个成员调用DFS算法。②最终未被标签的结点即为垃圾。
5.垃圾清理：从堆的起始地址向终止地址进行扫描，将已标记结点解除标记，并回收未标记结点（以链表形式放在freelist中）。
6.Mark & Sweep（垃圾回收）的触发时机：malloc申请失败时触发。
7.Worklist：①作用：保存所有reachable的对象。②每次从Worklist中删除一个结点，若该结点未被标记，则进行标记，并将从该结点出发，可以到达的所有子节点加入到Worklist中。
8.【问题一——时间、空间复杂度】运行时间和已经申请的对象数目成比例，且worklist需要大量空间（甚至占据可以等于内存大小）。
9.【举例】①首先，对p进行DFS，依次标记15, 12, 37结点。②注意到37结点指向5, 20结点，对此二结点进行标记。③r指向37结点，37结点及其子结点均已被标记。④freelist：依次扫描堆中各个对象，发现7, 9结点均未被标记，将其加入freelist中。
10.【使用显式栈代替递归】①Mark的深度优先搜索算法是递归的，最坏情况下，递归调用所需的活动记录（栈）大小可能超过整个堆。②用显式栈代替递归：x ← stack[t]; t ← t - 1; for each field fi of record x: if x.fi is a pointer and record x.fi is not marked: mark x.fi; t ← t + 1; stack[t] ← x.fi.

二、指针反转、引用计数、集合复制

1.指针反转：①基本思想：不使用显式栈，而是基于重用图结点的某个部分，进行回溯。②基本策略：record x的某个域x.fi压栈后，算法不再查看x.fi，因此可使用x.fi存储栈顶元素。③具体做法：当前结点的x.fi被标记前，存储的是指向一个子节点的指针；该子节点被标记后，当前结点的x.fi域可以改为指向当前结点父结点的指针；某一“分支”标记完后，反转的指针还需恢复原状。

[注]作业题：标记完N8结点的59 field时：t为父节点(N4)，y为当前处理的field(N8)，x为当前处理的record(N8)。
2.引用计数：①各对象包含一个引用计数器，表明有多少指针指向该对象。②各赋值语句，均会触发引用计数。③若指向记录p的指针被保存到x.fi（对象x的第i个域）中，则引用计数值增加；同时，x.fi原本保存的指针，指向对象的引用计数会减少。③若记录r的引用计数值减少为0，则r直接放入freelist中，且r指向的所有对象，引用计数值都会减少1。④可能触发级联式的对象释放。
3.引用计数的问题：①循环垃圾无法回收，即p, q互相指向对方，则无法回收。②维护引用计数器实际非常昂贵，如x.fi <- p指令需转化为9条指令。
4.集合复制思想：①堆中reachable部分：使用有向图进行表示，指针为有向边，堆中记录作为图结点，程序变量作为根结点。②堆空间一分为二，分成from-space/to-space。③申请空间与垃圾回收触发：从from-space申请；若from-space的next指针等于limit指针，则表明不可从from-space中申请，启动垃圾回收。④垃圾回收结果：所有由root结点直接/间接指向的reachable部分都移动到to-space中，并进行了空间压缩，to-space中next < limit；from-space和to-space进行互换。
5.集合赋值——Forward(p)算法：①若p指向from space，则进行步骤二，否则返回p。②若p.f1指向to-space，则返回p.f1；否则对p的每个域fi：令next.fi <- p.fi; p.f1 <- next; next <- next + size of record p; return p.f1。③第二步的操作，执行的是将记录从from-space拷贝到to-space的操作，完成后记录本身位于to-space，但是记录中的某些指针可能还是指向from-space中的子节点。
6.Chenny算法：①使用广度优先算法遍历所有可达数据。②首先，对于每个根结点r，进行一次Forward(r)操作，即将所有一级子节点拷贝到to-space。③scan初始化为to-space中的起点，在to-space中每次scan一条记录，对该记录的各个域scan.fi调用Forward(scan.fi)，然后scan增加size of record，直到scan == next，算法终止。
7.【举例】

①根节点Forward：结点15, 37拷贝到to-space中的15', 37'结点，注意到：15', 37'记录中的指针，指向的仍然是from-space中的记录；暂时位于from-space还未被释放的旧记录，第一个field不再是15/37，而是指向to-space中记录15', 37'的指针。②扫描to-space中的记录15，子节点12未放入to-space，进行Forward操作；子节点37已经位于to-space，可以略过；更新指针scan，使其指向to-space中的记录37。
8.集合复制的优缺点：①优点：from-space中的记录拷贝到to-space，顺带进行了压缩操作，而Mark and Sweep算法基于原有空间进行垃圾回收，不易于进行空间压缩。②缺点：空间利用率低，只利用了堆空间的一半。
9.引用局部性：①Chenney算法：基于BFS进行拷贝，因此放到to-space中的记录，引用局部性较差，即堆中相邻记录对应的父节点往往不同。②Mark and Sweep算法：基于DFS，引用局部性较好。③混合算法（BFS/DFS结合），总体上使用BFS进行集合复制，但如果某个记录被复制了，则通过Chase操作，试图将该记录指向的子记录复制到其相邻空间中。

面向对象的语言

1.类的扩展class B extents A {...}：必须位于A的let表达式作用域之内，保证A可访问；B可重载A中某些方法（形参表、返回值类型均必须相同），但不可重载A的域。
2.类Object：不含任何域、方法，标识符为Object，有隐式参数self，self是每个方法中自动调用绑定对象的标识符。
3.类的方法调用：基于绑定对象的类型，比如说class Child extends Father，且Child重载了Father类的SelfIntroduction()方法。现在有一个Child类型的对象child_obj，用父类指针father_ptr指向child_obj，那么father_ptr->SelfIntroduction()实际调用的是子类的重载方法，而不是父类的方法。
4.单继承与前缀：①单继承每个子类只能继承一个父类。②前缀：此时域可通过“前缀”技术进行排列，即class C extends A，那么C的各个域中，首先是父类的域，父类的域之后才是子类单独增加的域。
5.静态/动态方法：①静态方法：调用c.f()时，先在类C中搜索方法f，若搜索到则调用，否则依次搜索父类、爷爷类、老祖宗类。②动态方法：若A -> C -> D（父类指向子类），A有一个动态方法f，则该方法可被C, D分别重载。假设一个C类型的指针C_ptr指向某个对象obj，则在编译期间无法确定obj的具体类型，且如果C_ptr指向C类型对象，则调用C类型的f方法，若指向D类型的对象，则调用D类型的f方法。
6.类描述符需包含方法表（向量）：方法表中存储每个非静态方法名，对应于到真正的方法实例。

7.执行动态方法c.f()：①在对象offset = 0位置，取出类描述符(class descriptor)；②从d位移f处，取出方法实例指针p；③保存返回地址，转移到地址p（即方法f对应的代码段）。
8.多继承：①静态方法（全局图染色）：静态分析所有类，确定每个field的offset，使得该offset能够用于包含该field的所有类，不产生冲突或歧义问题。②图染色：一个域名作为一个结点，同一个类中两个field之间形成一条边。
9.图染色方法的问题：①问题：各个对象中，存在空单元，浪费存储空间。②解决方法：把域的排布方式放在class descriptor中，在具体的object中，让所有的field紧凑安排在一起。读取x.a时，需要从x的class descriptor中取出与a对应的word，该word包含了一个小的offset，表明x对象中a的真正偏移量。③结果：空单元只出现在class descriptor中，不会出现在实际存储的对象中；但是一条指令变为三条指令，计算开销有一定程度上升。
10.图染色与方法查找：①method和field可以同时对应于图中结点，进行染色，class descriptor中存储method instance对应的机器码地址，以及field在对象中相对于起始地址的偏移量。
11.全局图染色的执行时间：①至少应在动态链接时完成，此时自己写的代码、第三方库链接在一起，才知道所有的类。②一些面向对象的系统，可能具有向运行系统中动态加载新类的能力，此时不能在动态链接时完成全局图染色。
12.哈希方法基本思想：①每个class descriptor中含一个哈希表，将域名映射到offset，将方法名映射到方法实例，能很好地适应于分开链接、动态编译。②每个class descriptor分别有field-offset table（大小为N，存储method instance的起始地址、field offset）和key table（存储域名字符串，用于冲突检测）。③可使用任意一种冲突处理手段。
13.哈希方法取c.x的步骤：①从对象offset = 0处，取class descriptor。②从地址为d + KeyTable_offset + hash(x)处，取出域f。③测试f = ptr(x)是否成立，如果不成立，需运用冲突处理手段寻找域f的位置。④从地址为d + FieldOffsetTable_offset + hash(x)取出域x真正的偏移量k。⑤从c + k处，读取域的内容。
14.类和对象关系测试：①IsType(x, C)/ x isinstanceof C，测试x是否为类C的对象。②单继承：从x的class descriptor出发，依次查询当前类、父类、爷爷类等，看是否为C类。③display(of parent classes)：父类嵌套层次显示表，设D类的嵌套深度为l，则其class descriptor的display表中，第l单元存放指向D的class descriptor的指针，第l - 1, l - 2, ...单元分别存放父类、爷爷类、曾祖父类、老祖宗类的class descriptor的指针，其余l + 1, l + 2, ...等单元均为空指针。④display实例判断：从当前对象类描述符d的display中，依次从第l单元向第0单元查询，看是否为类C。
15.私有域、私有方法：在symbol table中，除了存储field offset/pointer to method instance之外，给每个表项增加一个布尔标识，表明该域/方法是否为私有。
16.私有性的不同保护方式：①域和方法只能由声明它们的类进行访问。②域、方法可以由声明它们的类，以及该方法的所有子类进行访问。③域和方法只在声明类的同一个module/package/namespace中可访问。④域在类声明之外只读，对于本类的方法可写。

循环优化

一、支配节点与循环嵌套树

1.循环体——头结点(header node)定义：①循环体中每个结点，都有通向\(h\)的路径。②\(h\)能到循环体中的任一结点。③外部结点只有到\(h\)的边，没有到其他结点的边。
2.循环入口与出口：入口恰好一个，出口可以多个。
3.支配结点定义：从头结点\(h\)到\(n\)的每一条路径都经过结点\(d\)，则\(d\)支配\(n\)；性质：header支配所有结点；结点支配自身；支配结点可以不止一个。
4.支配结点寻找算法：①各结点是自己的支配结点。②当前结点的前驱结点，它们支配结点的交集，就是当前结点的支配结点。
5.直接支配结点：不是其他任何支配结点的支配结点。
6.【支配定理】若\(d, e\)都是\(n\)的支配结点，则必定有\(d\)支配\(e\)或者\(e\)支配\(d\)。
7.支配结点树：从直接支配结点\(idom(n)\)向当前结点\(n\)发出有向边，形成支配结点树。
8.[回边(back edge)的自然循环]设回边为\(n \rightarrow h\)，\(h\)支配\(n\)，则该回边的自然循环中，包含的结点\(x\)满足：\(h\)支配\(x\)，且存在一条从\(x\)到\(n\)，不经过\(h\)的路径。
9.自然循环的性质：若两个自然循环首结点不同，则要么互补相交，要么一个自然循环包含另一个自然循环。
10.循环嵌套树：①计算各节点的支配结点。②构建支配树（即：直接支配结点向当前结点发出有向边）。③寻找所有自然循环及其头结点。④对每个头结点，归并属于该结点的所有自然循环，作为一个统一的循环。⑤若某个非根节点暂未被归并，则将其归并到根节点。⑥建立循环嵌套树，若头结点\(h_2\)在循环\(loop[h_1]\)中，则令\(h_1\)作为\(h_2\)的父节点。
11.循环前置结点：若有多个外部结点到达头结点，则需增加前置头结点，使得循环具有唯一入口。（注：循环结点集合不变、循环中的回边不变，仅改变外部连接方式）

二、循环不变量

1.循环不变量：\(t \leftarrow a \space op \space b\)，若循环计算中，\(a, b\)均不变，则\(t\)为循环不变量。
2.循环不变量的判定：①操作数为常数；②操作数在循环外部定义，在循环内部不会定义；③操作数只有一个定义到达\(d\)，且该定义具有循环不变性（递归定义）。
3.运用算法寻找循环不变量：①寻找所有操作数为常数/在循环之外定义的循环不变量。②递归寻找其他循环不变量。
4.外提\(d: t \leftarrow a \space op \space b\)的几个要求：①对于任意一个循环出口，若\(t\)是出口活跃的，则\(d\)应该支配该出口。（该规则常常针对分支）②在循环中，\(t\)有且仅有一个定义。③在循环中，\(t\)先定义，后使用。
5.语句转换：while循环转换为repeat-until循环，即if前置判断条件 + repeat语句块 + until判断条件。（同一个判断条件在代码段中出现2次）

习题解答

课件例题

·\(LR(0)\)分析：注意同一产生式，点号位置不同，则为不同的item，不能混淆。
·\(LR(1)\)分析与\(LALR\)分析：同样的item，不同的终结符，对应状态是否能合并，是\(LR(1)\)文法和\(LALR\)文法的本质区别。

测验二

（1）FIRST/FOLLOW集合的计算
·注意每添加一项，都要针对其他非终结符进行检查，看是否需要相应地进行补项，如此迭代直到不再更新。
·注意非终结符是否为可空非终结符。若\(D\)可空，则由\(C \rightarrow SD\)可知：\(FOLLOW(C) \subset FOLLOW(D)\)。

期中考真题（判断）

1.A LR(1) parser cannot parse any left-recursive CFG without ambiguity.
【解答】错。\(LR(1)\)分析法可以分析一部分\(CFG\)文法。左递归可能会导致shift-reduce冲突，但如果对reduce作出限制的FOLLOW集合不包含shift字符，则这类左递归不会影响\(LR(1)\)分析器的正常行为，不会在\(LR(1)\)分析中产生二义性。
2.LL(1) grammar cannot be left-recursive.
【解答】对。LL(1)文法等价判断条件的三个要求之一，就是不能为左递归文法。
3.Given a legal string of tokens for a CFG, there must be a unique parsing tree to derivate the string.
【解答】错，要看CFG是歧义文法还是非歧义文法。
4.The language L={a^n b^n|n>=1} can’t be generated by any regular expression.
【解答】对，DFA存储能力有限，无法应对“无限内存”的场景。
5.There is only one parse tree for the string of an unambiguous grammar.
【解答】对。
6.If a grammar is LR(1), but not LALR(1). There may be shift-reduce conflicts in its parsing table of LALR(1).
【解答】错。\(LR(1)\)和\(LALR(1)\)表达能力的区别在于reduce-reduce冲突，它们面临shift-reduce冲突的表达能力是相同的。
7.Finding the next handle is the man task of a LR parser.
【解答】
对。句柄即已分析的句型（含终结符、非终结符）中，与产生式右侧序列相匹配的字串。
8.Both DFA and NFA can recognize regular set.
【解答】对。正则集(regular set)即正则表达式表达的字符串集合，在表达能力上，正则表达式、NFA、DFA是一致的。
9.The parse tree will completely reflect the derivation steps for a string.
【解答】错。仅语法分析树本身，不能完全看出推导过程。
10.Left recursion is commonly used to make operations left associative.
【解答】对。自行举例展开\(S \rightarrow S + a\)，根据操作离语法分析树树根越远，越优先执行的原则，可验证该结论。

期中考真题（选择）

1.\(LL(1)\)文法的等价判断条件（见知识点）。
2.YACC的分析方法是：LALR(1)分析法。
3.LL(1)分析属于自顶向下分析，因此其分析表只有generate, accept两种动作，没有自底向上分析表中的shift, reduce动作。
4.When inheriting a previously computed synthesized attribute during LR parsing, it is suitable to treat the computed synthesized attribute as (external data structure).
5.All inherited attributes can be changed into synthesized attributes by suitable modification of the grammar, without changing the language of the grammar.
6.继承属性：应通过语法分析树的前序遍历进行计算。

期中考真题（解答）

【题型——\(LL(1)\)分析法】
①如果\(T \rightarrow \epsilon\)，要在\(FIRST(T)\)中写上\(\epsilon\)符号。②由于\(T \rightarrow ST'\)，\(T'\)可空，因此\(FOLLOW(T) \subset FOLLOW(S)\)。特别关注与nullable符号相关的\(FOLLOW\)集合的包含问题。

补充（手写）——汤普森法则NFA构造技巧

作业

【6.3-寄存器/内存变量】①寄存器变量：函数调用传参。②内存变量：引用传参需访问内存地址；数组且被函数以reference方式访问，放在内存中更合理。
【6.7-Display/Static Link】（1）Static Link：当前函数的静态链接，存储的是父嵌套函数的帧指针。（2）Display按照嵌套深度进行索引，D[i]存储深度为i的函数帧指针，相当于一个以深度为索引的查询表。
【7.2-IRTree构造】①注意a[i]读写对应的抽象语法树（见知识点部分）。②注意true label/false label，总有一段代码执行完之后需进行jump n。③需显式说明：n为循环体之后第一条顺序执行的指令。④副作用ESEQ(s, e)：s对寄存器/内存中的某些变量进行修改，可能影响e的值。
【8.2-IRTree规范化】（1）ESEQ作为MEM的左子结点，上提后无需补充额外的操作。（2）①CALL的返回值需建立临时变量进行存储。②CALL建立临时变量存储，带来ESEQ语句，ESEQ需上提至顶部。③注意到e1为常值表达式，可以跟副作用语句s交换顺序。（3）①g函数调用前，应先设置好参数TEMP x为CONST 0。②两个函数调用后，分别立即将返回值存储到t1, t2临时变量中，之后再对两个临时变量进行BINOP操作。
【8.6-基本块划分、迹的求解】①基本块划分技巧：目标语句上方画横线，表示开启一个新的基本块；JUMP/CJUMP下方画横线，表示结束当前基本块，下一语句开启新的基本块。②迹的求解：不断按照无条件跳转逻辑，将顺序执行的语句块纳入迹中；若为CJUMP，则只能将其中一个目标基本块纳入当前trace，另一个基本块可能要放在另一个trace中；注意各trace交集为空，恰好覆盖所有基本块。
【8.7-基本块指令转化为IRTree】基本块中指令线性执行，因此无需使用SEQ/ESEQ语句，直接用,隔开各表达式即可。
【9.1-最大覆盖算法】①注意4结点同时覆盖的内存读写操作，要求+的一个子节点为常数。②观察选取最大匹配规则。③贪心思想。
【10-活性分析】见下列“干涉图构造”相关注意事项。
【11.1-寄存器选择】（1）干涉图构造：use/def, out/in，对各结点的live-out/live-in变量进行倒序迭代求解。②列举各结点的successor，若某结点n的successor跟{n + 1}不完全相同，则需额外关注。③关注MOVE相关的语句（结点）。（2）①简化->合并->简化/溢出。②若结点溢出，则需寻找重写变量。假如某变量c在代码段开头就被定义，但是结尾才被使用，则将开头定义的c重写为c1，将结尾使用的c重写为c2，从而解决c长时间活跃但不真正起作用，跟其他变量产生大量冲突的问题。
【11.3-潜在溢出和实际溢出】①潜在溢出：其他结点完成染色后，该结点补回图中，可以染色。②实际溢出：其他结点完成染色后，该结点补回图中，不能染色。③结论：对无实际干涉的MOVE结点进行合并，可以降低实际溢出的可能性。
【13.2-指针反转算法】①寻找各记录及其子记录的标记顺序，画“标记树”。②各标记树实际上进行的是“前序遍历”，即先标记根结点，再依次标记子节点。③done表示各结点完成标记的field个数。④t为父节点，x为当前处理的记录，y为当前处理的field。