编译原理复习
前言
转眼间,这个semester也来到了学期末,在考试之神和DDL之神的双重压迫下能做的也只有痛苦的接受.本着复习也要尽到舍己为人的义务,就此写下一份编译原理的复习指南,倘若后来者能够学习到上面,那也不枉我的一片赤忱之心.
本复习指南使用的是«编译原理» 陈意云著(实际就是龙书的低质量翻译版本还翻译不全,要想学的好,还建议去看原书)
鄙人学校考试只考10道简答题和两道综合大题,题目至于是什么,大概率会从自测题里面抽,简答题和自测题我会放在每一章的最后面以供参考
第一章 引论
编译器,翻译器,解释器
能够完成从一种语言到另一种语言的保语义变换的软件称为翻译器,这两种语言分别称为该翻译器的源语言和目标语言,编译器是一种翻译器,它的特点是目标语言比源语言低级
解释器是不同于编译器的一种语言处理器。解释器不编译源程序并将其通过编译来生成目标程序，而是直接执行源程序所指定的运算。解释器也具有和编译器类似的地方，它也需要对源程序进行词法分析、语法分析和语义分析，这样它才有可能知道程序到底指定了一些什么运算。
编译器概述
词法分析
词法分析阶段将源程序的字符流，按编程语言的词法规则切割成词法记号（token）流。 对于一个词法单元，词法分析产生的记号是
<记号名，属性值>二元组。
记号名是词法单元的类别名称，而属性值是一个词法单元有别于同类中其他词法单元的特征值。赋值语句(1.1)的字符流在词法分析阶段被组成如下这些记号。
语法分析
语法分析（syntax analysis）简称分析（parsing），它检查词法分析输出的记号流是否符合编程语言的语法规则，并依据这些规则所体现出的语言构造（construct，如函数、语句、表达式等）的层次性，用各记号的第一元建立一种树形的中间表示，这个中间表示用抽象语法的方式描述了该记号流的语法情况。一种典型的中间表示是语法树，其中内部结点表示运算，它们的孩子结点代表该运算的运算对象。
语义分析
语义分析阶段使用语法树和符号表中的信息，依据语言定义来检查源程序各部分之间的语义一致性，以此保证程序各部分能有效地结合在一起。它还收集类型信息，把它们保存在符号表或语法树中。
语义分析的一个重要部分是类型检查，编译器检查每个算符的运算对象，看它们的类型是否适当。例如，当运算符为数组下标时，许多语言的定义都要求其编译器报告错误。语言定义也能允许运算对象类型间的类型转换，例如当二元算术运算符作用于一个整数和一个实数时，编译器会把其中的整数转换为实数。
中间代码生成
经过语法分析和语义分析后，许多编译器为源程序产生更低级的显式中间表示，可以把这种中间表示想象成一种抽象机的程序。这种中间表示必须具有两个性质：它易于产生并且易于翻译成目标程序。
第 7 章主要采用一种称为三地址代码的中间表示形式，它像一种抽象机的汇编语言，这种机器中存储单元的使用类似于寄存器。三地址代码由三地址指令序列组成，每条三地址指令最多有三个操作数，语句(1.1)的三地址代码如下：
t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3
这种中间形式已有它们的格式。首先，除了赋值语句外，每条指令至多有一个算符，因此，在生成这些指令时，编译器必须决定运算完成的次序，语句(1.1)的乘优先于加。其次，编译器必须产生临时变量，用以保留指令语句的计算结果。第三，某些三地址指令的运算对象不是三个，例如指令序列(1.3)的第一条和最后一条指令。
代码优化
独立于机器的代码优化既试图改进中间代码，以便产生较好的目标代码。通常，“较好”是指执行较快，但也可能期望其他目标，如目标代码较短或目标代码执行时能够较少。
如果中间代码生成器是为语法的每个产生一系指令，因而得到上面这样的中间代码。用这样的中间代码生成最算法上的一种代码优化便是一种可行的方法，因为产生较优代码的问题可以在代码化阶段得以解决。比如，代码优化器会推断出，把60从整数转换为浮点数可以延在编译时完成，从而用60.0代替60就可以把inttofloat运算删除。还有，id3只被引用一次，就是取它的值得语句id1，因此用id1代替id3，把(1.3)的最后一条指令删除也是可以的。这样，优化器可以得到如下结果：
t1 = id3 * 60.0
id1 = id2 + t1
不同编译器所实现的代码优化是不同的，能完成大部分优化的编译器称为“优化编译器”，但这时编译时间和中间代码的大小都会在某种程度上增加。简单的优化也可以使目标程序的运行时间大大缩短，而编译速度并没降低太多。
代码生成
代码生成是把源程序的一种中间表示作为输入并把它映射到一种目标语言。如果目标语言是机器代码，则需要为程序所用的变量选择存储器内存单元，然后把中间指令序列翻译为完成同样任务的机器指令序列。此阶段的一个关键问题是寄存器分配。
例如，使用寄存器R1和R2，可以把上面代码优化阶段的中间代码可以翻译成:
MOVF id3, R2
MULF #60.0, R2
MOVF id2, R1
ADDF R2, R1
MOVF R1, id1
符号表管理
编译器一项重要工作是记录源程序中使用的变量名，并收集每个名字的各种属性。这些属性散落在名字有关分析结果，类型检查和使用等信息。如果要求是过程名字，还有参数的个数，每个参数的类型，参数传递方式和返回值得类型等。
符号表是为每个变量名保存一个记录的数据结构，记录的域是名字的属性。该数据结构应该设计成允许编译器迅速地找到一个名字的记录，并在此记录中迅速地存储和读取数据。
阶段分组
上面的介绍把编译器从逻辑上分成了7个阶段。最粗糙的看法是把编译器分成分析部分和综合部分。分析部分检测源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。综合部分根据程序的中间表示建立起目标程序，被称为后端。
在实际的编译器中，源于几个阶段的活动可以组合在一起，各阶段之间的中间表示也无需显式构造。源于几个阶段的活动用一遍(pass)扫描来实现，一遍扫描也包括读一个输入文件和写一个输出文件。例如，词法分析，语法分析，语义分析和中间代码生成可以组成一遍，源于机器的代码优化可以单独作为一遍，然后为特定目标机器的代码生成可以作为一个后端遍。
取一个编译器前端，直至它可以产生同一源语言在一类机器上的编译器已经是件普 遍的事。如果原来的后端是经过仔细设计的，那么在它不需要对它做很多更新设计。把几个不同的语言编译成同一种中间表示，让不同的前端使用同一个后端，从而得到一 种机器上不同源语言的编译器，也已经有不少成功的例子。
前端一般包含词法分析,语法分析,语义分析
后端一般包含中间代码生成,代码优化,目标代码生成(汇编生成)
自测题:
结合常用的语言，例如JAVA、Python 、C、C++等，说明：
1.什么是编译程序
- 编译程序是一种翻译器,不过一般是从高级语言翻译到低级语言的计算机程序,比如Gcc,Clang,llvm等
2.什么是解释程序
- 解释程序是用来直接执行源程序所制定的运算,比如Html,JavaScript
3.什么是翻译程序
- 能够完成从一种语言到另一种语言的保语义变换的软件称为翻译程序,比如百度翻译谷歌翻译都是翻译程序
4.以上3种程序的区别
编译程序:完成从高级语言到低级语言的转换,需要进行完整的编译过程
解释程序:效率比编译程序低,边执行边编译,无需完整的编译过程,但是词法分析,语法分析,语义分析只需要进行一次
翻译程序:只是用来保语义翻译
5.简述什么是编译前端和编译后端，编译前端包括编译器的哪几个阶段？
- 编译前端负责处理源代码的词法分析和语法分析,语义分析,生成中间代码,前端一般只依赖于源语言程序,独立于机器架构
- 编译后端负责中间代码优化、目标代码生成和目标代码优化，以提高程序的执行效率和性能,后端只依赖于机器架构,独立于高级语言
- 编译前端包括:词法分析,语法分析,语义分析
综合题
1.论述编译过程的每个阶段的输入及输出，以及每个阶段所采用的相关技术（P6图1.3）, 以声明语句和算术表达式语句的处理过程为例。
- 词法分析（Lexical Analysis）： 输入： 字符流 “position=initial+rate60” 输出： 词法记号（Token）流 <id,1> <=> <id,2> <+> <id,3> <> <60>
- 语法分析（Syntax Analysis）： 输入： 词法单元序列 <id,1> <=> <id,2> <+> <id,3> <*> <60> 输出： 语法树（Syntax Tree）
- 语义分析（Semantic Analysis）： 输入： 语法树 输出： 经过语义检查和类型检查的语法树，并可能进行类型转换
- 中间代码生成（Intermediate Code Generation）： 输入： 经过语义分析的语法树 输出： 中间代码，例如三地址码（Three-Address Code）
- 代码优化（Code Optimization）： 输入： 中间代码 输出： 经过优化的中间代码 图中展示了将常量表达式 “id3 * 60.0” 直接计算出来，简化了后续计算。
- 代码生成（Code Generation）： 输入： 经过优化的中间代码 输出： 目标代码，例如汇编代码或机器代码
作业题
什么是编译程序,翻译程序,解释程序
什么是源语言,目标语言
什么是编译前端和后端
简述编译程序各个阶段的任务和输入输出
编译过程分为那几个阶段
什么是符号表
编译系统中”遍”是什么意思,遍数多好还是少好
第二章 词法分析
词法分析任务
词法分析是编译过程的第一步，它的任务是将源代码分解成一系列的词素（tokens）。每个词素代表一个原子单位的输入，例如一个关键字，一个标识符，一个常量，或者一个操作符。
正规式
正规式（Regular Expression）是一种用于描述一类字符串的模式。在编译器设计中，正规式通常用于定义词法单元的模式，例如标识符，数字，和字符串字面量。
状态转换图
状态转换图（State Transition Diagram）是一种图形表示，用于描述一个有限状态机的行为。在状态转换图中，每个节点代表一个状态，每条边代表一个状态转换。
NFA
非确定性有限自动机（Nondeterministic Finite Automaton，NFA）是一种有限状态机，它可以从一个状态通过一个输入转移到多个状态。NFA通常用于实现正规表达式的匹配。
DFA
确定性有限自动机（Deterministic Finite Automaton，DFA）是一种有限状态机，它从一个状态通过一个输入只能转移到一个状态。DFA通常用于实现词法分析器。
子集法NFA转DFA
子集法是一种将NFA转换为等价的DFA的算法。该算法通过构造一个新的DFA，其状态集合是原NFA状态集合的幂集。
具体如何实现可以看这个帖子
自测题
1、 词法分析器常用的构造方法有哪几种？
- 手动构造 易于理解,但是花费精力较多
- 使用词法分析器生成工具自动构造(使用类似Lexme的词法分析器进行构造),方便简单
2、判断如下图所示的有限自动机是NFA还是DFA，并判断它能识别何种字符串，给出它对应的状态转换表。 
为NFA 能识别(a)*(a|b)字符串
| 状态\输入 | a | b |
|---|---|---|
| 1 | 1, 2 | 2 |
| 2 | END | END |
第三章 语法分析
上下文无关文法
上下文无关文法（Context-Free Grammar，CFG）是一种用于描述编程语言语法的形式化系统。在CFG中，每个规则都是一个从一个非终结符（如一个语句或表达式）到一串终结符和非终结符的映射。
AST
抽象语法树（Abstract Syntax Tree，AST）是源代码的图形表示，它将源代码表示为树形结构，其中每个节点代表一个构造（例如，一个操作符，一个语句，或者一个函数）。AST使得编译器可以轻松地处理源代码的结构和语义。
消除左递归和二义性
左递归是指一个非终结符在其产生式的左边直接或间接地引用自身，这会导致某些自上而下的解析器陷入无限循环。消除左递归的方法包括使用右递归的产生式替换左递归的产生式。
二义性是指一个语句有多于一种的解析树。消除二义性通常需要修改文法，例如通过引入新的非终结符或改变产生式的顺序。
自上而下和LL(1)文法
自上而下的解析是从根节点开始，按照产生式的顺序生成解析树的过程。LL(1)文法是一种特殊的上下文无关文法，它可以被一个自上而下的解析器解析，且在任何时刻，解析器都只需要看前面一个符号就能决定下一步的动作。LL分析表构造,FIRST集和FOLLOW集构造可以看这个帖子
自下而上和LR(1)文法
自下而上的解析是从叶节点开始，按照产生式的逆序生成解析树的过程。LR(1)文法是一种特殊的上下文无关文法，它可以被一个自下而上的解析器解析，且在任何时刻，解析器都只需要看前面一个符号就能决定下一步的动作。相关帖子可以看这个帖子
自测题
1.什么是上下文无关文法，上下文无关文法由哪几部分组成（文法的定义）。
上下文无关是指产生式左边的非终结符可以被右边的字符串自由替换,而无需考虑该非终结符出现在上下文中的具体环境
- 形式地说,一个上下文无关文法G是一个四元组(Vt,Vn,S,P), 用于描述上下文无关语言。它定义了一组规则，用于生成语言中的所有字符串。
- Vt是终结符,Vn是非终结符,S是开始符号,P是产生式有限集合
2.LL（1）文法和LR文法适用于哪些语句的语法分析？适用于哪些语句的语义分析？并给出原因（理由）。
- LL文法自顶向下语法分析器,适合简单语句,不适合语义分析,不具备回溯功能
- LR 文法自底向上语法分析器,适合一切语句,具备完整上下文信息和语法制导翻译, 更适合一切的语义分析
3.预测分析器模型由哪些部分组成。
- 栈,输入,预测分析程序,分析表M,输出
4.LR分析器模型由哪些部分组成。
- 输入,栈,LR分析驱动程序,分析表,输出
5.自上而下语法分析的基本思想。
- 自上而下语法分析，也称为预测型语法分析，其基本思想是从文法的起始符号开始，尝试推导出与输入符号串完全匹配的符号序列。它采用了一种类似于“预测”的方式，根据当前已有的符号和文法规则，尝试预测下一个应该出现的符号，并逐步构建语法树。
6．自下而上语法分析的基本思想
- 自下而上语法分析，也称为移进-归约分析，是一种从输入符号串开始，逐步将其归约为文法起始符号的语法分析方法。它不像自上而下分析那样进行预测，而是根据已扫描的符号和文法规则，尝试将输入符号串的子串“归约”成相应的非终结符，最终目标是将整个输入符号串归约成文法的起始符号。
综合题
一．完成分析以下文法 G 的 LL(1) 预测分析器（语法分析器）的构造。
(1) L → E;L | ε
(2) E → TE’
(3) E’ → +TE’ | -TE’ | ε (4) T → FT’
(5) T’ → 乘号(markdown 用了星号当乘号会破坏当前的加粗语法,体谅一下)FT’ | /FT’ | mod FT’ | ε (6) F → (E) | id | num
1. 给出或画出预测分析器模型的组成
预测分析器模型由以下部分组成：
- 栈: 用于存储文法符号，初始状态下栈底为
$，栈顶为文法开始符号S。 - 分析表: 一个二维表格，根据栈顶符号和当前输入符号决定语法分析器的动作（移进、归约、接受、报错）。
- 输入语句: 待分析的符号串，末尾添加结束符
#。 - 分析程序: 根据分析表和当前输入符号对栈进行操作，控制语法分析过程。
模型示意图:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
┌────────┐ ┌────────┐
输入语句 --> │ 分析程序 │ --> 分析结果
└────────┘ └────────┘
▲ │
│ │
│ ▼
┌────────┐
│ 栈 │
└────────┘
▲
│
│
┌────────┐
│ 分析表 │
└────────┘
2. 构造预测分析表
技巧: 看到该行的行首非终结符 A 找到左部是上面看到的这个非终结符 A 的产生式，根据产生式右部的不同，按以下三种情况处理：
如果产生式是以非终结符 B 打头的序列 α ，那么找到 FIRST(B)，将 FIRST(B) 集合中每个元素所在列、非终结符 A 所在行确定的位置填写上序列 α
如果产生式是以终结符 a 打头的序列 β ，那么直接去找终结符 a 所在列，并将 β 填入 A 行 a 列的位置中
如果产生式是 ε，则找到 FOLLOW(A) ，将 FOLLOW(A) 集合中每个元素所在列、非终结符 A 所在行确定的位置填写上
3. 给出驱动器算法的伪代码
4. 填表给出用此分析器分析句子 id * id + id; # 的过程
| 步骤 | 栈 | 输入 | 动作 |
|---|---|---|---|
| 1 | $L | id * id + id; # | L→E;L L移出,压入E;L |
| 2 | $L;E | id * id + id; # | E→TE’ E移出,压入TE’ |
| 3 | $E;E’T | id * id + id; # | T→FT’ T移出,压入FT’ |
| 4 | $E;E’T’F | id * id + id; # | F→id F移出,压入id |
| 5 | $E;E’T’id | id * id + id; # | 匹配id，栈顶id弹出 |
| 6 | $E;E’T’ | * id + id; # | T’→FT’ T’移出，压入FT’ |
| 7 | $E;E’T’F* | * id + id; # | 匹配，栈顶弹出 |
| 8 | $E;E’T’F | id + id; # | F→id F移出，压入id |
| 9 | $E;E’T’id | id + id; # | 匹配id，栈顶id弹出 |
| 10 | $E;E’T’ | + id; # | T’→ε T’移出，ε不压栈 |
| 11 | $E;E’ | + id; # | E’→+TE’ E’移出，压入+TE’ |
| 12 | $E;E’+T | + id; # | 匹配+，栈顶+弹出 |
| 13 | $E;E’T | id; # | T→FT’ T移出，压入FT’ |
| 14 | $E;E’T’F | id; # | F→id F移出，压入id |
| 15 | $E;E’T’id | id; # | 匹配id，栈顶id弹出 |
| 16 | $E;E’T’ | ; # | T’→ε T’移出，ε不压栈 |
| 17 | $E;E’ | ; # | E’→ε E’移出，ε不压栈 |
| 18 | $E; | ; # | 匹配;，栈顶;弹出 |
| 19 | $L; | # | L→ε L移出，ε不压栈 |
| 20 | $# | # | 匹配#，栈顶#弹出，分析成功，语法正确 |
5. 填表给出用此分析器分析句子 id + id * ; # 的过程
分析过程和上面类似，指针移动到”;”时会导致该句子无法被该文法识别，分析过程中会出现语法错误。
二．有文法 G：
(1) E → E + T
(2) E → T
(3) T → T * F
(4) T → F
(5) F → (E)
(6) F → i
1. 完成表 2 中 LR 分析器利用 LR 分析表和驱动器对输入串 i * i + i 进行分析的过程
2.若在语法分析同时进行语义分析，请在有语义翻译动作的步骤中标出，无语义翻译动作的步骤中空白，如步骤1~步骤3。
| 步骤 | 栈内容 | 当前输入 | 移进-规约动作 | 语义动作 |
|---|---|---|---|---|
| 1 | #0 | i*i+i# | 移进：s5 | |
| 2 | #0i5 | *i+i# | 规约：r6 (F→i) | F.val := i.val |
| 3 | #0F3 | *i+i# | 规约：r4 (T→F) | T.val := F.val |
| 4 | #0T2 | *i+i# | 移进：s7 | |
| 5 | #0T2*7 | i+i# | 移进：s5 | |
| 6 | #0T2*7i5 | +i# | 规约：r6 (F→i) | F.val := i.val |
| 7 | #0T2*7F5 | +i# | 规约：r4 (T→F) | T.val := F.val |
| 8 | #0T2*7T10 | +i# | 规约：r3 (T→T*F) | T.val := T.val * F.val |
| 9 | #0T2 | +i# | 规约：r2 (E→T) | E.val := T.val |
| 10 | #0E1 | +i# | 移进：s6 | |
| 11 | #0E1+6 | i# | 移进：s5 | |
| 12 | #0E1+6i5 | # | 规约：r6 (F→i) | F.val := i.val |
| 13 | #0E1+6F3 | # | 规约：r4 (T→F) | T.val := F.val |
| 14 | #0E1+6T9 | # | 规约：r1 (E→E+T) | E.val := E.val + T.val |
| 15 | #0E1 | # | 接受：acc |
第四章 语义分析
语法制导
语法制导定义（Syntax-Directed Definition，SDD）是一种用于描述输入串如何被翻译成输出的方法，它将语义规则与语法规则关联起来。在SDD中，每个语法规则都有一组相关的语义规则。
属性
在语法制导定义中，属性是与语法单元关联的值。属性可以是继承的（从父节点或兄弟节点获取值）或者是合成的（从子节点获取值）。属性的值可以是任何类型，包括基本类型（如整数和字符串）和复杂类型（如符号表和抽象语法树）。
翻译方案
翻译方案（Translation Scheme）是一种特殊的语法制导定义，它将语义动作嵌入到语法规则中。在翻译方案中，语义动作通常是一些生成中间代码或目标代码的指令。
自测题
1、 简述语法制导翻译的基本思想
利用上下文无关文法描述程序的语法结构。为文法的每个产生式规则关联一组语义动作（Semantic Actions）。 这些动作定义了如何根据产生式规则中的语法成分来计算语义属性或生成中间代码。
在语法分析过程中，当识别出一个产生式规则时，就执行与该规则相关联的语义动作。
概要:将代码生成和语法分析结合起来,利用语法规则来指导代码生成
2、 文法符号的属性有哪两类，两类属性的计算过程是怎样的？ 
- 综合属性和继承属性
- 综合属性的值只能通过其子节点的属性值来计算。信息从语法树的底部向上流动。
- 继承属性的值可以通过其父节点、兄弟节点或自身节点的属性值来计算。信息可以在语法树中横向或向下流动。
第五章 类型检查
不考 PASS
第六章 运行时存储空间的组织和管理
存储分配策略
在编译器设计中，存储分配策略是决定如何分配和管理计算机内存的策略。以下是一些常见的存储分配策略：
静态存储分配
在静态存储分配中，所有的内存需求都在编译时确定。这种策略的优点是它简单且执行效率高，但缺点是它不能支持动态数据结构（如链表和树）和递归。
栈式存储分配
在栈式存储分配中，内存被组织成一个栈，新的内存块被压入栈顶，释放内存时则从栈顶弹出。这种策略支持动态数据结构和递归，但不能处理在函数调用之间持久存在的数据。
堆式存储分配
在堆式存储分配中，内存被动态地分配和释放。这种策略可以处理在函数调用之间持久存在的数据，但管理堆的复杂性和开销比其他策略要大。
自测题
1 JAVA、Python 、C、C++语言的编译系统应该采用哪种存储分配策略，并简述理由。
- Java 面向对象 ,主要采用堆分配策略(New),辅助以栈
- Python 面向对象 ,主要采用堆分配策略(New),辅助以栈
- C/C++ 静态分配,堆分配,栈分配
- 面向对象的语言常用堆分配,操作灵活
- 更底层的语言可以选择静态分配,上限更高
2 编译系统常见的存储分配策略有几种？它们都适合于什么性质的语言？
- 静态分配,适合早期的编程语言，如 Fortran,嵌入式系统等资源受限的环境，需要可预测的内存使用,程序中数据结构大小固定，不需要动态增长的场景。
- 栈分配适合大多数编程语言,使用栈分配来管理函数的局部变量和参数。尤其是数据量较小、生命周期在函数内的变量。
- 堆分配适合现代大多数编程语言，如 Java、Python、C++ 等，都大量使用堆分配。适合于数据量较大、生命周期不确定、需要动态增长的数据
第七章 中间代码生成
后缀表示(逆波兰表达式)
后缀表示法，也被称为逆波兰表示法，是一种不需要括号来表示运算优先级的数学表达式表示法。在这种表示法中，运算符被放在与其相关的操作数之后。例如，中缀表达式 “2 + 3” 在后缀表示法中表示为 “2 3 +”。
图形表示(AST和DAG)
抽象语法树（AST）和有向无环图（DAG）是编译器中常用的两种数据结构，用于表示源代码的结构。
抽象语法树是源代码的图形表示，它将源代码表示为树形结构，其中每个节点代表一个构造（例如，一个操作符，一个语句，或者一个函数）。AST使得编译器可以轻松地处理源代码的结构和语义。
有向无环图是一种可以表示具有共享子表达式的表达式的图形结构。在DAG中，节点代表操作数，边代表操作符。如果两个子表达式的值和操作符都相同，那么它们就可以共享同一个节点。这使得DAG可以用于优化，例如，消除公共子表达式和死代码。
三地址码
三地址码是一种中间代码表示，它每条指令最多包含三个地址（即，两个源操作数和一个结果）。三地址码的主要优点是它的结构简单，易于生成和转换。
三地址码通常包含以下类型的指令：
- 赋值指令，例如
x = y - 二元运算指令，例如
x = y + z - 一元运算指令，例如
x = -y - 无条件跳转指令，例如
goto L - 条件跳转指令，例如
if x < y goto L
自测题
一．给出下面表达式的语法树和有向无环图DAG(重复计算的式子连起来就行)。
（1）P201图7.2 
（2）c=a*(b-c)- (b-c-5)
（3）c=(a+b)*(c+d)-(a+b+c)
AST:
graph TD
assign("=")---c1("c")
assign---minus("-")
minus---multiply("*")
multiply---plus1("+")
plus1---a("a")
plus1---b("b")
multiply---plus2("+")
plus2---c2("c")
plus2---d("d")
minus---plus3("+")
plus3---plus4("+")
plus4---a2("a")
plus4---b2("b")
plus3---c3("c")
DAG:
第八章 代码生成
基本块
基本块是一个连续的三地址语句序列，控制流从它的开始进入，并从它的末尾离开，没有停止或分支的可能性（末尾除外）。下面三地址语句序列形成一个基本块：
t1=a*a
t2=a*b
t3=2*t2
t4=t1+t3
t5=b*b
t6 =t4+t5
优化原则
- 等价原则 经过优化后不应改变程序运行的结果
- 有效原则 使优化后的目标代码运行时间较短,占用的存储空间较小
- 合算原则 应尽可能以较低的代价取得较好的优化效果
基本块的优化策略
- 删除局部公共子表达式
- 删除死代码
- 交换相邻的独立语句
自测题
1、 简述编译过程中代码优化必须遵循的原则
- 等价原则 经过优化后不应改变程序运行的结果
- 有效原则 使优化后的目标代码运行时间较短,占用的存储空间较小
- 合算原则 应尽可能以较低的代价取得较好的优化效果
2、对中间代码中基本块的优化和循环优化都是与机器无关的代码优化吗？请给出3-5种对中间代码优化的方法。
中间代码基本块 (Basic Block) 是一段顺序执行的代码,比如for循环里面的操作可以看成一个独立于for循环外的基本块,亦或是单片机对各个引脚赋初值都是一个基本块
对中间代码中基本块的优化和循环优化都属于与机器无关的代码优化。与机器无关的代码优化指的是在不考虑目标机器具体架构的情况下，对中间代码进行的优化，其目的是为了提高代码的效率和质量。
- 删除局部公共子表达式
- 删除死代码
- 交换相邻的独立语句