编译原理知识点汇总
- 格式:doc
- 大小:50.00 KB
- 文档页数:3
编译原理的复习提纲
1.编译原理=形式语言+编译技术
2.汇编程序:把汇编语言程序翻译成等价的机器语言程序
3.编译程序:把高级语言程序翻译成等价的低级语言程序
4.解释执行方式:解释程序,逐个语句地模拟执行
翻译执行方式:翻译程序,把程序设计语言程序翻译成等价的目标程序
5.计算机程序的编译过程类似,一般分为五个阶段:词法分析、语法分析、语义分析及中
间代码生成、代码优化、目标代码生成
词法分析的任务:扫描源程序的字符串,识别出的最小的语法单位(标识符或无正负号数等)
语法分析是:在词法分析的基础上的,语法分析不考虑语义。语法分析读入词法分析程序识别出的符号,根据给定的语法规则,识别出各个语法结构。
语义分析的任务是检查程序语义的正确性,解释程序结构的含义,语义分析包括检查变量是否有定义,变量在使用前是否具有值,数值是否溢出等。
语法分析完成之后,编译程序通常就依据语言的语义规则,利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统,可以认为是一种抽象机的程序
代码优化的主要任务是对前一阶段产生的中间代码进行等价变换,以便产生速度快、空间小的目标代码
编译的最后一个阶段是目标代码生成,其主要任务是把中间代码翻译成特定的机器指令或汇编程序
编译程序结构包括五个基本功能模块和两个辅助模块
6.编译划分成前端和后端。
编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序,独立于目标计算机。前端进行分析
编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序,完全依赖于目标机器和中间代码。
把编译程序分为前端和后端的优点是:可以优化配置不同的编译程序组合,实现编译重用,保持语言与机器的独立性。
7.汇编器把汇编语言代码翻译成一个特定的机器指令序列
第二章
1.符号,字母表,符号串,符号串的长度计算P18,子符号串的含义,符号串的简单
运算XY,X n,
2.符号串集合的概念,符号串集合的乘积运算,方幂运算,闭包与正闭包的概念P19,
P20 A0 ={ε}
3.重写规则,简称规则。非终结符(V n),终结符(V t)的概念。
4.文法的概念。P23 识别符号.P23 文法的第一个重写规则的左部符号为识别符号。
BNF表示法P6
5.直接推导和直接规约,广义推导广义规约,P24 最左推导,最右推导P62
6.句型和句子P26,短语,简单短语,句柄P26,P27
7.语言的定义P31
8.递归,左递归P32
9.文法的形式化定义P36定义重点是正则文法和上下文无关文法
0型文法,短语结构语言
1型文法,上下文有关文法CSG
2型文法,上下文无关文法CFG
3型文法,正则文法RG
3型语言类(2型语言类(1型语言类(0型语言类
但四种语言之间没有必然的包含关系P38
3型语言的定义有穷状态自动机P41
2型语言下推自动机
1型语言线性界限自动机
0型语言图灵机
10.消去规则左递归P51
11.语法分析树的构造,能够根据语法书来寻找短语,直接短语,句柄。
12.文法的二义性问题P58,文法的二义性是不可判定的
-------------------------------
第三章
1.词法分析的功能P69
2.词法分析器可以有两种实现模式:完全融合模式(大多采用)和相对独立模式,完全独
立方式P71
3.有穷状态自动机的概念,如何从正则文法构造有穷状态转换自动机P72
4.如何从有穷状态转换自动机构造正则文法P75
5.确定有穷状态自动机DFA五元组(K,Σ,M,S,F),五个字母的含义。P75
6.非确定有穷状态自动机NFA,如何将NFA转化为DFA P82
7.DFA的化简
8.属性字由符号类和符号值组成。特定符号类,一个符号类对应一个符号值:关键字、括
号,运算符。非特定符号类:标示符,无符号整数。符号类识别不同类的符号,符号值识别同类的不同符号P90
9.字符表,符号机内表示对照表,标示符表,无符号整数表各自的定义和作用P93 词法
分析程序的大致思路
------------------------------
第四章自顶向下(重点是预测分析表的构造和应用预测分析表进行字符串分析)
1.带回溯的自顶向下分析方法P121 (一般采用最左或者最右推导)
2.无回溯的自顶向下分析方法:条件,无左递归性,无回溯性。
3.预测分析技术:消去文法左递归P51;构造first集合和follow集合P138,构造预测分
析表P139 进行字符串分析P134
-------------------------------------
第五章自底向上(重点是构造算符优先矩阵并进行字符串的分析)
1.规范分析:最右推导被称为规范推导,最左规约被称为规范规约。P145
2.分析需要解决的两个基本问题:找出要被归约的短语u;确定归约到哪个非终结符号U
3.一个符号串的前缀是指该串的任一部分。一个规范句型的前缀若不含句柄之后的任何符
号就称为活前缀
4.基本方法:移入规约法P147 四个动作之一:移进归约接受出错
5.算符优先分析技术:P150 定义5.2 构造算符优先关系表P151-154 算符优先识别
算法P155
6.LR(k)分析技术,要知道其中定义(为什么引入LR(K)):
圆点在产生式最右端的项目称为可归约项,如E→E+T·;圆点后面是终结符的项目称为移进项,如E→E·+T ;圆点后面是非终结符的项目称为待约项,如E→E+·T。项,项集,项集的闭包
--------------------------------------------
第六章(重点是四元式、逆波兰式、抽象语法分析树(三元式))
1.语义分析的基本功能:确定类型;类型检查;识别含义,作相应的语意处理;其他一些
静态语义检查。P215
2.语义分析以语法分析部分的输出(语法分析树或其他等价内部中间表示)为输入,输出
中间表示代码,甚至目标代码。P215
3.语义是上下文相关的
4.语法制导翻译技术
5.抽象语法树P297
6.逆波兰式P300
7.四元组P306
-------------------------------------------------
第七章
1.代码优化的定义P348 ,代码优化进行的是等价变换,为优化进行努力是值得的。
2.基本块的概念,对基本块的优化:合并常量计算,消除公共子表达式,消减计算强度,
删除无用代码。对循环的优化:循环不变表达式外提,归纳变量删除,计算强度消减。
3.代码优化的三个过程:控制流分析,数据流分析,变化。P350 各自的含义
4.代码优化是基于中间表示代码进行的
5.窥孔优化:定义P395 包括:四种典型优化,各自的含义、