编译原理实践与指导课程

1. 编译原理及实践的介绍

本书结合对现代编译器设计理论的详细研究，完整描述了一个可运行的小规模语方编译器（包括源代码）。本书反映了作者的这样一些观点：不掌握理论就不会理解实际的编译器设计；而对大学生来说，看不到理论在实际中的应用就不会真正地理解理论。

2. 编译原理与实践中正规表达式的问题

(aa|b)*
由连续两个a或一个b的任意序列组成的语言，比如aab,baaaabbbb.
(a|bb)*
连续两个b或一个a的任意序列。

正则语言里，｜表示任选，有时也用+号。*号表示闭包－－就是说任意组合。

3. 为什么要学习编译原理(转）

大学课程为什么要开设编译原理呢？这门课程关注的是编译器方面的产生原理和技术问题，似乎和计算机的基础领域不沾边，可是编译原理却一直作为大学本科的必修课程，同时也成为了研究生入学考试的必考内容。编译原理及技术从本质上来讲就是一个算法问题而已，当然由于这个问题十分复杂，其解决算法也相对复杂。我们学的数据结构与算法分析也是讲算法的，不过讲的基础算法，换句话说讲的是算法导论，而编译原理这门课程讲的就是比较专注解决一种的算法了。在20世纪50年代，编译器的编写一直被认为是十分困难的事情，第一Fortran的编译器据说花了18年的时间才完成。在人们尝试编写编译器的同时，诞生了许多跟编译相关的理论和技术，而这些理论和技术比一个实际的编译器本身价值更大。就犹如数学家们在解决着名的哥德巴赫猜想一样，虽然没有最终解决问题，但是其间诞生不少名着的相关数论。 推荐参考书 虽然编译理论发展到今天，已经有了比较成熟的部分，但是作为一个大学生来说，要自己写出一个像TurbocC,Java那样的编译器来说还是太难了。不仅写编译器困难，学习闷数编译原理这门课程也比较困难。 第一本书的原名叫《CompilersPrinciples,Techniques,andTools》,另外一个响亮的名字就是龙书。原因是这本书的封面上有条红色的龙，也因为獗臼樵诒嘁朐?砘?嘴域确实?忻?所以很多国外的学者都直接取名为龙书。最近机械工业出版社已经出版了此书的中文版，名字就叫《编译原理》。该书出的比较早，大概是在85或86年编写完成的，作者之一还是着名的贝尔实验室的科学家。里面讲解的核心编译原理至今都没有变过，所以一直到今天，它的价值都非凡。这本书最大的特点就是一开始就通过一个实际的小例子，把编译原理的大致内容罗列出来，让很多编译蚂罩首原理的初学者很快心里有了个底,也知道为什么会有这些理论，怎么运用这些理论。而这一点是我感觉国内的教材缺乏的东西，所以国内的教材都不是写给愿意自学的读者，总之让人看了半天，却不知道里面的东西有什么用。 第二本书的原名叫《ModernCompilerDesign》,中文名字叫做《现代编译程序设计》。该书由人民邮电出版社所出。此书比较关注的是编译原理的实践，书中给出了不少的实际程序代码，还有很多实际的编译技术问题等等。此书另外一个特点就是其现代而字。在传统的编译原理教材中，你是不可能看到如同Java中的垃圾回收等算法的。因为Java这样的解释执行语言是在近几年才流行起来的东西。如果你想深入学习编译原理的理论知识，那么你肯定得看前面那本龙书，如果你想自己动手做一个先进的编译器，那么你得看这本《现代编译程序设计》。 第三本书就是很多国内的编译原理学者都推荐的那本《编译原理及实践》。或许是这本书引入国内比较早吧，我记得我是在高中就买了这本书，不过也是在前段时间才把整本书看完。此书作为入门教程也的确是个不错的选择。书中给出的编译原理讲解也相当细致，虽然不如前面的龙书那么深入，但是很多地方都是点到为止，作为大学本科教学已经是十分深入了。该书的特点就是注重实践，不过感觉还不如前面那本《现代编译程序设计》的实践味道更重。此书的重点还是在原理上的实践，而非前面那本那样的技术实践。《编译原理及实践》在讲解编译原理的各个部分的同时，也在逐步实践一个现代的编译器TinyC.等你把整本书看完，差不多自己也可以写一个TinyC了。作者还对Lex和Yacc这两个常用的编译相关的工具进行了很详细的说明，这一点也是很难在国内的教材中看到的。 推荐了这三本教材，都有英文版和中文版的。很多英文好的同学只喜欢看原版的书，不我的感觉是这三本书的翻译都很不错，没有必要特别去买英文版的。理解理论的实质比理解表面的文字更为重要。 编译原理的实质 几乎每本编译原理的教材都是分成词法分析，语法分析（LL算法，递归下降算法，LR算法），语义分析，运行时环境，中间闷悉代码，代码生成，代码优化这些部分。其实现在很多编译原理的教材都是按照85,86出版的那本龙书来安排教学内容的，所以那本龙书的内容格式几乎成了现在编译原理教材的定式，包括国内的教材也是如此。一般来说，大学里面的本科教学是不可能把上面的所有部分都认真讲完的，而是比较偏重于前面几个部分。像代码优化那部分东西，就像个无底洞一样，如果要认真讲，就是单独开一个学期的课也不可能讲得清楚。所以，一般对于本科生，对词法分析和语法分析掌握要求就相对要高一点了。 词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。不过编译原理在讲解词法分析的时候，重点把正则表达式和自动机原理加了进来，然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显，就是要让词法分析从程序上升到理论的地步。 语法分析部分就比较麻烦一点了。现在一般有两种语法分析算法，LL自顶向下算法和LR自底向上算法。LL算法还好说，到了LR算法的时候，困难就来了。很多自学编译原理的都是遇到LR算法的理解成问题后就放弃了自学。其实这些东西都是只要大家理解就可以了，又不是像词法分析那样非得自己写出来才算真正的会。像LR算法的语法分析器，一般都是用工具Yacc来生成，实践中完全没有比较自己来实现。对于LL算法中特殊的递归下降算法，因为其实践十分简单，那么就应该要求每个学生都能自己写。当然，现在也有不少好的LL算法的语法分析器，不过要是换在非C平台，比如Java,Delphi,你不能运用YACC工具了，那么你就只有自己来写语法分析器。 等学到词法分析和语法分析时候，你可能会出现这样的疑问：词法分析和语法分析到底有什么？就从编译器的角度来讲，编译器需要把程序员写的源程序转换成一种方便处理的数据结构（抽象语法树或语法树）,那么这个转换的过程就是通过词法分析和语法分析的。其实词法分析并非一开始就被列入编译器的必备部分，只是我们为了简化语法分析的过程，就把词法分析这种繁琐的工作单独提取出来，就成了现在的词法分析部分。除了编译器部分，在其它地方，词法分析和语法分析也是有用的。比如我们在DOS,Unix,Linux下输入命令的时候，程序如何分析你输入的命令形式，这也是简单的应用。总之，这两部分的工作就是把不规则的文本信息转换成一种比较好分析好处理的数据结构。那么为什么编译原理的教程都最终把要分析的源分析转换成树这种数据结构呢？数据结构中有Stack,Line,List这么多数据结构，各自都有各自的特点。但是Tree这种结构有很强的递归性，也就是说我们可以把Tree的任何结点Node提取出来后，它依旧是一颗完整的Tree。这一点符合我们现在编译原理分析的形式语言，比如我们在函数里面使用函树，循环中使用循环，条件中使用条件等等，那么就可以很直观地表示在Tree这种数据结构上。同样，我们在执行形式语言的程序的时候也是如此的递归性。在编译原理后面的代码生成的部分，就会介绍一种堆栈式的中间代码，我们可以根据分析出来的抽象语法树，很容易，很机械地运用递归遍历抽象语法树就可以生成这种指令代码。而这种代码其实也被广泛运用在其它的解释型语言中。像现在流行的Java,.NET，其底层的字节码bytecode,可以说就是这中基于堆栈的指令代码的。 关于语义分析，语法制导翻译，类型检查等等部分，其实都是一种完善前面得到的抽象语法树的过程。比如说，我们写C语言程序的时候，都知道，如果把一个浮点数直接赋值给一个整数，就会出现类型不匹配，那么C语言的编译器是怎么知道的呢？就是通过这一步的类型检查。像C++语言这中支持多态函数的语言，这部分要处理的问题就更多更复杂了。大部编译原理的教材在这部分都是讲解一些比较好的处理策略而已。因为新的问题总是在发生，旧的办法不见得足够解决。 本来说，作为一个编译器，起作用的部分就是用户输入的源程序到最终的代码生成。但是在讲解最终代码生成的时候，又不得不讲解机器运行环境等内容。因为如果你不知道机器是怎么执行最终代码的，那么你当然无法知道如何生成合适的最终代码。这部分内容我自我感觉其意义甚至超过了编译原理本身。因为它会把一个计算机的程序的运行过程都通通排在你面前，你将来可能不会从事编译器的开发工作，但是只要是和计算机软件开发相关的领域,都会涉及到程序的执行过程。运行时环境的讲解会让你更清楚一个计算机程序是怎么存储，怎么装载，怎么执行的。关于部分的内容，我强烈建议大家看看龙书上的讲解，作者从最基本的存储组织，存储分配策略，非局部名字的访问，参数传递，符号表到动态存储分配(malloc,new)都作了十分详细的说明。这些东西都是我们编写平常程序的时候经常要做的事情，但是我们却少去探求其内部是如何完成。 关于中间代码生成，代码生成,代码优化部分的内容就实在不好说了。国内很多教材到了这部分都会很简单地走马观花讲过去，学生听了也只是作为了解，不知道如何运用。不过这部分内容的东西如果要认真讲，单独开一学期的课程都讲不完。在《编译原理及实践》的书上，对于这部分的讲解就恰到好处。作者主要讲解的还是一种以堆栈为基础的指令代码，十分通俗易懂，让人看了后，很容易模仿，自己下来后就可以写自己的代码生成。当然，对于其它代码生成技术，代码优化技术的讲解就十分简单了。如果要仔细研究代码生成技术，其实另外还有本叫做《》,那本书现在由机械工业出版社引进的，十分厚重，而且是英文原版。不过这本书我没有把它列为推荐书给大家，毕竟能把龙书的内容搞清楚，在中国已经就算很不错的高手了，到那个时候再看这本《》也不迟。代码优化部分在大学本科教学中还是一个不太重要的部分，就是算是实践过程中，相信大家也不太运用得到。毕竟，自己做的编译器能正确生成执行代码已经很不错了，还谈什么优化呢？ 编译原理的课程毕竟还只是讲解原理的课程，不是专门的编译技术课程。这两门课程是有很大的区别的。编译技术更关注实际的编写编译器过程中运用到的技术，而原理的课

4. 计算机专业不需要开设编译原理课程吗

随着信息技术的迅猛发展及其应用领域的不断深化，几乎所有专业的研究与应用都离不开信息技术。信息化浪潮对高等教育也带来非常直接的变化，各专业课程设置无不将计算机知识教育作为其课程设置的组成部分。几乎所有专业的大学毕业生，都要求掌握基本的计算机操作技能，非计算机专业学生需要通过计算机等级考试，而一些和信息技术密切相关的专业，如电子信息、信息管理、电子商务等，课程设置上与计算机专业更是大量重叠，计算机知识教育在各专业中的渗透程度日渐加剧。1 计算机专业面临的新挑战 在计算机知识正在成为各专业基本教育内容的背景下，计算机专业学生的专业优势受到很大的挑战，以往在软硬件知识和应用能力上的独特优势似乎在逐渐弱化，与具有特定专业背景的学生相比就业压力越来越大，由此也引发计算机专业到底学什么、专什么的现实思考，我们必须面临的问题是：计算机专业的学生专业优势体现在哪里？ 计算机学科是一门技术性、工程性和应用性很强的学科，并有其基础理论支撑的科学体系。计算机也是一种使用工具，但那种把工具使用等同于计算机专业的狭隘认识，其思维实际上和十多年前认为“会用计算机打字就是会用计算机”如出一辙。计算机专业学生的优势应该在于：通过系统的专业原理性知识的学习与训练，熟练掌握基本的应用技能，并能够“知其然，且知其所以然”，为此专业基础课程的熏陶必不可少。而编译原理就是一门介绍这种原理性知识的综合性专业基础课程。 2 编译原理是计算机专业必不可少的基础知识 计算机专业的理论基础对培养学生的计算机专业素养具有非常重要的作用。 在众多的原理性学习课程中，编译原理主要承担了语言实现原理、方法和技术的介绍。人们借助计算机减轻自己的劳动强度，提高生产率，完成一些人类无法进行的危险、高难度工作。然而所有这些工作都必须借助程序设计语言书写的程序来指挥计算机。非机器语言程序功能的实现必须由翻译程序来完成。正是有了编译程序、解释程序、汇编程序等翻译程序，人们才可以使用自己习惯的语言将需要计算机做的事情描述成程序，并通过这些翻译程序的工作让计算机理解并执行。可以说，没有翻译程序，计算机不可能象今天这样得到如此广泛的普及，网络也不会有今天这样大的吸引力，我们的生活、学习和工作将会是另一个样子。 包括编译程序在内的翻译程序承担了实现语言的功能，它所涉及的知识包括形式语言、自动机理论等语言定义、翻译与实现的基础知识，这些知识可以让学生领悟到计算机理论的精髓，可以让学生从实现的角度重新审视软件的开发，有助于学生对软件的真正认识，对于今后从事应用软件、语言开发平台、编译系统甚至操作系统开发等都是非常有好处的。同时，编译原理是许多课程的一个综合性的实践，它进一步加深了学生对程序设计语言课程中语言基本单位的定义和作用的理解。例如，编译程序使用的一些数据结构和算法是“离散数学”、“数据结构”以及“算法设计与分析”等课程相关知识的典型应用；编译程序对目标代码的存储组织与分配功能的实现原理又与“操作系统”的相关内容相互渗透；编译程序对中间代码的优化功能的实现则是数学、逻辑学、结构程序设计和优化理论的综合应用和专门化。因此，编译的原理性研究、学习和实践，可以多角度提高学生的逻辑思维能力、实践动手能力、编程调试及综合应用能力，有助于切实有效地提高学生的专业素质。另外，编译课程中介绍的知识也是后续许多课程的基础。所以，编译原理是计算机专业学生必须掌握的基本原理，编译原理课程是计算机专业非常重要的专业课程。 尽管经过计算机专业人员的大量努力，大量的工具软件为我们提供了极大的便利，以至于人们只需要通过若干次点击鼠标左键就可以方便地完成很多工作，但这并不是说所有问题都已经解决，还有很多深层次的工作需要计算机专业人员去完成。如果我们的计算机专业毕业生也只会“点击左键”，很难想象他们会开发出更好的工具，或对计算机技术的发展作出应有的贡献。 专业理论基础的学习，可以培养学生的思维方式和洞察力。计算机技术的更新是非常快的，系统的理论基础可以让学生在将来更好地适应新技术，可以让他们在理论框架的指导下寻找解决问题的方法，朝不同的方向发展！因此，“编译原理”课程应该是计算机专业必须的重要基础课。3 编译技术的应用及需求 编译原理课程的重要性，不仅仅是因为它所介绍的知识是计算机专业理论知识的重要组成，也在于编译程序所使用的一些原理、方法和技术在非编译系统的实际应用中也发挥了很大作用。 例如我们常用的文本编辑工具的实现，涉及到的字词、语法正确性等内容就是编译里介绍的词法分析、语法分析技术的具体应用；又如现在大家上网必不可少的搜索引擎，在处理用户输入的查询要求、对文档资源的特征分析、提取与描述等工作中都用到编译的相关知识；一些特定的应用也可以用到编译中的方法来解决问题，比如用正规表达式描述网络上某种信息的特征等。 随着消费类电子产品的大量开发，嵌入式系统的应用需求也不断增加。在这种情况下，搭建适合的交叉编译环境的工作日益重要，急需掌握编译器构造相关原理、方法和技术的从业人员。这不仅说明了编译知识的生命力，同时也给高等学校计算机专业的编译课程设置带来了新的要求。 现实告诉我们，目前的问题不是计算机专业要不要开设编译原理课程，而是该如何改进编译原理的内容与教学方式，以更好地适应社会的需求。4 国内外编译相关课程的设置情况 我们查阅了国外一些着名的大学计算机专业的课程设置情况，研究了其中与编译相关的课程安排，发现他们对与编译相关知识的介绍是非常重视的。 美国麻省理工学院的计算机专业课程设置中，与编译相关的课程就有Structure and Interpretation of Computer Programs, Computer Language Engineering (包括基本概念、编译器的功能和结构、基本程序优化技术、理论和实践的交互作用以及使用工具编制软件)，Multithreaded Parallelism: Languages and Compilers；加州大学伯克利分校工学院的计算机课程设置中，涉及编译的课程有Implementation of Programming Languages, Programming Languages and Compilers, Structure and Interpretation of Computer Programs等；英国剑桥大学的计算机科学课程与编译相关的有Compiler construction 和Advanced compiler design等。 在国内，多年来编译原理一直是各校特别是教育部所属高校计算机专业的必修课，曾经也是计算机专业硕士入学考试的必考科目，现在某些学校的计算机专业硕士生入学面试和博士入学考试还必考编译原理。编译原理课程在我国计算机专业人材培养中起了很重要的作用，新形势下开发具有自主知识产权的计算机系统软、硬件，更需要编译原理课程继续发挥作用。5 关于我国计算机专业编译原理课程设置的建议 一般认为，编译原理课程是计算机专业最难的课程之一，它是数据结构、语言、算法和软件设计等知识的综合体现，学生对这门课程的理解确实会有一定难度，但这正是教师工作需要解决的问题。实践证明，如果让学生认识到了课程内容的重要性，并辅之以合适的教学方法和教学手段，取得良好的教学效果是不难的。 为此，我们思考了新形势下编译原理课程所涉及内容的教学及课程设置的改革问题，如果必须改变现有的课程设置模式，我们建议在编译原理课程的设置上，可以考虑采取以下两种模式：(1) 课程分解式 将编译原理课程根据内容分成两门课：一门为必修，可命名为“编译技术”，主要介绍一些为满足基本应用而需要学生掌握的基础知识、方法、技术，以达到语言实现理论基础介绍的目的；另一门为选修，可命名为“编译理论”，主要介绍偏重原理性的、更深层次的内容，方便有进一步深造需要的学生学习。 (2) 内容分解式 可以不单独设置一门编译课程，可将课程的内容根据其深浅，涉及到的具体问题，及与其他课程内容的相关性等分解到不同的课程中去，使学生在不同课程的学习中逐步掌握相关知识。 比较两种模式，后者在目前阶段来说还存在一定的难度：一是编译课程内容的分解不是孤立的，需要与其他课程的内容进行重新整合，因而涉及面太大，短时期内难以做到科学分解与组织；二是增加了其他课程授课教师的工作量与难度，因为他们需要重新考虑、设计新增加的编译部分内容的教学方法、教学形式等问题，有可能需要在教学实践中磨合一段时间才能取得好的教学效果。 因此，在现有形势下，比较可行的还是第一种模式。当然，在经过学科知识点合理的分解与组织之后，可以逐步过渡到第二种模式。

5. 编译原理课程主讲老师是谁

编译原理主讲老师在华东师范大学计算机系任教，讲师。 在华东师范大学讲授的主要课程包括本科生的《计算机编程实践》，研究生的《高级算法》，夜大学和网络学院的《编译原理》等。个人主要研究兴趣方向是不确定推理，智能计算，分布式环境下的计算等。