编译原理知识点整理

第一章 概论

1. 低级语言：字位码、机器语言、汇编语言。与特定机器有关，功效高但使用复杂且易出错。

   高级语言：C、Java等语言。不依赖具体机器，移植性好易维护。

2. 源程序：汇编或高级语言编写的待翻译程序；

   目标程序：目标语言编写的程序；

   翻译程序：将源程序转换为目标程序的程序。

3. 源程序使用汇编，目标程序是机器语言，此翻译程序就是汇编程序；源程序使用高级语言，此翻译程序就是编译程序。

4. 编译过程指将高级语言程序翻译为目标语言程序的过程。

5. 五个阶段：词法分析、语法分析、语义分析与生成中间代码、代码优化、生成目标程序。

   七个逻辑部分：词法分析、语法分析、语义分析与生成中间代码、代码优化、生成目标程序、符号表管理、出错处理。

6. 遍：对源程序（以及源程序中间形式）从头到尾扫描一次，并进行相应处理。

7. 编译程序通常分为前端（分析，与源语言有关）和后端（综合，与目标机有关）。

第二章 文法与语言概念

1. 文法/语法：对语言结构的定义与描述。

2. 语法规则：描述句子的语法结构的规则。

   用 ::= 表示由什么组成。

3. 最左推导：从最左的语法成分进行推导，类似有最右推导、一般推导。

4. 语法树：推导为语法成分（非终结符），再推导为单词符号（终结符）。

5. 文法定义：，非终结符号集，终结符号集，规则集，开始符号/识别符号。

6. 在文法G中，由式子v推导到式子w，记作 。

7. 在文法G中，，若 ，记作 。

8. 在文法G中， ，推导符号下加文法G、上加正闭包+，或 ，记作 。

9. 规范推导：若，且y是终结符号，则称作规范推导。（规范推导就是最右推导）

10. 文法G[Z]，Z能推导到的任何串称为句型，Z能推导到的只含终结符的串称为句子，文法G[Z]产生的所有句子的集合称为语言。

11. 文法G与G’为不同文法，若两个文法产生的语言相同，则称为等价文法。

12. 递归规则：规则右部有与左部一致的非终结符。

    对于，若，称为左递归；若，称为右递归；若，称为自嵌入递归。

13. 递归文法：若，称为左递归文法；若，称为右递归文法；若，称为递归文法。

14. 短语：句型可以推导到的串，即任何非终结符所能推导出的最终字符串，不可含自身（简单短语是由一个非终结符一步推导出的只含终结符的字符串）

15. 句柄：句型能够推导到的最左简单短语。

16. 若一个文法的某句子存在两种不同的规范推导，则称该文法具有二义性。

17. 有害规则：形如，会引起二义性。

18. 多余规则： 该规则的左部非终结符不出现在任何句型中。（不可达符号）

    ​ 该规则中含有推不出任何终结符号串的非终结符。（不活动符号）

19. 某文法中不含有害规则或多余规则，则称该文法是压缩过的。

20. 文法语言分类：0型，1型，2型，3型

    0型：短语结构文法，可以用图灵机接受；()

    1型：上下文敏感或上下文有关，只有在左右为x、y的情况下可以完成推导，可以用线性界限自动机接受；()

    2型：上下文无关，与BNF等价，可以用下推自动机接受；()

    3型：正则文法，可以用有穷自动机接受；(左线性：，右线性：)

第三章 词法分析

1. 词法分析：根据此法规则识别及组合单词，进行词法检查。

2. 单词种类：保留字（for，begin，end，do）、标识符（函数变量名称）、常数、分界符（+-*/）

3. 单词内部形式：

   • 按单词种类分类：类别编码+单词值

   • 保留字和分界符采用一符一类

     

   • 标识符和常数的单词值又为指示字

4. 状态图： 状态以圆表示，箭头由规则右侧状态指向规则左侧状态，箭头上写转移时的终结符。

   ​ 初始状态以S表示，其表示推导的最终结果（仅存在终结符）

   ​ 文法G[Z]初始语句Z以状态Z表示，其外围两圈圆，内圆为虚线

