编译原理复习提纲整理 - 图文

一、 概述

1. 编译方式与解释方式区别：是否生成目标代码 2. 编译程序总框架

二、 词法分析

1. 状态转换图的功能：识别（接受）一定的符号串（单词） 2. 状态转换图的程序实现的思路：为每个状态结点都编写一个子程序 3. 字母表的概念：一般用∑表示

4. 闭包的概念：闭包V*中的每个字都是由V中的字经过若干次连接而成的 5. 正则闭包V+的概念：是V上所有符号串的集合

6. ∑*定义：表示∑上所有字的全体，空字ε也包括在其中 7. ∑+空字ε不包含，非ε 8. ε，{ }，{ε}之间的区别 9. ε所对应的正规集为{ε}

10. 正规式与正规集的定义：知道如何用正规式表示一个正规集 11. 简述NFA和DFA的定义与区别

12. 若M的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态结点的ε

通路，那么空字ε可为M所识别 13. 正规式与优先自动机的等价性

14. 定理2.对于∑上的每一个正规式V，存在一个∑上的DFA M，使得L(M)=L(V)

15. DFA M的化简的概念和方法：终态和非终态是可区别的，因为终态可以读出空字ε，而非终态

不能读出空字ε 16. 课后作业一个例题

17. 构造一个DFA，它接受∑={x，y}上所有倒数第二个字符为y的字符串

三、 语法分析

（1）基本定义

1. 上下文无关文法的定义 2. 句型、句子的概念

3. 文法和语言的对应关系，给出文法构造语言，文法G产生的句子的全体是该文法的语言 4. 语法分析树与二义性：判断文法的二义性方法：如果一个文法含有二义性的句子（对应两棵不同

的语法树），则称该文法是二义性文法 5. 3型文法是正规文法、正则文法、线性文法 6. 2型文法也称为称为上下文无关文法

7. 若一个文法是递归的，则由它产生的语言的句子个数是无限的

（2）自上而下 8. 文法左递归的定义

9. 消除文法的左递归的方法：直接左递归 10. 消除回溯的方法：提取公共左因子 11. 递归下降分析法的概念，应满足什么条件？

12. 递归下降法对文法的每个非终结符构造一个相应的子程序

13. 预测分析法：给文法构造预测分析表：消除左递归、消除回溯、First集、Follow集。举例子时，

便成S→a|aS|（T） （3）自下而上

14. 短语、直接短语的概念

15. 句柄的概念（一个句型的最左直接短语） 16. 规范归约（最左）、规范推导（最右）、规范句型 17. 规范归约的关键问题是寻找句柄 18. 在规范归约中，可归约串必出现在栈顶 19. 算符文法、算符优先文法的概念，如何判断

20. 构造算符优先关系表、Fisrtvt、lastvt集合，可不考虑#号 21. 素短语：算符优先归约的关键问题是寻找最左素短语 22. 算符优先法尤其适用于表达式的分析 23. 给出文法G（P） X → jYj

Y → kZ|i Z → Yid

该文法是否为算符优先文法？请根据FIRSTVT、LASTVT集合构造算符优先关系表说明之

24. 欲构造行之有效的自上而下分析器，则必须消除文法中含有的左递归 25. LR分析法属于自底向上分析方法 26. 从文法出发构造LR（0）分析表的步骤 四、语义分析

1. 综合属性和继承属性概念

五、中间代码生成

1. 中间代码是一种面向语法，易于翻译成目标代码的代码 2. 后缀式（逆波兰式）的概念

3. 逆波兰式中各运算法出现的顺序与实际运算顺序一致 4. 后缀式与抽象语法树（表达式树）的关系 5. DAG的含义

6. 四元式表示方法，联系时通过临时变量，可以翻译各种语句 7. 将赋值语句表示成后缀式和四元式 六、代码优化

1. 简述代码优化的原则与优化的级别，并列举三种常用的优化技术 2. 基本块、流图的概念，如何画、节点对应基本块 3. 局部优化的方法，DAG是对基本块进行优化的有效工具 4. 不变运算的代码外提的条件 5. 循环优化中的强度削弱的含义

七、目标代码生成

1. 编译程序生成的目标程序种类(309)

一：概述

1. 编译方式与解释方式区别

在于是否生成目标代码，编译方式生成了目标代码。

2. 编译程序总框架

二：词法分析

