compile

编译

五大组成部分

1. 词法分析：将程序文本拆分成字符或tokens， 跟据语言词法规则分析并识别单词，并以相应的编码方式输出(四大类单词：标识符、关键字、常量、运算符)。
2. 语法分析:根据语言的语法规则，识别单词之间的关系，并生成语法树，并进行语法检查。
3. 语义分析\生成中间代码：检查语义错误，如类型检查、作用域检查等，并生成中间代码(便于优化、编译程序的移植(LLVM)，常用：四元式、三元式和逆波兰式等)。
4. 优化：减少内存使用或使程序运行的更快。
5. 目标程序生成，生成目标程序
   编译程序中都需要包括符号表管理(建表和查表)和错误处理模块。

概念

源程序是翻译程序的输入、目标程序是其输出；
汇编程序和编译程序都是翻译程序，前者是将汇编语言转为机器码，但后者是将高级语言转换。
解释程序(python)：对源程序进行解释执行程序。
编译-解释程序(java)：先编译后将源程序中间形式进行解释执行。

遍(PASS)

对源程序从头到尾扫描一次并做相应加工处理，生成新的源程序中间形式或目标程序，为一遍。扫描几次能够完成5个阶段就称为几遍。
分为单遍和多遍编译器。是否分遍，视具体情况而定(内存大小、语言复杂度等)。分遍后带来的主要缺点就是增加了不少重复性工作(如每一遍输入和输出都要进行文件的读写)。

前后端

前端与源语言有关(词法,语法,语义,中间代码生成和代码优化)，后端与目标机器有关(目标程序生成)。

前后处理器

前处理器：对源程序进行预处理，如C语言中的宏替换、文件包含等。
后处理器：对目标程序进行后处理，如汇编程序中的符号地址替换等。

cool

抽象、静态键入、复用(继承)、内存管理

语义分析

中间代码

四元式

分成四个部分：运算符、两个操作数(运算符左右两边)和结果(一般为编译程序引入的临时变量)。

文法和语言

文法的形式定义

文法G=(N, T, P, Z)
N:非终结符集合(变量)
T:终结符集合(字母表)
P:产生式集合(规则)
Z:开始符号(文法的起点)
参见OO。
文法G[Z]作为规则的非空有穷集合，其中Z为文法的开始符号。
所有规则中，左边只能是非终结符，右边可以是终结符和非终结符的任意组合。
规则左右部所有符号组合文法的字汇表V。

BNF范式

巴科斯-诺尔范式，非终结符用尖括号括起来表示，终结符直接写出。
元符号::=表示“定义为”，|表示“或”，ε表示空串。

EBNF范式

推导

直接推导

从一个字符串直接应用某一条产生式得到另一个字符串。
记为A=>B，表示A直接推导出B。

间接推导

通过一系列直接推导得到的推导。
记为A=>B=>C，表示A间接推导出C。
A=>*B，表示A经过零次或多次推导得到B。
A=>+B，表示A经过一次或多次推导得到B。

语言

语言L(G)是由文法G生成的所有句子的集合。

句型

Z=>*w(w∈(TUN)*)，则称w为文法G的句型。可以是空串、终结符和非终结符的任意组合。

句子

Z=>+w(w∈T*)，则称w为文法G的句子。只能是终结符的任意组合。

规范推导(最右推导)

在推导过程中，如果每一步都只应用某一条产生式，而不进行任何其他操作，则称这种推导为规范推导。
xUy=>xuy,y∈T*，则称xuy为xUy的规范推导式。即U为推导式中最右边的非终结符，y为U的推导式。
记为xUy=|=>xuy。

等价文法

两个文法G1和G2，如果它们生成的语言相同，则称它们是等价的，记为L(G1)=L(G2)。

递归规则与递归文法

左递归文法不能使用自顶向下的方法进行语法分析。
递归文法(自嵌入递归文法,U->...U...)、左递归(U->U...)、右递归(U->...U)

短语、简单短语和句柄

对于文法G=(N,T,P,Z)的句型w∈L(G)，w的任意子串u，
如果存在推导Z=>*xUy=>+xuy，则称u为w的短语。
若存在推导Z=>*xUy=>xuy，则u是句型w相对于U的简单短语。
省流：短语是其前句型中某个非终结符所能推出的符号串。
任何句型本身一定是相对于识别符号Z的短语。
任一句型的最左简单短语为该句型的句柄。
短语或简单短语是相对于句型而言，一个句型可能有多个短语、简单短语，但只有一个句柄。

语法树

句子结构的图示表示法，一种有向图，由节点和有向边组成。
根节点为识别符号；中间节点为非终结符；叶节点为终结符或非终结符。
有向边指****节点间的派生关系。
对于给定文法和句型，可以建立推导序列和语法树。

一个重要事实：文法产生的句子可用不同的推导原则(产生式顺序不同)将其推导出来，生成规律不同，但最终生成语法树形状完全相同。
不过某些文法有，其余则没有，二义性问题。
语法树中某节点(子树的根)连同其向下派生的部分组成。
某棵子树末端节点从左至右顺序排列为该句型的相对于子树根的短语。
短语中所有成分节点的父节点与其组成的子树高度为2的为简单短语。
所有简单短语中在语法树上最左边的简单短语为句柄。
具体参考B站视频

