编译原理

1.介绍:

1.1 翻译程序:

将某一种语言描述的程序(源程序——Source Program)翻译成等价的另一种语言描述的程 序(目标程序——Object Program)的程序。

1.1.1 解释程序与编译程序:

解释程序:

边解释边执行：不断读取源程序的语句，解释语句，读取此语句需要的数据，根据执行结果读取下一条语句，继续解释执行，直到返回结果

编译程序:

将源程序完整地转换成机器语言程序或汇编 语言程序，然后再处理、执行的翻译程序.

编译系统 =编译程序 +运行系统

1.2 总体结构:

1.3 词法分析:

词法分析器从左到右扫描组成源程序的字符 串，并将其转换成单词串；同时要：查词法 错误，进行标识符登记（符号表管理）。

输入：字符串

输出： (种别码，属性值)——序对  属性值——token的机内表示

1.4 语法分析:

功能:Parser实现“组词成句”： 将词组成各类语法成分， 例如因子、项、表达式、语句、子程序 … 构造分析树,指出语法错误,指导翻译.

输入：token序列

输出：语法成分

1.5 语义分析:

分析由语法分析器识别出来的语法成分的语义

获取标识符的属性：类型、作用域等

语义检查：运算的合法性、取值范围等

子程序的静态绑定：代码的相对地址

变量的静态绑定：数据的相对地址

1.6 中间代码生成:

中间代码的特点:

简单规范

与机器无关

易于优化与转换

1.7 代码优化:

对中间代码进行优化处理，使程序运行能够 尽量节省存储空间，更有效地利用机器资源， 使得程序的运行速度更快，效率更高.

这种优化变换必须是等价的。 分为（与机器无关的优化）和（与机器有关 的优化）两种.

1.8 目标代码生成:

编译程序的最后一个阶段.

为中间代码中出现的运算对象分配存储单元、 寄存器等.

将中间代码转换成目标机上的机器指令代码或汇编代码.

目标代码的形式:

具有绝对地址的机器指令

汇编语言形式的目标程序

模块结构的机器指令（需要链接程序）

2.高级语言及文法:

2.1 语言:

语言:信息交流的工具.

程序设计语言——形式化的内容提取  程序设计语言(Programming Language)：

组成程序 的所有语句的集合.

程序(Program)：满足语法规则的语句序列。

语句(Sentence) ：满足语法规则的单词序列。

单词(Token) ：满足词法规则的字符串。

2.2 基本定义:

2.2.1 字母表:

字母表（Alphabet）∑是一个非空有 穷集合，字母表中的元素称为该字母表的一 个字母（Letter），也叫字符（Character).

2.2.1.1 字母表的闭包:

用加号表示.

就是把字母表中的元素互相组合起来,然后再加上之前的.

2.2.2 句子:

设∑是一个字母表，∀x ∈ ∑*，x称 为字母表∑上的一个句子（sentence），ε叫做∑ 上的一个空句子.

设∑是一个字母表，对任意的x， y∈∑*，a∈∑，句子xay中的a叫做字符a在该句 子中的一个出现(occurrence)。

设∑是一个字母表，∀x∈∑*，句子x 中字符出现的总个数叫做该字符串的长度 (length)，记作|x|.

2.2.3 前后缀:

设∑是一个字母表，对∀x，y，z∈∑*，如 果x=yz，则称y是x的前缀(prefix)，如果z≠ε，则称y是x 的真前缀(proper prefix)；z是x的后缀(suffix)，如果 y≠ε，则称z是x的真后缀(proper suffix)。

如果x=yz，w=yv，则称y是x和w的公共前缀 (common prefix)，如果x和w的任何公共前缀都是y 的前缀，则称y是x和w的最大公共前缀(maximal common prefix).

如果x=zy，w=vy，则称y是x和w的公共后缀 (common suffix )，如果x和w的任何公共后缀都是y 的后缀，则称y是x和w的最大公共后缀(maximal common suffix).

2.2.4 子串:

2.2.5 语言:

设∑是一个字母表，∀L ⊆ ∑*，L称为字 母表∑上的一个语言（Language），∀x∈L，x叫做L 的一个句子。

所有句子的集合.

2.3 文法:

2.3.1 定义:

