南航复试笔试真题资料 编译课件 第一章 概论

1、编译原理,计算机与信息工程学院 软件工程教研室 何岸,第一章 引论 2,本课程的地位,是软件技术基础 是计算机专业的学生必修的一门主干专业课,第一章 引论 3,学习要求,成绩考核方法 平时成绩占30% 期末考试成绩占70%。 平时成绩为： 课堂点名15% 作业15% 我的联系方式： E-Mail：,第一章 引论 4,第一章 引论1.1程序设计语言,1)程序设计语言 高级语言 汇编语言 机器语言 在计算机上如何执行一个高级语言程序？ 把高级语言程序翻译成机器语言程序 运行所得的机器语言程序求得计算结果,第一章 引论 5,程 序 设 计 语 言,机器语言,机器指令（0，1）,汇编语言,机器指令（符

2、号）,高级语言,Pascal、 c 、c+,002 0123 取出a 00E 1234 除以b 009 2103 减去c 004 0576 送c,CLA a 取出a DIV b 除以b SUB c 减去c STO c 送c,X=a/b-c,什么叫编译程序,高级程序设计语言,机器语言,目标程序,源程序,编译程序,编译程序：将高级语言程序根据其语法和语义翻译成与之等价的机器能够接受的机器语言程序的程序。 编译技术：介绍如何设计和构造编译程序，也即讨论编译程序构造的一般方法技术等。 编译原理：是讨论编译程序设计的基本理论、基本概念、基本方法。,第一章 引论 6,翻译程序 汇编程序：源语言为汇编语言，

3、目标语言为 机器语言 编译程序：源语言为高级语言，目标语言为 sx 某台计算机上的汇编语言或机器语言 解释程序：能够按源程序的动态顺序逐句进行分 d 析解释，根据语句功能翻译成与该语 d 句相应的机器指令序列，并立即执 s 行，直至结束,1.2 编译程序,翻 译 程 序,第一章 引论 7,1.3 源程序执行的途径（编译途径、解释途径）,编译的转换过程 两阶段转换：编译运行,编译途径即是将一份源程序从头至尾翻译成某台计算机上的机器语言表示的目标程序，然后执行该目标程序得到运行结果，并允许重复执行若干次。,第一章 引论 8,编译的转换过程 三个阶段的转换：编译汇编运行,1.3 源程序执行的途径（编

4、译途径、解释途径）,第一章 引论 9,1.3 源程序执行的途径（编译途径、解释途径）,解释途径即是对于源程序的一个语句，把它翻译成相应的机器语言，并让计算机立即执行。如果需要数据时，则提示用户输入初始数据，并立即进行处理。解释途径就是边解释边执行，直至源程序动态处理完毕为止。 当用高级语言编写的源程序输入计算机后，键入运行程序命令，则解释程序就对源程序逐条翻译，翻译一条立即执行一条。该途径不产生目标代码程序，故占用内存较少，但执行速度要慢些。,第一章 引论 10,1.4 编译程序的结构,编译程序的工作 先看自然语言的翻译 1.识别出句子中的一个个单词 2.分析句子的语法结构 3.根据句子的含义

5、进行初步翻译 4.对译文进行修饰 5.写出最后译文,第一章 引论 11,编译程序的工作,词法分析器,语法分析器,语义分析器,中间代码生成,优化,目标代码生成,源程序,目标代码,表格管理,出错处理,第一章 引论 12,1.词法分析,任务 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词极其有关属性，并转换成属性字。 单词 是高级语言中有实在意义的最小语法单位，它由字符构成。 属性字 指单词的一种机内表示,第一章 引论 13,识别右边程序中的单词,基本字： 标识符 常数 : 运算符 : 界限符:,Void jisuan() float r, s,c; s=3.14*r*r; c=

6、2*3.14*r; ,Void , float,r, s, c, jisuan,3.14 ， 2,*,=, ; , ( ),第一章 引论 14,2.语法分析,任务： 在词法分析的基础上，根据语言的语法规则，逐一分析词法分析时得到的属性字，检查语法错误，若没有错误，则给出正确的语法结构（如短语、子句、句子、程序段、程序等）。 语法规则： 语言的规则，又称为文法；规定单词如何构成短语、语句、过程和程序。,c=2*3.14*r,赋值语句,第一章 引论 15,3.语义分析,任务 对语法分析识别出的各类语法范畴，分析其含义，进行和初步翻译，产生介于源代码和目标代码之间的一种代码。 分为两阶段工作 对每种

