编译原理和离散数学.doc

2011年考研，离散数学和编译原理怎么复习2010-06-23 10:37离散数学和编译原理 前阵子很多人在议论说2010年如果加考离散数学怎么办。其实，在本科阶段，这两门课是典型的学起来很难而考试出题比较简单的科目。就算2010年添了离散数学，也肯定占不了太多的分，认真把定义搞懂搞熟，拿个七八成的分不是多大问题。离散数学蛮多的内容出题和解题的思路都是死的，不像高数有那么多的定理和公式，遇到难题还要拆来凑去啥的。尤其要注意的一点是 紧扣定义！ 打个易懂的比喻，高等数学是求值，线性代数是求解的个数，那么离散数学的一个核心要素就是求元素以及集合之间的相互关系。不要抱着一种求具体值的思想来解离散数学题。离散数学和编译原理是学好了很有用的两门课，要钻进去，而不是逃避，因为你当初义无反顾地选择了计算机科学与技术这个振奋人心的专业。离散数学中的集合论思想对我们思考问题的方式有着巨大帮助，而编译原理是要写出高效能软件所必须掌握的课程。中国科学技术大学2009年计算机学院考研复试就以笔试形式考了这两门课，100分，占了复试的半壁江山了，可见它们的重要性。 计算机基础综合的大纲到8月初左右公布，如果真要考的话，我推荐下参考书： 方世昌 编著 西安电子科技大学出版社 配套有本绿色的习题解答，写的很详细。我本科是西电计算机学院的，做过这2本书，感觉不错。而它更是被指定为这次中科大复试的参考书目，多少具备了一定的权威性。方世昌老师是个不折不扣的牛人，国内第一本外文算法书教材就是他翻译过来的，我读过一本也是他翻译的。编译原理有些学校复试可能会考，认真研究一下陈意云老师的和配套那本薄薄的习题精选 （高等教育出版社），就没啥问题了。 关于政治改革和报辅导班 听说2010年政治变动蛮大，也不必惊慌，第一次改革一般出题都不会很难。况且政治从来就不是决定考研成败的学科，只要复习了，大部分人的分是集中在5570之间的。大纲会在7月底8月初公布，从9月开始准备足矣。考研其实和足球、篮球比赛是一个道理，要尽量将对手引入自己的节奏中去，而不是教育部有个啥风吹草动咱就整天惶惶不安。 有同学问要不要报辅导班。我觉得这个问题的答案因人而异。如果你是已经毕业的历届生来考研，我建议最好报班，因为考研和高考不同，闭门造车容易看不清自己的优势劣势，也不好把握进度。 报班的性价比：政治 数学 专业课 英语 。 专业课和英语有着非常多的零碎知识点和易混知识点，主要靠平时的不断积累，指望辅导班来提高的话作用不是很大。政治是效果最明显的，基本认真上个班跟着老师把框架梳理一遍，突破60易如反掌。数学报班可以跟着它的进度每天完成相应的练习，1个月下来就可以养成个每天做一做数学题的好习惯。如果说一位同学每天认真做1020道数学题，做个半年，考不到100，你相信么？你肯定不信。恩，我也不会信的。这就是习惯的力量。 如果你是在校的应届生，自制力又不强（爱打游戏或是纠缠于恋爱等等，这非常正常），也可以针对自己的弱势学科报个班，从头到尾认真上完，做做笔记，甚至带个mp3把老师讲课录下来，回去多听几遍。倒不一定说上个班你就提高了多少，但它起码能改变你的生活方式，一来上课下课走走路锻炼身体；二来让你认识一些新的朋友，那种一起为一个目标奋斗的气氛，自高三以后咱就很难再体会到了，它的影响力不容忽视 学校的选择 不要盲目追求名校。如果是这样，一旦考研失败了，你会极其沮丧。你该知道自己对哪些方向感兴趣（不是泛泛指软件、应用这3个大方向），能具体到小方向最好。这可以保证你以后的3年研究生生活过得更有意义。 然后看看哪些学校在这方面比较强势，搜集搜集导师信息（在这个环节，校内网是个超级有力的工具，尤其是对于跨校或者跨专业的学生。我打个比方，你2010年想考西电，你可以在校内网用高级搜索西安电子科大 2006年入学 计算机学院，结识一些西电的大4本科生，向他们打听打听情况，导师具体的方向是啥，性格类型，等等），9月预报名你可以多报几个学校，或是报一个学校的多个老师。然后，到了11月，你结合下自己的复习进度和实力评估，及各高校往年的大致复试分数线，做出自己最终的决定。“发表，是最好的记忆”候捷语。前言：作为考研课程中最难的科目，编译原理的复习一直以来困扰着无数的计算机考研者，特别是本科期间没有认真学习这门课程或者专业外的人士。由sodme写作的这一系列文章将主要以陈火旺院士的编译原理教材为主线，对编译原理的复习重点和复习思路进行归纳和总结，以帮助大多数朋友尽快入门。由于绝大多数的本科编译教材，都是在围绕着原理性方面的知识进行介绍和展开，所以，本总结也适合于使用其它教材的朋友。anyway，希望使用各种不同教材的朋友都能从中受益并有所感悟。与数据结构的总结类似，对于编译的总结都是采用我自己认为比较容易理解的语言进行描述，绝不对书上的概念和算法进行原原本本的照搬，这里，在多数情况下讲的都是我自己的学习经验和学习心得。So，其行文写作的style可能有些朋友不太适应，but，I promise：这个总结绝不会平庸、泛泛无奇。Ok，now，lets go.一、编译原理的章节结构及重点构成第1章引论：本章属非重点章节，简单介绍了编译的基本知识。出题分值不会太多，如果出题（很多情况是不出题，_），其分值比例一般情况下不会超过5%.第2章高级语言及其语法描述：本章属重要章节，在本章逐步引出了编译的若干基础概念和术语。如果出题，其分值比例一般在5%-20%.第3章词法分析：重难点章节。本章是难点章节之一，同时又是编译原理最重要的章节和多数学校的必考章节之一，通常作为大题中的先行题考查。分值比例各有侧重，一般在10%20%不等。第4章语法分析自上而下分析：重难点章节。本章的难度要高于词法分析一章，与词法分析一章一样，同属编译原理最重要的章节之一，是多校学校的必考章节之一，通常作为大题考查。如果出题，其分值在10%20%不等（如果同一试卷中既出现词法分析又出现语法分析，语法分析题目的分值一般比词法分析的分值要大）。第5章语法分析自下而上分析：重难点章节。属多数学校的必考章节之一，其重要性描述同上，通常作为大题考查。一般情况下，在同一学校的同一张编译试卷内，多数不会同时考自上而下分析和自下而上分析两种语法分析方法，各学校会根据自身题目的难度定位选择考查自上而下的还是自下而上的。自下而上的分析要难一点。如果本章出题，其分值比例约为：10%20%.第6章属性文法和语法制导翻译：重难点章节。属多数学校的必考章节之一。多数与语义分析一章联合出题，通常作为大题考查。如果出题，本章的分值比例约为：10%20%左右。第7章语义分析和中间代码生成：重难点章节，常考内容之一，报考名校的同学应该多留意本章节内容。如果出题，本章分值约为：10%左右。第8章符号表：非重点章节，本章介绍的是编译过程中的辅助内容，并未紧密联系编译的主体思想。多数学校在本章不出题，如果出题，其分值比例约为：5%左右。第9章运行时存储空间组织：常考内容之一。本章多数会联系实际语言进行考查，如果出题，其分值比例约为：10%左右。第10章优化：常考内容之一。分值比例约为：10%左右。第11章目标代码生成：较少考查，即使考查，分数比例一般在5%左右。第12章并行编译基础：很少考查，只作了解，了解其基本概念即可。关于重要性标识的几点说明：“必考内容”：是针对于多校学校一般的出题规律而言，本章极易被考到。或者说，作为一个完整的试卷，本章是应该被考查的，这是放在多个学校都比较适合的规律，也就是说本章是不同的学校共同关注的章节。“常考内容”：虽然本章内容重要，但是，各校根据自己的考查方式，可能选择考，也可能不选择考查这一章，这样的章节常常作为对必考章节的配合和补充，以完善和形成一张完整的试卷。这些章节要求读者自己对所报院校的历年试题进行归纳和分析，从中找出哪些是是这一次比较容易考查到的。注：关于分值比例的统计样本来自于国防科大，中科院，上海交大，哈工大，清华等多所学校的历年试题。二、编译原理各章节重点难点归纳第1章 引论：本章作为编译原理的开启章节，其意义在于为原本对编译一无所知的朋友撩开一条细缝，让你从本章大致了解编译程序工作的原理。所以，本章的考点都是象征性的。需要读者掌握的是：清楚编译程序的总框架，了解编译程序工作的大致过程，能分辨清楚编译前端与后端的区别及其相互配合的方法，要清楚编译程序是如何生成的。请大家记忆并理解以下概念：编译程序，解释程序，翻译程序，扫描器，分析器，编译前端与后端，符号表，“遍”的概念等。说让大家记忆并理解以上概念，并不是要大家原原本本地记住书上的解释，而是让大家达到这样的一种程度：知道这些概念的含义，并且能够按照自己的语言对其进行准确描述。一般而言，当你真正理解了一个概念之后，你是有能力对其进行精辟描述的。针对于本章的考点，多数是考查这些小概念，比如国防科大就曾经考过“扫描器”等概念。In a word，理解第一。第2章 高级语言及其语法描述：本章的2.1和2.2节在先期为2.3节作了很多铺垫，其目的是为了引出2.3中的几个重量级概念：上下文无关文法，语法分析树和二义性，同时也引出了与此紧密联系的其它概念：推导，句型，句子，最左推导，最右推导等。最后给出了另一个常考点：乔姆斯基的方法分类。对于本章，读者应该掌握：正确理解程序设计语言中语法和语义的含义，了解书上列举的高级语言中的一般特性。一般情况下，这两点是不会直接考查的，如果是想考查某种高级语言的特性，也会放在后面的优化或目标代码生成章节中进行考查。所以，这里只要求你理解及了解。但是，下面的这些东东就是必须掌握的了，而且是必须通过大量作题掌握的：1.上下文无关文法的定义，判断和转化，以及与上下文无关文法密切相关的概念。首先，应该掌握上下文无关文法的四个构成要素；其次，应该清楚对于上下文无关文法，其每个产生式的左部和右部必须满足的条件。在有关上下文无关文法的考点中，有这样几种考查方式：给出某语言的自然语言描述方式，要求写该语言的上下文无关文法表述形式；给出某语言的上下文无关文法，要求用自然语言描述该语言；给出某语言的上下文无法方法，要求证明该文法是否二义；给出某语言的上下文无关文法，要求给出指定句子的最左或最右推导；给出某语言的上下文无关文法，要求给出指定句子的语法分析树；给出一个具有二义性的上下文无关文法，要求将其转换成非二义性的。以上的综合分析，几乎含盖了所有与上下文无关文法有关的出题角度，大家应该全部掌握。2.乔姆斯基的文法分类。首先，应该非常清楚乔姆斯基对于四种文法分类的定义，并能理解其含义。几种文法中，最基本的是0型文法，读者可以将它理解为其它所有文法的基础，它是可以表示任何语言的文法。后面的1，2,3三种文法，是分别对于0型文法产生式的两边作了不同的限制之后，形成了新的文法。比如：规定0型文法的每个产生式中，其左边字符集长度小于右边字符集长度并且同时规定开始符号只可出现于产生式的左边，不能出现在任何产生式的右边，这样，就成为了1型文法(即上下文有关文法)。其它与此类似，在1型文法的基础上，进一步规定该文法的任意产生式，其左部只允许有一个字符且必须为非终结符，这样就构成了上下文无关文法；再在上下文无关文法的基础上进行限制：规定除了左部有且只有一个非终结符外，还特别规定右部最多只允许有两个字符，当为两上字符时必须一个为非终结符，另一个为终结符，而当只有一个字符时，必须为终结符，这样的文法就成了正规文法。这样一层套一层的限制，就形成了从0型到3型文法的定义体制，每一层都是在前一层基础上进行定义的，所以说前一层一定比该层表示的范围要广，因为其受的限制要少。那么，我们在判断一个文法时应该以什么规则来判断呢？这个规则当然是：3-2-1-0.也就是说，我们判断是从高到低来判断的，比如：一旦判断其属于正规文法之后就没必要再判断其是否属于上下文无关的了(因为它必定属于上下文无关，我们应该以最高规则来判定其属于的文法类型)，其它情况与此类推。只有当我们判断不属于3型文法时，我们才向下判断，其是不是属于2型的，若不属于2型的，则依此类推再向下判断。最终的结果如果不属于3，2和1三种类型，那就只有属于0型了。“给定一个文法，要求判断其属于何种文法”是一个重要考点，其出题形式可能是填空，选择等多种题型。第3章 词法分析：很多人觉得编译这个科目很难学，望而生畏，以致于举步不前，最大的一个原因是把编译技术看得过于神秘化了。其实，说白了，编译这门课程无非就是对一个“大”程序的各个部分、各个模块上升到理论化的程度进行分析和介绍。这个“大程序”就是我们所要研究的“编译程序”。前两章为研究编译技术作了一些概念和技术上的先期铺垫，在本章的词法分析内容里将开始介绍编译技术的第一个重要技术点：词法分析。本章最为重要的内容是3.3节：正规式和有限自动机，对于词法分析一章的考点，可以说80%到90%以上集中在这一节的内容上。针对于这一节的知识点介绍和考点分析，我们将稍后给出，现在先来看一下学习3.3节所必须先知道和理解的基本概念：a.词法分析器的功能（或称词法分析的任务）：输入的是源程序，输出的是分析完成的单词符号；b.状态转换图：是一张有向图，用于标识在特定的输入下词法分析器应该选择的分析方向。对于考点a，有些学校会作为选择、判断或填空题进行考查，而对于考点b，多数是与有限自动机一些考查，要求给出以“状态图”表示的确定有限自动机，也有的学校的试题中，是要求直接给出针对于某正规式的状态转换图，比如中科院曾经考到：已知某系统下的设备文件名的定义方式（以正规式给出），要求给出符合这种定义的状态转换图。理解状态转换图的含义是进行本章学习的重要前提，大家记住一句话：状态转换图，就是一张当输入不同的内容时，选择不同分析路径的有向图。下面，我们重点看一下有关“正规式与有限自动机”这一考点的各种可能考查形式：a.题目给定一正规式，要求给出其NFA，DFA或最简DFA形式。b.题目给定一用状态图表示的NFA，要求给出其对应的DFA或最简DFA形式。c.题目给定一NFA，DFA或最简DFA，要求给出其对应的正规式。d.题目给定一正规集，要求给出其相应的DFA。e.题目给定一用自然语言描述的正规集，要求给出其相应的正规式表示形式。这些考点，综合起来看，是在正规式，正规集，NFA和DFA之间作各种可能的转换，当然这种转换正确与否的判断标准就是转换之后的内容是不是与转换之前的内容等价，如果等价，我们就认为转换是正确的。在考点e这类的转换题目中，有一些是需要另外规纳出来的，他们在某一方面具有共同的特征，如果掌握了其中一题，将可举一反三解出其它题。比如有以下的几种题目就可以作以总结：1.求偶（奇）数个a与偶（奇）数个b构成的语言的正规式2.求能被3（4、5、或其它任意给定的n）整除的正规式的DFA3.求不以（或以）n（n从0到9）开头的XXXX（符号某种条件的）奇（偶数）数的正规式以上三种类型的考题，在每一种类型中，都是有规律可循的，也都有简便的方法可以帮助我们快速求解其正规式，进而快速确定DFA及最简DFA。针对于这三种类型的解题思路分析，我会在另外的文章中给出。第4章 语法分析自上而下的分析：大家在参阅编译原理的这个重点归纳贴子时，可能会感觉与数据结构规纳贴子风格不太一致，在编译的总结里，我较多地讲解了书上的一些我认为是较难理解的内容，而不仅仅是给出考点。因为从我接触的网友反映的情况看来，大家对编译还是比较头疼的，所以，我希望通过这样的规纳同时帮助大家从另外一个角度或以另外一种思维来看待编译原理课程。当词法分析器对源程序进行了词法分析，获得了一个个独立的单词符号后，编译程序总控模块就会调用语法分析子程序对这些单词符号集进行语法分析，也就是：利用该文法的产生式来判断这些单词符号是否足以构成一个在语法上正确的程序。如果可以构成一个在语法上正确的程序，则接着作编译下面的工作，比如：语法制导翻译，中间代码生成、代码优化等工作；而如果不能构成一个在语法上正确的程序，则给出相应的错误提示并将错误信息记入对应的数据记录中。语法分析的规则主要基于两种：自上而下分析和自下而上分析。这一章，主要讲解自上而下的分析方法。自上而下分析的大致思路是：根据产生式规则，从产生式的开始符号进行推导，一直推导到可以产生当前要判断的这个句子为止。如果推导了所有可能情况，但没有推出这样的句子，那么这个句子就是不符合该语言的语法规则的（产生式即定义了语言的语法规则）。在陈火旺老师的编译教材上，详细描述了一种自上而下的分析方法：LL(1)分析法，陈老教材的这一章也是围绕这一点而展开的。下面，我们介绍一下本章的主要常考知识点及考查角度：1.给定一文法，要求将其改造成可以进行自上而下分析的形式。这里面涉及到两方面的知识点：左递归的去除及公因子的提取。所谓的左递归是指产生式是形如：P-Pab.的形式，即：产生式右边的第一个字符就是该产生式左边的那个非终结符。当一个文法中有左递归的产生式时，是无法进行自上而下推导的，因为只要这个产生式被推导，就势必会使这种推导过程陷入一种递归循环无休止推导的情形。去除左递归的方法是比较简单的，其基本思路是将左递归通过转化变成与之等价的右递归。即将形如：P-Pa|b 形式的左递归变成如下形式：P-bP,P-aP|e(注：e表示空)。这一点只要多作练习，很快就会掌握。提取公因子的目的是为了避免推导过程中的回溯，也就是使每一次的向下推导是唯一的，而不是有多个选择，因为有多个选择的话就可能出现回溯。2.给定一文法，要求判断其是否为LL(1)文法。判断一个文法是否为LL(1)文法主要有两种方法：一种是判断文法是否二义，如果二义，则文法必定不为LL(1)（注意：此命题的否合命题不真）；二是根据陈老教材P73页：关于LL(1)文法成立的三个条件。显然，第一种判断方法效率是比较高的，但是，其只能判断文法“不为”LL(1)的，并不能判定文法“是”LL(1)的，要判断文法“是”LL(1)的，就得用第二种方法，但在考题中，如果要求你判断某文法是否为LL(1)的，则该文法多半不是LL(1)的，而且此点可以很容易地用二义性来证明，这是一种常考形式。3.给定一文法，要求构造LL(1)分析表。LL(1)分析的重点和难点内容都在其分析表的构造上，后面要讲的LR分析也是，它的难点也在于其分析表的构造。构造LL(1)分析表是一个常考点，也是大分值题的可能出题点，对于普通学校而言，相比于LR分析，他们更喜欢考LL(1)，因为LR要比LL(1)复杂得多，而名校则更喜欢考LR，当然，这只是针对于较普遍的情况作的总结，并不是一定成立的推论。LL(1)分析表构造前，需要先弄清FIRST集和FOLLOW集的构造方法，简单地说，FIRST集是用于求非终结符推出的产生式中的第一个终结符的，而FOLLOW集是用于求与该非终结符后紧邻的那个终结符的。FIRST集的构造方法见教材P78页，在构造的三个规则中，前两个规则都是比较容易理解的，第三