编译原理第一章编译引论

编译原理第一章编译引论2一什么是编译程序？计算机经过几十年的发展，在程序设计语言方面,已经从低级语言发展到高级语言;然而,计算机内部的本质只能识别0,1代码序列（机器语言）,而对高级语言甚至符号语言仍然一窍不通。因此用高级语言编写的程序,必须先翻译为机器语言，才能被计算机理解执行。第一个完成这种翻译任务的编译程序为FORTRAN编译程序,是上世纪五十年代设计的.第一章引论第一节、编译程序概述3定义:设源语言为L1,目标语言为L2,

翻译程序是一个程序,它能将L1转换为逻辑上等价的L2。

若L1为高级语言，L2为低级语言或机器语言，称这种翻译程序为编译程序。若L1为低级语言，L2为机器语言，称这种翻译程序为汇编程序。解释程序是指逐条翻译L1的语句，并立即执行翻译出的目标代码序列。

编译原理

就是介绍编译程序的一般规律及设计方法的一门课程。高级语言程序机器语言程序翻译为4二编译过程概述

编译程序从接受源程序到输出目标代码的整个过程，可逻辑的分为5个阶段，词法分析语法分析中间代码生成代码优化目标代码生成1）词法分析：把源程序作为字符串进行扫描，根据单词词法，识别出所有单词，过滤无用符，并检查是否为合法的单词。单词一般分为如下几种：基本字，标识符，常数，算符，界符5例如：ifn<=1thenf:=1elsef:=n*f(n);

该程序经过语法分析,得到如下单词序列:ifn<=1thenf:=1elsef:=n*f(n);过滤掉回车换行,空格,注释等62)语法分析:根据语言的语法规则,从单词符号串中识别出各种语法单位,进行句子分析,并检查整个输入字串是否为合法的程序;重要的语法单位有:程序,子程序,语句,短语,表达式等例如:programadd;vara,b:real;beginread(a,b);write(a+b);end.7程序首部说明段执行部program程序名及参数var说明语句add变量名表变量类型a,brealbegin多语句endread(a,b)write(a+b)83)中间代码生成:根据语义规则,把各种语法单位翻译成中间代码序列.中间代码有三种:四元式,三元式,逆波兰式.中间代码的特点:结构简单,语义明确,易于理解及优化.四元式可表示为:(操作符,操作数1,操作数2,结果)例如:语句

Z:=(x+0.4)*Y/W;翻译后得到右面的四元式序列:四元式序列(+,x,0.4,T1)(*,T1,Y,T2)(/,T2,w,T3)(:=,T3,,Z)从示例可看出:每条四元式只进行一次最基本的操作.94)代码优化：对产生的中间代码序列进行加工变换，使变换后的代码更为高效（时间，空间上）。优化主要有：循环优化，公共表达式提取，强度削弱等。5)目标代码生成：把中间代码程序翻译为机器指令或汇编指令程序。这一部分的处理，与计算机硬件及操作系统密切相关。如寄存器数目，机器指令功能及指令条数；操作系统的

BIOS，内存管理，文件管理等。三编译程序的结构

编译程序可以划分为如下几个基本模块：10词法分析器语法分析器中间代码生成中间代码优化目标代码生成源程序单词符号语法单位四元式四元式目标程序

表格管理

错误处理编译程序总框11表格管理:对各种表格进行管理,包括表格的构造、查找、修改、删除、插入等；编译程序中，表格的种类较多，最主要的有如下几种：符号表，常量表，标号表，子程序名表，四元式表等。表格由若干结构相同的表格项组成，表格项由二元式表示：项名信息表格项表格项名1信息项名2信息项名n信息12四设计编译程序

编译程序的设计方式可以分为两类：方式人工设计自动生成低级语言高级语言自动生成扫描器自动生成分析器自动生成编译程序13第二节、高级语言概述一什么是程序设计语言程序设计语言是一符号系统，由语法和语义两方面所定义。语法：是一组规则，规定了语言的形式结构，包括单词结构，句子结构，程序结构等。语法={词法规则+句法规则} 词法规则：规定了形成单词的规则；如常数，标识符，基本字，算符等。 句法规则：规定了由单词构造更大语法单位的规则；

如表达式，短语，语句，程序等。14语义：也是一组规则，规定了各语法单位的确切含义。例如：A=B，可解释为：A赋值为B；（C语言）

也可以解释为：A等于B（P语言）

这完全由语义规则所确定。二数据类型