5. 词法分析中使用的全局变量和过程：

1. 正则文法：左线性文法 + 右线性文法

第四章 语法分析

1. 自顶向下：给定符号串，遵照文法尝试对其建立语法树。

2. 存在问题：左递归文法、需要回溯

3. 左递归消除：

   • 使用扩充BNF表示改写文法：提因子（），递归文法改写（）；
   • 将左递归文法改写为右递归文法。

4. 回溯问题：分析工作需要部分或全部退回去。

5. 回溯问题不发生的充要条件：

   定义$FIRST(\beta) = {c\,|\,\beta\overset{}{\Rightarrow}c\,…,c\in V_t}FOLLOW(A)={c\,|\,Z\overset{}{\Rightarrow}\,…Ac\,…,c\in V_t}A::=\alpha\,|\,\betaFIRST(\alpha)\cap FIRST(\beta) = \varnothingFIRST(\alpha)\cap FOLLOW(A) = \varnothing\beta\overset{*}{\Rightarrow}\epsilon 空字符$）。

6. 回溯问题消除：多次改写和提因子，最终使得分析过程满足不需要回溯的冲要条件；超前扫描：向前多侦察多个字符，以确定文法选择。

7. 分析程序主要使用方法：递归下降法

第五章 符号表

1. 符号表：编译过程中，编译程序用来记录源程序中各种名字的特性信息，也称名字特性表。

2. 常见符号：程序名、过程名、函数名、用户定义类型名、变量名、常量名、枚举值名、标号名等。

   常见信息：种类、类型、维数、参数个数、数值、存储单元地址等。

3. 各种标识符通过声明存入符号表（填表）；填表前检查是否重复定义，后续使用时需查询符号表标识符是否声明（查表）。

4. 符号表结构：名字+特性

5. 特性域：应该包含多个子域。

   • 普通标识符：种类（变量名、函数名）、类型（int/char）、性质（var/const）、值、地址、所占地址大小、作用域嵌套层次
   • 数组：维数、上下界值、首元素地址、数组元素类型
   • 记录（结构、联合）：域的个数、域名、地址位移、类型
   • 过程、函数：形参个数、所在层次、返回值类型、局部变量所占空间大小
   • 指针：所指对象类型

6. 组织方式：大部分共同信息按统一格式制表，部分特殊信息用指针连接。

7. 非分程序结构语言：可独立编译的程序单元是一个不包含子模块的单一模块，如FORTRAN语言。

8. 标识符按作用域不同分为全局局部，制成全局符号表、局部符号表。

9. 子程序、函数名、公共区名填入全局符号表

   子程序（函数）声明部分制造或填入局部符号表（本单元局部符号表，有同名：重复声明报错，无同名：造表）

   语句部分读到标识符查表（本单元局部符号表及全局符号表，有同名：已声明，无同名：无定义报错）

   程序单元结束释放该单元局部符号表，程序编译结束释放全部符号表。

10. 符号表可为无序符号表、有序符号表、哈希表

11. 分程序结构语言：模块内可嵌入子模块

12. 标识符声明性出现建表（本层符号表，有同名：重复声明报错，无同名：填表）

    标识符引用性出现查表（本层符号表，有同名：已声明，无同名：转到直接外层）

    标准标识符（不必声明可全程使用，标准名及数目已知）初始化时建表并将名字表填入

第六章 运行时存储管理

1. 静态存储分配：在编译阶段有编译程序实现对存储空间的管理和为源程序中变量分配存储。

   条件：在编译时能够确定变量在运行时的数据空间大小，且运行时不改变。

2. 动态存储分配：在目标程序运行阶段由目标程序实现对对存储空间的管理和为源程序中变量分配存储。

   特点：在目标程序运行时进行变量存储分配，编译时要生成进行动态分配的目标指令。

3. 静态存储分配：

   • 分配策略：开辟数据区，为每个模块分配，在模块内按序分配，目标地址填入符号表

   • FORTRAN子程序（模块）典型数据区：

     变量、返回地址、形式参数、临时变量

     