自下而上修剪子树的末端节点，直至将整棵树只剩根，每剪一次对应一次规约。
对句柄进行的规约称为规范规约。
规范规约和规范推导互为逆过程。
通过上两种方式得到的句型为规范句型。
若某个文法的某规范句型的句柄不唯一，则该文法有二义性否则无二义性。
文法二义性的判断方式：1.一个文法的某一句子存在两颗不同的语法树或者存在两个不同的规范推导；2.一个文法的某规范句型的句柄不唯一。
理论上，文法的二义性不可判定。
现只能通过提出一些限制条件当作无二义性的充分条件。
或者通过确定一种编译算法，其满足无二义性的充分条件。
若某文法中无有害规则或多余规则，则称其为压缩过的。
通过对于产生式施加不同的限制分为4种文法和语言：

• 0型P:u->v,u∈V+,v∈V*，短语结构文法，左右均可为符号串，一个短语可产生另一个，这种语言可用图灵机接受。
• 1型P:xUy->xuy,U∈Vn,x、y、u∈V*，上下敏感文法，与上下文有关，该语言可由一种线性界限自动机接受。
• 2型P:U->u，上下文无关文法，与BNF表示等价，这种语言可由下推自动机接受。
• 3型正则文法，是在2型文法上进一步限制，该语言可被有穷自动机接受。
• 0型文法可产生所有型语言，2型文法只可产生2、3型语言，3型只产3型语言。

符号串的分析

自顶向下分析

顾名思义，即从识别符号开始，判断是否能够建立起一个推导序列使识别符号可以推导出该符号串。

自底向上分析

能若建立一个规约过程将该符号串变为识别符号，则该符号串也是文法的合法句子。

词法分析

根据词法规则(大多数程序语言是乔姆斯基的3型文法，即正则文法)识别并组合单词，进行词法检查，实现对数字常数完成字符串到数值的转换以及删去空格字符和注释的要求。

词法分析程序的自动生成

正则表达式，等价于3型文法

有穷自动机(DFA)

一个DFA M 由如下五元组组成，S(有穷状态集)、Σ(输入字母表，不含空串)、б(映射函数，即状态转移函数)、s0(初始状态)、Z(终止状态集)
规则可以用状态机来解释
若存在一条从初始状态到某一终止状态的路径，且该路径上所有弧的标记符连接成符号串α，则称α为DFA M识别。

简化，极小化

对任一个DFA，存在一个唯一的状态最少的等价的DFA。
一个有穷自动机可通过消除多余状态和合并等价状态转换成最小的与之等价的有穷自动机。
从初始状态经过任意输入都无法经过的状态即为多余状态。
等价状态<=>两个状态满足两个条件：1.一致性条件：两个状态必同时为可接受或不接受状态；2.蔓延性条件，所有输入符号，两状态必转换到等价的状态里。
则对所有输入符号c，Ic(s)=Ic(t)，则状态s、t对于c有相同的后继，称s和t等价
可以使用”分割法”，得到极小化的DFA，将DFA(不含多余状态，因此现要对DFA进行多余状态的去除)的状态分割成一些不相关的子集，使得任何不同的两个子集状态可区别，同一个子集中的任何状态都是等价的，可以先按照是否为终态划分为两个分区并标号，然后在每个分区内求解每个状态的Ic，若与分区内其他状态则另立山头，和臭味相投的自成一区。

非确定的有穷状态机(NFA)

若映射函数是为多值函数，且输入可允许为空，则该有穷自动机不确定，即对某个输入字符存在多个后继状态。

NFA的确定化

找到和NFA等价的DFA。

集合I的空闭包

对于一个状态集的子集I来说，定义其空闭包为满足下列任意规则的元素的集合:1.属于集合I；2.集合I中的元素s所能经过任意条空弧达到的任何状态。
也就是集合I本身和其内所有元素通过空串得到的所有状态的并集。

状态子集Ia

Ia=J的空闭包，其中J为从状态子集I中的每个状态出发，经过标记为a的弧所到达的所有状态集合。
也就是某一个子集合能过通过标记为a的弧达到的空闭包。

确定化方法

则求解方法即为先求出起始状态的空闭包，将其作为初始空闭包，然后求出通过每一种不为空的标记的弧求出的空闭包，对于每个新出现的空闭包，再次按照上述方式求解其余空闭包，最终，直到不再出现新的空闭包，即，通过上述方式重新创建许多不同的空闭包，作为新的不含空弧的状态点，显然，这样转化后就为一个等价的DFA。
其中**包含原起始状态的新空闭包即为新的DFA的起始状态，包含原终止状态的新

空闭包即为新的DFA的终止状态**。
在输入集合上的一个字集V是正则集合<=>存在一个DFA M，使得V=L(M)

有穷自动机=>正则文法

算法：

1. 对转换函数f(A,t) = B，可写一个产生式：A->tB，也就是A节点存在一个标记为t的边指向B
2. 对可接受状态，即终止状态Z，增加产生式:Z->空
3. 文法的开始符号为有穷状态机初态、终结符号集为有穷自动机字母表

正则文法=>有穷状态机

1. 字母表与文法的终结符号同
2. G中每个非终结符生成一个M的状态，开始状态为开始符号
3. 增加新状态Z作为终止状态
4. 对G中的形如A→tB，其中t为终结符或ε, A和B为非终结符的产生式，构造M的一个转换函数f (A, t) = B。
5. 对G中的形如A→t的产生式，构造M的一个转换函数
   f (A, t) = Z，其中t为终结符或ε。
