说明1.这份资料的最初来源是王金伟老师给大家发的复习提纲，我在下面会给大家附一份原版，后面的21面资料是在那个的基础上整理和细化得到的。
最初做这份资料的目的是我本人作为班长为了帮助我们班的同学顺利通过考试而整理的。
听王老师说有想法留给学弟学妹们用，我放假后又对一些内容进行了修正和改进，得到了大家看到的这个版本2.这份资料加入了很多我个人的理解。
与原提纲相比，我增删了一些内容，并对某些内容进行了调序与合并。
3.这份资料融入了老师平时上课的以及最后复习课给的，更重要的是我个人的理解和猜测。
大家或许都有感受，觉得编译原理书上或者上说的句子根本看不懂。
针对这个问题，我把很多晦涩难懂的形式化的算法通过我的理解后用比较形象易懂的话表述了出来，表述得可能并不科学严谨，但我的目的是为了能帮助大家做题和考试4.里面的每一个考点我都在最后用括号加了注释，方便不同起点不同准备时间的同学进行选择，这里简单说明“了解”：代表这一部分的内容被老师列在提纲内，但其实并不太影响大家对大题的计算；并且据我的分析也并不太可能出小题所以时间很紧的同学可以略看就好，当然看看还是有好处的。
“小题”一类的字样代表这一块的知识点值得出填空选择，大家1 / 47有时间应该理解性的记忆下来（在2012年的期末考试上，选择为1分*10题；填空为1分*10题，判断改错为2分*5题，小题总计30分）“简答”：老师在最后复习课上说过编译原理是有简答题的，简答不同于计算，很可能是让你默写一些步骤。
所以这一块内容大家需要背诵，即使不理解也要背下来（在2012年的期末考试上，简答题的分值为5分*4题=20分“铺垫”“大题步骤”等代表这一块的内容对于综合大题的做题是必须了解的，或者其实就是做大题的分解步骤，这些块的内容是所有人必须看懂并且记下来的“实际大题”：总共列出的有4道，应该每年考察的都会是这4中题型，每一道的分值都在12~15分左右，是所有人想通过考试所必须攻克的。
这里通常我会标出他需要用到之前的哪些哪些知识点（2012年期末考试4道题的总分值为50分）5.如果大家想去打印，最好在装有2007及以上的机器上打印，否则有些符号可能会显示不出来。
建议大家去生活广场找机器打，不要去景元鸿6.由于时间仓促，这份资料做的并不完善和严谨，难免有错漏之处，希望大家谅解。
大家可以一边看我的这份资料，一边看老师最后给的两套，课本来不及就别看了。
真心希望这份资料能对大家有用，祝大家都考得好。
2 / 47最后说一句，我们去年编译原理考得好的人挺多的，其实也不是很难，没有人挂！本人惭愧，只有89，考得比我好的多太多了。
总结原因是把时间花在了研究大题上面，小题的很多知识点都没有背熟，随便错了几个小题就基本和90无缘了。
10计1 王成正2012/7/9（老师给的提纲原版）概述一、1. 编译方式与解释方式区别：是否生成目标代码2. 编译程序总框架词法分析二、状态转换图的功能：识别（接受）一定的符号串（单词） 1.状态转换图的程序实现的思路：为每个状态结点都编写一 2.个子程序字母表的概念：一般用∑表示 3.闭包的概念：闭包V*中的每个字都是由V中的字经过若干 4.3 / 47次连接而成的上所有符号串的集合正则闭包的概念：是V 5.定义：表示∑上所有字的全体，空字ε也包括在其中∑* 6.ε∑+空字ε不包含，非7.之间的区别ε，{ }，{}ε 8.}ε所对应的正规集为{ε 9.正规式与正规集的定义：知道如何用正规式表示一个正规10.集简述和的定义与区别 11.的某些结点既是初态结点又是终态结点，或者存在一若M12.εε通路，那么空字条从某初态结点到某个终态结点的所识别可为M 正规式与优先自动机的等价性13.， MV2.对于∑上的每一个正规式，存在一个∑上的定理14.L(M)(V)使得的化简的概念和方法：终态和非终态是可区别的，因 M15.ε为终态可以读出空字ε，而非终态不能读出空字课后作业一个例题 16.yy}上所有倒数第二个字符为，构造一个，它接受∑={x17.的字符串语法分析三、（1）基本定义4 / 47上下文无关文法的定义 1.句型、句子的概念 2.文法和语言的对应关系，给出文法构造语言，文法G产生 3.的句子的全体是该文法的语言语法分析树与二义性：判断文法的二义性方法：如果一个 4.文法含有二义性的句子（对应两棵不同的语法树），则称该文法是二义性文法3型文法是正规文法、正则文法、线性文法 5.2型文法也称为称为上下文无关文法 6.若一个文法是递归的，则由它产生的语言的句子个数是无7.限的（2）自上而下8. 文法左递归的定义9. 消除文法的左递归的方法：直接左递归10. 消除回溯的方法：提取公共左因子11. 递归下降分析法的概念，应满足什么条件？12. 递归下降法对文法的每个非终结符构造一个相应的子程序13. 预测分析法：给文法构造预测分析表：消除左递归、消除回溯、集、集。
举例子时，便成S→（T）（3）自下而上14. 短语、直接短语的概念5 / 4715. 句柄的概念（一个句型的最左直接短语）16. 规范归约（最左）、规范推导（最右）、规范句型17. 规范归约的关键问题是寻找句柄18. 在规范归约中，可归约串必出现在栈顶19. 算符文法、算符优先文法的概念，如何判断20. 构造算符优先关系表、、集合，可不考虑#号21. 素短语：算符优先归约的关键问题是寻找最左素短语22. 算符优先法尤其适用于表达式的分析23. 给出文法G（P）X →Y →Z →24. 该文法是否为算符优先文法？请根据、集合构造算符优先关系表说明之（12分）25. 优先函数的优点：便于比较，节省空间26. 优先函数的构造方法27. 欲构造行之有效的自上而下分析器，则必须消除文法中含有的左递归28. 分析法属于自底向上分析方法29. 从文法出发构造（0）分析表的步骤四、语义分析1. 综合属性和继承属性概念6 / 47五、中间代码生成1. 中间代码是一种面向语法，易于翻译成目标代码的代码2. 后缀式（逆波兰式）的概念3. 逆波兰式中各运算法出现的顺序与实际运算顺序一致4. 后缀式与抽象语法树（表达式树）的关系5. 的含义6. 四元式表示方法，联系时通过临时变量，可以翻译各种语句7. 将赋值语句表示成后缀式和四元式六、代码优化1. 简述代码优化的原则与优化的级别，并列举三种常用的优化技术2. 基本块、流图的概念，如何画、节点对应基本块3. 局部优化的方法，是对基本块进行优化的有效工具4. P285中间注意5. 不变运算的代码外提的条件6. 循环优化中的强度削弱的含义七、目标代码生成1. 编译程序生成的目标程序种类一：概述编译方式与解释方式区别（小题）1.7 / 47在于是否生成目标代码，编译方式生成了目标代码。
）2. 编译程序总框架（简答题，背！二：词法分析1.状态转换图的功能：（较重要铺垫）识别（接受）一定的符号串（单词）上图是一个很简单的状态转换图。
上图代表：状态0通过X弧可以转换到状态1，通过Y弧可以转换到状态2（较重要铺垫）2.字母表的概念：一个由有限元素组成的集合，每个元素称为一个符号或一个字，一般用∑表示一个字母表例：∑ = {a , b , c}元素：a，b，c字母表中的字可拼接在一起构成一个序列，如等，符号的顺序不同所代表的序列也不同。
8 / 47不包含任何字符的序列称为空字，用ε来表示另外有几个概念必须先了解：字(符号串)的连接设x和y是两个字(符号串)，则定义为他们的连接例：和连接是注: (1)ε（空字）是连结运算的恒等元素εx = xε= x(2)字(符号串)的n次连接= (x)= ε规定x，x，321= x x= x集合的(连接)积，(符号串)的集合”设U和V是两个“字积)(连接则定义为他们的V}y∈ {∈U且{a, }, {b, },例：设{, , , }则积记为：次)(连接V集合的n= V V V (V)n个ε} V 规定0= {，那么{a, b}例：设9 / 47ε} V0= {1= {} V2{}V32{, V}（较重要铺垫）闭包的概念：3.是一个字（符号串）的集合，V设V 则V*，的闭包定义为V = V∪V∪V21*0∪…VV 注：闭包*中的字经过有限次连接中的每个字都是由而成的正则闭包的定义为*=因为闭的，ε闭包与正则闭包的差别在于，闭包里是含有0而正则闭包由于在闭包的基础上又连接了包里有集合V，的。
，所以正则闭包里是没有空字εV一个*定义：表示∑上所有字的全体，空字ε也包括在其中∑表示∑上所有字的全体，但不包括ε+∑之间的区别（小题）}，{ε{ }4.ε，空字：表不包含任示何字符的序列称ε：表示一个空集{ }的集合ε }{ε：表示含有空字10 / 47（较重要铺垫）正规式与正规集的定义：5.我们可以把具有相同特征的字放在一起组成一个集合，即所谓的正规集然后使用一种形式化的方法来表示正规集，即所谓的正规式正规式是描述单词结构的一种形式；正规集是该类单词的全集。
举例个的含义，4对于下面的例子，大家应该好好思考一下后面对做大题是很有帮助的。
做大题时，题目通常会给你一个你需要先把他要实现的功能抽象成一个正规集，实际问题，再用正规式表达出来，才能继续做后面的步骤。
ε所对应的正规集为{ε}6.简述有限自动机和的定义与区别（重要铺垫）代表非确定的有限自动机；代表确定的有限自动机11 / 47所谓的有限自动机，大家一定觉得这个概念坑爹死了。
其实他并不代表任何实体的机器，只是一种数学模型而已。
就像函数、数列是一种数学模型一样。
函数通过函数表达式实现他的功能：你给他一个自变量，他能根据表达式求出因变量的值。
而有限自动机是通过状态转换图来实现功能，你给他一个初始状态和一个输入符号，他能根据你输入的这个符号将原状态转换到另一个状态，用他来模拟计算机的识别功能。
下面简单介绍一下（确定的有限自动机）的五元式表示法：(重要)定义：一个确定有限自动机（）M是一个五元式：M = (S, ∑, f, s, F)，其中0S是一个有限的状态集合，它的每个元1)素我们称为一个状态∑是一个有穷的输入符号的字母表，2)它的每个元素我们称为一个输入字符f是从 S×∑→S的单值部分映射3)s是S的一个元素，为初始状态，它是4)0唯一的状态集合F是终止状态的集合，它是S5)的子集(可空)一个非确定有限自动机（）M是一个五元式12 / 47，其中M = (S, ∑, f, S0, F)它的每个元素我们称为一个状⑴S是一个有限的状态集合，态⑵∑是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符的幂表示S*→2S 的部分映射，其中，2S是从⑶fS×∑是非M是非单值的的子集组成的集合）（fà集合（所有S确定）的子集S⑷状态集合S0是初始状态集合，它是的子集S⑸状态集合F是终止状态的集合，它是这是4），其他几点都差不多，注：和的区别在于（3）和（，大家要记住他们的区别和联系有可能出简答题的的识别功能（小题）7如果存在一条从初态结点到某个终态中任何字α，对于∑*则，结点的道路，这条路上所有的标识符连成的字等于α)所识别(接受，读出α可被 M的某些结点既是初态结点又是终态结点，或者存在一M若ε通路，那么空字条从某初态结点到某个终态结点的ε可为M所识别8.状态转换图的分裂规则（大题步骤）13 / 47这里Y有两个圈圈代表他是最终状态的点)例子：(14 / 47划到最后要求每条弧上都只有一个字母或者数字=ε(J)的构造方法（大题步骤）9.ε(I) 和这里先需要了解几个定义，这个集合中含有不同的I我们假设有某个状态集状态。