文法G为一个四元组: Ｇ = (Ｖ，T，Ｐ，Ｓ)

Ｖ：非终结符集:每个非终结符称为一个语法变量——代表某个语言的 各种子结构

T：终结符集:语言的句子中出现的字符，Ｖ∩T = ∅

Ｓ：开始符号，S∈Ｖ代表文法所定义的语言，至少在产生式左侧出现一次

Ｐ：产生式(Product)集合.

2.3.1.1 产生式:

α→β，被称为产生式（也称为定义式），读作： α定义为β。其中α∈(Ｖ∪T)+，且α中至少有Ｖ 中元素之一出现。β∈(Ｖ∪T)*。

α称为产生式α→β的左部(Left Part)

β称为产生式α→β的右部(Right Part)。

产生式定义各个语法成分的结构（组成规则）

举个例子:

简写:

2.3.2 推导与规约:

推导可以 看作是用 产生式的 右部替换 左部.

归约可以看作 是用产生式的 左部替换右部.

2.3.3 语言:

文法Ｇ的作用——语言的有穷描述\

以有限的规则描述无限的语言现象

有限：

产生式集合、终结符集合、非终结符集合

无限：

可以导出无穷多个句子

2.3.4 句子与句型:

句子w是从S开始，在G中可以推导出来的终结符号行，它不含语法变量；

句型α是从S开始，在G中可以推导出来的符号行，它可能含有语法变量；

句子一定是句型，但句型不一定是句子.

句型的包含更广一些.

2.4 文法的分类:

Chomsky体系:

0型文法 (即：短语结构文法)

1型文法 (即：上下文有关文法)

2型文法 (即：上下文无关文法)

3型文法 (即：正规文法)

2.4.1 0型文法:

如果G满足文法定义的要求，则G是０型文 法（短语结构文法PSG: Phrase Structure Grammar ）。

L(G)为短语结构语言（PSL）.

2.4.2 1型文法:

如果对于∀α→β∈P，均有|β|≥|α|成立，则 称Ｇ为１型文法

即 ： 上 下 文 有 关 文 法 （ CSG——Context Sensitive Grammar）

L(G)为1型/上下文有关语言(CSL).

2.4.3 2型文法:

如果对于∀α→β∈P，均有|β|≥|α|，并且 α∈V成立，则称G为２型文法

即：上下文无关文法(CFG: Context Free Grammar)

L(G)为2型/上下文无关语言（CFL） .

CFG能描述程序设计语言的多数语法成分.

2.4.4 正规文法:

设A、B∈V， α∈T+

右线性(Right Linear)文法：A→ αB或A→α

左线性(Left Linear)文法：A→Bα或A→α 都是３型文法(正规文法 Regular Grammar - RG)

L(G)为3型/正规集/正则集/正则语言（RL）

能描述程序设计语言的多数单词

2.4.4 CFG的语法树:

CFG：上下文无关文法

相对简单

描述能力也比较恰当

高级程序设计语言的绝大多数成分都可以用 CFG来描述

语法成分是上下文无关的，即在其句型中总是存在这样的子串，该子串是由某个变量推导出来的.

语法树的目的：希望更清晰地表示句型的文法结构以及推导和归约的过程

根 据 CFG 的 定 义 ， CFG 中 每 个 产 生 式 AX1X2…Xn的左侧 只有一个变量，右侧 有一个或多个变量,可以用如下的树结构表示:

用树的形式表示句型的生成.

树根：开始符号.

中间结点：非终结符

叶结点：终结符或者非终结符.

每个推导对应一个中间结点及其儿子.

又称为分析树(parse tree)、推导树 (derivation tree)、派生树(derivation tree).

2.4.4.1 短语:

设有CFG G=(V，T，P，S)，∃α, β, γ∈(V∪T)*，S γAβ，A α，则称α是句型 γαβ的相对于变量A的短语(phrase).

短语可以看作是语法树中子树的结果.

如果此时有Aα，则称α是句型γαβ的相对于变 量A的直接短语(immediate phrase)。

2.4.4.2 句柄:

设有CFG G=(V，T，P，S)，G的句 型的最左直接短语叫做句柄(handle)。

