《编译程序概述》PPT课件.ppt

1、编译原理,信息工程系 王养廷,计算机学院,教学要求,1.上课时做笔记 2.每班选一位课代表 ,负责收作业，联系，准备记分册（标上班长、学委电话） 3.有问题及时向老师反馈 4.课堂纪律（上课不允许说话、上机不允许玩游戏,手机打成震动）,辅导答疑,辅导答疑： 时间：每周周三11、12节，课前后 地点：博观楼209 可以另约时间答疑 联系方式： TelEmail： QQ：1458920766,个人建议,培养正思维 思维模式=行为模式=最终结果 目标为了个人进步 培养良好学习习惯 多讨论怎样做好，不讨论为什么没做好 树立目标 目标=价值 专业学习目标,主要内容,引入 编译程

2、序与解释程序 编译程序的功能分解与组织结构 编译程序的复杂性 编译程序的设计与实现 编译程序的测试与维护 几个经典的编译程序,1 引入,计算机科学与技术 编译原理课程 编译原理主要内容 选用教材 为什么要学习编译原理 需要注意的问题,1.1 计算机科学与技术,含义 科学：构成计算基础的基本概念和模型（又称为：形式理论） 技术：设计计算系统的工程和技术 形式理论 有限自动机、正则表达式、正则集合 上下文无关文法 下推机 图灵机 不可判定性 与编译原理的关系 形式理论是编译原理的理论基础 在后面我们要讲到前三个部分,1.2 编译原理课程,课程性质 学科基础课 先修课程 程序设计语言（Pascal、

3、C等） 程序设计、数据结构 离散数学 操作系统,1.3编译原理主要内容,按照编译程序的主要组成部分进行介绍 词法分析 语法分析 语义分析 代码生成和优化 符号表和错误处理 一个编译程序实例 PL/0编译程序分析,1.4 选用教材,教材 金成植：编译程序设计原理 编译程序 构造原理 实现技术 特点 采用原理与实例相结合的方法进行介绍 兼顾原理和实现技术,1.5 为什么要学习编译原理,编译程序是一个大型综合、复杂的程序，通过该课程的学习了解一个大型软件的设计与实现 有助于理解现有的编译程序的实现方法 加深对程序设计语言的理解 提高调试程序能力 为进一步深造打下基础,1.6 需要注意的问题,对课程的

4、难度应该有足够的思想准备 注意平时的听课和积累 原理侧重理解 具体的算法和程序需要实际动手分析,2 编译程序与解释程序,语言与程序设计语言 程序设计语言主要内容 程序设计语言分类 编译原理基本概念 编译程序与解释程序的异同 使用解释程序的情况,2.1 语言与程序设计语言,语言 人们用来交流的工具 程序设计语言 人与计算机交流的工具 二者的区别 对象 二义性,2.2 程序设计语言主要内容,数据定义 字符集、常量、类型、变量、表达式 语句 顺序、分支和循环 函数 过程、函数、子程序 复杂数据类型 数组、记录、指针等等,2.3 程序设计语言的分类,按照层次 高级语言 低级语言 按照结构 过程式语言（

5、C、Pascal） 函数式语言（LISP、ML） 逻辑式语言（Prolog） 对象式语言（SmallTalk 、Java 、C+）,2.4 编译程序基本概念,源程序：用程序设计语言编制的程序 目标程序：与源程序功能等价的目标代码 编译程序：把源程序转换成目标程序的程序 解释程序：执行源程序得到执行结果的程序 汇编程序：把汇编源程序转换成目标程序的程序,2.5 编译程序与解释程序区别,源程序,数据,源程序,解释程序,计算结果,编译程序,目标程序,2.6 使用解释程序的情况,不追求执行速度 有些程序允许执行式改变自身 人机对话的交互语言 由解释程序到编译程序的自动生成系统,3 编译程序的功能分解与

6、组织结构,功能结构图 遍的概念 源程序的处理过程,3.1 功能结构图,3.1 功能结构图（续）,编译程序的输入：源程序 编译程序的输出：目标程序 编译程序的功能模块 词法分析：把源程序变成单词串 语法分析：检察源程序是否符合语法结构 语义分析：标识符的含义是否正确 代码生成：生成目标代码,3.2 遍的概念,遍的概念 对源程序或与其等价的中间代码扫描一次 按遍划分 一遍 多遍 一遍特点 避免重复工作、速度快、代码质量不高 多遍特点 结构算法清晰、易于掌握、能够产生好的目标代码,3.3 源程序的处理过程,预处理器,编译程序,汇编程序,装配连接,扩展程序,源程序,目标汇编程序,可重定位机器代码,可执

