编译原理学习指导
编译原理是计算机专业课程中最难同时也是最有挑战性的一门,理论上高度抽象,而且要求扎实的数学功底,在实践上也对数据结构的知识要求比较高.但是编译原理又是计算机科学中最为基础和重要的,类似于高等数学在理工科中的地位,所以今天粗略的跟大家谈谈这门课程的学习.
一、为什么学编译原理?
1、 编译原理蕴涵着计算机学科中解决问题的思路、抽象问题和解决问题的方法;
2、 编译原理课程的学习有利于加深对程序语言的理解,可以帮助你更加快速的掌握新的语言工具;
3、 课程中包含了很多软件技术,这对于以后从事软件设计是很有帮助的.
二、编译原理主要内容提要
(一)编译程序的功能、工作过程、结构以及构造方法
计算机只能读懂0或者1,而我们用高级语言编写的程序(原程序)是抽象的符号化了的东西,为了让计算机读懂我们写的程序,必须把我们
书写的程序翻译成某台机器能够读懂的(机器)语言(目标程序),这就是翻译程序的作用.翻译程序进行的是等价的翻译,意思就是说目标程序
和原程序在功能上是等价的;翻译程序有两种方式:“编译”、“解释”,区别在于是否生成目标代码,解释方式下,是直接执行源程序本身的
或者与源程序等价的中间程序,并不生成目标代码,而编译方式下,必须生成目标代码.
编译方式的特点①源程序的执行是分阶段的:编译阶段和执行阶段(若编译生成的目标程序是汇编语言程序,则在两者之间还有一个汇编
阶段),而解释方式下,只有一个阶段---解释执行阶段(按照语句执行的动态顺序,逐条解释执行);②任何一种编译程序都是某一特定类型机器
上的关于某一特定语言的的编译程序;③编译生成的目标程序可能是机器语言的程序也可能是汇编语言程序.
编译程序的工作过程通常是词法分析、语法分析、语义分析、代码生成、代码优化,代码优化不是必须的,其他过程都是必须的.编译程
序的这些过程的执行先后就构成了编译程序的逻辑结构,但是这些逻辑结构不一定是按照某一个固定顺序的,也有可能是按照平行或者互锁的
方式执行的.
构造编译程序可以使用机器语言、汇编语言甚至高级语言,通常有2种方法:移植和自编译.移植就是说在一台机器上用一种高级语言
编写的编译器能在另外一台机器上运行,自编译方式则需要对语言的核心部分构造一个小型的编译程序,然后在以此为基础构造能编译更多
语言成分的较大的编译程序.
结合以上的知识去想一下JAVA的与平台无关性是怎么回事?
(二)词法分析以及程序的设计方法、有穷自动机、正则表达式
几个关键的问题是①由正则表达式构造确定化的有穷自动机;②确定的有穷自动机的最小化;③词法分析程序的设计.
正则表达式看上去复杂而且古怪,但是它广泛的被很多文本编辑软件以及教本软件支持,VC++和java等的交互式IDE中也开始对它支持.学习它一个最基本也是最重要的地方就是要把元符号的意义理解清楚,这是一个事半功倍的事情,希望大家做好这个工作再来进行正则表达式的学习;接着你要找一些例子来理解这些东西,例子最好由简单到难,最后你还可以了解一下不同工具中的正则表达式,比如在VC++中选择Edit->Replace，然后选择"Regular expression"选择框，在Find What输入框输入一些vi的替换命令进行实践理解(可以在线查阅一些在线的vi使用手册).
有穷自动机其实就是关于数学的方法的算法,本质上最重要的还是数学方法. 正则表达式实际上使用的是一个不确定有穷自动机(NFA)，NFA对同一个字符串输入完全有可能有多种理解方式，而DFA(确定有穷自动机)则只有唯一的一种理解方式,所以DFA的效率明显要高一些,其实从数学上来说,两者的本质就是在于状态转移函数不一样. 对于编译器来说，主要有两种构造DFA的方式，一种是LL分析方法，另外一种是LR分析方法。这两种都是基于输入预测的分析方法，但是分析的方法却有所不同，LL属于推导的方式，LR则属于归纳的方式。LL比较符合人的思维方式，但是却有一些局限性。LR则比较难理解，但是适用范围却比LL要广泛一点，效率也高一点。
(三)文法的构造、文法描述的语言、短语和句柄、语法树
为了使得源程序能被正确的翻译,产生等价的目标程序,源语言的使用者和实现者都应该遵循关于源语言的共同约定(语法规则),使用者可以根据这些规则保证书写的程序在形式和结构上的正确性,实现者根据这些规则来确定接受什么样的源程序以及怎样翻译这些源程序.一般这些语法规则用上下文无关文法进行描述.
上下文无关文法利用了类似于正则表达式的命名惯例和运算,所以学习了正则表达式以后应该不会再感觉到上下文无关文法很抽象了,唯一不同的是上下文无关文法中采取的是递归的规则(所以在学习的时候要深刻的领会递归规则,怎样用有穷的规则来定义无穷的语言),例如if语句中还可以嵌套其他的if语句,但是这在正则表达式中是不行的,所以导致用于语言语义结构的数据结构有了很大的变化,必须是递归的,不再是线形的,经常使用的数据结构就是分析树或语法树,分析的算法又涉及到两种方式:自顶向下和由底向上.
文法分成四种类型：0型（短语文法）、ⅰ型（上下文有关文法）、ⅱ型（上下文无关）、ⅲ型（正则文法）。与这四类文法对应的自动机分别为图灵机、线性有限自动机、非确定的下推自动机、有限自动机。在这四类文法中，常用ⅱ型文法来描述程序设计语言的语法，ⅲ型文法来描述程序设计语言的词法。由定义可知ⅲ型文法必为ⅱ型文法。ⅲ型文法对应的识别装置为有限自动机，有限自动机分确定的有限自动机和非确定的有限自动机，可证明对任一非确定的有限自动机都存在一个确定的有限自动机与之等价（两个有限自动机等价是说二者是别的语言相同）。
1、自下而上分析法
基本思想：从输入符号串开始逐步进行归约，直至归约成文法的起始符号。
基本问题：①如何找到进行直接归约的简单短语?也即如何找到句柄；②找出的简单短语应该直接归约到哪一个非终结符号? 对于这两个问题有不同的解决办法,所以才有不同的算法LR(0),LR(1),SLR(1),LALR(1),简单优先分析发,算符优先分析发等。算符优先分析法是不含ε产生式的算符文法。自上而下分析方法有LL(1)分析法，递归子程序法等。
2、自上而下分析法
基本思想：从文法的起始符号开始反复使用产生式进行推导直至推导出输入符号串。自上而下分析通常要求文法的产生式不含左递归，否则会使分析程序死循环。
基本问题：①什么是回嗍问题?怎么避免回嗍?为什么要避免回嗍?②左递归有什么影响?怎么避免或者消除?③递归下降分析法的基本思想和技术.
(四)运行时环境
(五)中间代码生成以及程序的优化
以上两个内容我已经在《计算机与组成原理》课程中做了详细的讲述,这里暂时不添加内容,等有了时间在慢慢添加.
三、怎样学习编译原理(建议)
1、做好思想准备,不要畏难,书一遍没看懂没关系,要多看几遍,甚至几十遍,不是有句话么:书读百遍,其义自见;还要结合课本后面的习题多做思考和类比,这些都是最基本的办法,在学习的过程中归纳出自己的难点和疑惑点,然后重点突破；
2、自己动手做一个虚拟机,在虚拟机的基础上开发自己的语言和编译器,加强实践,当然并不需要你把这些做的多么复杂,主要目的还是为了结合理论的学习,是为了更加深刻的理解书本上那些抽象的东西;但是谁又敢说,你不能由此发明了将来流行世界的新的语言和新的编译器呢?
3、在了解了本篇文章所说的东西后,可以直接专注于编码(Lex,Yacc等)的研究,然后去配合理论的学习,可以在第一次学习的过程中忽略一些内容,等以后用的时候再来学习.
四、推荐的资源
1、 http://ultra1.wuhee.edu.cn/compiler/compiler.html上面有不少的编译原理相关的资料,而且还有语法分析过程的JAVA演示程序,很形象生动的为大家演示一些比较抽象的概念；
2、《Compiler Design in C》作者:Allen I. Holub,出版社: Prentice Hall这是一本经典的编译原理教程,均衡了编译原理理论和实践的内容,详细讨论了自顶向下和自底向上的语法分析、语义分析、中间表示和代码生成等内容,所有的程序都采用大家熟悉的C语言来描述,是一本重点推荐的书；
3、《编译原理及实践》(《Compiler Construction Principles and Practice》),作者:Kenneth C. Louden等, 机械工业出版社.这本书对经典的编译技术做了全面详细的介绍, 也对诸如面向对象等比较新的编译技术做了系统的解说, 练习题十分的丰富而且具有极强的参考价值和思考价值, 强烈推荐；
4、 http://www.cstc.net.cn/?item=docs&sub=view&id=270编译原理学习导论, 是网络上现在很流行的一篇文章, 大家看看可以增加对编译原理的感性认识, 文章里面也推荐了一些很经典的书籍, 大家可以结合上面的两本书籍做出选择.