6. 将上述画出的NFA进行确定化

正则式=>有穷自动机

具体方式详见ppt，类似递归子程序法，不过这里是递归子NFA法，从内NFA逐层向外。



然后再进行NFA的确定化即可

NFA=>正则式

1. 在M一首一尾加两个结点x、y，其中x用空弧连M所有初态，M所有终态用空弧连y，形成与M等价的M’
2. 通过如下规则逐步消除M中所有节点，直至剩下x和y，删点过程中用正则式标记弧，最终的结果即为目标正则式：
   

正则文法=>正则式

使用如下规则，直至产生式右侧不含非终结符：

A->xB,B->y => A=xy
A->xA|y => A = (x)*y
A->x,A->y => A = x|y

正则式=>正则文法发

1. 对正则式r，选一个非终结符S作为标识符，生成产生式S->r
2. 对于正则式x、y根据上一条反过来生成相应的正则文法

大致有两种

词法分析单独作为一遍

后几遍去进行语法分析等操作。
结构清晰但效率低。

词法分析程序作为单独的子程序

高效但考虑较为复杂，例如可以作为语法分析的一个子程序。

一个完整的状态图

语法分析

将词法单元序列，根据上下无关文法输出抽象语法树。
本质上是去判断某个句子是否属于某个文法的语言。
有自顶向下和自底向上两种方法，前者主要使用递归子程序法，而后者主要使用算符优先分析法和LR分析法。
对前者来说就是从识别符号出发，去寻找一个推导序列使其推导出该句子，通常是需要进行回溯处理的(效率低下，且其余同时进行的工作也要推倒重来)，显然这样的规则并不适用于左递归文法，因此需要使用消除直接左递归：(1).使用扩充的BNF表示改写文法：1.提因子(提的是左侧共同的因子：xt|xw|...|xz -> x(t|w|...|z))，2.将有一个直接左递归的右部置于最后并进行相应的改写：U->x|y|..|z|Uv<=>U->(x|y|..|z){v}；(2).改写为右递归文法：P->Pa|b <=> P->bP'、P'->aP'|ε。
对后者来说就是从该句子出发，去寻找一个规约序列使其规约为识别符号。

自顶向下分析

主要问题是：左递归和回溯问题。
分析过程即是建立一棵末端节点能够与指定符号串相匹配的语法树。
由于分析过程是试探性的，因此难免失败，也就存在回溯的过程，这样效率较低。

左递归问题原因

假如刚好要使用U->Ua的规则进行匹配，则从词法分析的角度来看，无法很好的使用递归下降的方式来分析U的匹配，即将不断循环匹配U，无法终止。
对于间接或者一般左递归，先将其转化为直接左递归，然后再根据直接左递归的消除方法。

回溯问题

产生原因：文法中某个非终结符规则右部有多个选择而不能一次性匹配到所需要的表达式，就可能出现回溯。
什么样的文法尽可能减少回溯，回溯是由于右侧有多个化为终结符后的符号串的最左符号相同导致的存在多种可匹配选项，因此若能够确保所有选项的最左符号都唯一匹配一种形式，这样每次匹配只能选择唯一的方式进行匹配。
定义对于U->a1|a2|...|an，有FIRST(ai) = {a|ai=*>a···,a∈Vt}(此处的a···代表了化为最终只有终结符的句子)。
因此，若想要避免回溯，因此保证对于每个规则的右侧每个选项的FIRST都两两不相交即可。
符合不带回溯的自顶向下分析的文法：1.非左递归；2.文法的任一非终结符，规则右部有多个选择时各选择推出终结符号串的头符号集合两两不相交。特殊的，若该非终结符可推导出空串，则还要考查其后继符号集合。

LL分析法

分析表的构造

FIRST集

a=X1X2X3…Xn，求FIRST(a)

1. 若Xi∈Vt，则FIRST(Xi) = {Xi}
2. 若Xi∈Vn
   1. 且Xi -> a…|ε，且a∈Vt，则FIRST(Xi) = {a , ε}
   2. 且Xi ->y1y2…yn，则按如下顺序计算，
      1. 若ε !∈ FIRST(y1)，则将FIRST(y1)加入Xi的first集
      2. 若ε∈FIRST(y1)，则将FIRST(y2)-{ε}加入…
         1. 若ε∈FIRST(y2)，则将FIRST(y2)-{ε}加入…
         2. …同理下推
         3. 若ε∈所有yi的FIRST集，则将s加入…，进而计算a的FIRST集

按上述方式从下往上计算。

FOLLOW集

连续使用以下规则，直到不再扩大

1. 若S为识别符号，则将#加入FOLLOW(S)
2. 若A->aBb(b!=ε)，则将FIRST(b) - {ε}加入FOLLOW(B)中
3. 若A->aB或A->aBb，且b-*->ε，则将FOLLOW(A)加入FOLLOW(B)中

分析表构造方法

A->ai为文法中任意一条规则，a为任一终结符或#。