短语：一棵子树的所有叶子自左至右排列起来 形成一个相对于子树根的短语。  直接短语：仅有父子两代的一棵子树，它的 所有叶子自左至右排列起来所形成的符号串。  句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列.

2.5 最左推导与最右推导:

每次推导都施加在句型的最左边的语法 变量上。——与最右归约对应.

最右推导:每次推导都施加在句型最右边的语法变 量上。——与最左归约（规范规约）对应.

2.6 CFG的二义性:

对(文法E→E+E|E*E|(E)|id ）,有两种语法树:

如果一个文法的句子存在两棵分析树，那么该句子是二义性的。

如果一个文法包含二义性的句子，则称这个文法是二义性的; 否则，该文法是无二义性的。

2.6.1 消除文法的二义性:

3.词法分析:

3.1 词法分析器:

功能：输入源程序，输出单词符号。即：把构成源程序的字符串转换成“等价的”单词序列

根据词法规则识别及组合单词，进行词法检查

对数字常数完成数字字符串到二进制数值的转换

删去空格和注释等不影响程序语义的字符

3.2 单词的分类:

分类方法:

对于标识符和常量，按单词种类分类

属于同一类的不同单词，具有相同的种别码，通过不同的属性值来区分

问题：如何存储标识符和常量的属性值

方法1：用标识符和常量本身的值表示

方法2：用指针表示

3.3 源程序的输入缓冲与预处理:

源程序以字符流形式存储于外部介质,为正确识别单词，编译程序需要一系列相关处理.

3.4 错误处理:

1.非法字符检查:

维护一个合法字符集合，对于每一个输入字 符，判断该字符是否属于该字符集合

2.单词拼写错误:

关键字拼写词法分析阶段无法检测，待语法 分析阶段发现错误

标识符拼写错误，如3b78，处理方法有两种

识别出整数3、标识符b78

错误的标识符

3.不封闭错误检查:

影响正常程序分析

对注释或字符串长度加以限制，如注释长度不超过1行，字符串长度最大是256

4.重复声明检查:

兼顾符号表的查填工作.

5.错误恢复与续编译:

词法分析阶段的错误使得编译无法继续进行， 需要采取措施使得编译继续下去.

3.5 单词的描述:

单词是程序设计语言的基本语法单位

如果每类单词都看作一种语言，则大多数单词词法可以用正则文法来描述.

3.5.1 正则文法与正则表达式:

正则文法 G = ( V ， T ， P ， S)中，对 ∀ α →β ∈ P ， α →β均具有形式A → w 或A →wB (A → w 或A →Bw ) ， 其中 A ， B ∈ V ， w ∈ T+ 。

正则文法描述 T上的正则语言.

除正则文法外，正则表达式也可以描述单词  正则文法和正则表达式的能力相同，可以互 相转化  正则表达式比正则文法更直观，有时首选正 则表达式来表示正则语言.

一个正则表达式通常称为一个模式，用来描 述一系列符合某个句法规则的字符串.

二者可以互相转换.

3.6 高级语言词法的简单描述:

单词符号的文法，用来描述高级语言中的： 标识符、常数、运算符、分界符、关键字.

3.6.1 有穷状态自动机:

正则语言的另一种等价描述.

从语言识别的角度实现对相应语言的刻画

具有有穷个内部状态，不同状态代表不同意义.

系统只需根据当前所处的状态和面临的输入,就能确定后继的行为.

3.6.1.1 形式定义:

3.6.1.2 表示方式:

一个ＤＦＡ有三种表示： （ 1）转移函数； （ 2）转移矩阵； （ 3）状态转换图。

设ＤＦＡ Ｍ＝（｛０，１，２，３ ｝，｛ a ， b｝， δ，０，｛３｝)

转移函数:

转移矩阵:

状态转换图:

3.6.1.3 执行过程:

3.6.1.4 构造过程:

有穷状态自动机和正则文法等价

3.7 单词识别问题:

⑴ 从初始状态出发；

⑵ 读入一个字符；

⑶ 按当前字符转入下一状态；

⑷ 重复 ⑵ -⑶ 直到无法继续转移为止。

3.7.1 标识符的识别:

4. 自顶向下的语法分析:

4.1 概述:

语法分析(syntax analysis)是编译程序的核心部分， 其任务是检查词法分析器输出的单词序列是否是源语言中的句子，亦即是否符合源语言的语法规则.\

