《编译原理简明教程》PPT课件.pptx

1.1 程序设计语言和编译程序 1.2 编译程序的历史及发展 1.3 编译程序的工作过程与结构 1.4 编译程序的开发 1.5 构造编译程序所应掌握的内容;1.1 程序设计语言和编译程序;　由于汇编语言和机器语言一样都是面向机器的，故相对于面向用户的高级语言来说，它们都称之为低级语言，而FORTRAN、PASCAL、C、ADA、Java这类面向应用的语言则称之为高级语言。因此，编译程序就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序，见图1–1。;图1-1 编译程序的功能;　　一个高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段，如图1–2所示。编译阶段将源程序变换成目标程序；运行阶段则由所生成的目标程序连同运行系统(数据空间分配子程序、标准函数程序等)接受程序的初始数据作为输入，运行后输出计算结果。;图1–2 源程序的编译和运行阶段 ;　　如果编译生成的目标程序是汇编语言形式的，那么在编译与运行阶段之间还要添加一个汇编阶段，它将编译生成的汇编语言目标程序再经过汇编程序变换成机器语言目标程序，如图1–3所示。;图1–3 源程序的编译、汇编和运行阶段 ;　　用高级语言编写的程序也可通过解释程序来执行。解释程序也是一种翻译程序，它将源程序作为输入，一条语句一条语句地读入并解释执行，如图1–4所示。解释程序与编译程序的主要区别是：编译程序将源程序翻译成目标程序后再执行该目标程序；而解释程序则逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不产生目标程序。典型的解释型高级语言是BASIC语言。;图1–4 解释程序解释执行过程示意 ;1.2 编译程序的历史及发展; （3） 1954~1957年，IBM John Backus带领的一个研究小组对FORTRAN语言及其编译器进行了开发。但是，由于对编译程序的理论及技术研究刚刚开始，这个语言的开发付出了巨大的辛劳。与此同时， 波兰语言学家Noam Chomsky开始了他的自然语言结构研究。Noam Chomsky根据文法（Grammar，产生语言的规则）的难易程度及识别它们所需的算法对语言进行了分类，定义了0型、1型、2型和3型这四类文法及其相应???形式语言，并分别与相应的识别系统相联系。 （4）20世纪70年代后期和80年代初，大量的研究都关注于编译器其他部分的自动生成，其中包括代码生成。; （5）现今编译器的发展包括了更为复杂的算法应用程序，它用于简化或推断程序中的信息，这又与具有此类功能的更为复杂的程序设计语言发展结合在一起。其中典型的有用于函数语言编译Hindley-Milner类型检查的统一算法。目前，编译器已经越来越成为基于窗口的交互开发环境（Interactive Development Environment，IDE）的一部分，这个开发环境包括了编辑器、链接程序、调试程序以及项目管理程序。尽管近年来对IDE进行了大量的研究，但是基本的编译器设计在近20年中都没有多大的改变。 （6）现代编译技术已转向并行编译的研究。 ;1.3 编译程序的工作过程与结构 　　1．词法分析 　　词法分析的任务是输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号，如基本字(if、for、begin等)、标识符、常数、运算符和界符(如“(”、“)”、“=”、“；”)等，将所识别出的单词用统一长度的标准形式(也称内部码)来表示，以便于后继语法工作的进行。因此，词法分析工作是将源程序中的字符串变换成单词符号流的过程，词法分析所遵循的是语言的构词规则。;　　2．语法分析 　　语法分析的任务是在词法分析的基础上，根据语言的语法规则(文法规则)把单词符号流分解成各类语法单位(语法范畴)，如“短语”、“子句”、“句子(语句)”、“程序段”和“程序”。通过语法分析可以确定整个输入串是否构成一个语法上正确的“程序”。语法分析所遵循的是语言的语法规则，语法规则通常用上下文无关文法描述。;　　3．语义分析和中间代码生成 　　这一阶段的任务是对各类不同语法范畴按语言的语义进行初步翻译，包含两个方面的工作：一是对每种语法范畴进行静态语义检查，如变量是否定义、类型是否正确等；二是在语义检查正确的情况下进行中间代码的翻译。注意，中间代码是介于高级语言的语句和低级语言的指令之间的一种独立于具体硬件的记号系统，它既有一定程度的抽象，又与低级语言的指令十分接近，因此转换为目标代码比较容易。把语法范畴翻译成中间代码所遵循的是语言的语义规则，常见的中间代码有四元式、三元式、间接三元式和逆波兰记号等。;　　4．优化 　　优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效(节省时间和空间)的目标代