1.状态转换图的功能：识别（接受）一定的符号串（单词）

上图是一个很简单的状态转换图。上图代表：状态0通过X弧可以转换到状态1，通过Y弧可以转换到状态2

2.字母表的概念：一个由有限元素组成的集合，每个元素称为一个符号或一个字，

一般用∑表示一个字母表 例： ∑ = {a , b , c}

元素：a，b，c

字母表中的字可拼接在一起构成一个序列，如aa,ab,bc,bbc等，符号的顺序不同所代表的序列也不同。

不包含任何字符的序列称为空字，用ε来表示

另外有几个概念必须先了解：

字(符号串)的连接

设x和y是两个字(符号串)，则定义xy为他们的连接 例：ab和ba连接是abba

注: (1)ε（空字）是连结运算的恒等元素εx = xε= x (2)字(符号串)的n次连接

n

x = xxx…x

规定x0 = ε x1= x，x2=xx，x3= xxx 集合的(连接)积

设U和V是两个“字(符号串)的集合”， 则定义UV为他们的(连接)积

UV={xy|x∈U且y∈V} 例：设U={a, ab}, V={b, ba}, 则UV={ab, aba, abb, abba} 集合V的n次(连接)积记为：

V = V V V…V

n个

0

n

规定 V= {ε} V= {ε} V= {a,b}

V=VV={aa,ab,ba,bb}

V=VVV=VV={aaa,aba,baa,bba,

aab,abb,bab,bbb}

3

2

210

例：设V={a, b}，那么

3.闭包的概念：

设V是一个字（符号串）的集合，

则

V的闭包定义为V*， V* = V0∪V1∪V2∪…

*+

注：闭包V 中的每个字都是由V中的字经过有限次连接而成的 正则闭包V的定义为

V+ = VV*

0

闭包与正则闭包的差别在于，闭包里是含有ε的，因为闭包里有集合V，而正则闭包由于在闭包的基础上又连接了一个V，所以正则闭包里是没有空字ε的。

∑*定义：表示∑上所有字的全体，空字ε也包括在其中 ∑+表示∑上所有字的全体，但不包括ε

4.ε，{ }，{ε}之间的区别（小题）

ε 空字：表不包含任示何字符的序列称 { }：表示一个空集

{ε}： 表示含有空字ε的集合

5.正规式与正规集的定义：

我们可以把具有相同特征的字放在一起组成一个集合，即所谓的正规集 然后使用一种形式化的方法来表示正规集，即所谓的正规式 正规式是描述单词结构的一种形式； 正规集是该类单词的全集。 举例

对于下面的例子，大家应该好好思考一下后面4个的含义，对做大题是很有帮助的。做大题时，题目通常会给你一个实际问题，你需要先把他要实现的功能抽象成一个正规集，

再用正规式表达出来，才能继续做后面的步骤。

ε所对应的正规集为{ε}

6.简述有限自动机NFA和DFA的定义与区别

NFA代表非确定的有限自动机；DFA代表确定的有限自动机

所谓的有限自动机，其实他并不代表任何实体的机器，只是一种数学模型而已。就像函数、数列是一种数学模型一样。函数通过函数表达式实现他的功能：你给他一个自变量，他能根据表达式求出因变量的值。而有限自动机是通过状态转换图来实现功能，你给他一个初始状态和一个输入符号，他能根据你输入的这个符号将原状态转换到另一个状态，用他来模拟计算机的识别功能。

下面简单介绍一下DFA（确定的有限自动机）的五元式表示法：(重要)

定义：一个确定有限自动机（DFA）M是一个五元式： M = (S, ∑, f, s0, F)，其中

1) S是一个有限的状态集合，它的每个元素我们称为一个状态 2) ∑是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符

3) f是从 S×∑ →S的单值部分映射

4) s0是S的一个元素，为初始状态，它是唯一的 5) 状态集合F是终止状态的集合，它是S的子集(可空)

一个非确定有限自动机（NFA）M是一个五元式 M = (S, ∑, f, S0, F)，其中

⑴S是一个有限的状态集合，它的每个元素我们称为一个状态

⑵∑是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符

⑶f是从S×∑*→2S 的部分映射，其中，2S表示S的幂集合（所有S的子集组成的集合）（f是非单值的?M是非确定）

本文来源：https://www.bwwdw.com/article/0ouh.html