编译原理强化版.docx
《编译原理强化版.docx》由会员分享，可在线阅读，更多相关《编译原理强化版.docx（62页珍藏版）》请在冰点文库上搜索。
编译原理强化版
2010计算机科学与技术
编译原理资料整理
[知识点强化版]
杨磊
2013/12/22Sunday
注：
本资料用于知识点全面复习，内容经PPT及整理得到，分成知识点，补充重点，例题三部分适用于有一定时间（至少3天）复习的同学。
目录
第一章编译系统概述2
第二章词法分析3
第三章程序设计语言的语法描述5
第四章自上而下的语法分析7
第五章自下而上的语法分析13
第六章语法制导翻译和中间代码生成24
第七章目标代码生成32
第一章编译系统概述
源语言和源程序
用程序设计语言书写的程序，称为源程序，该程序设计语言称为源语言。
源程序通常用编辑程序输入，用字符（ASCII码）表示，以文本文件形式存储。
目标语言和目标程序
目标语言可以是机器语言（二进制），也可以是汇编语言（字符），但最终结果必定是机器语言。
机器语言程序用二进制文件存储，汇编语言用文本文件存储。
目标程序是经翻译程序加工后用目标语言表示的程序。
翻译程序
将源程序译成逻辑上等价的目标程序的程序。
翻译程序有二种工作方式：
编译和解释
解释方式
以源程序作为输入，输入一句解释执行一句，不产生完整的目标程序，相应的翻译程序称为解释程序
编译方式
将源程序全部译为目标程序，该目标程序可在操作系统环境下直接执行，相应的翻译程序称为编译程序。
解释方式和编译方式比较
解释方式和编译方式的主要区别是：
目标代码的执行方式不同，基本原理和方法没有本质上的区别。
解释方式的优点
提供一种直接的交互调试功能，容易获得较好的动态调试效果。
（结构简单）
解释方式的缺点
在执行时需动态地对程序进行分析翻译，开销大，其执行速度相当于编译方式的1/10至1/100。
（执行速度慢，占用空间大）
编译程序过程（有哪几部分）
从数据加工的角度来看，可将其分成4个逻辑阶段，词法分析、语法分析、语义分析（中间代码产生）、目标代码生成
编译程序各个部分的工作、依据以及输入输出
（一）词法分析
执行词法分析任务的程序称为词法分析器。
任务：
字符串形式单词编码形式单词内部码（二元式）
依据：
语言的构词规则
（二）语法分析
执行语法分析任务的程序称为语法分析器。
任务：
检查源程序的语法结构是否正确
依据：
语言的语法规则
（三）语义分析
执行语义分析任务的程序称为语义分析器或中间代码产生器。
任务：
建立符号表和常数表，记录源程序中标识符属性和常数值，根据语言的语义规定生成中间代码。
依据：
语言的语义内涵
语义分析主要工作为：
语义正确性检查、语义翻译
中间代码
结构简单、意义明确的记号系统，非常接近机器指令，又独立于具体机器。
常用的中间代码有三元式和四元式。
符号表
符号表用于记录源程序中出现的标识符（Identifier），一个标识符往往具有一系列的语义值，它包括标识符的名称、标识符的种属、标识符的类型、标识符值的存放地址等等。
而在四元式中填写的是标识符在符号表中的记录地址，通常称为符号表入口。
常数表
常数表用于记录在源程序中出现的常数。
假定，每个整常数在常数表中占2个字节，每个实常数在常数表中占4个字节。
目标代码生成
执行目标代码生成的程序称为目标代码生成器。
任务：
中间代码目标代码（机器指令或汇编语言）
依据：
目标机器的系统结构
编译程序的前端和后端
由于在编译程序的内部引入了中间代码，这样可将编译程序分为二个相互独立部分。
（一）编译程序前端
组成：
词法分析器、语法分析器和中间代码产生器
特点：
依赖于被编译的源语言，输出结果用中间代码描述，和目标机器无关。
（二）编译程序后端
组成：
目标代码生成器
特点：
和源语言无关，以中间代码形式的源程序为输入进行处理，输出结果依赖于目标机器。
第二章词法分析
词法分析器的构成及各部分的功能
（一）预处理程序
功能：
1）删除注释
2）删除续行符和后续换行符
3）换行符、TAB替换成空格
（二）扫描器（单词识别程序）
读入字符并识别单词
词法分析任务：
从文件读入源程序，去除源程序中与编译无关的编辑字符、注释等，得到由字符拼接的单词。
每当识别出一个单词，就用单词的内部码（单词二元式）替换。
执行词法分析任务的程序称为词法分析器。
单词二元式编码
经词法分析后，单词用二元式（Code,Val）表示。
code表示单词的种别，用整数码表示。
单词种别表示单词的语法特性，在语法分析时使用。
Val表示单词的值，在本书中用字符串表示。
单词值表示了单词的语义特性，在语义分析时使用。
手工构造词法分析器的方法是
先用状态转换图描述出所有单词，然后用程序实现状态转换图，最简单的办法是让每个状态对应一小段程序。
正规式（构词规则）和正规集（有穷字母表∑所有字的特殊子集）的定义：
ε和Φ是∑上的正规式，相应的正规集为{ε}、{}。
若字符a∈∑，则字符a是正规式，相应正规集为{a}。
若α、β为正规式，相应正规集分别记为L（α）和L（β），则α|β是正规式，其相应正规集记为L（α|β）=L（α）∪L（β）
若α、β为正规式，相应正规集分别记为L（α）和L（β），则αβ（或α·β）、是正规式，其相应正规集记为L（αβ）=L（α）L（β），
若α、β为正规式，相应正规集分别记为α*是正规式，其相应正规集记为L（α*）=L（α）n
正规式和正规集实际意义
有穷字母表Σ是程序设计语言所使用的字符集的抽象
正规集是程序设计语言单词集的抽象
正规式是程序设计语言构词规则的抽象
DFA定义
一个确定有限自动机M是一个五元式
M=（S，Σ，f，s0，Z）
S是一个有限集，它的每一个元素称为状态。
Σ是一个有穷字母表，它的每个元素称为一个输入字符。
f是一个从S×Σ至S的映射，即f：
S×Σ→S（单值函数）
s0∈S，是唯一的一个初态。
Z⊂S，是一个终态集。
NFA定义
一个非确定的有限自动机M是一个五元式M=（S，Σ，f，S0，Z）
S是一个有限集，它的每一个元素称为状态。
Σ是一个有穷字母表，它的每个元素称为一个输入字符。
f是一个从S×（Σ∪ε）到S的幂集的映射，即f：
S×（Σ∪ε）→P（S）（多值函数）
S0⊂S，是一个非空初态集，即NFA的初态不一定唯一。
Z⊂S，是一个终态集。
NFADFA（NFA到DFA的转换，要会过程并标明初态和终态）
为了便于描述NFA确定化算法，我们引进二个概念。
（一）I的ε闭包
I的ε闭包记为ε_CLOSURE（I）或CLOSURE（I），设I是NFAM状态集的一个子集，I的ε闭包定义为：
若状态s∈I，则s∈ε_CLOSURE（I）。
若状态s∈I，则从状态s出发，经一条或多条ε弧所能到达的状态s'∈ε_CLOSURE（I）。
（二）Ia
INFAM状态集的一个子集
Ja从I出发经一条a弧所能到达的状态全体
Iaε_CLOSURE（Ja）
扫描器控制程序工作原理
每次识别单词，控制程序总是从初态出发，不断读入字符，进入下一状态，寻求最长匹配，直到无法前进为止，这样始终都读一个字符。
（从左往右扫描）
在状态迁移过程中，需用Token数组保存读入字符。
在无法前进时，若发现当前状态为终态，则认为识别出一个单词，反之出错，即Token数组所保存的字符串不构成一个单词，而是源程序中的一个错误词形。
事先设置一个单词二元式编码表，它包括除标识符和整常数以外的所有单词（基本字、运算符和界符）。
当DFA识别出一个单词，就根据Token数组所保存的字符串去查表。
若该单词在表中存在，即可获得二元式编码；若不存在，则该单词必为标识符和整常数二者之一，只要稍加判断即可区分。
首字符为字母的是标识符，首字符为数字的是无符号整常数。
练习：
2-6,2-7
第三章程序设计语言的语法描述
语法树
非叶结点称为语法单位，在形式语言中称为非终结符。
处于根结点位置的结点在形式语言中又称为开始符号。
叶结点称为单词符号，在形式语言中称为终结符。
规则
可以通过建立一组规则，来描述上述句子的语法结构，规则在形式语言中称为产生式。
规则推导句子
可用规则来推导出句子。
从开始符号出发，若能从规则推导出某符号串，则该符号串就是该文法的合法的句子，反之语法错误。
文法
是由终结符、非终结符、开始符号（特殊非终结符）及产生式四个要素构成。
作用：
从开始符号出发，根据产生式能推导出的句子全体称为文法所规定的语言
递归文法：
含有递归规则和间接递归的文法，称为递归文法。
利用递归文法，可以用有穷的规则来描述无穷的语言，这不但解决了语言的定义问题，而且使得对语言的语法检查成为可能。
形式文法分类
0型文法：
短语结构文法
1型文法：
上下文有关文法
2型文法：
上下文无关文法
3型文法：
正规文法
文法和语言
一个文法G是一个四元式（VT,VN,S,P），其中
VT是一个终结符的非空有限集，终结符通常用小写字母表示。
VN是一个非终结符的非空有限集，非终结符通常用大写字母表示。
S是一个特殊的非终结符（S∈VN），称为开始符号。
P是一个产生式（规则）的有限集合，每个产生式的形式是A→α，其中A∈VN，α∈（VT∪VN）*。
（一）终结符是语言的基本符号，即程序设计语言的单词。
语法分析时，终结符用单词的种别表示。
（二）非终结符表示抽象的语法单位.
例“算术表达式”、“布尔表达式”、“赋值语句”、“说明语句”和“程序”等。
非终结符通常用大写字母表示，也可以用带尖括号的汉字表示。
（三）开始符号是一个特殊的非终结符，它代表我们最感兴趣的语法单位。
例如讨论算术表达式，那么描述算术表达式文法的开始符号就是<算术表达式>。
在程序设计语言中，我们最感兴趣的语法单位是“程序”。
（四）产生式是定义语法单位的一种书写规则。
上下文无关文法产生式的左部必定是一个非终结符，该非终结符称为左部符号。
产生式的右部是终结符和非终结符经有限次连接构成的文法符号串，可以是空字ε。
基本术语
（一）直接推出和直接归约=>
（二）推导和归约
推导：
用产生式右部代替左部
规约：
用产生式左部代替右部
α1=+>αn：
从α1始，经一步或一步以上可推导出αn。
α1=*>αn：
从α1始，经０步或０步以上可推导出αn，即α1=+>αn或α1=αn。
（三）句型
若存在推导S=*>α（S为文法的开始符号），则称α是文法的一个句型。
（四）句子:
仅包含终结符的句型称为句子。
（五）语言
文法Ｇ所能推导出的句子全体称为该文法的语言，记为：
L（G）
（六）等价文法
Ｇ1和Ｇ2是二个不同的文法，若L（G1）=L（G2），则称G1和G2是等价文法。
等价文法的存在，使我们能够在不改变文法所规定的语言的前提下，为了某种目的改造文法。
（七）最左推导和最右推导
在各种推导中，考虑今后语法分析的需要，我们仅对两种推导感兴趣。
1）最左推导
在推导过程中始终对最左面的非终结符进行替换，记为α=L>β
2）最右推导（规范规约的逆过程）
在推导过程中始终对最右面的非终结符进行替换，记为α=R>β
语法树
我们可以用一个有向图表示一个句型的推导，这种表示称为语法树。
二义文法
若一个文法所产生的语言中，只要存在一个句子，它有二个最左推导，或有二个最右推导，或句子的推导对应两棵语法树，则称该文法为二义文法。
二义文法的利用和处理
（一）根据条件修改文法，语言不变。
算符优先性：
规定*优先于+，i+i*i等价于i+（i*i）。
算符结合性：
规定同级运算服从左结合，i+i+i等价于（i+i）+i。
（二）根据条件修改编译程序的语法分析表，文法保持不变（详见第四、五章）。
练习：
见期中复习题
第四章自上而下的语法分析
带回溯的自上而下分析法
从根结点出发，试图用一切可能的办法，自上而下地为输入串建立一棵语法树。
或者说，为输入串寻找一个最左推导。
问题和困难
（一）对于左递归文法定义的语言，不能采用自上而下的语法分析法。
试图用非终结符去推导和匹配输入串，而推导所得到的子树第一个子结是该非终结符本身，这样就陷入了死循环。
（二）存在虚假匹配，回溯不可避免。
（三）编译程序的语法分析和语义分析通常是同时进行的。
由于回溯，编译程序所做的一大堆语义分析工作必须推倒重来。
（四）当选用所有的不同候选组合，都不能为输入串建立一棵语法树，那么输入串存在语法错误。
这种分析法最终只能告知输入串不是文法的一个句子，而无法告知输入串错在何处。
（五）带回溯的自上而下分析法实际上是一种穷尽一切可能的试探法，因此效率很低，这种分析法几乎没有实用价值。
总上所述，必须消除分析过程中的回溯，只有不带回溯的分析方法才是实际可使用的。
直接左递归消除方法
假定关于非终结符P的规则为
P→Pα|β
其中，β不以P开头。
可以把关于P的规则变换为如下形式：
P→βP'
P'→αP'|ε
由于二者推导出的句型均为βαn（n≥0），故上述变换是等价的。
例文法G：
E→E+T|T
T→T*F|F
F→（E）|i|x|y
经消除直接左递归后变成
E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'|ε
F→（E）|i|x|y
不带回溯的自上而下的分析法
在推导时，根据面临的输入符号去找出A的那个唯一正确的候选式。
对于文法某一句型，只要该文法不是二义文法，从非终结符A出发的最左推导只有一个候选是正确的。
如果该候选式获得匹配，那么这个匹配决不会是虚假的。
若该候选式无法完成后续匹配任务，则任何其它候选式也肯定无法完成。
提取左因子
㈠实例引入
例定义无符号整数的文法
N→DN|D
D→0|1|2|3|4|5|6|7|8|9
因first（DN）∩first（D）={0,1,2,3,4,5,6,7,8,9}，故文法含有左因子。
㈡解决方法
提取左因子，引进ε产生式，将文法改造为G'。
N→DN'
N'→N|ε
D→0|1|2|3|4|5|6|7|8|9|0
㈢提取左因子一般规则
考虑一般情况，设非终结符P的规则为
P→δβ1|δβ2|…|δβn，δ∈（VT∪VN）+，βi∈（VT∪VN）*
引进非终结符P'，可以把这些规则改写成
P→δP'
P'→β1|β2|…|βn
first集定义
α是文法G的任一符号串（包括候选式），α∈（VT∪VN）*
first（α）={a∣αa……，a∈VT}
若αε，则规定ε∈first（α）。
first（α）直观意义是：
从α推导出的所有符号串的第一个终结符。
或者，从α可推导至空字ε。
文法符号（X,x）first集构造算法
（一）终结符x的first集为终结符本身。
（二）观察每个产生式，若有X→a……，其中a∈VT，则a∈first（X）；若X→ε，则ε∈first（X）。
（三）观察每个产生式，若有X→Y……，其中Y∈VN，则将first（Y）中的非ε元素（记为first（Y）/ε）加到first（X）中。
文法G如下所示,求文法符号的first集。
E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'|ε
F→（E）|i|x|y
解：
文法符号first集的计算规则如下:
First集
规则
（一）
规则
（二）
规则（三）
E
first（E）∪first（T）/ε
E'
{+,ε}
T
first（T）∪first（F）/ε
T'
{*,ε}
F
{（,i,x,y}
+
{+}
…
…
Ø在“规则（三）”列处填入的是计算公式，需多次重复计算，直至每个非终结符的first集不再增长为止。
计算过程如下：
First集
规则②
规则（三）1
规则（三）2
规则（三）3
E
{}
{}
{（,i,x,y}
{（,i,x,y}
E'
{+,ε}
{+,ε}
{+,ε}
{+,ε}
T
{}
{（,i,x,y}
{（,i,x,y}
{（,i,x,y}
T'
{*,ε}
{*,ε}
{*,ε}
{*,ε}
F
{（,i,x,y}
{（,i,x,y}
{（,i,x,y}
{（,i,x,y}
说明：
Ø由于终结符的first集计算较为简单，在计算过程中不再列出。
Ø在计算E的first集时（E→TE'），因first（T）不含ε，故没有必要考虑E'的first集，同理T的first集计算（T→FT'）。
Ø计算也可从下至上进行。
follow集定义
设S是文法开始符号，对于文法的任何非终结符A
follow（A）={a∣S=*>…Aa…，a∈VT}
特别是，若S=*>…A，规定#∈follow（A）。
（注：
由于算法的需要，人为地在源程序尾部添加了'#'，特别规定因此而来）
follow（A）直观意义是：
在所有句型中紧跟在非终结符A之后的终结符或'#'。
follow集构造算法
（一）对于文法开始符号S，因为S=*>S，故#∈follow（S）。
（二）观察每个产生式，若A→αBβ，其中α、β∈（VT∪VN）+，B∈VN，则把first（β）/ε加至follow（B）。
（三）观察每个产生式，若A→αB或A→αBβ（βε），则把follow（A）加至follow（B）。
例，文法G如下所示，求非终结符的follow集。
E→TE'first（E'）/ε={+}
E'→+TE'
E'→ε
T→FT'first（T'）/ε={*}
T'→*FT'
T'→ε
F→（E）|i|x|yfirst（））={）}
解：
根据上述规则，非终结符follow集的计算规则如下
规则
（一）
规则
（二）
规则（三）
E
{#}
{）}
E'
follow（E'）∪follow（E）
T
{+}
follow（T）∪follow（E）∪follow（E'）
T'
follow（T'）∪follow（T）
F
{*}
follow（F）∪follow（T）∪follow（T'）
Ø“规则（三）”列处填入的是计算公式，需多次重复计算，直至每个非终结符的follow集不再增长为止。
计算过程如下
规则
（一）②
规则（三）1
规则（三）2
E
{#,）}
{#,）}
{#,）}
E'
{#,）}
{#,）}
T
{+}
{+,#,）}
{+,#,）}
T'
{+,#,）}
{+,#,）}
F
{*}
{*,+,#,）}
{*,+,#,）}
Ø根据E→TE'，follow（E）应加至follow（E'）；因E'=*>ε，所以follow（E）还应加至follow（T）。
同理E'→+TE'、T→FT'、T'→*FT'。
Øfollow集的计算也可从下至上进行。
预测分析法基本原理
产生式的一般形式为：
A→α1|α2|…|αn|ε
设当前输入符号为a，根据下述原则
if（a∈first（αi））用A→αi推导（1≤i≤n）
elseif（a∈follow（A））用A→ε推导
else报错
文法G候选式的first集：
E→TE'first（TE'）=first（T）/ε={（,i,x,y}
E'→+TE'|εfirst（+TE'）={+},first（ε）={ε}
T→FT'first（FT'）=first（F）/ε={（,i,x,y}
T'→*FT'|εfirst（*FT'）={*},first（ε）={ε}
F→（E）|ifirst（（E））={（}、first（i）={i}
F→x|yfirst（x）={x}、first（y）={y}
非终结符的follow集
规则
（一）
（二）
规则（三）-1
规则（三）-2
E
{#,）}
{#,）}
{#,）}
E'
{#,）}
{#,）}
T
{+}
{+,#,）}
{+,#,）}
T'
{+,#,）}
{+,#,）}
F
{*}
{*,+,#,）}
{*,+,#,）}
分析表构造规则
（一）构造所有候选式的first集，构造所有非终结符的follow集。
（二）对于文法的每个产生式A→α执行（三）和（四）。
（三）对于每个终结符a∈first（α），把A→α加至M[A][a]。
（四）若ε∈first（α），则对于每个终结符b∈follow（A），把A→α加至M[A][b]。
（五）把所有未定义的M[A][c]标上“出错标志”（c∈VT）。
+
*
（
）
i
x
y
#
E
E→TE'
E→TE'
E→TE'
E→TE'
E'
E'→+TE'
E'→ε
E'→ε
T
T→FT'
T→FT'
T→FT'
T→FT'
T'
T'→ε
T'→*FT'
T'→ε
T'→ε
F
F→（E）
F→i
F→x
F→y
预测分析控制程序实现
（一）数据结构
M:
二维数组，存放预测分析表。
stack:
符号栈，初始时为"#S"（S为开始符号）。
X:
表示栈顶符号
t.code:
当前处理单词种别
（二）算法描述（暂不考虑出错情况）
预测分析控制程序任何时刻的动作，都按照栈顶符号X和当前输入符号t.code行事（X←Pop（stack）），控制程序每次执行下述三种可能的动作之一。
若X和t.code均为'#'，则分析成功，输入串为合法句子，终止分析过程。
若X是终结符，并且X和t.code相等，表示期望的终结符号和输入符号相等，则读入下一个单词二元式。
若X是非终结符，则查预测分析表。
若M[X][t.code]存放着一条关于X的一个产生式，那么把产生式右部符号串按反序压入stack栈。
若右部符号串为空字ε，则意味着无任何文法符号进栈。
假设由单词种别构成的源程序为“i+i#”，手工计算如下：
stepstackXt.code文件Lex_r.txt
0）#Ei+i#
1）#Ei+i#
#E'T（入栈顺序相反）i+i#
2）#E'Ti+i#
#E'T'Fi+i#
3）#E'T'Fi+i#
#E'T'ii+
升级会员 