简单来说,就是确定句子的类型,针对不同的类型,所要采取的语义动作也不同.

4.1.1 分析方式:

判断某个单词序列是否是源语言的句子，主要有两种方式:

产生句子的方式：从文法的开始符号开始，逐步推导出该单词序列，也称为自顶向下的语法分析

识别句子的方式：逐步将构成程序的单词序列归约为文法的开始符号，称为自底向上的语法分析

无论是自顶向下还是自底向上 ,语法分析器都是自左到右地扫描输入单词序列 ,每次读入一个单词 ,针对输入单词序列建立一棵语法分析树 。

不同的分析方法对应着不同的构建树的方式.

4.1.2 基本思想: 递归下降:

从文法的开始符号出发，寻求所给的输入符号串的一个最左推导

自顶向下分析实际上是一种试探性的过程，可能导致分析效率极低，甚至失败.

针对开始符号的产生式,和第一个读入的符号:

1.选择他的一个产生式.

2.针对产生式右边的每一项进行遍历.

3.有两种情况:

如果是终结符,那么判断和当前的符号是否相等,相等就进入获取下一个符号.不相等就报错.

如果不是终结符,就递归的调用这个方法.

这种方法模拟了自顶向下建立语法分析树的过程,而且属于最左推导(即:一个产生式右部,最左边的符号先进行遍历.)

但是这种方法存在一些问题:

比如二义性问题,左递归问题,回溯问题(可能匹配到一半了 发现压根不是这个句子,于是还要从头再来).等等.所以是不确定的自顶向下分析方法.

于是我们希望实现确定的自顶向下分析方法,毋庸置疑的是,这种方法对文法自然有着一定的要求,而符合这种条件的文法就是LL(1)文法.

4.1.3 LL(1)文法:

核心是候选式唯一.

4.2 预测分析法:

一种高效的自顶向下分析法,能够对LL(1)文法实现确定的自顶向下分析.

4.2.1 工作流程:

1. 构建 First 集合： 计算每个非终结符的 First 集合，即该非终结符能推导出的第一个终结符集合。这是为了处理文法中的 ε 规则和 First 集合。

2. 构建 Follow 集合： 计算每个非终结符的 Follow 集合，即该非终结符可能在推导中的后继位置的终结符集合。这是为了处理文法中的左递归和确定每个产生式在分析中的位置。

3. 构建预测分析表： 利用 First 集合和 Follow 集合，构建 LL(1) 预测分析表。这个表是一个二维表格，行代表文法的非终结符，列代表终结符和输入符号。表中的每个单元格包含一个产生式，表示在给定非终结符和输入符号的情况下，应该使用哪个产生式进行推导。

4. 进行分析： 从文法的开始符号开始，根据预测分析表进行分析。从输入串中读取一个符号，查找表中对应的产生式，进行推导。重复这个过程直到达到文法的结束符号.

4.2.1.1 First集:

4.2.1.1.1 符号:

终结符的First集是自己.

非终结符的First集是从这个非终结符,推导出的所有的串,的首终结符的集合.

就是写出一个非终结符的所有的推导,然后找出其中第一次出现的非终结符,如果有好几个(或)就一并写出.

如果非终结符能推导出空串,那么也要有空串.

4.2.1.1.2 符号串:

1.首先加入符号串的第一个符号的first集合.

2.如果第一个符号可以推出空串,则加入第二个符号的first集合,以此类推.

4.2.1.2 Follow集:

4.2.1.2.1 符号:

Follow集的含义是在一个非终结符后面所有可能出现的符号.

如果这个式子是最右符号,那么还需要添加结束符.

文法的开始符号的follow集要加入结束符.

逐个分析每个产生式.follow集永远不可能为空.

4.2.1.2.2 符号串:

一般不求.

4.2.1.3 构建LL(1)分析表:

1.确定坐标:

左边是非终结符,上面是终结符和结束符号.

2.确定内容:

内容是一个个的产生式,

3.填入内容:

逐条分析产生式,对于每条产生式:

求出产生式的first集.

把[产生式左部,first集中的元素]这个位置放上产生式.

如果这个集合中带有空串,那么在[产生式左部,产生式左部的非终结符的follow集合中的元素]这个位置填入产生式

