编译原理知识点汇总

时间：2019-05-29 22:28:58 网站：公文素材库

编译原理知识点汇总

编译原理的复习提纲

1.编译原理=形式语言+编译技术

2.汇编程序：把汇编语言程序翻译成等价的机器语言程序3.编译程序：把高级语言程序翻译成等价的低级语言程序

4.解释执行方式：解释程序，逐个语句地模拟执行

翻译执行方式：翻译程序，把程序设计语言程序翻译成等价的目标程序

5.计算机程序的编译过程类似，一般分为五个阶段：词法分析、语法分析、语义分析及中

间代码生成、代码优化、目标代码生成

词法分析的任务：扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等）

语法分析是：在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析

程序识别出的符号，根据给定的语法规则，识别出各个语法结构。

语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记

号系统，可以认为是一种抽象机的程序

代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码

编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序

编译程序结构包括五个基本功能模块和两个辅助模块6.编译划分成前端和后端。

编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析

编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。

把编译程序分为前端和后端的优点是：可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。

7.汇编器把汇编语言代码翻译成一个特定的机器指令序列

第二章

1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单

运算XY，Xn，2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，

P20A0={ε}

3.重写规则，简称规则。非终结符（Vn），终结符（Vt）的概念。

4.文法的概念。P23识别符号.P23文法的第一个重写规则的左部符号为识别符号。BNF表示法P6

5.直接推导和直接规约，广义推导广义规约，P24最左推导，最右推导P626.句型和句子Ｐ26，短语，简单短语，句柄Ｐ２６，Ｐ２７7.语言的定义Ｐ318.递归，左递归Ｐ9.文法的形式化定义Ｐ36定义重点是正则文法和上下文无关文法

0型文法，短语结构语言

１型文法，上下文有关文法CSG2型文法，上下文无关文法CFG3型文法，正则文法RG

3型语言类（2型语言类（1型语言类（0型语言类但四种语言之间没有必然的包含关系P383型语言的定义有穷状态自动机P412型语言下推自动机1型语言线性界限自动机0型语言图灵机10.消去规则左递归P51

11.语法分析树的构造，能够根据语法书来寻找短语，直接短语，句柄。12.文法的二义性问题P58，文法的二义性是不可判定的

-------------------------------第三章

1.词法分析的功能P69

2.词法分析器可以有两种实现模式：完全融合模式（大多采用）和相对独立模式，完全独立方式P71

3.有穷状态自动机的概念，如何从正则文法构造有穷状态转换自动机P724.5.6.7.

如何从有穷状态转换自动机构造正则文法P75

确定有穷状态自动机DFA五元组（K，Σ，M，S，F），五个字母的含义。P75非确定有穷状态自动机NFA，如何将NFA转化为DFAP82DFA的化简

8.属性字由符号类和符号值组成。特定符号类，一个符号类对应一个符号值：关键字、括

号，运算符。非特定符号类：标示符，无符号整数。符号类识别不同类的符号，符号值识别同类的不同符号P90

9.字符表，符号机内表示对照表，标示符表，无符号整数表各自的定义和作用P93词法

分析程序的大致思路

------------------------------

第四章自顶向下（重点是预测分析表的构造和应用预测分析表进行字符串分析）1.带回溯的自顶向下分析方法P121（一般采用最左或者最右推导）

2.无回溯的自顶向下分析方法：条件，无左递归性，无回溯性。

3.预测分析技术：消去文法左递归P51；构造first集合和follow集合P138，构造预测分

析表P139进行字符串分析P134

-------------------------------------

第五章自底向上（重点是构造算符优先矩阵并进行字符串的分析）

1.规范分析：最右推导被称为规范推导，最左规约被称为规范规约。P145

2.分析需要解决的两个基本问题：找出要被归约的短语u；确定归约到哪个非终结符号U3.一个符号串的前缀是指该串的任一部分。一个规范句型的前缀若不含句柄之后的任何符

号就称为活前缀

