CompilerPrinciples1第一讲引论课程信息编译程序概述高级语言的语法描述CompilerPrinciples3§1.课程信息一、课程名称:编译原理基本内容是介绍编译程序构造的基本原理、方法和技术,包括词法分析、语法分析、语义分析与中间代码产生、代码优化及目标代码产生等。简言之,就是介绍如何将源程序翻译成目标代码程序。CompilerPrinciples4二、课程性质:专业基础课,必修编译程序(器)出现于上世纪50年代后期(第一个高级语言1958年)60年代~70年代是研究高峰期60年代中期开始在高校中开设课程80年代开始作为计算机科学与技术专业的必修基础课程CompilerPrinciples5CompilerPrinciples6三、课程特点:充分体现了计算学科中抽象、理论和设计三个学科形态该课程涉及多门课程的内容综合运用,涉及面广,内容庞杂,学习艰难程序设计语言、计算机体系结构、语言理论及算法等数据结构、离散数学该课程涉及的原理、方法和技术具有十分普遍的意义每一个计算机科学与技术工作者的职业生涯中反复用到,“享用一辈子”这儿接受的训练很难在其他地方获得,如:抽象与形式化方法、局部与全局优化方法、构造技术、证明方法等CompilerPrinciples7四、学习该课程的意义编译程序是计算机系统不可缺少的重要组成部分对程序设计语言的设计与实现能有更深刻的理解对程序设计语言有关理论有所了解从宏观上把握程序设计语言——掌握了编译原理后,就不能再说:“某语言未学过,所以不会”有助于快速理解、定位和解决程序调试与运行中出现的问题CompilerPrinciples8编译方法与技术有着广泛应用安全技术、程序理解、软件逆向工程、应用软件与软件工具开发、软件测试与验证等编译课程蕴含着计算学科中解决问题的思路、抽象和方法,这些与高等数学一样,使你“享用一辈子”课程所涉及的内容至今非常活跃自然语言的翻译软件移植网络安全形式化方法形式语义学等CompilerPrinciples9鉴于以上所述,作为计算机科学与技术专业的学生必须学习和掌握编译原理这门课程,当然由于其综合性、处理问题的复杂性等,学习起来有一定难度,这就需要艰苦奋斗的精神和良好的学习方法CompilerPrinciples10五、学习方法编译程序的构造是一个庞大而复杂的系统工程,无论是概念还是理论、方法,对初学者来说许多都是新的,学习起来会感到困难大一些,这一点必须有充分认识,为此建议学习方法上注意以下几点:CompilerPrinciples111.课前预习,课堂认真听讲,课后复习加深理解,特别要经常有意识地将前后内容联系起来融会贯通。因为编译程序是一个庞大的程序系统,讲解过程必须“分而治之”(这也是人们处理复杂问题的基本方法),这就要求大家在学习过程中,始终以处理过程为主线,把前后联系起来考虑。CompilerPrinciples122.理论联系实际——亲自动手,构造一个演示性编译程序,至少要完成扫描器和语法分析器,以及语法制导翻译产生中间代码(课程设计)3.认真完成作业,进一步巩固并加深理解所学知识4.特别要下功夫认真学习如何从实际问题进行抽象并形式化,最终建立实际问题的模型(上升为理性认识),并借助模型进一步设计实现,这将对你能力的提高大有益处CompilerPrinciples13六、教材《程序设计语言编译原理》(第3版)国防工业出版社陈火旺等1.内容详实丰富,理论与技术相结合2.较为全面介绍了编译程序构造的基本原理、方法与技术3.厚度适中4.大多数院校一直采用,硕士入学考试参考书5.所谓教材,实为第一参考书而已CompilerPrinciples14七、参考书目1.《编译原理》第2版赵建华等译,Compilers:Principles,Techniques,&ToolsA.V.Aho,M.S.Lam,RaviSethi,J.D.Ullman著,机械工业出版社,2009;2.《编译原理课程设计》王雷等著,机械工业出版社,2005;八、期末总评平时成绩:10%课程设计:20%期终考试:70%CompilerPrinciples15CompilerPrinciples16§2.编译程序概述一、翻译程序(Translator)能够把一种语言程序(称为源语言程序)转换成逻辑上等价的另一种语言程序(称为目标语言程序)的程序CompilerPrinciples17任何非机器语言程序都需要翻译程序翻译程序的工作就是进行等价变换(映射)两个程序逻辑上等价是指对相同输入得到相同的输出翻译程序解释程序汇编程序编译程序CompilerPrinciples181.汇编程序(Assembler)把汇编语言程序转变为机器语言程序的翻译程序2.解释程序(Interpreter)把源程序作为输入接收,边解释边执行的翻译程序源程序数据解释程序结果CompilerPrinciples193.编译程序将高级语言程序转变为低级语言程序的翻译程序源程序编译程序目标程序CompilerPrinciples20CompilerPrinciples21编译程序又可根据用途和侧重点的不同,进一步分类为:①诊断编译程序(DiagnosticCompiler)专门用于帮助程序开发和调试的编译程序②优化编译程序(OptimizingCompiler)着重于提高目标代码效率的编译程序③交叉编译程序(CrossCompiler)能够产生不同于其宿主机机器代码的编译程序④可变目标编译程序(Retargetablecomplier)无须重写与机器无关部分就能改变目标机的编译程序CompilerPrinciples22二、与编译程序相关的程序本讲义只介绍编译程序(器)构造的基本原理、方法与技术,但在一个完整的语言开发(或称程序设计)环境中,除了编译器这一主要工具外,还需要其他一些工具,如编辑器、连接器、装入程序等。现代计算机系统常将这些相互独立的程序设计工具集成起来,构成一个集成化的程序开发环境,以提高程序设计效率和程序的质量。如TurboC、VisualC++等语言环境都是集成化的程序设计环境。而Ada语言的集成环境是这方面的典型代表。CompilerPrinciples23如Ada语言的集成环境是一个分层的程序开发环境编译程序MAPSE编辑程序连接程序宿主机OSAPSE工具界面用户界面KAPSE调试程序配置管理程序命令解释程序其他工具CompilerPrinciples24这儿要强调的是:尽管本课程只介绍编译的基本理论、方法和技术,但这些基本理论、方法与技术对其他工具的构造同样起作用!CompilerPrinciples251.编辑器(Editor)完成源程序输入、编辑并产生标准文件(如ASCII文件)的程序。近来已与编译器和其他程序捆绑进一个交互开发环境——IDE中尽管这样的编辑器仍生成标准文件,但会转向正被讨论的程序设计语言的格式或结构(称为基于结构的),且已包含了编译器的某些操作;因此在程序编写时而不是编译时就可得知错误,甚至也可调用编译器CompilerPrinciples262.预处理程序(Preprocessor)在真正翻译开始之前产生编译程序的输入的程序处理宏及注释:宏是被经常使用的较长结构的缩写处理文件包含:把头文件包含到程序正文中(如C的文件包含include….h)“理解”预处理器:把现代控制流和数据结构机制添加到比较老式的语言中语言扩充:通过大量的内部宏定义来增强语言的能力,如Equel语言是一种嵌套在C语言中的数据库查询语言CompilerPrinciples273.连接程序(Linker)——又称为连接编辑器。将分别在不同的目标文件中编译(或汇编)的代码、所用标准库函数的代码以及操作系统提供的资源(如存储分配程序及输入/输出设备)收集到一个可直接执行的文件中的程序4.装配程序(Loader)完成程序的装入和连接编辑两项功能。装入过程包括读入可重定位机器代码、修改可重定位地址、并将修改后的指令和数据放到内存的适当位置。装入程序使得可执行代码更加灵活CompilerPrinciples285.调试程序(Debugger)可在被编译了的程序中判定执行错误的程序它经常与编译程序一起放在IDE中运行一个带有调试程序的程序与直接执行不同,这是因为调试程序保存着所有的或大多数源代码信息,它可以在预先指定的位置(断点BreakPoint)暂停执行,并提供有关信息(已调用的函数、变量名的当前值等)CompilerPrinciples296.其他有关的还有描述器(Profiler)——执行中搜集目标程序行为统计的程序项目管理程序(ProjectManager)——如Unix系统中的SCCS(源代码控制系统)和RCS(修正控制系统)和汇编程序等综上所述可给出一个“语言处理系统”的图示:CompilerPrinciples30我们这个课只介绍编译程序这一部分预处理器编译器源程序汇编器目标汇编程序装载器/连接编辑器可重定位机器代码源程序梗概可执行机器代码库、可重定位目标程序CompilerPrinciples31三、编译过程与编译程序结构1.编译过程:输入输出(高级语言源程序)(低级语言目标程序)编译程序工作过程如下:识别出一个个的单词分析句子的语法结构分析句子的语义并进行初步翻译对初步翻译进行优化整理出目标程序对以上过程进一步整理可得如下编译程序结构总框:编译程序CompilerPrinciples322.编译程序总框:词法分析器语法分析器语义分析与中间代码产生器优化器目标代码生成器单词符号语法单位中间代码中间代码出错处理表格管理源程序目标代码CompilerPrinciples333.五个阶段简介第一阶段:词法分析——依据语言构词规则,识别出一个个单词(符号)◇单词种类保留字:forifwhile算符:+-×/界符:,;(){}标识符:a1a2pi常数:910244.86E6无穷性有穷性思考:识别有穷集合VS识别无穷集合CompilerPrinciples34◇词法分析工作由词法分析器(或称扫描器)完成。◇扫描器输出为等长度的单词符号(二元式)流。◇例:Position=initial+rate*60词法分析(扫描器)保留字表(06,‘Position’)(11,─)(06,‘initial’)(12,─)(06,‘rate’)(13,─)(07,’60的二进制’)CompilerPrinciples35第二阶段:语法分析——依据语言的语法规则,把扫描器提供的单词符号串分解成各种语法单位(范畴),如“短语”、“子句”、“句子”乃至“程序”。同时进行语法检查,以确定输入串是否正确,该工作是由语法分析器完成的。◇如:Position=initial+rate*60是一个“赋值表达式”(C语言中)Position=表达式表达式表达式+表达式标识符表达式*表达式initial标识符常数rate60标识符CompilerPrinciples36第三阶段:语义分析与中间代码产生——针对各类不同的语法范畴,按语言的语义规则进行语义分析和初步翻译工作,产生某种中间语言形式的中间代码(即一种结构简单,含义明确的记号系统)。该阶段工作通常包括两个方面的工作:◇对每种语法范畴进行静态语义检查,包括:变量是否定义过类型是否正确是否用了0作除数……CompilerPrinciples37将语法范畴翻译成某种形式的中间代码,如四元式:OpARG1ARG2Result*rate60T1+initialT1T2=T2PositionCompilerPrinciples38第四阶段:优化——对前阶段产生的中间代码进行加工变换,以期在最后阶段能产生出高效(节省时、空)的目标代码,这一任务是由优化器来完成的根据优化的范围不同,可分为:局部优化,循环优化和全局优化一个循环优化的例子:CompilerPrin