4. 动态存储分配：编译时不能具体确定程序所需数据空间，编译程序生成有关存储分配的目标代码，实际分配在目标程序运行时进行。

   分程序结构，且允许递归调用的语言：栈式动态存储分配

   分配策略：整个数据区为一个堆栈，进入过程时，在栈顶分配数据区；退出过程时，撤销过程数据区。

5. 典型活动记录可以分为三部分：局部数据区（各局部变量），参数区（显式隐式参数），display区（存放各外层模块活动记录的基地址）

6. 参数区：显式参数：形参数据，出现在用户源程序中；隐式参数：prev abp（存放调用模块记录基地址，执行完后释放数据区，数据区指针指向调用前地址）、ret addr（返回地址，调用语句的下一条执行指令地址）、ret value（函数返回值）

第七章 源程序中间形式

1. 一般编译程序都是先生成中间代码，再生成目标代码，优点是可移植性（与具体目标程序无关）与可优化性。主要有三种中间代码表示形式：波兰表示，N元组表示，抽象机代码。

2. 波兰表达式：前序后序中序表达式，

   算法：设立操作符栈。读到操作数时立即输出；读到操作符时，与栈顶操作符比较优先级，栈顶操作符优先级高/相同时栈顶操作符出栈，栈顶操作符优先级低时读入操作符入栈。

3. N元组表示：每条指令由N个域组成，通常第一个域表示操作符，其余表示操作数。（常用三元组四元组）

   前序表达式，$a+bc \Rightarrow (1),b,c \quad(2)+,a,(1)$

4. 间接三元式：三元式不便优化，优化时会删除一些三元式，或对三元式顺序（编号）进行改变，但有些改变的三元式结果出现于其他三元式中，因此引入间接三元式。将三元式与三元式的执行顺序存储为两张表，优化时改变三元式执行顺序表。

5. 四元式：操作符+操作数1+操作数2+结果

   结果通常是由编译引入的临时变量，可由编译器分配一个寄存器或主存单元。

6. 抽象机代码：P-code中间代码，主要操作寄存器，保存程序指令的存储器，堆栈式数据

   使用的寄存器： PC: 程序计数器

   ​ NP: New指针，指向存放由New生成的动态数据的堆顶端

   ​ SP: 运行栈指针，存放所有可按源程序的数据声明直接寻址的数据

   ​ BP: 基地址指针，指向当前活动记录的起始位置指针

   ​ MP: 栈标志指针

   ​ EP: 极限栈指针

7. 抽象机所有操作都在运行栈的栈顶进行，顺序与波兰表达式相同

8. 中间代码的图表示：

   • 语法树：操作数出现在叶结点，操作符出现在中间结点。
   • DAG图：Directed Acyclic Graphs有向无环图，语法树的一种归约表达形式（语法树中相同表达部分表示一次）

9. 三地址码：适合目标代码优化生成的表达形式，是语法树或DAG图的线性表示，树的中间结点由临时变量表示。

第八章 错误处理

1. 错误分为两类：语法错误（不合文法）和语义错误（不合语义规则或超越系统限制）

2. 语义规则：标识符先声明后引用；引用要符合作用域规定；调用时形参实参要一致；参与运算的操作数类型一致；下标变量下标不能越界。

   超越系统限制：数据溢出错误；符号表、静态存储分配数据区溢出；动态存储数据区溢出。

3. 错误诊察： 违反语法语义规则、超过编译系统限制的错误（语法语义分析时）

   ​ 下标越界、计算结果溢出、动态存储数据区溢出（目标程序运行时）

4. 错误报告： 出错位置：行号计数器、单词序号计数器

   ​ 出错性质：文字信息、错误编码

5. 错误处理技术：发现错误后，在报告错误的同时还要对错误进行处理，以便编译能继续进行。

   错误改正：查出错误后，根据文法进行错误改正

   错误局部化：尽可能将错误的影响限制在一个小范围内，避免错误扩散和影响程序其他部分分析。