7、语法范畴进行静态语义检查 若语义正确，就进行中间代码的翻译 中间代码形式 四元式、三元式、逆波兰式,第一章 引论 16,“翻译”工作仅仅在这里才开始涉及到。,“中间代码”是一种结构简单、含义明确的记号 系统。这种记号系统或者与现代计算机的指令形式 有某种程度的接近，或者能够比较容易地把它变换 成现代计算机的机器指令。,常用的中间代码如：三元式、四元式、逆波兰式,第一章 引论 17,例如,x = 2 * a + b,三元式 (*,2,a) (2) (+,(1),b) (3) (=,(2),x),四元式 (*,2,a,t1) (2) (+,t1,b,t2) (3) (=,t2,/,x),依循规则：

8、语义规则,第一章 引论 18,如上述源程序经语义分析得到下列中间代码程序,Void jisuan() float r, s,c; s=3.14*r*r; c=2*3.14*r; ,（1） （*，3.14，r） （2） （*，（1），r） （3） （：=，（2），s） （4） （*，2，3.14） （5） （*，（4），r） （6） （：=，（5），c）,第一章 引论 19,如上述源程序经代码优化得到下列中间代码程序,Void jisuan() float r, s,c; s=3.14*r*r; c=2*3.14*r; ,（1） （*，3.14，r） （2） （*，（1），r） （3） （：=，

9、（2），s） （4） （*，2，（1） （5） （ ：=， （4），c）,（1） （*，3.14，r） （2） （*，（1），r） （3） （：=，（2），s） （4） （*，2，3.14） （5） （*，（4），r） （6） （：=，（5），c）,第一章 引论 20,4.优化,任务 对前面产生的中间代码进行加工变换，以期在最后阶段能产生更为高效的目标代码。 原则：等价变换 主要方面 公共子表达式的提取、合并已知量、删除无用语句、循环优化等。,第一章 引论 21,5.目标代码生成,任务 把经过优化的中间代码转化成特定机器上的低级语言代码 目标代码的形式 绝对指令代码:可立即执行的目标代码。 汇

10、编指令代码：汇编语言程序，需要通过汇编程序汇编后才能运行。 可重定位指令代码：先将各目标模块连接起来，确定变量、常数在主存中的位置，装入主存后才能成为可以运行的绝对指令代码。,第一章 引论 22,编译程序的工作,词法分析器,语法分析器,语义分析器,中间代码生成,优化,目标代码生成,源程序,目标代码,表格管理,出错处理,第一章 引论 23,6.表格与表格管理,表格作用： 用来记录源程序的各种信息以及编译过程中的各种状况。 与编译前三阶段有关的表格有： 符号表、常数表、标号表、分程序入口表、中间代码表等。,第一章 引论 24,1）符号表,符号表：用来登记源程序中的常量名、变量名、数组名、过程名等，

11、记录它们的性质、定义和引用情况。,第一章 引论 25,2）常数表与标号表,常数表,（登记各类常量值） （登记标号的定义与应用）,标号表,第一章 引论 26,3）入口名表,作用：登记过程的层号，分程序符号表入口等,第一章 引论 27,4）中间代码表,第一章 引论 28,7.出错处理,任务 如果源程序有错误，编译程序应设法发现错误，并报告给用户。 完成：由专门的出错处理程序来完成 错误类型: 语法错误:在词法分析和语法分析阶段检测出来。 语义错误：一般在语义分析阶段检测。,第一章 引论 29,8、编译程序的趟 趟 指一个编译程序在编译时把源程序或与之等价的中间程序从头到尾扫描一遍，并转换成为紧密相

12、邻的等价的程序的全过程。 单趟扫描：五个阶段结合在一起对源程序从头到尾 扫描一遍生成目标程序。 优点：速度快、效率高 缺点：编译程序复杂、占用存储空间大 多趟扫描：五个阶段单独成趟扫描。 优点：编译程序简单且易于分工。 缺点：各趟的工作有些要重复进行、效率较低,第一章 引论 30,语法分析,扫描器,语义子程序,源程序,目标代码,编译程序,取单词,类号内码,一遍扫描（以语法分析为中心）,归约,返回,第一章 引论 31,1.5 编译程序构造,要在某机器上为某种语言构造一个编译程序，必须掌握下面的内容： ： 1、源语言：语法、语义。 2、目标语言：对于机器指令，搞清硬件的系统结构和OS的功能。 3、编译方法：必须掌握一二种。 4、语言选择：编制程序。,第一章 引论 32,编译程序的设计与实现还要根据环境的不同可能有各种不同目标，例如： 目标程序效率高 目标程序短 编译的时间短