文档介绍：编译原理
课程简介
先行课程:高等数学、C (PASCAL)、离散数学、
汇编语言、数据结构
编译原理课程应用领域
编译器的设计
一般的软件设计
例如:
文本编辑器、信息检索系统、模式识别器
排版、绘图系统
程序验证器
语言与计算理论导引
什么是语言?为什么要研究语言?
狭义地讲,语言是人类内心世界的外在符号,是交流的工具,广义地讲,动物等事物都具有语言,比如狗的不同叫声和摇尾表达不同的情感,汽车不同的闪灯表示不同的意义。汽车的语言是人赋予的,是一种人工语言。但无论什么语言,它最重要的用途是不同事物间交流意思。既然世界上存在如此众多的语言,那么他们有些什么区别哪?显然人的语言比狗或车复杂多了,一个自然的推论就是能够处理越复杂语言的物体,则它越“聪明”,具备的能力越强大。
语言与计算理论导引
计算机已经从最初单纯的辅助计算工具逐渐演化***脑的模拟器,但只有当计算机处理的语言同人脑处理的语言一样复杂,它才可能真正完***脑能够完成的所有工作。因此,自然要问:如何准确地刻画一个语言的复杂度?很多年前,我们知道上海比北京暖和,现在科学的进步让我们能够精确地显示两地温度的差异。我们能够找到(或发明)刻画语言复杂度的“摄氏温度计”吗?
语言与计算理论导引
一个了不起的观点是:一个语言是一个集合。研究语言不是仅仅关心其中的一两个句子,要研究组成语言的所有句子的共性,发现处理组成语言的所有句子的通用方法。我们认为自然界的语言确实是有共性的句子组成的,即他们是有规律的。因此人工语言也应当是依照一定规律设计。
语言与计算理论导引
既然语言有规律,那么刻画一个语言除了罗列这个语言的所有句子,另一个方法就是描述这个语言的规律。语言规律的表现形式往往是规则。描述语言规律的一个简单方法是罗列规则,因此一个语言可以是句子集,也可以表示为一个规则集。规则集在形式上往往比句子集要简洁很多,因此我们希望用规则集的复杂度来表示语言的复杂度。
语言与计算理论导引
那么问题变成什么是刻画语言的规则和规则集?什么是规则的复杂度?
显然刻画规则也需要一种语言,存不存在一个语言,它描述的规则能够刻画所有的语言(甚至包括它自身)?只有用相同语言描述的规则才能比较它们的关系和复杂度。当然我们可以用某种自然语言,比如英语等,但自然语言的缺陷是显而易见的,它只能被人使用,而英语一般只能被英语国家的人使用。既然我们希望计算机理解这些语言的差异,因此我们最好使用某种计算机理解的语言。Chomsky找到(或发明、发现)的这种语言称为文法语言,它描述的规则称为文法,形如。因此有了文法,就可以定义规则和语言的复杂度了。
语言与计算理论导引
但Chomsky文法仍有缺点,比如刻画语言的能力和粒度不够细,它可以刻画0型、1型、2型和3型语言,但还有许多语言无法刻画,其中包括很重要的人类自然语言。尽管如此,它是目前我们找到的较好方法,为包括高级程序语言的人工语言的设计和发展给出了指导性方针。这些人工语言在形式上由于有精确的定义,往往又称为形式语言。
语言与计算理论导引
我们仅仅研究形式语言,我们希望这些研究有助于更深刻地理解自然语言,为最终发现具有自然语言同样能力的形式语言作出贡献,而那一天就是计算机真正具备人脑能力的一天,当然目前而言,这不是一个可实现的梦想,我们期待在追逐这个梦想的过程中,得到人类精神生活中的一些收获,或一些较低目标的物质的副产品。