4.基本方法：移入规约法P147四个动作之一：移进归约接受出错5.算符优先分析技术：P150定义5.2构造算符优先关系表P151-154算符优先识别算法Ｐ１５５

6.LR(k)分析技术,要知道其中定义（为什么引入LR(K)）:

圆点在产生式最右端的项目称为可归约项，如E→E+T；圆点后面是终结符的项目称为移进项，如E→E+T；圆点后面是非终结符的项目称为待约项，如E→E+T。项，项集，项集的闭包

--------------------------------------------

第六章（重点是四元式、逆波兰式、抽象语法分析树（三元式）)

1.语义分析的基本功能：确定类型；类型检查；识别含义，作相应的语意处理；其他一些

静态语义检查。P215

2.语义分析以语法分析部分的输出（语法分析树或其他等价内部中间表示）为输入，输出

中间表示代码，甚至目标代码。P2153.语义是上下文相关的4.语法制导翻译技术5.抽象语法树P2976.逆波兰式P3007.四元组P306

-------------------------------------------------第七章

1.代码优化的定义P348，代码优化进行的是等价变换，为优化进行努力是值得的。2.基本块的概念，对基本块的优化：合并常量计算，消除公共子表达式，消减计算强度，

删除无用代码。对循环的优化：循环不变表达式外提，归纳变量删除，计算强度消减。3.代码优化的三个过程：控制流分析，数据流分析，变化。P350各自的含义4.代码优化是基于中间表示代码进行的

5.窥孔优化：定义P395包括：四种典型优化，各自的含义、

扩展阅读：编译原理知识点汇总

编译原理知识点汇总

第一章：

一．基础知识（10）

1．编译程序是现代计算机系统的基本组成部分之一2．一个计算机系统中通常配置多个高级语言的编译程序

3．在一个计算机系统中可为某些高级语言配置多个不同性能的编译程序

4．编译程序是一种语言翻译程序，其功能是把一种语言编写的程序翻译成另一种语言的等价程序

5．被编译的程序称为源程序，编译后的等价程序称为目标程序6．编译程序的任务就是将源语言程序翻译成等价的目标语言程序

7．通常将编译过程分为六个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

8．词法分析的主要任务是从左至右扫描字符序列，并按照此法规则识别出一个个的单词9．单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。

10．计算机语言中，单词的种类通常有保留字、标识符、数、算符、界符等

11．语法分析的主要任务是：按照语言的语法规则，把词法分析所得的单词序列分解成各类语法成分。

12．词法分析和语法分析都是对源程序进行结构分析，但二者是有区别的。

13．语义分析的主要功能是审查源程序有无语义错误，伪代码生成阶段收集类型信息。14．中间代码生成阶段的主要任务是，把源程序转换成一种中间代码15．中间代码是一种结构简单、含义明确的记号系统

16．中间代码可以设计成多种形式，其设计原则有两点：一是容易生成，二是容易转换成目标代码

17．代码优化的主要任务是对中间代码进行改造，使生成的目标代码更为高效18．目标代码生成阶段的任务是把中间代码转换成特定机器上的绝对指令代码或者可重定位的指令代码或者汇编指令代码

19．在编译过程的每个阶段中都含有出错处理和表格管理的工作

20．编译程序的结构可以按功能分为八个模块，即词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序和目标代码生成程序，此外还有与上述每个阶段都有关系的出错处理程序和表格管理程序。21．按照编译程序的工作主要是与源语言有关还是与目标机有关，编译过程也可前端和后端22．前端的工作主要依赖于源语言而与目标机无关，包括词法分析、语法分析、语义分析、中间代码生成以及每个阶段中的出错处理和表格管理工作，还包括代码优化阶段的部分工作23．后端的工作主要与目标机有关而与源语言无关，主要是代码生成及相关的出错处理和表格管理工作24．编译过程中，对源程序或者中间语言程序从头至尾扫描一次并完成相应工作的过程称为“一遍”或者“一趟”

