资源描述
此处编辑母版单击标题样式,母版单击此处编辑文本样式产,*,*,此处编辑母版单击标题样式,母版单击此处编辑文本样式产,1,编译原理,2,一 什么是编译程序？,计算机经过几十年的发展，在程序设计语言方面,已经从低级语言发展到高级语言;然而,计算机内部的本质只能识别 0,1 代码序列（机器语言）,而对高级语言甚至符号语言仍然一窍不通。因此用高级语言编写的程序,必须先翻译为机器语言，才能被计算机理解执行。第一个完成这种翻译任务的编译程序,为,FORTRAN,编译程序,是上世纪五十年代设计的.,第一章 引论,第一节、编译程序概述,3,定义:设源语言为,L1,目标语言为,L2,翻译程序,是一个程序,它能将,L1,转换为逻辑上等价的,L2。,若,L1,为高级语言，,L2,为低级语言或机器语言，称这种,翻译程序为,编译程序,。,若,L1,为低级语言，,L2,为机器语言，称这种翻译程序为,汇编程序。,解释程序,是指逐条翻译,L1,的语句，并立即执行翻译出的,目标代码序列。,编译原理,就是介绍编译程序的一般规律及设计方法的一门课程。,高级语言程序,机器语言程序,翻译为,4,二 编译过程概述,编译程序从接受源程序到输出目标代码的整个过程，可逻辑的分为 5 个阶段，,词 法 分 析,语 法 分 析,中间代码生成,代 码 优 化,目标代码生成,1）词法分析：把源程序作为字符串进行扫描，根据单词词法，识别出所有单词，过滤无用符，并检查是否为合法的单词。,单词一般分为如下几种：,基本字，标识符，常数，算符，界符,5,例如：,if n=1 then f:=1,else f:=n*f(n);,该程序经过语法分析,得到如下单词序列:,if,n,=,1,then,f,:=,1,else,f,:=,n,*,f,(,n,),;,过滤掉回车换行,空格,注释等,6,2)语法分析:根据语言的语法规则,从单词符号串中识别出各种语法单位,进行句子分析,并检查整个输入字串是否为合法的程序;,重要的语法单位有:,程序,子程序,语句,短语,表达式等,例如:,program add;,var a,b:real;,begin,read(a,b);,write(a+b);,end.,7,程序,首部,说明段,执行部,program,程序名及参数,var,说明语句,add,变量名表,变量类型,a,b,real,begin,多语句,end,read(a,b),write(a+b),8,3)中间代码生成:根据语义规则,把各种语法单位翻译成中间代码序列.,中间代码有三种:,四元式,三元式,逆波兰式,.,中间代码的特点:结构简单,语义明确,易于理解及优化.,四元式可表示为:,(操作符,操作数1,操作数2,结果),例如:语句,Z:=(x+0.4)*Y/W;,翻译后得到右面,的四元式序列:,四元式序列,(+,x,0.4,T1),(*,T1,Y,T2),(/,T2,w,T3),(:=,T3,Z),从示例可看出:每条四元式只进行一次最基本的操作.,9,4)代码优化：对产生的中间代码序列进行加工变换，使变换后的代码更为高效（时间，空间上）。,优化主要有：,循环优化，公共表达式提取，强度削弱等。,5)目标代码生成：把中间代码程序翻译为机器指令或汇编指令程序。,这一部分的处理，与计算机硬件及操作系统密切相关。,如寄存器数目，机器指令功能及指令条数；操作系统的,BIOS，,内存管理，文件管理等。,三 编译程序的结构,编译程序可以划分为如下几个基本模块：,10,词法分析器,语法分析器,中间代码生成,中间代码优化,目标代码生成,源程序,单词符号,语法单位,四元式,四元式,目标程序,表,格,管,理,错误处理,编译程序总框,11,表格管理:对各种表格进行管理,包括表格的构造、查找、修改、,删除、插入,等；,编译程序中，表格的种类较多，最主要的有如下几种：,符号表，常量表，标号表，子程序名表，四元式表等,。,表格由若干结构相同的表格项组成，表格项由二元式表示：,项名 信息,表格项,表格,项名 1 信息,项名 2 信息,项名,n,信息,12,四 设计编译程序,编译程序的设计方式可以分为两类：,方式,人工设计,自动生成,低级语言,高级语言,自动生成扫描器,自动生成分析器,自动生成编译程序,13,第二节、高级语言概述,一 什么是程序设计语言,程序设计语言是一符号系统，由,语法,和,语义,两方面所定义。,语法：,是一组规则，规定了语言的形式结构，包括单词结构，,句子结构，程序结构等。,语法=,词法规则+句法规则,词法规则,：规定了形成单词的规则；如常数，标识符，,基本字，算符等。,句法规则,：规定了由单词构造更大语法单位的规则；,如表达式，短语，语句，程序等。,14,语义：,也是一组规则，规定了各语法单位的确切含义。,例如：,A=B，,可解释为：,A,赋值为,B；（C,语言）,也可以解释为：,A,等于,B （P,语言）,这完全由语义规则所确定。,二 数据类型,各种语言都提供了一些最基本的数据类型,称为初等数据类型，这些数据类型的特征是数据的单一性；还提供了由初等数据类型构造复杂结构类型的手段。,1）初等数据类型,数值类型：（整数，实数）可进行算术运算和比较运算；,逻辑类型：可进行逻辑运算；,字符类型：可进行比较远算及字符串操作；,指针类型：指向另一变量的地址。,15,2）结构类型-数组,数组是由同一类型数据所组成的多维结构，数组元素是多维空间的一个点，代表了一个存储空间。数组的存储，是通过按行或按列方式，把每个数组元素存放在一个连续的存储空间中。,设数组类型为,A:array,L,1,.u,1,L,2,.u,2,.L,n,.,u,n,of elemtype,数组元素为,Ai,1,i,2,.i,n,d,i,=u,i,-L,i,+1,则该元素的地址可按如下公式计算:,addr=a +(i,1,-L,1,)*d,2,d,3,d,4,.d,n,+,(i,2,-L,2,)*d,3,d,4,.d,n,+,(i,n-1,-L,n-1,)*d,n,+(i,n,-L,n,)*elemlength,16,addr=a-c+v,c,=(L,1,)*d,2,d,3,d,4,.d,n,+,(L,2,)*d,3,d,4,.d,n,+,(L,n-1,)*d,n,+(L,n,)*elemlength,=(.(L,1,d,2,+L,2,)d,3,+L,3,)d,4,+L,4,).)d,n,+L,n,*elemlength,v,=(.(i,1,d,2,+i,2,)d,3,+i,3,)d,4,+i,4,).)d,n,+i,n,*elemlength,C,是常量,在编译时可以计算出;,V,是可变部分,只能在程序运行时才能计算出。,从上可知：计算数组元素地址涉及到如下几个因素：,a c L,1,.L,n,d,1,.d,n,elemlength i,1,.i,n,17,这些因素中,在编译时能确定的部分,用一个数组,内情向量表,来记录,以便计算数组元素地址使用。换句话说：当编译程序扫描到数组说明语句时，就把数组的各确定部分登记到内情向量表中。,内情向量表组织如下：,L,1,u,1,d,1,L,2,u,2,d,2,L,n,u,n,d,n,a,c,n,elemlength,18,3）结构类型-记录,是由多种类型的数据组合起来的一种数据结构。,Pascal,语言中，可如下定义一种记录类型,type =,record,:;,:;,:;,end;,域名即记录分量,域的类型可以是简单数据类型,也可以是已经定义过的数据类型。,可采用分量顺序方式,分配记录的地址空间。由于每个域类型及空间大小都可能不同,因此,只能通过表映射方式计算各个域在记录中的地址。,19,记录分量表：,域名 相对位移 域类型,name1 offset1 type1,name2 offset2 type2,name,n,offset,n,type,n,因此，,name,i,在记录中的地址为：,addr=a+offset,i,a,为记录的第一个分量的地址；,20,三 表达式,表达式是由算符和运算量组成,可递规定义如下:,1 变量,常量,函数为表达式,E;,2 若,E,1,E,2,为表达式,则:,E,1,op E,2,op E,(E),为表达式。,算符间存在如下优先顺序：,乘幂（*）,负号（）,乘除（*/）,加减（+-）,关系符（=类型定义段,type =,set of,;,=,array of,;,=,record,end,;,22,2 变量说明段,var,:;,:;,:;,3 函数及过程定义,function,(参数说明):;,;,procedure,(参数说明);,;,4 赋值句,:=,;,左边变量取其地址,右边表达式取其值.,23,5 分支语句,if,then,else,;,case,of,:,;,:,else,:,end;,goto,;,24,6 循环控制语句,while,do,;,for,:=,to,do,;,repeat,;.,until,7,子程序调用,函数调用一般出现在表达式中,形式如下:,(实际参数),过程调用一般作为语句,形式如下:,(实际参数);,25,8 输入输出语句,read,();,write,();,9,简单句和复合句,简单句,是指不包含其它语句的基本语句,复合句,是指句中有句,.,例如:,V:=E,goto L,read(a,b),等都是简单句;,if B then S else S,while B do S,等都是复合句.,26,五 子程序参数传递,当调用一个子程序时,首先应将所需的数据传递给子程序,传递方式主要有三种:,传值,传地址,传名,设有如下函数:,function distence(x1,y1,x2,y2):real;,begin,distence:=sqrt(x2-x1)*2+(y2-y1)*2),end;,x1,y1,x2,y2,称为形式参数,设主程序调用如下:,d=distence(a1,b1,a2,b2);,a1,b1,a2,b2,称为实际参数.,27,1传值,调用程序把实际参数的,值,传递到形式参数的空间中.,1,1,4,5,x1,y1,x2,y2,1,1,4,5,a1,b1,a2,b2,主程序空间,子程序空间,这种方式,子程序一般不改变实际参数的值,.,28,2传地址,调用程序把实际参数的,地址,传递到形式参数的空间中.,addr(a1),addr(b1),addr(a2),addr(b2),x1,y1,x2,y2,1,1,4,5,a1,b1,a2,b2,主程序空间,子程序空间,这种方式,子程序间接访问主程序实际参数的值,改变了实际参数的值,.,29,3传名,传名是一种,宏替换,直接在调用处产生一个子程序副本,并且,用实际参数名替代形式参数名.,设主程序调用如下:,d:=distence(a1,b1,a2,b2);,相当于在此处产生一段程序:,d:=sqrt(a2-a1)*2+(b2-b1)*2);,30,六 存储分配,程序运行时,必须分配相应的存储空间.这些空间包括:,变量空间,常量空间,临时空间,连接单元,等.有的空间在编译时就能确定其大小,而有的空间必须在程序运行时才能确定.根据这一特性,把空间分配分为两种:,静态存储分配,动态存储分配,1 静态存储分配,若在编译时能完全确定程序所需空间大小,并能确定每个数据项的地址,就可在编译时分配所需空间,这种分配方法称为静态存储分配.,若一个语言无递归调用,无可变数据项,则可静态地确定各数据项的空间大小和地址.,Fortran,语言满足这种定义.,31,2 动态存储分配,是指在程序运行时才能确定存储空间和地址的一种分配方法.适用于允许递归和可变数据项的语言,如,pascal,和,c,语言.,一般采用堆栈动态地分配空间,当调用子程序时,就在堆栈中为该子程序分配所需空间;而子程序运行结束后,就释放该子程序空间.,子程序空间,编译时可确定(活动记录),运行时可确定(可变空间),活动记录,连接数据,形式参数,局部变量,
展开阅读全文