1. 若a∈FIRST(ai), 则将A->ai加入M[A, a]中，代表A在栈顶，输入符号是a，选择ai去匹配
2. 若ai=ε或ai=+=>ε，且a∈FOLLOW(ai)，则A->ε放入M[A, a]中，代表A已匹配输入串成功，其后继符号终结符a由A后的语法成分匹配
3. 将所有无定义的M[A, a]标上error

文法G是LL(1)文法的充要条件

对G的每个非终结符A的任意两条规则A->a|b，下列条件成立：

1. FIRST(a) ∩ FIRST(b) = 空
2. 若b=*=>ε,则FIRST(a) ∩ FOLLOW(A) = 空
   因为这两条可以保证分析表中同一格内的唯一性，否则存在两种规则可以填入一格将产生冲突。

LR

活前缀的有效项目集，就是当栈内的符号是这个活前缀的时候，可能运用的下一步的最左规约的规则。

符号表管理技术

定义

编译过程中，用于记录用户设定的特定的信息，各种名字的表，也称名字特性表。如：程序名、变量名、用户定义类型名等。

建表查表

填表：分析到程序中的说明或定义语句时，将相关说明或定义的名字及相关信息存入符号表中。
查表：1.填表之前，避免名字在同一作用域下一致。2.
必要性：用户通过声明语句声明名字，将其各类信息存入表中，此后引用到该名字时，需要通过查表来判断语义正确性，判断此处引用是否正确。

组织方式

1. 统一符号表，按照信息量最大的名字设计表项结构。
2. 对不同种类的名字分别建立符号表，可节省空间，但查表和填表不便。
3. 折中法，大部分共同信息组成统一格式的符号表，特殊信息另外存表，通过指针连接。

非分程序语言

模块内不可嵌入子模块。
FORTRAN语言，通过类似函数的实参形参和公共区来进行数据交换。
构建全局符号表(子程序、函数名和公共区变量名)和局部符号表(查本单元局部符号表有无同名变量)。
查表时先查当前的局部符号表，再从全局符号表中查找，若均没有则报错。
程序单元结束释放相应符号表，整个程序执行结束，释放全局符号表。

分程序语言

模块内可嵌入子模块。
标识符作用域：1.模块中定义标识符的作用域是定义该标识符的子程序。2.过程或函数说明中定义的标识符(含形参)，作用域为本过程体。3. 循环内的标识符作用域为循环体。
程序声明读到标识符填表。
语句中读到标识符查表。
标准标识符的使用(一些库函数，如sin、abs等)，预先填入最外层名字表中。
通过栈的数据结构来实现，对于多层嵌套并并列程序的程序体的符号表进行识别。

注意，对于函数名和函数参数应该是位于不同层的符号表，函数参数位于该函数的符号表中，而函数名位于定义该函数的那一层符号表中。
符号表构造方法：在扫描具有嵌套分程序结构的源程序时，总是按先进后出的顺序来扫描各个分程序，设置一个临时工作栈，每当进入一层分程序就在栈顶预构造该分程序的符号表，遇到结束符时，其该分程序的全部项都位于栈顶，再将其全部登记项移入正式符号表中，注意：此处需要将该分程序的信息，例如：如果有形参要求，则需要将相应参数需求放入上一层程序的符号表中。

运行时的存储组织及管理

特指：目标程序运行时所需存储空间的组织与管理以及源程序中变量存储空间的分配。

静态存储分配

在编译阶段由编译程序实现对存储空间的管理和为源程序中的变量分配存储的方法：针对于那些编译时可以确定数据空间大小且运行时不改变的。
分配策略：用简单方法分配目标地址：1.开辟数据区；2.按编译顺序给每模块分配存储；3.模块内按顺序给变量用相对地址分配存储；4.目标地址填入变量符号表。这种方式不允许指针或动态分配，不允许递归调用过程。

数据区分配类似如上。

动态存储分配

目标程序运行阶段由目标程序…
运行时分配，编译时生成进行动态分配的目标指令。
对分程序且允许递归调用语言，常使用栈式动态存储分配，使用一个类似堆栈的“运行栈”实现分配，进入一个过程(程序模块)时在栈顶为其分配一个数据区(常称为活动记录(AR))；反之撤销。

活动记录

包含保存局部于该程序模块的变量的值必需的存储空间。开始位置称为基。
分为以下三部分(从上至下，一般为高地址向低地址)：局部数据区、参数区和display区。

局部数据区

存放模块中定义的各个局部变量。

参数区

存放显隐式参数，从上至下为形参数据区(显式，存放实参值或地址)、prev abp(存放调用模块记录基地址，用于在函数执行完时，重指回调用前的位置)、ret addr(返回地址，调用语句的下一条指令地址)、ret value(函数返回值)

display区

存放各外层模块活动记录基地址。
变量一般使用二元地址(BL, ON)，BL代表所在层次、ON表示形参数据区开始位置的偏移
类似于下图的形式：

如何构建第j层的display

假设由第i层程序调用第j层程序，则若j==i+1，则复制i层display然后增加一个第i层即可；若j<= i，则将i``display中的前j-1个复制即可。

运行时地址计算

假设访问变量地址：(BL,ON)，则在LEV层的地址计算公式：

if BL == LEV then
    addr := abp(当前活动记录基指针值) + (BL - 1) + nip + ON
else if BL < LEV then 
    addr := display[BL](当前活动记录display区中的第BL个元素) + (BL - 1) + nip + ON