4.错误处理:

在剩下的位置填入错误符号.

4.2.1.4 使用分析表分析输入的式子:

根据栈顶元素和输入缓冲区的元素在分析表中定位到所需要的产生式,进行推导.

直到两边都只剩下结束符号为止.

(1)根据栈首元素和输入缓冲区的第一个元素查表

然后得到产生式进行推导.用推导右边替换左边.

(2)如果栈顶和输入缓冲区开头相匹配 那就消掉

直到什么都没有了为止.

4.3 递归下降分析法:

所谓递归下降分析法，是指根据各个候选式的结构，为文法的每个语法变量编写一个处理程序，用来识别该语法变量所代表的语法成分.

4.3.1 语法图:

使用语法图可以方便地进行递归子程序的设计.

语法图是根据产生式来画的.每一条产生式对应着一个语法图.

用圆圈代表状态.箭头上面的变量代表着读入的符号.

举个例子:

E→TE’ 这个句子的语法图:

5.自底向上的语法分析:

自底向上的语法分析，是指从给定的输入符号串出发，试图自底向上地为其建立一棵语法分析树.

一个输出流向栈中输出.

一旦可以规约,就发生规约.

如果不能规约,那就继续读入下一个token

5.1 LR分析法:

为了解决自底向上分析中的移进-移进冲突,和移进-规约冲突,准确的识别出句柄(应当规约的部分),LR引入了状态的概念.

5.1.1 项目:

每个项目对应着一个自动机的状态

针对一个产生式,用一个圆点表示状态,代表了它识别的程度.

比如这个产生式s->bBB,就有四个状态,每一个状态被称为项目.

s->.bBB 移进项目 点后面是终结符

s->b.BB 待约项目 点后面是非终结符

s->bB.B 待约项目

s->bBB. 规约项目 点后面是空

5.1.1.1 等价项目:

同一个状态,就是等价的项目.

为了减少具体的状态,产生了等价项目.

以等价项目集合作为状态构造自动机.

5.1.1.2 增广文法:

就是新增一个开头,使其指向原先的开头.

5.1.2 构建LR(0)分析表.

5.1.2.1 先求文法的所有项目:

5.1.2.2 构建自动机:

5.1.2.2.1 初始状态:

初始状态一开始为增广文法的第一句.

然后求闭包,就是找到这个状态所有的等价状态.

5.1.2.2.2 状态转移:

针对初始状态中的每一个项目,判定:

如果为规约项目,那么状态不会改变,结束.

对于其他情况,观察每个项目的点后面的元素,然后传入这个元素就意味着它能被识别.

这样会产生很多新的状态.

对每个状态接着求闭包,然后转移.

5.1.2.2.3 终止:

直到新产生的状态中,全部都是规约项目为止.

构建出来的这个东西,被称为LR(0)的规范集项目族.

5.1.2.3 根据自动机构建分析表:

首先明确一下分析表的结构.

他的行是状态的个数,列分两种,准确的说是两个表.action表和goto表.action表的列是终结符和结束符号,goto表是非终结符.

然后开始遍历各个状态.

对于每个状态的转移过程:

1.如果接受的是终结符,那么执行的是移入过程,填入的是action表的[当前状态,接受的终结符]这个位置,填入转移的状态数(一般用s表示.)

2.如果接受的是非终结符,那么执行的是规约过程,同样填入相同的位置.只不过去掉了s,直接填入数字.

3.如果这个状态已经是规约状态,那么调用的就是规约语句,填入r+规约语句.

4.如果这个状态是增广文法的一开始状态,填入acc.

5.1.2.4 根据分析表分析输入文法:

维护一个输入栈,一个状态栈,一个输入流.

一开始状态为0,输入流为待分析串,输入栈为空.

1.栈顶啥也没有,就执行s,移进.

2.栈顶有非终结符,就goto表,规约(就是在状态栈中加一个状态)

3.栈顶是终结符,就action表.如果是s就移进.加了一个状态,如果是r就规约,少一个状态.

4.直到acc结束.

5.1.3 构建slr(1):simple lr(1)分析表:

前面的过程基本都是一样的.

画完图(也就是构建完自动机)之后,按照正常的方式填表.

填s和goto表的方式都是统一的.