6. 局部化处理：

   • 一般原则：诊察到错误后停止对后面符号进行分析，跳过错误所在语法成分继续分析（一般是跳到语句右界符，从新语句开始分析）
   • 局部化处理实现：递归下降法，出错后转存，并跳到正确部分分析。
   • 提高错误局部化的方法：建立语法成分对应的合法后继符号集、停止符号集（跳读必须停止的符号）

7. 目标程序运行时错误检测与处理：较难确定出错位置，只需打印错误信息，保留寄存器储存器中的值

第九章 语法制导翻译技术

1. 程序语言的语义形式化描述有三种，操作语义、指称语义、公理语义。

2. 翻译目标是将中缀表达式变为后缀表达式（逆波兰表示）。（只需在中缀表达文法中插入相应动作符号）

3. 输入文法：未插入动作符号时的文法，可推导出输入序列。

   翻译文法：插入动作符号后的文法，可推导出活动序列（输入序列/动作序列）。

   输入文法：

   翻译文法：

   其中，为动作符号标记，代表一个动作，比如是打印其后字符串。

4. 活动序列：由翻译文法推导出的字符串，由终结符和动作符号组成。去除动作符号，可得输入序列；去除输入序列，可得动作序列。（执行动作序列即可完成翻译任务）

   活动序列中的输入序列和动作序列构成对偶集。

5. 语法制导翻译：给定输入字符串，根据翻译文法获得动作序列并完成动作的过程。

6. 属性文法：在翻译文法基础上，为终结符、非终结符、动作符号加上属性（综合属性/继承属性）。

7. 综合属性： 代表该属性，是综合属性标记，是属性变量或属性值。根据文法自顶向下构建语法树，自底向上计算属性。

   继承属性： 代表该属性，是继承属性标记，是属性变量或属性值。可从之前得到，继承之前的值，自顶向下计算属性。

8. L属性翻译文法(L-TAG)：输入文法要求是LL(1)文法，可自顶向下构造分析器，分析过程中可进行属性求值。要求文法中的非终结符、终结符、动作符都需要存在属性，开始符号的继承属性和终结符号的综合属性有初值。继承属性自顶向下自左向右求值，综合属性自底向上自右向左求值。

9. 简单赋值形式的L属性翻译文法(SL-TAG)：属性传递时除去动作符号，其余符号的属性只是简单的赋值关系，不存在复杂运算。

   产生式右侧符号的继承属性等于左侧符号的继承属性或同右侧在其左边符号的综合属性。

   产生式左侧符号的综合属性等于左侧符号的继承属性或右侧符号的综合属性。

   非SL-TAG文法：，其中

   SL-TAG文法：，其中

10. 递归下降翻译器：翻译文法的自顶向下翻译。思路与输入文法的递归下降分析基本相同，只需按照翻译文法在过程中增加动作即可。

11. 递归下降属性翻译器：属性文法的自顶向下翻译。对每个非终结符设置一个子程序，根据其具有属性数目设置相应参数。继承属性设置为赋值形参，综合属性设置为变量形参。

    关于属性名：产生式左部同名非终结符使用相同属性名，具有相同值的属性取相同属性名。

12. 过程调用函数实参，继承属性传递继承属性值，综合属性传递属性变量名（地址）。

第十章 语义分析和代码生成

1. 源语言：通用的过程语言。

2. 生成代码：栈式抽象机生成的伪汇编代码。

3. 翻译方法：自顶向下的属性翻译。

4. 语法成分翻译子程序参数设置：继承属性为值形参，综合属性为变量形参。

5. 语法成分动作翻译子程序参数设置：继承属性为值形参，综合属性不设形参而作为动作子程序返回值。

6. L属性翻译文法(L-ATG)：输入文法要求是LL(1)文法，可用自顶向下分析构建分析器。

   其拥有特征：终结符、非终结符和动作符都具有属性；非终结符和动作符属性可分为继承属性综合属性；开始符号的继承属性具有指定初始值；终结符号的综合属性具有指定初始值；属性求值规则。