else
    error
// BL:变量声明所在层次，用其寻找该层数据区起始地址，(BL - 1) 大致为display区大小，nip为隐式参数区大小，可参照活动记录的分布图来理解

中间表示

**便于移植(将前端独立出来了)、便于优化(与源语言和目标机器无关)**。

波兰表示

根据表达式的中缀表达式翻译成波兰表示可以使用类似算符优先分析的方法：遇操作数直接输出；遇操作符和操作符栈顶比较优先级，高则外入栈，低则输出栈顶，继续比较直至外入栈。

N-元表示

每条指令由n个域组成，通常第一个域代表操作符，其余为操作数。常用为三、四元式。例如：三元式(操作符、左操作数、右操作数)、四元式(操作符、操作数1、操作数2、结果(一般为临时变量))

特殊四元式SSA

静态单一赋值,主要特征每个变量只赋值一次.
优点:1.可以简化优化,例如:单一赋值可以帮助分析出哪些无用变量赋值可以省略,或者哪些寄存器作用域并未相交则可以节省开的寄存器数.

抽象机代码

P-code抽象代码，抽象机常是虚拟的一台堆栈计算机(若干寄存器、一个保存程序指令的储存器和一个堆栈式数据及操作存储)。
PC——程序计数器、NP——New指针，指向存放NEW生成动态数据的堆顶部、SP——运行栈指针，存放所有可按源程序的数据声明直接寻址的数据、BP(abp)——基地址指针，指向当前活动记录的起始位置指针。

其他形式中间代码

二叉树表示

抽象语法树，树形图，操作数在叶节点，操作符在中间节点。

图表示

DAG图

三地址码

都可分解为一个四元组，每个陈述都含有三个变量,书中间节点由临时变量(类似于四元式)表示,是语法树或DAG图的线性表示.

错误处理

局部化处理

将错误尽可能限制在一个局部范围内。

一般原则

诊断到错误时，暂停对后续符号的分析，跳过错误所在的语法成分(最小范围内进行跳过)，然后继续向下分析。

实现(递归下降法)

使用CX全局变量，存放错误信息。
递归下降时，遇到错误将错误信息送入CX再转出错误处理程序打印相关的错误信息。
原则：在保证出错位置被正常跳过的前提下，跳过的越少越好。

语法错误

不符合语法(含词法)规则的错误。

语义错误

不符合语义规则或超越限制，如数大溢出，符号表溢出、标识符未声明就引用、实参形参个数不对等等

遏制重复错误信息

方法：1. 建立一张错误信息表，每次打印时判断其是否已经被打印过；2.为各数据区设置

语义分析和代码生成技术

活动序列

活动序列：由翻译文法(插入动作符号的文法)推导出的符号串，由终结符和动作符号组成。
若翻译任务只是将中缀表达式变换为波兰后缀表示，那么只需在文法中插入相应的动作符号即可。
抽去动作符号得到输入序列。抽去输入序列，得动作序列，执行动作序列即可完成翻译工作。
作为上下文无关文法，翻译文法的终结符号集由输入符号和动作符号组成。
只进行输出动作符号后的字符的文法称为符号串翻译文法。
语法制导翻译：按翻译文法进行的翻译，对于给定输入符号串，根据翻译文法获得翻译该符号串的动作序列并执行其规定的动作过程，通过在文法的适当位置插入语义动作符号，当按文法分析到动作符号时调用相应的语义子程序，完成翻译任务。
翻译文法所定义的翻译是由输入序列和动作序列组成的对偶集。

属性翻译文法

属性

综合属性

求值规则：自右向左，自底向上，属性值可以依次传递。向上的箭头表示属性计算是自底向上的，属性变量名局限于每个产生式，可使用不同的名字。

继承属性

求值规则：自左向右，自顶向下。
继承前面符号的值，属性值从左边到右边，从上到下，

L-属性翻译文法

要求输入文法为LL(1)文法，用自顶向下分析方法构造分析器，分析过程进行属性求值。
LL(1)文法：

• 无左递归
• 不带回溯
• A->a|b，若b-*>ε，则FIRST(a)∩FOLLOW(A)=空

该翻译文法满足：

1. 终结符、非终结符和动作符号都有属性，每个属性有一个值域。
2. 终结符属性只有综合属性(词法分析提供)，其他两类的属性可分为继承属性和综合属性。
3. 开始符号的继承属性有指定初始值，输入符号/终结符号的每个综合属性有指定初始值(为了能够顺利计算规约，自顶向下和自底向上)
4. 求值规则如下：
   1. 对于继承属性：1.产生式左部非终结符的继承属性值取决于此前产生式右部该符号已有继承属性值；2.产生式右部符号(非终结符、动作符号)的用该产生式左部符号的继承属性或出现在该符号左边的右部符号的属性值进行计算。(继承属性箭头向下，因此产生式左边的继承属性值向右边传递，那最左边的只能由上部传递了)
   2. 对于综合属性：1.产生式右部非终结符的，取自其后产生式左部同名非终结符综合属性值；2.产生式左部非终结符的，用该产生式左部符号的继承属性或者某些右部符号的(任意)属性进行计算；3.动作符号的综合属性用该符号的继承属性或某些右部符号的(任意)属性计算。(同理，综合属性箭头向上，因此产生式右边的综合属性值向左边传递，产生式右部的非终结符综合属性只能由下面的综合属性传递上来。)
      