只不过填r(也就是规约项目时),需要根据follow集填入.

分析过程也如上.

6.语法翻译制导与属性文法:

6.1 概述:

为了提高编译程序的可移植性，一般将编译程 序划分为前端和后端 。

前端通常包括词法分析 、语法分析 、语义分析 、 中间代码生成 、符号表的建立，以及与机器无关的中间代码优化等，它们的实现一般不依赖于具体的目标机器.

后端通常包括与机器有关的代码优化 、目标代码的生成、相关的错误处理以及符号表的访问等。

语义分析器的主要任务是检查各个语法结构的静态语义，即验证语法正确的程序结构是否真正有意义，也称为静态语义分析或静态检查

类型检查：操作数和操作符的类型是否相容

控制流检查：控制流转向目标地址是否合法

惟一性检查：对象是否被重复定义

关联名检查：同一名字多次特定出现是否一致

静态检查比较简单，可以和其他工作结合

将静态检查 和中间代码生成结合到语法分析中进行的技术称为语法制导翻译 (syntaxdirected translation) 。

6.2 基本思想:

在进行语法分析的同时，完成相应语义处理.

一旦语法分析器识别出一个语法结构（例如 E E+T），立即对其进行翻译 。

翻译是根据语言的语义进行的，并通过调用 事先为该语法结构编写的语义子程序来实现.

对文法中的每个产生式附加一个 /多个语义动 作 (或语义子程序 )，用于传送或处理语义信息、查填符号表、计算值或者计算中间代码.

在语法分析的过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作 (或调用相应的语义子程序 ) 。

6.2.1 语义子程序:

指明相应产生式中各个文法符号的具体含义，并规定使用该产生式进行分析时所应采取的语义动作.

语义信息是通过文法符号来携带和传递的.

一个文法符号X所携带的语义信息称为 X的语义属性，简称为属性.

文法符号的属性的计算规则称为语义规则.

6.3 翻译模式:

通过将属性与文法符号关联，并将语义规则插入到产生式的右部来描述语言结构的翻译方案.

在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作.

适宜在进行推导时完成.

6.4 语法制导定义:

通过将属性与文法符号关联、将语义规则与产生式关联来描述语言结构的翻译方案.

对应每一个产生式编写一个语义子程序，当一个产生式获得匹配时，就调用相应的语义子程序来实现语义检查与翻译.

适宜在进行推导时完成.

语法制导定义是附带有属性和语义规则的上下文无关文法.

属性是与文法符号相关联的语义信息.

语义规则是与产生式相关联的语义动作.

语法制导定义中的属性类似于程序中用到的数据结构（结构体的成员），用于描述语义信息.

语义规则类似于计算，用于收集、传递和计算语义信息.

由于属性的计算在语法分析过程中进行， 属 性通常被保存在分析树的相关节点 中.

令 X表示分析树中的某节点，则X.a表示该文 法符号的属性 a的值.

6.4.1 属性分类:

6.4.2 依赖图:

依赖图：描述属性之间依赖关系的图，根据语义规则来构造.

每个属性对应依赖图中的一个节点，如果属性 b依赖于属性 c，则从属性c的节点有一条有向边指向属性 b的节点

拓扑排序:

1.在依赖图中寻找一个入度为 0的节点，输出该节点

2.删除该节点的所有出边

3.在剩下的图中继续寻找入度为 0的节点，直到输出 图中的所有节点为止

6.4.3 注释分析树:

节点带有属性值的分析树.

6.5 属性定义:

6.5.1 s型:

只含综合属性的语法制导定义称为 S属性定义。

如果某个语法制导定义是S-属性定义，则可以 按照自下而上的顺序来计算分析树中节点的属性.

6.5.2 l型:

S-属性定义的属性自下而上传播.

如果增加从左向右的传播方向，就得到L属性定义.

6.6. 属性计算:

抽象语法树是把分析树中对语义无关紧要的 成分去掉，是分析树的抽象形式.

7.语义分析与中间代码生成:

7.1 中间代码:

中间代码的作用:

过渡：经过语义分析翻译成中间代码序列

7.2 常用的中间代码:

7.2.1 抽象语法树:

7.2.2 逆波兰表示:

首先明确前,中,后缀表示:

逆波兰表示是一种后缀表示.

表达式的运算顺序就是运算符出现的顺序 ， 它不需要使用括号来指示运算顺序.

7.2.3 三地址码:

三地址码是中间代码的一种抽象表示形式.

所谓三地址码，是指这种代码的每条指令最多只能包含三个地址，即两个操作数地址和一个 结果地址.

每条指令是能够运算的,而且只能包含三个地址.

7.2.3.1 四元式:

四元式是一种比较常用的中间代码形式，它由四个域组成，分别称为op 、arg1 、arg2 和 result .

op是一元或二元运算符

arg1 和arg2分别是op的两个运算对象，可以是变量、常量或编译器生成的临时变量.

运算结果放入result.

7.2.3.2 三元式:

为了节省临时变量的开销，也可以使用只有三个域的三元式来表示三地址码.

三元式的三个域分别称为op ，arg1 和arg2.

arg1 和arg2的含义与四元式类似，区别只是 arg1 和arg2可以是某个三元式的编号，表示用 该三元式的运算结果作为运算对象.

7.2.4 图表示:

抽象语法树：一种中间代码的图表示，可看作 无回路有向图daq (directed acyclic graph) .

表达式a+a*(b-c)-(b-c)/d:

在dag中，每个内节点对应一个运算符，代表表达式的一个子表达式，其子节点则与该运算符的运算对象相对应.

叶节点对应的是变量或者常量，可以看成是原子运算.

可以消除公共子表达式，具有公共子表达式的.节点具有多个父节点

7.3 语句翻译:

编译的任务:

在符号表中记录被说明对象的属性 (类型、 相对地址、作用域等) ，为执行做准备.

类型可以具有一定的层次结构，用类型表达式来表示.

类型表达式或者是基本类型，或者是将类型构造符作用于类型表达式

7.3.1 声明语句:

声明语句的作用：为程序中用到的变量或常量名指定类型.

类型检查：验证程序运行时的行为，是否遵守语言的类型的规定，是否符合该语言关于类型的相关规则

辅助翻译：编译器从名字的类型可以确定该名字在运行时所需要的存储空间。在计算数组引用的地址、加入显式的类型转换、选择正确版本的算术运算符以及其它一些翻译工作时同样需要用到类型信息.

文法:

声明语句的翻译：在符号表中为每个局部名字创建一个表项，同时维护该名字的类型及相对地址等信息

7.3.2 赋值语句:

赋值语句的语义是将赋值号右边算术表达式 的值保存到左边的变量中，其翻译主要是算术表达式的翻译。要实现数组元素的寻址， 需要计算该元素在数组中的相对位移。

7.3.3 流程控制语句:

控制语句的翻译中既可以通过根据条件表达 式改变控制流程，也可以通过计算条件表达式的逻辑值的方式实现条件转移的控制.

switch语句的翻译通过对分支的实现来完成.

过程调用与返回语句的翻译主要在于实现参数的有效传递和相应的存储管理.

7.3.4 I/O语句:

I/O语句要求输出参数都是有效的.

8.符号表:

8.1 作用:

编译的各个阶段都会用到符号表中登记的信息.

协助进行语义检查和中间代码生成.

在目标代码生成阶段，当需要为名字分配地址时，符号表中的信息将是地址分配的主要依据.

编译器用符号表来记录、收集和查找出现在 源程序中的各种名字及其语义信息。

8.2 结构:

符号表是以名字为关键字来记录其信息的数据结构.

支持的两个最基本操作是添加表项和查找表项，这两个操作必须是高效的.

每一个符号表表项中需要存放的基本信息就是符号的名字及其属性 。

散列表可以提高lookup操作的效率，同时也可 以提高insert操作的效率，许多实际编译器的 符号表实现中均采用了散列技术.

8.3 作用域:

变量的作用域满足最近嵌套原则

为每个程序块建立一个符号表，程序块内的符号记录在该程序块所对应的符号表.

建立符号表之间的联系，刻画出符号的嵌套作用域.

8.4 C语言符号表:

一个完整的 C程序由一个或多个相对独立的函数组成，函数之间的通信依靠参数传递和全局变量.

全局变量和函数名的作用域是整个程序，而其余变量的作用域则是定义它们的函数.