7. 语义分析：

   • 上下文有关分析：标识符作用域；

   • 类型一致性检查

   • 语义处理： 声明语句：语义是声明变量类型等。编译程序工作是填符号表，登录名字特征信息，分配存储。

     ​ 执行语句：语义是某种操作。编译程序工作是按某种操作的目标结构生成代码。

8. 用上下文无关文法只能描述语言的语法结构，而不能描述其语义。

   构建上下文有关文法过于困难，其分析器效率低。通常把与语义相关的上下文有关信息填入符号表中，并通过查符号表中的这些信息来分析程序的语义是否正确。

9. 栈式抽象机：三个存储器、一个指令寄存器和多个地址寄存器组成。

   存储器：数据存储器（存放AR的运行栈）、操作存储器（操作数栈）、指令存储器。

10. 栈式抽象机指令代码：

    | 指令名称 | 操作码 | 地址 | 指令意义 |
    | ———— | ———————————————————— | ——- | —————————————————————— |
    | 加载指令 | LOD | D | 将D的内容→栈顶 |
    | 立即加载 | LDC | const | 常量→栈顶 |
    | 地址加载 | LDA | (D) | 变量D的地址→栈顶 |
    | 存储 | STO | D | 栈顶内容→变量D |
    | 间接存 | ST | @D | 栈顶内容→D所指单元 |
    | 间接存 | STN | | 栈顶内容→次栈顶所指单元 |
    | 加 | ADD | | 栈顶和次栈顶内容相加，结果留栈顶 |
    | 减 | SUB | | 次栈顶内容减栈顶内容 |
    | 乘 | MUL | | |
    | 逻辑与 | AND | | |
    | 逻辑或 | ORL | | |
    | 逻辑非 | NOT | | |
    | 比较 | EQL, NEQ,
    GRT, LES,
    GTE, LSE | | 次栈顶内容与栈顶内容比较，结果（1或0）留栈顶 |
    | 转子 | JSR | lab | |
    | 分配 | ALC | M | 在运行栈顶分配大小为M的活动记录区 |

11. 声明的处理：处理声明主要是填表并检查是否重复声明，处理已声明实体主要是查表。

12. 对于静态数组，编译程序处理声明时应建立数组模板（数组信息向量），以便后期计算数组元素的存储地址。一般存储下界上界和地址计算常量。

13. 大部分程序语言数组元素按照行优先存放，FORTRAN例外。

14. 翻译文法中的动作符号也称为动作程序。

15. 表达式的处理：处理表达式主要是生成计算该表达式值的代码。通常是把操作数装载到操作数栈栈顶或某个寄存器中，执行表达式所指定的操作，并将结果保留在栈顶或寄存器中。

16. 操作数栈可以和运行栈（动态存储分配）合并，也可单独设栈。本章选择单独设栈的方式。

17. 对于实际表达式计算允许整型实型混合使用，允许出现数组元素。因此除去基本运算，还应加入类型一致性检查或转换，计算下标变量地址并取下标变量值的语义动作。

18. 过程调用：

    • 传值：调用段：计算实参值，放在操作数栈栈顶；被调用段：从栈顶取得值，对应形参单元。对形参的访问等于对相应实参的访问。
    • 传值：调用段：计算实参地址，放在操作数栈栈顶；被调用段：从栈顶取得地址，对应形参单元。通过对形参的间接访问来访问相应的实参。
    • 传名：将实参名传给形参。当实参变量为下标变量时，传名和传地址效果可能不同。传名实现复杂效率较低，现基本不使用。

19. 返回语句：返回返回值，并删除被调用过程活动记录。

第十一章 词法分析自动化

1. 正则表达式和正则集合：有字母表 , 定义在 上的正则表达式和正则集合递归定义如下 :

   • 和 都是 上的正则表达式, 其正则集合分别为: 和 ;

   • 任何 , 是 上的正则表达式,其正则集合为: ;

   • 假定 和 是 上的正则表达式, 其正则集合分别记为 和 , 那么 , 和 $U \SigmaL(U) \cup L(V)L(U) \cdot L(V)L(U) $ ；
   • 任何 上的正则表达式和正则集合均由 1、2和3产生。