5. 一般来说，对出现在产生式右边的继承属性和出现在产生式左边的综合属性必须提供一个求值规则。

SL-ATG简单赋值形式的L-属性翻译文法

一个L-属性翻译文法，若其所有属性的求值规则均为简单赋值形式，则称为SL-ATG。
当且仅当：

1. 产生式右部符号的继承属性是一个常量，为左部符号的继承属性值，或为出现在所给符号左边某个右部符号的综合属性值。
2. 产生式左部非终结符综合属性为常量，等于自身的继承属性值或右部某个符号的综合属性值。
   目的是为了，使除了动作符号外，其余符号的属性求值规则右部是属性或是常量。

翻译文法的自顶向下翻译——递归下降翻译器

按翻译要求，在文法中插入语法动作符号，在分析过程中调用相应的语义处理程序，完成翻译任务。

属性翻译文法的自顶向下翻译——递归下降翻译

对每个非终结符都编写一个翻译子程序，根据其拥有的属性数目设置相应的参数：继承属性声明为赋值形参(传递实参值)、综合属性声明为变量形参(传地址，保证子程序返回时有值，作为动作子程序的返回值，由return语句返回)。
关于属性名有如下约定：

1. 有相同值的属性名相同
2. 产生式左部的同名非终结符用相同属性名，有简单赋值形式的属性变量名取相同的属性名，可删去属性求值规则。

语义分析

1. 上下文有关分析：即标识符的作用域。上下文有关文法构造困难且分析器十分复杂，分析效率低不实用。一般使用专门的语义动作来补充上下文无关分析器的动作，通常将与语义相关的上下文有关信息填入符号表中，通过查符号表中的信息来分析程序语义正确与否。
2. 类型的一致性检查
3. 语义处理：对于声明语句：其语义为声明变量的类型等，不要求其他操作；语义分析程序的工作是填符号表，登录名字的特征信息，分配存储；对于执行语句：进行某种操作，按操作的目标结构生成中间代码或目标代码。

栈式抽象机及其汇编指令

栈式抽象机：三个存储器(存放AR的运行栈的数据存储器、存放操作数的操作存储器、指令存储器)、一个指令寄存器和多个地址寄存器组成。
指令代码如下：

声明的处理

常量类型声明处理

语义的表示为：给出语言结构的属性翻译文法说明其语义及语义动作，并将这些动作插入属性翻译文法产生式中的适当位置。
对于声明，编译程序任务：1.分离出每个声明的实体，并将其名字填入符号表中；2.把被声明实体的有关特性信息尽可能多的填入符号表中，即先查表后填表。
对于已声明实体，处理对该实体的引用时要做：1.检查对所声明实体引用(种类、类型等)是否正确；2.根据实体的特征信息，如类型、所分配目标代码地址(可能为数据区单元地址、目标程序入口地址)生成相应的目标代码。查表。
例如：

对于变长字符串(或其他大小可变数据实体)，通常使用动态申请存储空间的方式将可变实体存储在堆中。可通过指向存放该实体数据区的指针来引用该实体，即可变长实体存储在堆中，但其指针存放在符号表中。

数组变量声明的处理

静态数组

编译时已知大小，可建立数组模板/数组信息向量便于后续程序中引用该数组元素，计算数组元素的存储地址。

动态数组

运行时才知道大小，编译时仅分配空间，内容将在运行时填入。

n维数组地址计算公式

假设有一个n维数组A，其维度大小分别为d1、d2、...、dn，元素类型大小为w，则元素A[i1][i2]...[in]的地址计算公式为：

数组信息向量表(数组模板)

计算下标变量地址，检查下标是否越界。
其空间大小(元素个数)取决于数组维数，即(3n+2)，每一维存3个单元，上下界和P(i)，最后还存储一个维数和RC不变量。
所以无论常界或变界数组，编译时即可确定数组模板大小，不过前者，编译时可造信息向量表；但后者的要在目标程序运行时才能构造，编译程序生成相应的指令。
针对于形如array B(3,-2:1) char;的属性翻译文法大致如下：

其中@init将为在分配给数组模板区中保留两个存储单元，存放RC和n，并将维数计数器j清0.@dimen将维数自增一；@bounds将省略下届的情况下进行上界设置并把下界设置成默认值1，并计算P(i)，可利用P(i) = (U(i+1)-L(i+1)) * P(i+1)，需要进行反填。@lowerbnd和upperbnd同理

表达式处理

生成生成表达式值的代码，将表达式中操作数装载到操作数栈(或运行栈)栈顶单元或某个寄存器中，此后执行表达式指定操作，操作结果保留在栈顶或寄存器中.

过程调用和返回

传值

值调用，过程体对形参的访问等于对相应实参的访问，但不影响具体的实参值。

传地址

引用调用，过程体通过对形参的间接访问来访问相应的实参。

传名

名字调用，将实参名传给形参，在过程体中引用形参时相当于对当时实参变量的引用，实参变量为下标变量时，其效果与传地址不一定一致。
过程调用处理动作如下：1.检查过程名是否已定义(过程名和函数名不能错，实参和形参在类型、顺序和个数上是否一致)(查表)；2.加载实参(值或地址)；3.加载返回地址；4.转入过程体入口地址。