7、行机器码,可重定位目标文件库,3.3 源程序的处理过程（续）,实例 以DOS下的C语言处理过程为例 C是多遍编译 第一遍处理包含、宏等信息 以后各遍进行编译 过程 第一遍编译得到标准C程序 经过C编译器的到目标程序 经过连接得到可执行程序 装入DOS执行,4 编译程序复杂性,元程序 处理程序的程序 编译程序复杂性 元级程序 高级语言与低级语言差别大 编译程序要求高,5 编译程序的设计与实现,设计编译程序条件 精通源语言 精通目标语言 精通编译技术 编译程序的性能 可靠性、速度、目标代码速度、占用空间、可移植性、可维护性、可扩展性,5 编译程序的设计与实现（续）,开发编译程序的途径 预处理法 移

8、植法 直接移植 交叉编译 自展法 工具法 例如：LEX、YACC 理论法,6 编译程序的测试和维护,编译程序测试 机械证明 测试 测试用例设计 编译程序维护 长期有效地改正发现的错误,7 几个经典的编译程序,Pascal编译程序 设计者：Wirth 使用技术：递归下降、一遍扫描、栈式抽象机 特点：产生P代码 C编译程序 设计者：D. M. Ritchie 使用技术：递归下降、二遍扫描、有可选的第三遍 特点：可移植性好 Fortran编译程序 设计者：Lowry和Medlock 使用技术：综合 特点：优化好,小结,内容 编译程序的基本概念和相关知识 编译程序的组成和复杂性 几个常见的编译程序 要

9、求 掌握编译程序的组成和复杂性 预习标准的Pascal语言 预习Turbo Pascal开发环境,PASCAL语言基础知识,任课教师 王养廷,复习,编译程序的主要组成部分，每个部分的功能 编译程序为什么复杂 预习标准的Pascal语言 预习Turbo Pascal开发环境,主要内容,Pascal概述 数据 语句,1 Pascal概述,Pascal历史 Wirth Pascal Pascal 语言最初由瑞士苏黎士理工学院的尼古拉斯-沃斯(Niklaus Wirth)教授在1971年设计, 作为Algol语言(1960年设计)简化本用于教学目的。 Turbo Pascal 1983年Borland

10、公司推出了世界闻名的Pascal编译器 - Turbo Pascal。由于既简洁功能又强，Turbo Pascal成为当时最畅销的编译器之一，而且在PC平台上非常流行。 Delphi中的Pascal 1995年Borland发布了Delphi ，使Pascal成为一种可视化编程语言。,1 Pascal概述（续）,一个Pascal程序实例 program circle(input,output); const pi=3.1416; var r,l,s:real; begin read(r); l:=2*pi*r; s:=pi*r*r; write(r,l,s) end.,2 数据,字符集 标识符

11、和保留字 常量 变量 运算符,2.1 字符集,Pascal字符集 字母 数字 其它符号 字符集的引申 多语言的处理（ASCII,UniCode）,2.2 标识符和保留字,标识符 定义：以字母开头，后面跟字母、数字组成的字符串。 作用：用来表示各种程序元素的名称 规定： 大小写不敏感 有效长度8，超过8个不起作用 建议： 采用一个或多个英文单词组成 举例 score、charPosition,2.2 表识符和保留字（续）,保留字 Pascal系统已经使用的单词 主要保留字 例如：program、begin、end、const、var、read、write、if、then、else等等 详细内容参

12、考Pascal教程 作用 用来标识程序的语法成分,2.2 表识符和保留字（续）,注释 注释的内容用 括起来 例子 this is a comment 这是一个例子,2.3 常量,常量 一般常量 程序中的数值 例如：23、-1.2、a 符号常量 定义：在const部分定义 格式：常量名=表达式 举例： const pi = 3.14； st = t；,2.4 变量,变量 定义：在var部分定义 格式：变量名表：类型； 说明： 类型名可以是任意Pascal类型 变量名表是多个变量，中间用逗号间隔 举例 var x,y:integer; flag:boolean;,2.4 变量（续）,类型主要有四个

13、： 整型 integer 描述一个整数类型 实型 real 描述一个实数类型 字符型 char 描述一个字符类型，值是一个字符 布尔型 boolean 描述一个逻辑类型，只有两个：true和false。,2.5 运算符,算术运算符 关系运算符 逻辑运算符 运算符优先级,2.5 运算符（续）,算术运算符 +、-、*、/、mod、div 说明 用于算术运算 +、-、*整数、实数运算符 mod、div整数运算符 /实数运算符 举例 m:= n mod 10; x:= y+100;,2.5 运算符（续）,关系运算符 用于关系表达式 符号：、=、 举例 X+10 y X=1,2.5 运算符（续）,逻辑运