2. 正则表达式符号： 或， 连接， 重复， 括号。

3. 正则表达式与3型文法等价。

4. 确定有穷自动机DFA： ，其中 代表有穷状态集， 代表输入字母表， 状态转移函数， 初始状态， 终止状态集。

   DFA的确定性表现在状态转换函数是单值函数。

5. 不确定有穷自动机NFA：若 是一个多值函数，且输入可允许为 ，则有穷自动机是不确定的 , 即在某个状态下，对于某个输入字符存在多个后继状态。

6. ，其中 是指 中元素经过任意条 弧能够到达的状态的集合。

7. NFA到DFA的转换原理是构建新的状态，按照NFA图构建新的转换函数 。

8. DFA的化简：多余状态、等价状态（一致性：同为可接受或不可接受；蔓延性：任意输入符号都得转换到等价状态）。

9. DFA与正则文法等价。

10. 正则文法可分为左线性正则文法和右线性正则文法。

第十二章 语法分析提高

1. LL分析法：LL自左向右扫描、自左向右地分析和匹配输入串，表现出最左推导的性质。从左到右扫描，自顶向下归约。

2. ，其中 可以为空字符。

   。若 ，则 。

3. LL(1)文法：文法分析表不含多重定义入口，即分析表中每格无两条以上规则。

4. LL(1)文法充要条件：对任意规则 ，都有

   • ；
   • 若 ， 。

5. 自底向上分析：从输入符号串开始，重复查找当前句型句柄，并利用有关规则进行归约。

6. 移进-归约分析：建立符号栈，记录分析历史和现状，根据所面临状态，确定下一步动作是移进还是归约。

7. 算符优先分析：仿效算术式四则运算，为每个终结符设定执行的先后顺序。

   该分析不一定是严格的最左归约/规范归约。

8. ；

   。

9. 素短语：一个短语，至少包含一个终结符号，且除它自身外不包含其他素短语。

10. LR分析法：从左到右扫描，自底向上归约。

11. LR分析器有状态栈、分析表、控制程序三部分。

12. 分析表种类：SLR（简单LR）、LR（标准LR）、LALR（超前LR）。

13. 规范句型：通过规范规约得到的句型。

    前缀：输入串前部终结符串，只要满足剩余部分与其连接成为输入串即可。

    活前缀：若分析过程能保证栈中符号串均是规范句型的前缀，则称为活前缀（表示当前分析中并无语法错误，活前缀实际是不包括句柄右边符号的前缀）。

14. 有效项目：若项目 对活前缀 成立，则必有规范推导 。（假设活前缀为 ，获得项目族群和项目间转移关系后，按照活前缀顺序输入进行转移，最终所在项目即是该活前缀的有效项目集）

15. 状态转移表（GOTO）：终结符导致状态转移

16. 分析动作表（ACTION）：移进（shift），归约（reduce），接受（accept），出错（error）

17. 控制程序：根据栈顶状态和现输入符号查ACTION表执行规定操作，并根据GOTO表设置新栈顶状态。

18. LR分析过程：每次归约总是归约当前句型的句柄（规范规约）；分析每一步栈中符号串均是规范句型的活前缀，与输入串剩余部分构成规范句型。

19. SLR分析表构建：

    • 确定文法状态集合，即LR(0)项目集规范族：实现时首先应拓广文法，如普通G[S]文法，应该添加推导规则 ，保证分析表只有一个接受状态。初始状态是 以及这个项目的闭包（所有可以转移到的项目，如 ）。
    • 确定转移函数，从初始项目集出发，将 后移一位，判断转移函数，填写ACTION和GOTO表。
    • 确定文法归约，在状态中，寻找形如 的语句，则在 的字符对应的格子中填入该语句对应的归约编号。如该语句编号为 ， ，则在 对应的格子中填入 。