25．解释程序是另一种语言处理程序，其工作特点是边分析边执行，不生成目标代码。

第二章：（2）

1．终结符：构成语言文法的单词，是语法成分的最小单位

2．非终结符：是由终结符和非终结符串或者终结符串构成的语法成分3．终结符和非终结符都是语法成分第三章：

一．基础知识（10）

1．文法，是用有穷集合描述无穷集合的一个工具

2．字母表，是元素的非空有穷集合，表中的元素称为符号，因此也叫符号集3．符号串，是由字母表中的符号组成的任何有穷序列4．符号串的长度

5．符号串的头和尾，固有头和固有尾6．符号串的连接7．符号串的方幂8．符号串集合的乘积9．闭包与正闭包

10．文法的形式定义：G=（VN，VT，P，S），其中每个元素的含义是什么，VN和VT有何关系

11．推导，长度>=1的推导，长度>=0的推导12．句型的定义13．句子的定义14．语言的定义15．文法等价的定义16．文法的四种类型：

17．语法树，也叫推导树，它需满足四个条件：18．最左推导，最右推导，规范推导19．文法的二义性

20．短语，直接短语，句柄

21．多余规则：有不可到达和不可中止两种二．分析解答题：（20）习题1,2,3,4,5,6,8,11,13

第四章：

一．基础知识（10）

1．词法分析的工具有正规文法，正规式和有穷自动机三种，三者之间存在等价性2．正规式的定义，参考例4.23．正规式服从的代数规律：

4．正规式与正规文法的等价变换，表4.15．有穷自动机分为两类：6．DFA的定义7．NFA的定义

8．每个NFA都可以确定化为一个等价的DFA9．有穷自动机的无用状态有两种情况：

10．有穷自动机中两个状态等价的条件有两个：二．分析解答题：（20）

1．正规文法与正规式的等价变换。参考例4.3、4.42．画出有穷自动机的状态图。参考例4.6、4.73．DFA化简。例4.9

4．正规式与有穷自动机的等价变换。记住几个变换规则，参考例4.10、4.5．正规文法与有穷自动机的等价变换。参考例4.12、4.136．习题：1(1)、4(b)只需最小化、7（只需消除多余规则）、8

第五章：

一．基础知识（5）

1．开始符号集的定义（定义5.1）2．后跟符号集的定义（定义5.2）3．SELECT集合的定义（定义5.3）4．LL（1）文法的定义（即充要条件）5．LL（1）文法的含义

6．非LL（1）文法到LL（1）文法等价变换的两种情况：7．引起回溯的几种情况：二．分析解答题：（10）

1．判断一个文法是否为LL（1）文法。参考例5.15.42．非LL（1）文法到LL（1）文法等价变换。

（1）提取左公因子，参考例5.6、5.7

（2）消除左递归，参考P88-89页1）和2）3．习题：1（1,3），2（1,2），7（1,5）

第六-八章：（15）一．基础知识（）

1．自底向上分析法也叫移进-归约分析法2．规范归约是指自左向右的归约

3．自底向上优先分析法有简单优先分析法和算法优先分析法两种4．简单优先分析法和算符优先分析法的特点5．算符优先文法的基本概念（定义6.1,6.2,6.3）

6．LR分析法是自底向上分析法，其分析过程是一种规范归约过程。二．分析解答题（）

1．求算符优先关系。参考例6.3

2．求中间代码（逆波兰式、树形表示、三元式和四元式）。参考教材8.3节例题及表8.113．习题：P122：1，4（都只需求出优先关系即可）P202：1（1,3,5），

友情提示：本文中关于《编译原理知识点汇总》给出的范例仅供您参考拓展思维使用，编译原理知识点汇总：该篇文章建议您自主创作。

　　来源：网络整理免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。

《编译原理知识点汇总》
由互联网用户整理提供,转载分享请保留原作者信息,谢谢!
http://m.bsmz.net/gongwen/747406.html