《编译原理教案综述》由会员分享，可在线阅读，更多相关《编译原理教案综述（46页珍藏版）》请在金锄头文库上搜索。
1、第1章 编译原理概述主要内容：1 编译程序概述 2 编译程序的工作过程与结构 3 编译程序的开发 4 构造编译程序所应掌握的内容 任何一门高级语言都需要有相应的翻译程序将其翻译为机器语言，才能真正在计算机上执行。编译程序是这样的一种翻译程序，它对一个计算机系统来说非常重要。编写编译程序所涉及到的一些原理、技术和方法在计算机相关的各个领域中都会反复用到，具有十分普遍的意义。本章首先介绍编译原理的基本概念及与编译程序相关的一些工具，然后介绍编译的过程以及编译程序的结构、组成以及实现方法，最后对编译的相关理论和方法的应用做了简单介绍。1程序设计语言与翻译程序在计算机系统中，语言分三个层次：机器语言、
2、汇编语言和高级语言。只有机器语言程序可直接在计算机上执行，高级语言和汇编语言编写的程序必须翻译为对应的机器语言程序才能执行。计算机刚出现时，人们用机器语言(Machine Language)编写程序，如”C7 06 0000 0002”，其含义是将2放到一个存储单元中。用机器语言编写程序费时、乏味，开发难度大，周期长，很快就被汇编语言(Assembly Language)代替了。汇编语言以助记符的形式表示指令和地址。如与上述指令等价的汇编代码为：MOV X,2，它不能直接执行，需要汇编程序（Assembler）将其翻译为机器语言程序才能执行。与汇编语言有关的程序有：反汇编程序（disassem
3、bler）是把机器语言程序逆向翻译为汇编语言程序的程序；交叉汇编程序（cross assembler）是把甲计算机上的汇编语言程序翻译为乙计算机上的机器语言程序的程序。汇编语言仍与人类的思维相差甚远，不易阅读和理解，它严格依赖于机器，为一种机器编写的代码在应用于另一种机器时必须完全重写。高级语言的出现缩短了人类思维和计算机语言间的差距，如上述指令用PASCAL语言写为x:=2。编写高级语言程序类似于定义数学公式或书写自然语言，与机器无关。起初人们担心这不可能，或者即使可能，目标代码也会因效率不高而没有多大用处。编译程序(Complier)的出现解除了人们的这种担忧，它能够直接将高级语言（如FO
4、RTRAN、Pascal、C或Java等）程序翻译为对应的低级语言（如汇编语言或机器语言）程序。实际上，除了上述程序之间的翻译之外，同一种机器上的不同语言和不同种机器上的相同或不同语言程序之间都可以进行翻译Error! Reference source not found.给出了常见语言程序之间的翻译模式。把一种语言（称为源语言）书写的程序翻译成另一种语言（称为目标语言）书写的程序统称为翻译程序（Translator），后者与前者在逻辑上等价。高级语言之间也可以相互转换，把用一种高级语言书写的程序转换为另一种高级语言的程序，统称为转换程序（converter）。尽管人类可以借助高级语言与计算机
5、进行交往，但是计算机硬件真正能够识别的只是0、1组成的机器指令序列。实际使用中，高级语言除了通过编译程序将其翻译为机器语言执行外，解释程序也可以把高级语言翻译为机器语言，二者的主要区别是：编译程序先把全部源程序翻译为目标程序，然后再执行；该目标程序可以反复执行；解释程序对源程序逐句地翻译执行，目标代码只能执行一次，若需重新执行，则必须重新解释源程序。编译过程类似笔译，笔译后的结果可以反复阅读，而解释过程则类似于同步翻译，别人说一句，就译一句，翻译的结果没有保存。图1是两个过程的比较。（a）编译过程（b）解释过程图1 编译与解释过程对比2编译程序的发展及分类用高级语言编写程序简单方便，多数程序都
6、可用高级语言编写。在一台计算机中对每一种高级语言，都至少配有一个编译程序。对有些高级语言甚至配置了几个不同性能的编译程序，以实现用户的不同需求。编译程序最早出现在50年代早期，IBM的John Backus带领一个小组开发了FORTRAN语言，编写FORTRAN语言的编译器共用了18人年。与此同时Noam Chomsky开始了自然语言的研究，Chomsky的研究导致了根据语言文法 (grammar) 的难易程度以及识别它们所需的算法来对语言分类。接着人们花费了很大的功夫来研究编译器的自动构造，出现了词法和语法分析的自动生成工具Lex与YACC。在70年代后期和80年代早期，大量的项目都关注于编
7、译器其他部分的生成自动化，其中就包括了代码生成自动化。目前，编译器的发展与复杂的程序设计语言的发展结合在一起，如用于函数语言编译的Hindley-Milner类型检查的统一算法；编译器也已成为基于窗口的交互开发环境(IDE)的一部分；随着多处理机和并行技术、并行语言的发展，将串行程序转换成并行程序的自动并行编译技术正在深入研究之中；另外随着嵌入式应用的迅速增长，推动了交叉编译技术的发展；对系统芯片设计方法和关键EDA技术的研究，也带动了专用语言VHDL等及其编译技术的不断深化。根据不同的用途和侧重，编译程序可分为很多类。专门用于帮助程序开发和调试的编译程序称为诊断编译程序（Diagnostic
8、 Complier）。着重于提高目标代码效率的编译程序叫优化编译程序（Optimizing Complier）。运行编译程序的计算机称为宿主机，运行编译程序所产生的目标代码的计算机称目标机。如果一个编译程序产生不同于其宿主机的机器代码，称为交叉编译程序（Cross Complier）。如果不需重写编译程序中与机器无关的部分就能改变目标机，则称该编译程序为可变目标编译程序（Retargetable Complier）。编译程序的重要性在于它使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员独立于机器硬件。除编译程序外，还需要其他一些程序才能生成在计算机上执行的目标程序。预处理程序是指，当源
9、程序以几个模块的形式存放在不同的文件中，将这些源程序汇集在一起的程序。预处理程序也能够把源程序中称为宏的缩写语句展开为原始语句加入到源程序中。源程序由编译程序编译后生成目标程序，图中的目标代码是汇编代码，需要经过汇编程序汇编转换为可装配的机器代码。再经装配连接程序连接成真正能在机器上运行的代码。装配连接程序是指，将可再装配的机器代码进行装配连接形成绝对机器代码的程序。3 编译过程和编译程序的结构 编译过程概述编译程序完成从源程序到目标程序的翻译工作，这是一个复杂的过程。整个工作过程需要分阶段完成，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。
10、根据各个阶段的复杂程度、理论基础和实现方法的不同，一般将编译程序的工作过程划分为词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成五个阶段。词法分析每种高级语言都规定了允许使用的字符集，如字母AZ，az，数字09，、*、/等。高级语言的单词符号都由定义在各语言的字符集上的这些符号构成，有的单词由一个符号组成，如，*，/等，有的单词由两个或多个符号组成，如=、end等，它们都是语言的最基本的组成成分。在多数程序设计语言中，单词一般分为5类：保留字（begin、end、if、for、while等）、标识符、常数、运算符和分界符（标点符号、括号、注释符号等）。词法分析是编译的第一个阶
11、段，其任务是从左至右逐个字符的对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成单词符号串形式的中间程序。在词法分析过程中，还要对源程序做一些简单处理，如滤掉空格、去掉注释、报告错误等。有的扫描器要求将识别出来的名字填入符号表，以备后续阶段使用。词法分析的工作主要依据语言的构词规则，描述构词规则的有效工具是正规式和有限自动机。语法分析语法分析是编译过程的核心部分，其基本任务是根据语言的语法规则进行语法分析，若不存在语法错误则给出正确的语法结构并为语义分析和代码生成做准备。完成语法分析任务的程序称为语法分析程序（parser）。如上述输入串中的单词序列id1:=int1 + id2
12、 * id3 + id2 * id3经过语法分析后可以确定它是一个赋值语句，可以表示为图2所示的语法树。图2 语句id1:=int1 + id2 * id3 + id2 * id3的语法树语法分析所依据的是语言的语法规则，语言的语法规则通常是由递归规则来定义，如上述例子中表达式和赋值语句可由下述递归规则来定义：(1) 任何标识符是表达式；(2) 任何常数是表达式；(3) 若表达式1和表达式2都是表达式，则表达式1+表达式2，表达式1*表达式2都是表达式；(4) 赋值语句就可以用规则：标识符 := 表达式；来定义。图1-2的语法树就是根据赋值语句和表达式的递归定义规则生成的。这种用递归规则表示语
13、法规则的工具称为上下文无关文法，用下推自动机实现。推倒（derive）和归约（reduce）。推倒又分为最左推倒和最右推倒。例如：x=a+b*50;对该赋值语句进行：最右推倒，最左归约（根据文法要求，由文法的初始符号最终能够推出我们要证明的语句，且在最右推倒过程中，每次替换掉的都是产生式最右边的非终结符（大写符号）。若能推倒，则是正确地语句。AVEVETVETF VETC VET50 VEF50 VEV50 VEb50 VTb50 VFb50 VVb50 Vab50（V为最终结符） xab50若将上式从右向左证明是一个赋值语句，最右推倒的反相推倒，这种方法就是最左归约（归约也分为最右归约和最左
14、归约）。推倒和归约的关系互为逆过程。例如：x=a+b*50;对该赋值语句进行：最左推倒，最右归约AVExExETxTTxFTxVTxaTxaTFxaFFxaVFxabFxabCxab50（在最右推倒过程中，每次替换掉的都是产生式最右边的非终结符。这里只做了最右推倒。若将上面的式子，从右向左替换，即为最左归约）。在描述程序语言的语法结构时，需要借助于上下文无关文法，而文法是描述程序语言的依据。语法分析的方法通常分为两类，即自上而下分析方法和自下而上分析方法。所谓的自上而下分析方法，就是从文法的开始符号出发，根据文法的规则进行推导，最终推导出给定的句子来。包括递归下降分析法和LL(1)分析法。递归
15、下降分析法是一种自上而下的分析方法，文法的每个非终结符对应一个递归过程。分析过程就是从文法开始符出发执行一组递归过程，这样向下推导直到推出句子；或者说从根结点出发，自上而下为输入串寻找一个最左匹配序列，建立一棵语法树。LL(1)分析法又称预测分析法，是一种不带回溯的非递归自上而下分析法。LL(1)分析法基本思想：自左向右扫描分析输入符号串从识别符号开始生成句子的最左推导 LL(1):向前看一个输入符号，便能唯一确定产生式 LL(k):向前看k个输入符号，才能唯一确定产生式自下而上分析法则是从给定的输入串开始，根据文法规则逐步进行归约，直至归约到文法的开始符号为止。自下而上分析原理是从输入符号串开始，通过重复查找当前句型的“可归约串”并利用有关规则进行规约若能规约为文法的识别符号,则表示分析成功,输入符号串是文法的合法句子,否则有语法错误.算符优先分析法是一种简单且直观的自上而下分析方法，它适合于程序语言中各类表达式的分析，并且宜于手工实现。所谓算符优先分析，就是依照算术表达式的四则运算过程来进行语法分析，即这种分析方法要预先规定运算符(确切地说是终结符)之间的优先关系和结合性质，然后借助于这种关系来比较相邻运算符的优先级，以确定句型的“可归约串”来进行归约。因此，算符优先分析法不是一种规范归约，