20. SLR判断方法：判断是否有移进-移进冲突（即一个字符出现两种转移）、移进-归约冲突（即一个字符可能为转移也可能为归约）。

第十四章 代码优化

1. 优化目标：提高目标代码运行效率，时间+空间

2. 优化方法分类：

   • 与机器无关（中间代码优化）、与机器有关（目标代码优化，指令与寄存器的使用）；
   • 局部优化（基本块内）、全局优化（函数内基本块间）、跨函数优化（整个程序内）。

3. 基本块定义：连续的语句序列，控制流只能从第一句进入基本块，从最后一句离开基本块。

4. 流图定义：有向图，节点是基本块，基本块间关系是前驱和后继。

5. 基本块内优化：

   • 代数变换：常数计算与合并，削弱运算强度；

   • 复写传播：形如 的赋值语句称为复写语句，满足一定条件时，后续 可用 替代，称为复写传播；

   • 死代码删除：如 ，永真的 if-else 语句块。

     消除公共子表达式

     通过构建DAG图（有向无环图）消除公共子表达式。

     DAG图构建算法

     对于形如 的表达式，在图中寻找 、 对应的节点，如果没有就在图中新添加。接着寻找 对应的节点（该节点存在有向边分别指向 、 对应的节点），如果没有就在图中新添加。完成后将 所代表的节点设置为 对应的节点。

     对于数组元素，需要改写表达式。对于形如 的表达式，改写为 的形式， 作为运算符。对于形如 的表达式，改写为 的形式， 作为运算符。对于指针运算，尽量不要优化。

     从DAG图导出中间代码算法

     选择DAG图中任意一无父节点（即无有向边指向它）的节点，去除并加入队列。接着如果它的最左子节点符合无父节点的条件，则去除并加入队列，继续对加入节点的最左子节点判断；如果不符合条件，则在图中再选取一个符合条件的节点，继续上述流程。所有节点均加入队列后，反序输出队列中节点作为代码运算顺序。

6. 窥孔优化：窥孔优化关注在目标指令的 一个较短的序列上，通过删除其中的冗余代码，或者用更高效简洁的新代码来替代其中的部分代码，达到提升目标代码质量的目的。并不局限于一个基本块内。

7. 全局优化：首先应进行数据流分析， 或 对于任意基本块或语句都成立。
8. 到达定义分析：某个变量定义是在哪里产生、在哪里消除，在哪些语句中都可以使用。基本块的到达定义分析先获得 集合（ ，其中 ），并通过上式（ ）获得 集合。循环执行，直至全部块的 集合不变。
9. 活跃变量分析：某个变量在当前位置是否是活跃的，即后续是否使用。本块的活跃变量分析先获得 集合（ ，其中 ），并通过上式（ ，活跃变量中， 代表在使用前定义/赋值的变量； 代表在定义/赋值前使用的变量）获得 集合。循环执行，直至全部块的 集合不变。
10. 冲突图：假设只有跨越基本块活跃的变量才能分配到全局寄存器，并且活跃范围重合的变量之间无法共享全局寄存器。节点是待分配的全局寄存器，当两个变量中一个在另一个定义/赋值处活跃，他们之间便有一条边相连。
11. 变量的定义-使用链：每个变量可能有多个链，每个链头元素表示定义/赋值位置，后面元素表示使用位置，可写为 ${, …}$ 的形式。
12. 循环优化：循环不变式（不随循环控制变量改变而改变）外提、循环展开（以空间换时间，需判断展开前后是否更节省时间）、归纳变量（每次迭代过程中固定增加或减少一个值）的优化和条件判断的替换、多重嵌套变单层、相同形式循环合并。
13. in_line展开：将函数调用展开在主程序中，节省压栈和跳转时间。

第十五章 目标代码生成

1. 代码生成器输入：符号表、源程序中间表示。

   要求：获得中间表示、标识符表示直接操作的变量、完成语法语义等检查。

