（1）什么是推导？什么是归约？
推导：用某条规则的右部替换该规则的左部
归约：用某条规则的左部替换该规则的右部
（2）什么是句型？什么是句子？
句型:如果符号串α是从开始符号S推导出来的，即有S⇒*α，α∈(ＶT∪ＶN)* ，则称α是G产生的一个句型
句子:如果S ⇒* α，且α∈ＶT* ，则称α是G产生的一个句子
（3）什么是0~3型文法？各由什么机器识别？
Ｇ = (ＶT，ＶN，Ｐ，Ｓ)是一个文法,α→β ∈ P
| 文法 | 描述 | 由什么机器识别 | |
| 0型 | G | 图灵机 | 无文法/短语结构文法PSG |
| 1型 | |α|≤|β|(除Ｓ→ε)的G | 线性界限自动机 | 上下文有关文法CSG |
| 2型 | α∈ＶN 的Ｇ | 不确定的下推自动机 | 上下文无关文法CFG |
| 3型 | 右线性文法：A→aB或A→a的G左线性文法：A→Ba或A→ａ的 G | 有穷自动机 | 正规文法 |
L(G)为2型/上下文无关语言（CFL）
Ｌ(G)为3型/正规集/正则集/正则语言（RL）
第三章 词法分析
词法分析器的基本任务： 识别单词（的种类）
单词的机内表示(种别码，属性值)
单词种类：关键字， 标识符，常量，运算符算术，关系，界限
（1）正规式、NFA和DFA之间的等价变换
（2）各类单词的状态转换图
第四章 语法分析
（1）什么是最左推导？什么是最右推导？
最左推导：每次推导都施加在句型的最左边的语法变量上。与最右归约对应
最右推导：（规范句型）每次推导都施加在句型的最右边的语法变量上。
（２）自顶向下分析的基本思想
基本思想：
寻找输入符号串的最左推导
试图根据当前输入单词判断使用哪个产生式
基本过程： 从根开始，按与最左推导相对应的顺序，构造输入符号串(Token)的分析树
（３）产生回溯的原因
文法中每个非终结符A的产生式右部称为A的候选式，如果有多个候选式左端第一个符号相同，则语法分析程序无法根据当前输入符号选择产生式，只能试探
（4）文法的改造：消除左递归、消除回溯
直接左递归的消除方法A→Aα|β ＝ A →βA′ A′→αA′｜ε
消除间接左递归：为非终结符编号，再采用代入法将间接左递，归变为直接左递归
消除回溯：提取左因子
（5）求FIRST(α) 的算法，求FOLLOW( A ) 的算法
FIRST(α) 的算法:
若X→Y…∈P ，且Y∈ＶN 则FIRST(X)= FIRST(X)∪FIRST(Y)；
若X→Y1…Yn∈P，且Y1...Yi-1⇒*ε： FIRST(X)= FIRST(X)∪…∪FIRST(Yk) ；
FOLLOW( A ) 的算法:
1) 将# 加入到FOLLOW(S)
2) 若A→αBβ， 则FOLLOW(B)=FOLLOW(B)∪FIRST(β)
3) 如果A→αB或A→αBβ，且β⇒*ε，A≠B， 则FOLLOW(B)=FOLLOW(B)∪FOLLOW(A)
Selct( i) 的算法:
（6）LL(1)文法的判定，LL(1)分析表的构造
LL(1)文法:同一非终结符的各个产生式的可选集互不相交
不存在终结符a，使得同一非终结符A的两个候选式αi和αj都能导出以a为首的串
同一非终结符的各个候选式中最多只有一个可以推导出空串
（7）LL(1)通用控制算法
LL(1)通用控制算法
repeat
X=当前栈顶符号;a=当前输入符号；
if X∈ＶT∪{#} then
if X=a then
if X≠# then {将X弹出,且前移输入指针}
else error
else
if M[X,a]=Y1Y2…Yk then{将X弹出;依次将Yk…Y2Y1压入栈；输出产生式X→Y1Y2…Yk }
else error
until X=#
（8）预测分析法实现步骤
预测分析法实现步骤
1）构造文法
2）改造文法：消除二义性、消除左递归、提取左因子
3）求每个变量的FIRST集和变量的FOLLOW集，从而求得每个候选式的SELECT集
4）检查是不是LL(1) 文法
5）构造预测分析表
6）实现预测分析器
（9）递归下降法的基本思想
递归下降法算法基本思想
为每个非终结符编制一个递归下降过程，过程名表示产生式左部的非终结符，过程体则是按该产生式右部符号串顺序编写的
每匹配一个终结符，则再读入下一个符号；
对于产生式右部的每个非终结符，则调用相应的过程
当一个非终结符对应多个候选式时，过程体将按可选集来决定选用哪个候选式
（10）LR分析器的工作过程
LR分析器的工作过程
1. 初始化:s0 # a1a2…an# 对应“句型” a1a2…an
2. 一般情况下 s0s1… sm #X1…Xm aiai+1…an#对应“句型” X1…Xmaiai+1…an
①If action[sm,ai]= si then 格局变为：s0s1… sm i#X1…Xmai ai+1…an#
②If action[sm,ai]= ri表示用第i个产生式A→Xm-(k-1)…Xm进行归约then 格局变为：
s0s1… sm-k#X1…Xm-kA aiai+1…an# 查goto表，当goto[sm-k,A]=i then 格局变为：
s0s1… sm-k I #X1…Xm-kA aiai+1…an#
③If action[sm,ai]=acc then 分析成功
④If action[sm,ai]=err then 出现语法错
分析器的四种动作
1) 移进：将下一输入符号移入栈
2) 归约：用产生式左侧的非终结符替换栈顶的句柄
3) 接收：分析成功
4) 出错：出错处理
（11）LR分析器主控程序(LR分析算法)
LR分析器主控程序(LR分析算法)
置输入指针ip 指向w# 的第一个符号；令s是栈顶状态， a 是ip 所指向的符号;分析栈中为# 和开始状态0
重复执行如下过程
if action[s,a]=si(shift i) then
{把符号a 和状态i先后压入栈；使ip 指向下一符号}
elseif action[s,a]=ri(reduce A→β) then
{从栈顶弹出2*|β|个符号； 令s′是现在的栈顶状态； 把A 和goto[s′,A]先后压入栈中；
输出产生式A→β}
elseif action[s,a]=accept(acc) then return
else error()；
（12）什么是句柄？句柄和产生式右部之间的关系
假设Ｓ⇒rm* αγβ（即αγβ 是句型），如果A→γ∈P，且Ｓ⇒rm* αＡβ ，则称γ是句型αγβ的相对于变量A的直接短语
最左直接短语叫做句柄(Handle)
规范句型的活前缀: 不含句柄右侧任意符号的规范句型的前缀
（13）LR(0)文法的判定，LR(0)分析表的构造
LR(0)项目: 右部某个位置标有圆点的产生式称为相应文法的LR(0)
文法G= (VN, VT, P, S)的拓广文法G’： G’=（VN∪{S’}，VT，P∪{S’→S}，S’）
LR(0)文法的判定:
如果I 中至少含两个归约项目，则称I 有归约—归约冲突（Reduce/Reduce Conflict）
如果I 中既含归约项目，又含移进项目，则称I有移进—归约冲突（Shift/Reduce Conflict）
如果I 既没有归约—归约冲突，又没有移进—归约冲突，则称I 是相容的(Consistent)，否则称I 是不相容的
对文法G，如果∀ I∈C都是相容的，则称G为LR(0)文法
LR(0)分析表的构造算法
设G’的LR(0)项目集规范族：{I0,I1,…,In}用i表示闭包Ii对应
的分析器状态(即相应的DFA状态)
1 0为开始状态
2 对Ii∈C：
if A→α.aβ∈Ii and go(Ii,a)=Ij then action[i,a]=sj
if A→α.Bβ∈Ii and go(Ii,B)=Ij then goto[i,B]=j
if A→α.∈Ii then for ∀a∈VT∪{#} do action[i,a]=rj
if S'→S.∈Ii then action[i,#]=acc;
3 所有空格置error
（14）SLR(1)文法的判定，SLR(1)分析表的构造
SLR(1)文法的判定: SLR(1)分析表无冲突的CFG
SLR(1)分析表的构造算法
设G’的LR(0)项目集规范族：{I0,I1,…,In}用i表示闭包Ii对应的
分析器状态(即相应的DFA状态)
1 0为开始状态
2 对Ii∈C：
if A→α.aβ∈Ii and go(Ii,a)=Ij then action[i,a]=sj
if A→α.Bβ∈Ii and go(Ii,B)=Ij then goto[i,B]=j
if A→α.∈Ii then for ∀a∈FOLLOW(A)do action[i,a]=rj ;
if S'→S.∈Ii then action[i,#]=acc;
3 所有空格置error
（15）LR(1)文法的判定，LR(1)分析表的构造
LR(1)分析表的构造算法
设G’的LR(0)项目集规范族：{I0,I1,…,In}用i表示闭包Ii对应
的分析器状态(即相应的DFA状态)
1 0为开始状态
2 对Ii∈C：
if [ A→α.aβ，b ]∈Ii and go(Ii,a)=Ij then action[i,a]=sj
if [ A→α.Bβ，b ]∈Ii and go(Ii,B)=Ij then goto[i,B]=j
if [ A→α. ，a ]∈Ii then action[i,a]=rj ;
if [ S'→S. ，# ]∈Ii then action[i,#]=acc;
3 所有空格置error
（16）语法分析的错误处理
预测分析中的错误恢复
错误恢复策略的基本思想
跳过一些输入符号，直到期望的同步记号中的一种出现为止
其效果依赖于同步记号集合的选择，这个集合的选择应该使得语法分析器能够迅速地从实际可能发生的错误中恢复过来
LR(0)不考虑后继符，SLR(1)仅在归约时考虑FOLLOW集
LR(1)在构造状态时就考虑后继符的作用：考虑对于产生式A→α的归约，在不同使用位置，A会要求不同的后继符号
第五章 语法制导翻译
（1）什么是语法制导定义SDD？什么是语法制导翻译方案SDT？SDD与SDT之间是什么关系？
语法制导定义（SDD）: 把一些语义属性附加到代表语言成分的文法符号上，通过与产生式相关的语义规则来描述属性的值
语法制导翻译方案（SDT）: 在产生式体中嵌入了程序片段（称为语义动作）的CFG
语法制导翻译方案（SDT）是语法制导定义（SDD）的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号｛ ｝括起来，可被插入到产生式右部的任何合适的位置上。
SDD：
是关于语言翻译的高层次规格说明
它隐蔽了许多具体实现细节
使用户不必显式地说明翻译发生的顺序
SDT：
指明了语义规则的计算顺序
以便说明某些实现细节
是对SDD的一种补充
（2）什么是属性文法？
属性文法：一个没有副作用的SDD有时也称为属性文法
属性文法的规则仅仅通过其它属性值和常量来定义一个属性值
（3）什么是综合属性？什么是继承属性？
综合属性: 节点N上的综合属性只能通过N的子节点或N本身的属性值来定义
继承属性：节点N上的继承属性只能通过N的父节点、N的兄弟节点和N本身的属性值来定义；
终结符可以具有综合属性，但是不能有继承属性
（3）什么是S-属性定义？什么是L-属性定义？
S-属性定义：仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义
L-属性定义： 一个语法制导定义SDD是L-属性定义，如果∀A→X1X2…Xn∈P，其每一个语义规则中的每一个属性要么是一个综合属性，要么是Xj(1≤j ≤ n)的一个继承属性，这个继承属性仅依赖于下列属性1.产生式中Xj的左边符号X1，X2，…Xj-1的属性；2. A的继承属性。
每一个S-属性定义都是L-属性定义
（5）L-属性定义的自顶向下翻译（在LL(1)语法分析过程中进行翻译、在递归下降语法分析过程中进行翻译）
L(1)语法分析过程中进行翻译：
程中完成翻译过程，其中的语法分析栈需要进行扩展，以存放语义动作和属性求值所需要的一些数据项（一般来说，这些数据项是属性值的复制）
除了那些代表终结符和非终结符的记录之外，语法分析栈中还将保存动作记录（action record）和综合记录（synthesize record）
在递归下降语法分析过程中进行翻译：
1. 为A的每一个继承属性都设置一个形参，函数的返回值是A的综合属性值
2. 对出现在A产生式中的每个文法符号的每个属性都设置一个局部变量
3. 对于每个动作，将其代码抄进翻译器中，并把对属性的引用改为对变量的引用
第六章 运行存储分配
（1）什么是栈式存储分配策略？
栈式分配策略是一种以过程为单位的动态分配方案
当一个过程（函数或方法）被调用时，用于存放该过程的局部变量的空间被压入栈；
当这个过程结束时，该空间被弹出这个栈
使用过程、函数或方法作为用户自定义动作的单元的语言，其编译器的运行时刻存储大多都采用栈式分配策略
这种安排允许活跃时段不交叠的多个过程共享存储空间
（2）什么是活动？什么是活动记录？活动记录主要由哪些内容构成，各字段的作用？
活动： 过程体的每次执行称为该过程的一个活动
活动记录：过程每执行一次，就为它分配一块连续存储区，用来管理过程一次执行所需的信息，这块连续存储区称为活动记录
活动记录主要由内容构成：
实参
返回值
控制链：指向调用者的活动记录
访问链：用来访问存于其它活动记录中的非局部数据
保存的机器状态
局部数据
临时数据
（3）符号表管理
符号表的内容
变量： 类型、地址、长度、形参标识、数组的内情向量
过程： 类型、入口地址、外部过程、声明处理、形实结合信息
常数： 类型、地址、值
第七章 中间代码生成
（1）声明语句翻译的任务是什么？
声明语句:用于对程序中规定范围内使用的各类变量、常数、过程进行说明
编译要完成的工作:在符号表中记录被说明对象的属性，为执行做准备
（2）数组引用翻译的任务是什么？
数组引用翻译的任务:1.完成上下界检查 2. 生成完成相对地址的计算代码
（3）各类语句的代码结构
（4）各类语句的翻译
| 语句 | 基本文法 | SDT/SDD |
| 赋值语句 | S → id := E|L := E E → E1 + E2|−E1 |(E1)|id|L L → id[E]|L1[E] | S → id := E |L := E{ gen( L.array.base ‘[’ L.addr ‘]’ ‘=’ E.addr ); } E → E1 + E2|−E1 |(E1)|id |L { E.addr = newtemp(); gen( E.addr ‘=’ L.array.base ‘[’ L.addr ‘]’ ); } L → id[E]{ L.array = lookup(id.name); L.type = L.array.type.elem ; L.addr = newtemp(); gen( L.addr ‘=’ E.addr ‘*’ L.type.width ); } |L1[E]{ L.array = L1.array ; L.type = L1.type.elem ; t = newtemp(); gen( t ‘=’ E.addr ‘*’ L.type.width ); L.addr = newtemp(); gen( L.addr ‘=’ L1.addr ‘+’ t ; } L.array：用来记录指向符号表中相应数组名字表项的指针 L.type：L生成的子数组的类型。对于任何数组类型t，t.elem给出其数组元素的类型 L.addr：指示一个临时变量，用于累加公式中的ij*wj项，从而计算数组引用的偏移量 |
| 布尔表达式 | B → B or B | B and B | not B | (B) | E relop E | true | false | B → B1 or B2 {B1.true:=B.true; B1.false:=newlabel(); B2.true=B.true; B2.false:=B.false; B.code := B1.code||label(B1.false)||B2.code } B → B1 or M B2 {backpatch(B1.falselist,M.quad); B.truelist:=merge(B1.truelist,B2.truelist); B.falselist := B2.falselist} M → ε{M.quad:=nextquad} B → not B1 {B1.true:=B.false; B1.false:=B.true； B.code :=B1.code } B → E1 rel E2 { B.code:= E1.code || E2.code ||gen(‘if’ E1.addr rel E2.addr ‘goto’ B.true)||gen('goto' B.false)} B → false{ B.code:=gen( 'goto' B.false) } B → true{B.truelist := makelist(nextquad) gen(‘goto _’)} |
| S → if B then S1 | if B then S1 else S2 | while B do S1 | S → if B then S1 else S2 {B.true := newlabel(); B.false := newlabel(); S1.next := S.next; S2.next := S.next; S.code :=B.code||label(B.true)||S1.code || gen(‘goto’,S.next)||label(B.false)||S2.code } S → if B then M S1 {backpatch(B.truelist, M.quad) S.nextlist:=merge(B.falselist, S1.nextlist)} | |
| S → while B do S1 {S.begin:= newlabel(); B.true := newlabel(); B.false := S.next; S1.next := S.begin; S.code:=label(S.begin)||B.code|| label(B.true)||S1.code|| gen(‘goto’, S.begin) } | ||
| S → call id (Elist) Elist → Elist, E Elist → E | S → call id ( Elist ) { gen(‘goto‘pc+Elist.num+1); for 队列q中的每一项t do gen(’param’ t ); gen(‘call’ id.addr’,’Elist.num); } Elist → E { Elist.num := 1; 建立队列q，并将E.addr 放入q } Elist →Elist1,E { Elist.num := Elist 1.num+1;将E.addr 放入队列q} | |
（1）什么是代码优化、代码优化的分类
代码优化： 编译时刻为改进目标程序的质量而进行的各项工作（ 空间效率，时间效率）
在代码中消除不必要的指令，或者把一个指令序列替换为一个完成同样功能的较快的指令序列
优化的分类
按优化语言级：1。 针对中间代码、2。针对机器语言
按优化范围：
局部优化：单个基本块范围内的优化
局部公共子表达式删除
计算强度削弱
全局优化：
全局公共子表达式删除
无用代码删除
基于循环的优化
循环不变表达式外提
归纳变量删除
计算强度削弱
（2）什么是基本块、如何划分基本块
基本块是满足下列条件的最大的连续三地址指令序列
控制流只能从基本块的第一个指令进入该块
除了基本块的最后一个指令，控制流在离开基本块之前不会跳转或者停机
基本块的划分
首先确定所有的入口语句
序列的第一个语句是入口语句
能由条件转移语句或无条件转移语句转到的语句是入口语句
紧跟在条件转移语句或无条件转移语句后面的语句是入口语句
每个入口语句到下一个入口语句之前的语句序列构成一个基本块
（4）什么是流图、如何构造流图？
流图是一种表示中间代码的方法。图中的结点表示基本块，流图的边指明了哪些基本块可能
紧随一个基本块之后运行 --前驱（predecessor）、后继（successor）
流图的构造
以所有的基本块为节点集合
有B1到B2的边(B2是B1的后继)当且仅当：
B2是紧紧跟随在B1后面的四元式，且B1的最后四元式不是无条件转向语句
B1的最后一个四元式有条件或无条件地转移到B2的第一个四元式
（5）什么是公共子表达式？
公共子表达式：如果表达式E先前已被计算过，并且从先前的计算到现在，E中变量的值没有改变，那么E的这次出现就称为公共子表达式
（6）什么是复制传播？
复制传播变换的思想是在复制语句f := g之后尽可能用g代替f
复制传播变换本身并不是优化，但它给其它优化带来机会： 删除死代码 常量合并
（7）什么是死代码？
死代码是指计算结果以后不被引用的语句
（8）什么是归纳变量？
归纳变量： 在循环中，如果变量i的值随着循环的每次重复都固定地增加或者减少某个常量，则称i为循环的归纳变量
（9）什么是强度削弱？
强度削弱: 用较快的操作代替较慢的操作，如用加代替乘
（10）基本块DAG图构造算法、基于DAG的基本块优化--无环有向图
基本块的DAG表示
叶节点表示一个出现在基本块中的变量的初值或常数，叶节点用标识符（变量名）或常数作为标记
内部节点n表示块中的一个语句s。内部节点n由语句s中用到的运算符来标记
n的子节点是那些在s之前最后一次对s中用到的操作数进行定值的语句所对应的节点
每个内部节点n有一个定值变量表，表示s是在此基本块内最晚对这些变量定值的语句
基本块DAG图构造算法
输入：一个基本块
输出：相应DAG图
算法说明：
通过逐个扫描四元式来逐步建立DAG图
函数node(x)表示最后给标识符x定值的节点
假设三地址语句为如下三种形式之一
(i)型： x:= y op z
(ii)型： x:= op y
(iii)型： x:= y
依次对基本块中的每个语句x:=y op z执行如下步骤。
如果node(y)没有定义，建立叶子节点，标记为y，让node(y) 等于这个节点。如果node(z)没有定义，为z建立叶子节点。
①如果语句为(i)型，查看是否存在标记为op的节点，且其左右子节点分别为node(y)和node(z)。如果找不到，建立这样的节点。无论是哪种情况，令n是所找到或建立的节点
②如果语句为(ii)型，寻找标记为op且子节点为node(y)的节点，如果找不到，建立这样的节点,并令n是这个找到的或创建的节点
③如果语句为(iii)型，则令n为node(y)
如果node(x)没有定义，则将node(x)设置为n,并把x加入到n的定值变量表中；
如果node(x)有定义，从node(x)的定值变量表中删除变量x，并把x加入到n的定值变量表中，并将node(x)设置为n
处理(i)型四元式的时候，如果op是满足交换率的运算符，可以允许其左右节点互换
（11）在构造基本块的dag时，对于数组、指针、和过程调用需要有哪些特殊的处理？
数组:对于形如a[j]=y的三地址指令，创建一个运算符为“[]=“的结点，这个结点的3个子结点分别表示a、j和y。
该节点没有定值变量表。
该结点的创建将杀死所有已经建立的、其值依赖于a的结点
一个被杀死的结点不可能再获得任何定值变量，也就是说，它不可能成为一个公共子表达式
指针: *p=y 进行一些全局指针分析，以便把p可能指向的变量在一个较小的范围内
杀死这些变量对应的节点，不需杀死其它节点
过程调用: 在缺乏全局数据流信息的情况下，必须假设一个过程调用使用和改变了它所访问的所有数据. 因此，如果变量x在过程p的访问范围之内，对p的调用将杀死x对应的节点
（12）变量获得值的方式都有哪些？
变量获得值的方式: 通过输入语句 通过赋值语句 通过过程形式参数
（13）什么是到达定值？
到达-定值:如果存在一条从紧随在定值d后面的点到达某一程序点p的路径，而且在此路径上d没有被“杀死”（即在此路径上没有对变量x的的其它定值），则称定值d到达程序点p。这表明，在p点使用变量x的时候，x的值可能是由d点赋予的。
到达定值分析的主要用途
代码外提中的循环不变量检测
判定x在p点上的值是否为常量
判定x在p点上是否未经定值就被引用
（14）什么是引用-定值链？如何构造引用-定值链？
引用-定值链（ud）：设变量x有一个引用u，变量x的所有能够到达u的一切定值称为x在u处的引用-定值链，简称ud链。（是一个集合）
如果B中变量x的引用u之前有x的定值d，且这个定值能够到达u，则u的ud链是{d}
否则，u的ud链就是IN[B]中x的定值集合
（15）什么是活跃变量？
对于变量x和流图上的某个点p，如果在流图中沿着从p开始的某条路径可以引用x在p点的
值，则称变量x在点p是活跃变量，否则称x在点p不活跃。
主要用途： 寄存器分配 删除无用赋值
（16）什么是定值-引用链？如何构造定值-引用链？
定值-引用链：设变量x有一个定值d，该定值所有能够到达的引用u称为x在d处的定值-引用链，简称du链
主要用途 复制传播
构造定值-引用链：
如果在求解活跃变量数据流方程中的OUT[B]时，将OUT[B]表示成从B的末尾处能够到达的
引用的集合，那么，可以直接利用这些信息计算基本块B中每个变量x在其定值处的du链
如果B中x的定值d之后有x的第一个定值d’，则d和d’之间x的所有引用构成d的du链
如果B中x的定值d之后没有x的新的定值，则B中d之后x的所有引用以及OUT[B]中x的所有引用构成d的du链
（17）什么是可用表达式？
可用表达式的定义：如果从流图的首节点到达点p的每条路径上面都有对x op y的计算，并且从最后一个这样的计算到点p之间没有再次对x或y进行定值，那么表达式x opy在点p是可用的(available)。
表达式可用的直观意义：在点p上，x op y已经在之前被计算过，不需要重新计算。
可用表达式信息的主要用途：消除全局公共子表达式
（17）到达-定值数据流方程、活跃变量数据流方程、可用表达式数据流方程
| 数据流分析的种类 | 数据流方程 |
| 到达-定值数据流 | IN[B]= ∪P是B的一个前驱OUT[P] B≠ENTRY OUT[B]=fB (IN[B])= genB ∪(IN[B]-killB ) B≠ENTRY OUT[ENRTY]=φ d：u = v + w 定值d的传递函数fd： fd (x）= gend ∪(x-killd ) gend ={d} killd →程序中所有其它对变量u的定值 gen(B)基本块中没有被块中各语句“杀死”的定值集合 kill(B) 被基本块B中各个语句杀死的定值的集合 |
| 活跃变量数据流 | OUT[B]= ∪S是B的一个后继IN[S] B≠EXIT IN[B] = useB∪(OUT[B]-defB ) B≠EXIT IN[EXIT] = φ useB： 在基本块B中引用，但是引用前在B中没有被定值的变量集合 defB： 在基本块B内定值，但是定值前在B中没有被引用的变量的集合 |
| 可用表达式数据流 | OUT[ENTRY]= φ IN[B]= ∩P是B的一个前驱OUT[P] B≠ENTRY OUT[B]= e_genB ∪(IN[B]- e_killB ) B≠ENTRY for(除ENTRY之外的每个基本块B)OUT[B]= U e_genB 的计算 初始设置： e_genB = φ ； 顺序扫描基本块的每个语句：z = x op y 把x op y加入e_genB 从e_genB中删除和z相关的表达式 e_killB 的计算 初始设置： e_killB = φ ； 顺序扫描基本块的每个语句：z = x op y 把所有和z相关的表达式加入到e_killB 中 从e_killB 中删除表达式x op y |
支配节点： 如果从流图的初始节点到节点n的每条路径都经过节点d，则称节点d支配节点
n，记为d dom n。任何节点都是自己的支配节点
（19）什么是回边？
回边： 假定流图中存在两个节点d和n满足d dom n。如果存在从节点n到d的有向边n->d，那么这条边称为回边
（20）什么是自然循环？如何识别自然循环？
自然循环：满足以下性质的循环
有唯一的入口节点，称为首节点（header）
首结点支配循环中的所有结点
循环中至少有一条返回首结点的路径
自然循环是一种适合于优化的循环
自然循环的识别：根据回边识别自然循环
在流图中，给定一个回边n->d，与这个回边对应的自然循环为：d，以及所有可以不经过d而到达n的节点。d为该循环的首节点。
（21）如何消除复制语句？
对于复制语句d: x=y，如果d的引用点u满足下列条件，那么可以在u点用对y的引用代替对x的引用
u的ud链只包含d（即d到达u的唯一的x的定值）
从d到达u的路径（可以穿过u若干次，但是不可以第二次穿过d）上，没有对y的定值。
如果x的所有引用都满足上述替换条件，那么可以删除复制语句x:=y
有效复制语句数据流方程
OUT[ENTRY]= φ
IN[B]= ∩P是B的一个前驱OUT[p] B≠ENTRY
OUT[B]= c_genB ∪(IN[B]- c_killB) B≠ENTRY
c_genB在基本块B中的所有复制语句x=y，并且从该语句开始到B的出口，x和y都没有再定值。
c_killB:包含了所有在流图中出现并且满足下列条件的复制语句x=y：B中存在对x或者y的定值，并且之后在没有复制语句x=y出现。
（22）如何识别循环不变计算？
循环不变计算检测算法
输入：循环L，已经建立的ud链
输出：循环不变计算语句
方法
步骤1：将下面这样的语句标记为“不变”：语句的运算分量或者是常数，或者其所有定值点都在循环外部。
步骤2：重复执行下面的步骤，直到某次没有新的语句可标记为“不变”为止：
将下面这样的语句标记为“不变”：先前没有被标记过，且运算分量要么是常数，要么其ud链中的定值点在循环外，或者该定值点已经被标记为“不变” 。
（23）循环不变计算外提的条件有哪些？
将循环不变语句s: x=y+z外提的条件
(1)s所在的基本块是循环所有出口节点（有后继节点在循环外的节点）的支配节点
(2)循环中没有其他语句对x赋值
(3)循环中x的引用仅由s到达
不考的内容
3.3.1扫描器的数据流图
3.3.2模块结构图
3.3.4状态转换图的程序实现
3.4 词法分析错误类型不考，但错误恢复策略需掌握
4.6 算符优先分析法下载本文
