编译原理复习提纲整理.doc

《编译原理复习提纲整理.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、概述1.编译方式与解释方式区别：是否生成目标代码2.编译程序总框架二、词法分析1.状态转换图的功能：识别（接受）一定的符号串（单词）2.状态转换图的程序实现的思路：为每个状态结点都编写一个子程序3.字母表的概念：一般用∑表示4.闭包的概念：闭包V*中的每个字都是由V中的字经过若干次连接而成的5.正则闭包V+的概念：是V上所有符号串的集合6.∑*定义：表示∑上所有字的全体，空字ε也包括在其中7.∑+空字ε不包含，非ε8.ε，{}，{ε}之间的区别9.ε所对应的正规集为{ε}10.正规式与正规集的定义：知道如何用正规式表示一个正规集11.简述NFA

2、和DFA的定义与区别12.若M的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态结点的ε通路，那么空字ε可为M所识别13.正规式与优先自动机的等价性14.定理2.对于∑上的每一个正规式V，存在一个∑上的DFAM，使得L(M)=L(V)15.DFAM的化简的概念和方法：终态和非终态是可区别的，因为终态可以读出空字ε，而非终态不能读出空字ε16.课后作业一个例题17.构造一个DFA，它接受∑={x，y}上所有倒数第二个字符为y的字符串三、语法分析（1）基本定义1.上下文无关文法的定义2.句型、句子的概念3.文法和语言的对应关系，给出

3、文法构造语言，文法G产生的句子的全体是该文法的语言4.语法分析树与二义性：判断文法的二义性方法：如果一个文法含有二义性的句子（对应两棵不同的语法树），则称该文法是二义性文法5.3型文法是正规文法、正则文法、线性文法6.2型文法也称为称为上下文无关文法7.若一个文法是递归的，则由它产生的语言的句子个数是无限的（2）自上而下8.文法左递归的定义9.消除文法的左递归的方法：直接左递归10.消除回溯的方法：提取公共左因子11.递归下降分析法的概念，应满足什么条件？12.递归下降法对文法的每个非终结符构造一个相应的子程序13.预测分析法：给文法构造预测分析表

4、：消除左递归、消除回溯、First集、Follow集。举例子时，便成S→a

5、aS

6、（T）（3）自下而上14.短语、直接短语的概念15.句柄的概念（一个句型的最左直接短语）16.规范归约（最左）、规范推导（最右）、规范句型17.规范归约的关键问题是寻找句柄18.在规范归约中，可归约串必出现在栈顶19.算符文法、算符优先文法的概念，如何判断20.构造算符优先关系表、Fisrtvt、lastvt集合，可不考虑#号21.素短语：算符优先归约的关键问题是寻找最左素短语22.算符优先法尤其适用于表达式的分析23.给出文法G（P）X→jYjY→kZ

7、iZ→Yid

8、该文法是否为算符优先文法？请根据FIRSTVT、LASTVT集合构造算符优先关系表说明之24.欲构造行之有效的自上而下分析器，则必须消除文法中含有的左递归25.LR分析法属于自底向上分析方法26.从文法出发构造LR（0）分析表的步骤四、语义分析1.综合属性和继承属性概念五、中间代码生成1.中间代码是一种面向语法，易于翻译成目标代码的代码2.后缀式（逆波兰式）的概念3.逆波兰式中各运算法出现的顺序与实际运算顺序一致4.后缀式与抽象语法树（表达式树）的关系5.DAG的含义6.四元式表示方法，联系时通过临时变量，可以翻译各种语句7.将赋值语句表示成后缀式

9、和四元式六、代码优化1.简述代码优化的原则与优化的级别，并列举三种常用的优化技术2.基本块、流图的概念，如何画、节点对应基本块3.局部优化的方法，DAG是对基本块进行优化的有效工具4.不变运算的代码外提的条件5.循环优化中的强度削弱的含义七、目标代码生成1.编译程序生成的目标程序种类(309)一：概述1.编译方式与解释方式区别在于是否生成目标代码，编译方式生成了目标代码。2.编译程序总框架二：词法分析1.状态转换图的功能：识别（接受）一定的符号串（单词）上图是一个很简单的状态转换图。上图代表：状态0通过X弧可以转换到状态1，通过Y弧可以转换到状态2

10、2.字母表的概念：一个由有限元素组成的集合，每个元素称为一个符号或一个字，一般用∑表示一个字母表例：∑={a,b,c}元素：a，b，c字母表中的字可拼接在一起构成一个序列，如aa,ab,bc,bbc等，符号的顺序不同所代表的序列也不同。不包含任何字符的序列称为空字，用ε来表示另外有几个概念必须先了解：字(符号串)的连接设x和y是两个字(符号串)，则定义xy为他们的连接例：ab和ba连接是abba注:(1)ε（空字）是连结运算的恒等元素εx=xε=x(2)字(符号串)的n次连接xn=xxx…x规定x0=εx1=x，x2=xx，x3=xxx集合的(连接

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

12、x∈U且y∈V}例：设U={a,ab}