14、算符 运算符 not、and、or 真值表,2.5 运算符（续）,运算符优先级 两个运算符相邻，先参加高优先级运算 同级运算符自左至右 有扩号先计算括号内,3 语句,程序结构 语句 声明语句 简单语句 分支语句 循环语句,3.1 程序结构,程序结构 程序首部 声明部分 语句部分 举例,3.1 程序结构（续）,program pl0(input,output); const norw = 11; no. of reserved words type symset = set of symbol; var ch: char; last character read procedure error(

15、n: integer); begin writeln( *, : cc-1, ,n: 2); err := err+1 end error; begin main program for ch := chr(0) to chr(255) do ssymch := nul; getsym; end.,3.2 语句,语句： 数据类型是Pascal 编程的一个基础，另一个则是语句 分类 声明语句 可执行语句 简单语句 复合语句,3.3 声明语句,常量声明 格式：const 常量名=表达式 例如：const pi=3.1416 类型声明 格式：type 类型名= 类型定义 例如：Tarray=arra

16、y1.10 of integer; 变量声明 格式：var 变量列表：类型 例如：var i,length:integer;,3.4 简单语句,赋值语句 格式：标识符:=表达式 例子：area:=pi*r*r; READ语句 格式：read(变量列表) 例子：read(ch1,x,y); readln语句 WRITE 语句 格式：write(输出表) 例如：write(x=,x,result=,x+y); writeln语句,3.4 简单语句(续),例子：已知三角形的两边和夹角，求面积。 program area(input,output); const pi=3.1416; var a,b,

17、s,alfa:real; begin writeln(please input a,b,alfa:); read(a,b,alfa); s:=1/2*a*b*sin(alfa); writeln(area is:,s) end.,3.5 分支语句,作用 根据条件进行不同的处理 格式 If 条件表达式 then 语句1 else 语句2 语句1和语句2可以是简单语句，也可以是复合语句,3.5 分支语句（续）,举例 if x0 then y :=1 else y:= 0;,3.5 分支语句（续）,举例：求三个数中最大数 program maxNumber(input,output); var nu

18、m1,num2,num3,max:integer; begin read(num1,num2,num3); if(num1num2) then max:=num1 else max:=num2; if (num3max) then max:=num3; writeln(the largest number:,max) end.,3.5 分支语句（续）,CASE语句 作用 用于多个分支的判断 格式 case 表达式 of 值表1：语句1； 值表2：语句2； else 语句n； end;,3.6 循环语句,for语句 作用 完成指定次数的循环 格式 for 循环变量：= 循环初值 to | dow

19、nto 循环终值 do 循环体； 例子 for i:= 1 to 10 do datai:= 1;,3.6 循环语句（续）,While语句 作用 完成条件循环 格式 while 条件表达式 do 循环体 举例 i:=0; sum :=0; while I100 do begin sum:= sum+i; i:= i+1; end;,3.6 循环语句（续）,Repeat语句 作用 完成条件循环 格式 repeat 循环体； until 条件表达式 说明 与while语句的不同之处在于先执行一次循环再判断条件,3.6 循环语句（续）,例子：求n的阶乘 program factorial(input

20、,output); var fac:real; n,i:integer; begin read(n); fac:=1; for i:=2 to n do fac:=fac * i; write(fac); end.,3.6 循环语句（续）,例子：计算正弦函数 program sinx(input,output); const eps=1e-7; var x,term,sun:real; n:integer; begin read(x); n:=1; term:=x; sum:=x; repeat n:=n+2; term:=term*(-x*x)/(n-1)/n; sum:= sum+term

21、 until abs(term)eps; writeln(result is:,sum) end.,小结,本次课程介绍了Pascal语言的 基本数据 语句 作业 输入20个数，统计正数、负数的个数 自学Pascal语言相关内容 答疑时间 周二晚上 单独约时间,PASCAL语言程序设计,任课教师 王养廷,主要内容,过程和函数 数组 记录 指针,1 过程和函数,函数与过程 过程的定义与调用 函数的定义与调用 过程与函数的区别 形参与实参 数值参数与变量参数 变量的作用域,1.1 函数与过程,例程 例程又称为子程序，它式结构化程序设计的产物 例程由一系列语句组成，例程名是唯一的，通过例程名你可以多次