符号表中只需要一个局部名字表来管理当前编译的函数中的符号，处理完毕即从该表中删除。

9.运行时的存储组织:

9.1 内存分配:

给定一个源程序，编译程序必须根据源语言 的特征为源程序中的许多问题做出决策，包 括何时、怎样为名字分配内存地址.

静态策略：在编译时即可做出决定的策略.

动态策略：直到程序执行时才能做出决定的策略.

9.2 运行时内存划分:

名字的绑定要体现名字的声明和作用域约定.

过程调用中参数的传递方式分为传值、传地 址、传值结果和传名4种.

典型的运行时内存空间包括目标代码、静态 数据区和动态数据区.

对编译时就能确定其运行时所需要的存储空间的对象实行静态存储分配，对编译时无法 确定过程何时运行、运行时所需要存储空间 的对象实行动态存储分配.

静态存储管理方式支持较高的运行效率，利用适当的策略可以提高内存的利用率，但是 无法支持动态数据和过程的递归调用.

栈式动态存储管理策略针对过程的每一次调用在栈顶创建一个栈单元用来存放这次过程调用产生的活动的数据区。这种方式支持过程的递归调用.

堆管理解决活动结束后数据仍需有效的问题， 但需要使用内存管理器实现对孔洞的管理.

对内存的层次体系的有效利用有助于提高目 标代码的运行效率.

10.代码优化:

10.1 介绍:

代码优化就是为了提高目标程序的效率， 对程序进行等价变换，在保持功能不变的前提下，对源程序进行合理的变换， 使得目标代码具有更高的时间效率和/或空间效率.

空间效率和时间效率有时是矛盾的，有时不能兼顾.

10.2 分类:

机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等.

局部优化：单个基本块范围内的优化，常量合并优化，公共子表达式删除，计算强度削弱和无用代码删除。

全局优化：主要是基于循环的优化，循环不变优化，归纳变量删除，计算强度削减.

10.3 公共子表达式删除:

如果表达式 E在某次出现之前已经被计算过， 并且 E中变量的值从那次计算到本次出现之间 未被改变过，则 E的本次出现称为公共子表达 式 .

用先前的计算结果替换公共子表达式的本次 出现称为公共子表达式删除.

10.4 复制传播:

形如f := g的赋值语句叫做复制语句.

复制传播变换的思想是在复制语句f := g之后 尽可能用 g代替 f.

复制传播变换本身并不是优化，但它给其它优化带来机会.

10.5 无用代码删除:

无用代码是指计算结果以后不被引用的语句.

一些优化变换可能会引入无用代码.

10.6 代码外提:

结果独立于循环执行次数的表达式称为循环 不变计算.

如果将循环不变计算从循环中移出到循环的前面，将会减少循环执行的代码总数，大大提高代码的执行效率。这种与循环有关的优化方法称为代码外提。

10.7 强度削弱:

实现同样的运算可以有多种方式。用计算 较快的运算代替较慢的运算。

11.代码生成:

代码生成是编译的最后一个阶段，由代码生成器完成。其任务是把中间代码转换为等价的、 具有较高质量的目标代码，以充分利用目标机 器的资源。当然，代码生成器本身也必须具有 较高的运行效率.

代码生成器的输入包括中间代码和符号表信息，符号表信息主要用来确定中间代码中的变量所代表的数据对象的运行时地址.

11.1 指令选择:

所谓指令选择是指寻找一个合适的机器指令序列来实现给定的中间代码。

目标机器指令系统的性质决定了指令选择的难易程度.

11.2 寄存器分配:

将运算对象放在寄存器中的指令通常要比将运算对象放在内存中的指令快且短，因此，要想 生成高质量的目标代码，必须充分使用目标机器的寄存器.

选择最优的寄存器指派方案是一个NP完全问题，如果考虑到目标机器的硬件和操作系统对寄存器的使用约束，该问题还会进一步复杂.

11.3 窥孔优化:

窥孔优化是一种简单有效的局部优化方法， 它通过检查目标指令中称为窥孔的短序列， 用更小更短的指令序列进行等价代替，以此 来提高目标代码的质量.

不可达和冗余指令删除、控制流优化、强度削弱、代 数化简、特殊指令使用等都是有效的窥孔优化方法.