返回语句和过程体结束的处理

1. 若为函数过程，应将操作数栈顶函数结果值送入函数值结果单元。
2. 生成无条件转移返回地址指令。
3. 产生删除运行栈中被调用过程活动记录的指令(根据DL活动链将abp退回去即可)。

代码优化

编译程序为了生成高质量的目标程序而做的加工和处理。

基本块

连续的语句序列，程序执行从基本块第一条语句进入，执行只能从基本块最后一条语句离开。

1. 通过以下三条规则确定每个基本块的第一条语句集合：1.整个语句序列第一条语句属于入口语句；2.任何能由条件/无条件跳转语句转移到的第一条语句属于；3.紧跟在跳转语句后第一条语句属于。
2. 每个入口语句直到下一个入口语句，或程序结束，之间所有语句都属于一个基本块.

基本块内优化

1. 代数性质(代数变换)
2. 复写传播,减少没有用到的变量开销
3. 删除冗余代码\似代码

消除公共子表达式

DAG图:有向无环图,表示基本块内各中间代码之间的关系,消除公共子表达式,其叶节点由变量名或常量标记(在基本块内先引用再赋值的变量,可采用变量名加下标0的方式命名其初值),图中间节点由中间代码的操作符标记,代表基本块内一条或多条中间代码,基本块中变量的最终计算结果都对应着图中的一个结点.
算法实现:
输入:基本块内中间代码序列;输出:完成局部公共子表达式删除后的DAG图

对于数组,指针和函数调用的DAG图生成:
数组:需要将数组标识符当作一个单独的变量考虑,将[]作为数组取值操作符,即a[j] = y中间代码对应为a = j '[]=' y, []=表示数组成员赋值操作符.
对于函数调用,在缺乏跨函数数据流分析支持下,保守假设函数调用改变了所有他可能改变的数据.

窥孔优化

关注目标指令的一个较短的序列,通过删除其中的冗余代码,或用更高效简洁的新代码来替代其中部分代码,并不局限于同一个基本块中.

流图

有向图,节点为基本块,有前驱后继概念:

全局优化

数据流分析

获取数据在程序执行路径中如何流动的有关信息.
全局优化的基础.
使用到达定义来进行数据流分析。
对于程序的某个执行点：out[S] = gen[S] ∪ (in[S] - kill[S])，S代表某语句，可为基本块或语句集合或基本块集合等，out代表S末尾得到数据流信息，gen为本身产生的，in为进入的，kill为注销的
到达定义分析：若从定义点d出发，存在一条路径到达p，并在路径上不存在对该变量的其他定义语句，则认为”变量定义点d到达静态点p”。若路径上存在对该变量的其他赋值语句，则路径上的前一个定义点就被路径上后一个定义点”杀死”或消除了。

输入：程序流图，基本块的kill集合和gen集合计算完毕，输出：每个基本块出入口的in和out集合。
根据in[B] = ∪(B的前驱基本块P)out[P]，以及数据流分析方程，为每个基本块计算in和out，循环计算到直至没有一个基本块的out集合计算出来不再产生改变。
具体实现该方程时可以使用位向量，即将集合中每个定义点根据下标映射为一个无限位二进制数的某一位，再根据位运算实现相应的并和差。

活跃变量分析

变量x的值在p点或沿着从p出发的某条路径中会被使用则称其在p点活跃。
活跃变量信息对寄存器分配有重要意义，若拥有寄存器的变量x在p点开始的任何路径上不再活跃，则释放寄存器。若两个变量的活跃范围不重合，则可共享一个寄存器。
数据流方程：in[B] = use[B] ∪ (out[B] - def[B])，out[B] = ∪(B的后继基本块P) in[P]，def[B]：变量在B中被定义先于任何对他们的使用，useB，该数据流信息需要沿着流图路径的反方向计算得出。也就是输入的数据流应该是该基本块使用的变量并上输出的数据流信息减去在该基本块中定义先于使用的变量。
则x在如下路径上活跃，路径后方的某个基本块中，变量x被使用，则沿着执行路径的逆向到x被定义的基本块的路径。
计算方式同数据流分析的数据流方程计算方式一致。
从活跃变量到冲突图，只有跨越基本块活跃的变量才能分配到全局寄存器，并且活跃范围重合的变量间无法共享全局寄存器。

链、网和冲突图