22、调用它。 Pascal例程 Pascal中的例程有两种形式：过程和函数。 过程与函数区别 过程相当一个语句 函数相当一个值,1.2 过程的定义与调用,过程定义 位置：在变量声明之后，主程序之前。 格式： procedure 过程名（形式参数表）； 常量定义； 类型定义； 变量定义； 过程或函数定义 begin 过程语句体； end;,1.2 过程的定义与调用(续),过程调用 位置：同级过程、函数或同级主程序中 格式：过程名（实际参数表）； 要求：实参的个数和类型要与形参匹配,1.2 过程的定义与调用（续）,实例 过程定义 procedure NumString(n:integer, var s

23、:array1.10 of char); var v,j:integer; begin v:=abs(n); j:=2; repeat sj:= chr(v mod 10 + ord(0) ; v:= v div 10; j:=j+1; until v = 0; if n0 then s1:=- else s1:= end; 过程调用 . NumString(-10, str); .,1.3 函数的定义与调用,函数的定义 位置：在变量声明之后，主程序之前。 格式： function 函数名（形式参数表）：类型； 常量定义； 类型定义； 变量定义； 过程或函数定义 begin 函数语句体； en

24、d;,1.3 函数的定义与调用（续）,函数调用 位置：同级过程、函数或同级主程序中 格式：函数名（实际参数表）； 要求：实参的个数和类型要与形参匹配,1.3 函数的定义与调用（续）,实例 函数定义 function max(a,b:integer):real; var m:integer; begin m:=a; if(ba) then m:=b; max:= m; end; 函数调用 . x:=max(x,y); .,1.4 过程与函数的区别,区别 在程序中的语法成分不同 函数有类型说明 函数要求有返回值 为什么定义两种例程 pascal严格区分语句和表达式，分别设计了两种例程。,1.5 形

25、参与实参,形参 过程或函数中，参数表中定义的参数 实参 过程或函数调用中，使用的参数 形参与实参的对应 要求过程或函数参数在个数和类型上要对应 可以使用兼容类型,1.6 数值参数和变量参数,数值的传入 把实参的值传给形参 实例 x:=max(x,y); 假设：x,y的值分别为10，20 在执行函数调用时，第一步是把两个数值传给形参a,b 这样在函数中参数a,b的值分别为10,20,1.6 数值参数和变量参数（续）,数值返回 函数或过程执行完成后需要返回结果 一般使用函数来返回数值 对于一些特殊情况需要使用参数返回结果数值 多个数值 复杂数据类型数值 过程返回值,1.6 数值参数和变量参数（续）

26、,数值参数 不需要返回结果数值的参数 参数定义格式 变量表：类型； 举例 a,b:integer;,1.6 数值参数和变量参数（续）,变量参数 需要返回结果数值的参数 参数定义格式 var 变量表：类型； 举例 var a,b:integer; 说明 函数或过程执行完成后，需要把变参的结果返回给相应的实参 在调用中实参必须是一个变量,2 数组,枚举类型 子界类型 数组 数组应用,2.1 枚举类型,类型定义 定义一个星期中的各天的类型 type day=(sun,mon,tues,wed,thu,fri,sta); 变量定义 var payday,today,firstday: day;,2.1

27、 枚举类型（续）,举例 program todaytomorrow(input,output); type day=(sun,mon,tues,wed,thu,fri,sat); var today,tomorrow:day; number:integer; begin read(number);,2.1 枚举类型（续）,case number of 0:today:=sun; 1:today:=mon; 2:today:=tues; 3:today:=wed, 4:today:=thu; 5:today:=fir; 6:today:=sat; end; if today = sat then

28、 tomorrow =sun else tomorrow = succ(day) end.,2.2 子界类型,类型定义 子界类型定义了某种类型的取值范围 ，这种类型必须是有序类型（如整型、字符型）。 定义举例： Type Ten = 1.10; OverHundred = 100.1000; Uppercase = A.Z;,2.2 子界类型（续）,类型说明 定义子界类型时，你不需要指定基类的名字，而只需提供该类型的两个常数。 所用基类必须是有序类型，定义结果将是另一种有序类型。 赋给子界类型变量的值必须是子界定义范围内的值 。 应用 经常用于数组的定义,2.3 数组,数组 用来表示一组相同类

29、型的数据 定义 Type DayTemperatures = array 1.24 of Integer; 说明 方括号中填入一个子界类型的值，或者用两个有序类型的常量定义一个新的子界类型,2.3 数组（续）,数组类型变量的定义 Var DayTemp1: DayTemperatures; 数组的引用 DayTemp1 1 := 54; DayTemp1 2 := 52; 多维数组 Type MonthTemps = array 1.24, 1.31 of Integer; YearTemps = array 1.24, 1.31, Jan.Dec of Integer;,2.4 数组应用,举例：输入一串小写字母