《编译原理复习提纲整理概要》由会员分享，可在线阅读，更多相关《编译原理复习提纲整理概要（22页珍藏版）》请在金锄头文库上搜索。
1、一、 概述1. 编译方式与解释方式区别：是否生成目标代码2. 编译程序总框架二、 词法分析1. 状态转换图的功能：识别（接受）一定的符号串（单词）2. 状态转换图的程序实现的思路：为每个状态结点都编写一个子程序3. 字母表的概念：一般用表示4. 闭包的概念：闭包V*中的每个字都是由V中的字经过若干次连接而成的5. 正则闭包V+的概念：是V上所有符号串的集合6. *定义：表示上所有字的全体，空字也包括在其中7. +空字不包含，非8. ， ，之间的区别9. 所对应的正规集为10. 正规式与正规集的定义：知道如何用正规式表示一个正规集11. 简述NFA和DFA的定义与区别12. 若M的某些结点既是初
2、态结点又是终态结点，或者存在一条从某初态结点到某个终态结点的通路，那么空字可为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. 语法分析树与二义性：判断文法的二
3、义性方法：如果一个文法含有二义性的句子（对应两棵不同的语法树），则称该文法是二义性文法5. 3型文法是正规文法、正则文法、线性文法6. 2型文法也称为称为上下文无关文法7. 若一个文法是递归的，则由它产生的语言的句子个数是无限的（2）自上而下8. 文法左递归的定义9. 消除文法的左递归的方法：直接左递归10. 消除回溯的方法：提取公共左因子11. 递归下降分析法的概念，应满足什么条件？12. 递归下降法对文法的每个非终结符构造一个相应的子程序13. 预测分析法：给文法构造预测分析表：消除左递归、消除回溯、First集、Follow集。举例子时，便成Sa|aS|（T）（3）自下而上14. 短语、
4、直接短语的概念15. 句柄的概念（一个句型的最左直接短语）16. 规范归约（最左）、规范推导（最右）、规范句型17. 规范归约的关键问题是寻找句柄18. 在规范归约中，可归约串必出现在栈顶19. 算符文法、算符优先文法的概念，如何判断20. 构造算符优先关系表、Fisrtvt、lastvt集合，可不考虑#号21. 素短语：算符优先归约的关键问题是寻找最左素短语22. 算符优先法尤其适用于表达式的分析23. 给出文法G（P） X jYjY kZ|iZ Yid 该文法是否为算符优先文法？请根据FIRSTVT、LASTVT集合构造算符优先关系表说明之24. 欲构造行之有效的自上而下分析器，则必须消除
5、文法中含有的左递归25. LR分析法属于自底向上分析方法26. 从文法出发构造LR（0）分析表的步骤四、语义分析1. 综合属性和继承属性概念五、中间代码生成1. 中间代码是一种面向语法，易于翻译成目标代码的代码2. 后缀式（逆波兰式）的概念3. 逆波兰式中各运算法出现的顺序与实际运算顺序一致4. 后缀式与抽象语法树（表达式树）的关系5. DAG的含义6. 四元式表示方法，联系时通过临时变量，可以翻译各种语句7. 将赋值语句表示成后缀式和四元式六、代码优化1. 简述代码优化的原则与优化的级别，并列举三种常用的优化技术2. 基本块、流图的概念，如何画、节点对应基本块3. 局部优化的方法，DAG是对
6、基本块进行优化的有效工具4. 不变运算的代码外提的条件5. 循环优化中的强度削弱的含义七、目标代码生成1. 编译程序生成的目标程序种类(309)一：概述1. 编译方式与解释方式区别在于是否生成目标代码，编译方式生成了目标代码。2. 编译程序总框架二：词法分析1. 状态转换图的功能：识别（接受）一定的符号串（单词）上图是一个很简单的状态转换图。上图代表：状态0通过X弧可以转换到状态1，通过Y弧可以转换到状态22.字母表的概念：一个由有限元素组成的集合，每个元素称为一个符号或一个字，一般用表示一个字母表例： = a , b , c元素：a，b，c 字母表中的字可拼接在一起构成一个序列，如aa,ab
7、,bc,bbc等，符号的顺序不同所代表的序列也不同。不包含任何字符的序列称为空字，用来表示另外有几个概念必须先了解：字(符号串)的连接设x和y是两个字(符号串)，则定义xy为他们的连接例：ab和ba连接是abba注: (1)（空字）是连结运算的恒等元素x = x= x (2)字(符号串)的n次连接xn = xxxx规定x0 = x1= x，x2=xx，x3= xxx集合的(连接)积设U和V是两个“字(符号串)的集合”，则定义UV为他们的(连接)积 UV=xy|xU且yV例：设U=a, ab, V=b, ba, 则UV=ab, aba, abb, abba集合V的n次(连接)积记为： Vn =
8、V V VV n个 规定 V0= 例：设V=a, b，那么V0= V1= a,bV2=VV=aa,ab,ba,bbV3=VVV=V2V=aaa,aba,baa,bba,aab,abb,bab,bbb3.闭包的概念：设V是一个字（符号串）的集合，则V的闭包定义为V*， V* = V0V1V2注：闭包V* 中的每个字都是由V中的字经过有限次连接而成的正则闭包V+的定义为V+ = VV* 闭包与正则闭包的差别在于，闭包里是含有的，因为闭包里有集合V0 ，而正则闭包由于在闭包的基础上又连接了一个V，所以正则闭包里是没有空字的。*定义：表示上所有字的全体，空字也包括在其中+表示上所有字的全体，但不包括4
9、.， ，之间的区别（小题） 空字：表不包含任示何字符的序列称 ：表示一个空集： 表示含有空字的集合5.正规式与正规集的定义：我们可以把具有相同特征的字放在一起组成一个集合，即所谓的正规集然后使用一种形式化的方法来表示正规集，即所谓的正规式正规式是描述单词结构的一种形式；正规集是该类单词的全集。举例对于下面的例子，大家应该好好思考一下后面4个的含义，对做大题是很有帮助的。做大题时，题目通常会给你一个实际问题，你需要先把他要实现的功能抽象成一个正规集，再用正规式表达出来，才能继续做后面的步骤。所对应的正规集为6. 简述有限自动机NFA和DFA的定义与区别NFA代表非确定的有限自动机；DFA代表确定
10、的有限自动机所谓的有限自动机，其实他并不代表任何实体的机器，只是一种数学模型而已。就像函数、数列是一种数学模型一样。函数通过函数表达式实现他的功能：你给他一个自变量，他能根据表达式求出因变量的值。而有限自动机是通过状态转换图来实现功能，你给他一个初始状态和一个输入符号，他能根据你输入的这个符号将原状态转换到另一个状态，用他来模拟计算机的识别功能。下面简单介绍一下DFA（确定的有限自动机）的五元式表示法：(重要)定义：一个确定有限自动机（DFA）M是一个五元式：M = (S, , f, s0, F)，其中1) S是一个有限的状态集合，它的每个元素我们称为一个状态2) 是一个有穷的输入符号的字母表
11、，它的每个元素我们称为一个输入字符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是非确定）状态集合S0是初始状态集合，它是S的子集状态集合F是终止状态的集合，它是S的子集注：DFA和NFA的区别在于（3）和（4），
12、其他几点都差不多，这是有可能出简答题的，大家要记住他们的区别和联系7.DFA的识别功能对于*中任何字，如果存在一条从初态结点到某个终态结点的道路，这条路上所有的标识符连成的字等于 ，则可被DFA M所识别(接受，读出)若M的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态结点的通路，那么空字可为M所识别8.状态转换图的分裂规则（大题步骤）例子：(这里Y有两个圈圈代表他是最终状态的点)划到最后要求每条弧上都只有一个字母或者数字9._CLOSURE(I) 和Ia =_CLOSURE(J)的构造方法（大题步骤）这里先需要了解几个定义我们假设有某个状态集I，这个集合中含有不同的状态
13、。定义1 状态集I的a弧转换：move( I, a ) 是一个状态集，是从I中的状态出发经过一条a弧到达的状态的全体。定义2 状态集I的(空字)闭包：_CLOSURE( I ) 是一个状态集，由两部分组成:n 状态集I中的所有原状态。n 从I中的状态出发经过任意条弧，所能到达的状态的全体。定义3 Ia =_CLOSURE( move( I, a ) ) 是一个状态集。下面给出一个实例：例：有如下一个状态转换图假定 I=1, 2，求Ia = ？J=move(I,a)=5,4,3Ia=_CLOSURE(J) = 5,4,3,6,2,7,8（即先做a弧转换，将求得的状态再求空字闭包）本知识点旨在让大
14、家掌握在知道了I这个状态集合后，怎样求Ia10.如何用子集法将非确定的有限自动机确定化（大题步骤）方法：先画一张表IIaIb_CLOSURE(S0)ABCBDECFG1.这张表的首行上首列上固定是大写字母I2.表格后面有几列，取决于这个有限自动机的输入符号数量，有几个输入符号就有几列，这里假设Ia Ib 的下标a b代表这个有限自动机的输入符号3.第二行的第一列也是固定的，S0代表的是这个有限自动机的初始状态,即求S0的空字闭包，我们假设求出来的状态集合是A4.将A所对应的Ia Ib 分别求出来，我们假设是B和C5.如果B和C都分别于A不同，需要将B，C作为新的状态集合加入到第一列中6.继续求出B和C所对应的Ia Ib ，再检验：对于DEFG这四个状态集合，有没有与ABC是不同的，如果有，加入到第一列的下面，再继续计算，如果与前面的ABC相同就不再需要加入了。7.按照这样的方法一直进行下去，知道第一列不再有新的状态集合加入了