冲突图：结点为待分配全局寄存器的变量，当两个变量中其中一个在另一个定义(赋值)活跃，注意是要定义处，否则不一定会产生冲突则两者间有边相连。
除了在每个变量的定义点处计算活跃变量；还可以通过计算基本块入口处的活跃变量，进而在其内部计算每个定义点的活跃变量，降低计算复杂度。
变量的定义-使用链：变量某一定义点为起点及所有可能使用该定义点所定义变量值使用点组成的一个链，形似：L5 {<B1, 2>, <B2, 1>, <B3, 1>, <B3, 2>} ；L6 {<B3, 2>, <B2, 1>, <B3, 1>, <B3, 2>。
若同一个变量的多个定义-使用链拥有某个同样的使用点，则合并成同一个网，形似：W3 { L5 {<B1, 2>, <B2, 1>, <B3, 1>, <B3, 2>}, L6 {<B3, 2>, <B2, 1>, <B3, 1>, <B3, 2>}}。

网之间的交点是共同的活跃点。

循环优化

循环不变式的代码外提

不随循环控制变量改变而改变的表达式或子表达式。外提可以减少计算计数的变量，频度削弱，即将一些常量的计算放在循环外计算。

循环展开

将构成循环体的代码(不含控制循环的测试和转移部分)，重新产生许多次(在编译时确定)，用空间换时间，也就是若循环体重复过多语句，则可以通过类似打表的方式实现循环。
识别好循环结构，确定循环初值、终值和步长后可以判断空间换时间是否合算进行展开。

归纳变量的优化和条件判断的替换

在每次执行循环迭代中若某变量值固定增加或减少一个常量值，则称其为归纳变量，通过将归纳变量统一成一个变量进行优化。

其他循环优化方法

• 将多层嵌套的循环变成单层；
• n个相同形式的循环合成一个循环

in_line展开

将过程(函数)调用改成in_line展开节省许多处理过程调用花费开销，省去函数调用时参数压栈，保存返回地址等指令，但仅限于简单的函数。

目标代码生成

指令集

栈式架构

类似于P-code和Java虚拟机

累加器式架构

寄存器架构

分为寄存器-内存和寄存器-寄存器架构，依据是否可直接内存寻址区分，前者可以直接操作内存，直接跟内存打交道；但是后者的操作数只能来自于寄存器，与寄存器打交道，本质上是运算指令是否支持内存操作数都可用多个寄存器直接作为ALU指令的任一操作数。

地址空间

代码区

存放目标代码

静态数据区

存放全局变量、静态变量和部分常量，如字符串

动态内存区

内存堆Heap，其中C、C++由程序员管理。Java、Ada自动管理，使用类似内存垃圾收集器来管理

程序运行栈

存放活动记录，函数调用的上下文现场：由调用方保存的一些临时寄存器和被调用方保存的一些全局寄存器。

MS-WIN应用程序为例

高地址向低地址，自上而下为：静态数据区、代码区、程序运行栈和动态内存区。

程序运行栈的设计

存放子程序/函数运行必需基本空间:活动记录。
进入子程序或函数时分配，地址空间向下生长(高地址向低地址)
从子程序或函数返回时，当前运行栈被废弃
递归调用同一个子程序或函数，每次调用都将获得独立的运行栈空间，保证递归程序和多线程程序的正确运行。
**一个典型运行栈有：函数返回地址、全局寄存器的保存区、临时变量的保存区、为分配到全局寄存器的局部变量的保存区和其他辅助信息的保存区(如，PASCAL/PL-I类的display区)**。

寄存器的分配和指派

分类

通用(保留、调用方保存(临时)、被调用方保存(全局寄存器)寄存器)、专用

全局寄存器

此处”全局”相对于”基本块”，非程序全局，分配的主要是函数局部变量，包含函数入口参数。
全局变量和静态变量一般不参与全局寄存器分配，即便他们在某个循环体中被多次访问，因为若发生线程切换，会导致相应数据被保留而且重置，导致运算结果出错。

全局寄存器分配方法

引用计数

统计变量在函数内被引用次数并根据被引用特点赋予不同权重，最终为每个变量计算出一个唯一权值，按权值大小排序，将全局寄存器依次分配给权值最大的变量。

着色图算法

构建变量间的冲突图，在图上应用着色算法，将不同的全局寄存器分配给有冲突的变量。

1. 通过数据流分析，构建变量的抽冲突图
2. 若可供分配k个全局寄存器，则尝试用k种颜色着色

启发式图着色算法：(寄存器数目为k)

1. 找到第一个连接边数目小于k的节点，将其从图G中移走，形成图G’,若无法找到则选择一个点移出(注意这个移出的点是不能再分配着色的点,也就是后续进行着色的时候不考虑这些点,即使实际上可以完成着色)
2. 重复步骤1，直到无法再从图G’中移走节点
3. 在图中选取适当节点，记录为”不分配全局寄存器“的节点，并从图中移走，注意此处移走即不能再分配寄存器或者不再着色，这些点在启发式算法下不能被着色,因此该算法并不是一个最优解
4. 重估步骤1-3，直至图中仅剩一个结点
5. 给剩余最后节点选取一种颜色，然后按节点被移走的顺序，反向将节点和边添加进去，并依次给新加入的节点选取颜色，此时需保证有链接边的节点着不同的颜色，也就是此时才决定所有可以着色的节点应该着什么颜色。
   

临时寄存器分配

采用寄存器池来管理临时寄存器，它们不超越基本块，不跨越函数调用。
在临时寄存器池中预设一些寄存器，

1. 进入基本块时，清空临时寄存器池
2. 为当前中间代码生成目标代码时，无论临时变量还是局部变量(亦或全局变量和静态变量)，若要使用临时寄存器都向临时寄存器池申请
3. 临时寄存器池接收申请后：1.若有空闲寄存器则将其标识为被该申请变量占用，并返回空闲寄存器。2.若无空闲，则选取一个在即将生成代码中不会被使用的寄存器写回相应的内存空间，标识该寄存器被新的变量占用，返回寄存器
4. 基本块结尾，或函数调用发生前，将寄存器池中所有被占用临时寄存器写回相应内存空间，清空池。

指令选择

不同架构需要使用不同的指令选择，生成代码时需要采用不同的策略。