各种语言都提供了一些最基本的数据类型,称为初等数据类型，这些数据类型的特征是数据的单一性；还提供了由初等数据类型构造复杂结构类型的手段。1）初等数据类型数值类型：（整数，实数）可进行算术运算和比较运算；逻辑类型：可进行逻辑运算；字符类型：可进行比较远算及字符串操作；指针类型：指向另一变量的地址。152）结构类型-------数组

数组是由同一类型数据所组成的多维结构，数组元素是多维空间的一个点，代表了一个存储空间。数组的存储，是通过按行或按列方式，把每个数组元素存放在一个连续的存储空间中。设数组类型为A:array[L1..u1,L2..u2,......Ln..

un]ofelemtype,数组元素为A[i1,i2,......in],di=ui-Li+1则该元素的地址可按如下公式计算:

addr=a+{(i1-L1)*d2d3d4...dn

+

(i2-L2)*d3d4...dn

+

(in-1-Ln-1)*dn

+(in-Ln)}*elemlength16addr=a-c+vc={(L1)*d2d3d4...dn

+

(L2)*d3d4...dn+

(Ln-1)*dn

+(Ln)}*elemlength={(...((L1d2+L2)d3+L3)d4+L4)......)dn+Ln}*elemlengthv={(...((i1d2+i2)d3+i3)d4+i4)......)dn+in}*elemlengthC是常量,在编译时可以计算出;V是可变部分,只能在程序运行时才能计算出。从上可知：计算数组元素地址涉及到如下几个因素：

acL1..Lnd1..dnelemlengthi1..in

17这些因素中,在编译时能确定的部分,用一个数组内情向量表来记录,以便计算数组元素地址使用。换句话说：当编译程序扫描到数组说明语句时，就把数组的各确定部分登记到内情向量表中。内情向量表组织如下：L1u1d1L2u2d2Ln

un

dnac

n

elemlength

183）结构类型-------记录是由多种类型的数据组合起来的一种数据结构。Pascal语言中，可如下定义一种记录类型

type<记录类型名>=record <域名1>:<类型1>; <域名2>:<类型2>;<域名n>:<类型n>;

end;

域名即记录分量,域的类型可以是简单数据类型,也可以是已经定义过的数据类型。可采用分量顺序方式,分配记录的地址空间。由于每个域类型及空间大小都可能不同,因此,只能通过表映射方式计算各个域在记录中的地址。19记录分量表：域名相对位移域类型name1offset1type1name2offset2type2

namenoffsetntypen因此，namei

在记录中的地址为：addr=a+offsetia为记录的第一个分量的地址；20三表达式表达式是由算符和运算量组成,可递规定义如下:1>变量,常量,函数为表达式E;2>若E1,E2为表达式,则:

E1opE2,opE,(E)为表达式。

算符间存在如下优先顺序：

乘幂（**）负号（—）乘除（*/） 加减（+-） 关系符（<>=<>>=<=)非(not)

与(and)

或(or)等优先级高优先级低21四语句语句可以分为两类:说明性语句 执行性语句

说明语句用于定义各种数据类型,变量,函数或过程.执行语句用于描述数据处理的过程和动作.1>类型定义段

type<类型名>=setof<基类型>;<类型名>=arrayof<基类型>;<类型名>=record

end;222>变量说明段var<变量名表1>:<类型1>; <变量名表2>:<类型2>; <变量名表n>:<类型n>;3>函数及过程定义

function<函数名>(参数说明):<函数类型>;<函数体>;

procedure<过程名>(参数说明);<过程体>;4>赋值句<V>:=<

E>;

左边变量取其地址,右边表达式取其值.235>分支语句

if<B>then<S> else<S>;case<有序表达式>of<值1>:<S1>;

<值n>:<Sn

>else:<Sn+1>

end;goto<标号>;246>循环控制语句

while<B>do<S>;for<V>:=<E1>to<E2>do<S>;repeat<S1>;<S2>;......<Sn>until<B>7>

子程序调用函数调用一般出现在表达式中,形式如下:<函数名>(实际参数)过程调用一般作为语句,形式如下:<过程名>(实际参数);258>输入输出语句

read(<变量名表>);

write(<输出元表>);9>简单句和复合句简单句是指不包含其它语句的基本语句,复合句是指句中有句.例如:V:=E,gotoL,read(a,b)等都是简单句;

ifBthenSelseS,whileBdoS等都是复合句.26五子程序参数传递当调用一个子程序时,首先应将所需的数据传递给子程序,传递方式主要有三种:传值,传地址,传名设有如下函数:

functiondistence(x1,y1,x2,y2):real;begindistence:=sqrt((x2-x1)**2+(y2-y1)**2)end;x1,y1,x2,y2称为形式参数设主程序调用如下:

d=distence(a1,b1,a2,b2);a1,b1,a2,b2称为实际参数.2