2. 指令集架构：

   • 栈式架构：PUSH、POP出入栈顶，计算指令计算栈顶单元。
   • 累加器式架构：LOAD、STORE加载存储栈顶，计算指令计算栈顶单元和新输入单元。
   • 寄存器架构：分为寄存器-内存指令架构（操作指令从寄存器和内存获得数据）和寄存器-寄存器（操作指令只能从寄存器获得数据）指令架构。

3. 为了程序效率，应该尽可能少访问除寄存器外的存储设备。

4. 循环可以通过循环交换优化提高缓存命中率。

5. 地址空间：代码区存放目标代码；静态数据区存放全局变量、静态变量和其他部分变量（如字符串）；动态内存区（也称内存堆）存放普通变量；程序运行栈存放活动记录和函数调用上下文现场。

6. 程序运行栈设计：进入子程序/函数时分配，地址空间向下生长；从子程序/函数返回时，当前运行栈将被废弃；递归调用的同一个子程序/函数，每次调用都应获得独立的运行栈空间。

7. 活动记录：函数返回地址、全局寄存器保存区、临时变量保存区、未分配到全局寄存器的局部变量保存区、其他辅助信息保存区。

8. 寄存器分类：通用寄存器（临时寄存器/全局寄存器）、专用寄存器。

9. 全局寄存器分配：相对于基本块而言，不是对于程序全局。

   分配原则：优先分配给跨基本块活跃的变量，尤其是循环体内最活跃变量；局部变量参与全局寄存器分配；为线程安全，全局变量、静态变量不参与全局寄存器分配。

10. 常用全局寄存器分配方法：

    • 引用计数：如果一个局部变量被访问次数较多，则获得全局寄存器概率越大；出现在循环尤其是内层嵌套循环中的变量被访问次数应获得一定加权。（但存在不再使用的寄存器不能及时释放寄存器）
    • 图着色算法：通过数据流分析，构建变量的冲突图。如果有 个可供分配的寄存器，尝试用 种颜色为冲突图着色。一种方法是不断找到连接边数目小于 k 的节点移走；当无法再移走点时，删除合适的点，记录为不分配全局寄存器的变量，并继续重复上述步骤；当只剩余一个节点时，给此节点分配一种颜色，按照节点被移走的顺序，反向添加节点和边并选取颜色。

11. 图着色构建变量冲突图：节点是待分配全局寄存器的变量。一个变量在另一个变量的定义/赋值处是活跃的，则这两个变量的节点间有一条边连接（即有边相连的变量无法共用一个全局寄存器）。

12. 临时寄存器的分配：如 $a0 、 $v0 、 $hi 此类寄存器。生成某些指令时必须使用指定寄存器，临时寄存器可能保有此前计算中间结果，因此需要合理使用临时寄存器。使用寄存器池管理分配临时寄存器。

13. 临时寄存器生存范围：不超越基本块，不跨越函数调用。

14. 分配原则：进入基本块时，清空临时寄存器池；如寄存器池中有空闲寄存器，标记该寄存器被占用，并返回该寄存器；反之选取一个不会被马上使用的寄存器写回相应内存空间，并将该寄存器分配给待分配变量；在基本块结束或调用函数前都应该将临时寄存器写回相应内存空间并清空寄存器池。

第十六章 编译程序生成方法和工具

1. 编译程序的书写语言：机器语言或汇编语言、高级程序设计语言。
2. 自编译性：如果一个高级语言可以书写自己的编译程序，则称为自编译语言。
3. 自编译性不是绝对的，只是强弱不同。数据类型、控制结构丰富（适于进行多分支程序设计）的语言自编译性强。
4. 自展：将语言分为多个部分，不断用前若干部分语言编写后若干部分的编译程序。（可提高生产率，核心语言小，可用汇编实现，其余部分高级语言编写）
5. 编译程序的移植：将宿主机软件移植到目标机上。将语言分为两部分（与机器有关与机器无关），使用与机器有关语言改写为目标机有关语言，编译生成在宿主机上运行的语言交叉编译程序（其生成只能在目标机上运行的代码），编译生成在目标机上运行的语言编译程序。
6. 编译程序的自动生成：目前还没有程序能自动生成整个编译系统。