第一章编译程序概述课件.ppt

1、第一章编译程序概述第一章编译程序概述教学要求教学要求1.1.上课时做笔记上课时做笔记2.2.每班选一位课代表每班选一位课代表 ,负责收作业，负责收作业，联系，准备记分册（标上班长、学联系，准备记分册（标上班长、学委电话）委电话）3.3.有问题及时向老师反馈有问题及时向老师反馈4.4.课堂纪律（上课不允许说话、上机课堂纪律（上课不允许说话、上机不允许玩游戏不允许玩游戏,手机打成震动）手机打成震动）辅导答疑辅导答疑n辅导答疑：辅导答疑：时间：每周周三时间：每周周三11、12节，课前后节，课前后地点：博观楼地点：博观楼209可以另约时间答疑可以另约时间答疑n联系方式：联系方式：Tel：Email：Q

2、Q：1458920766个人建议个人建议n 培养正思维培养正思维 思维模式思维模式=行为模式行为模式=最终结果最终结果 目标为了个人进步目标为了个人进步 培养良好学习习惯培养良好学习习惯 多讨论怎样做好，不讨论为什么没做好多讨论怎样做好，不讨论为什么没做好n 树立目标树立目标 目标目标=价值价值 专业学习目标专业学习目标周次周次星期星期节次节次实验室实验室第第2周周星期三星期三1-2 基础六基础六(96人人)第第4周周星期四星期四1-2 基础六基础六(96人人)第第7周周星期四星期四1-2 基础六基础六(96人人)第第9周周星期三星期三1-2 基础六基础六(96人人)第第13周周 星期四星期四

3、1-2 基础六基础六(96人人)主要内容主要内容n引入引入n编译程序与解释程序编译程序与解释程序n编译程序的功能分解与组织结构编译程序的功能分解与组织结构n编译程序的复杂性编译程序的复杂性n编译程序的设计与实现编译程序的设计与实现n编译程序的测试与维护编译程序的测试与维护n几个经典的编译程序几个经典的编译程序1 引入引入n计算机科学与技术计算机科学与技术n编译原理编译原理课程课程n编译原理编译原理主要内容主要内容n选用教材选用教材n为什么要学习编译原理为什么要学习编译原理n需要注意的问题需要注意的问题1.1 1.1 计算机科学与技术计算机科学与技术n含义含义 科学：构成计算基础的基本概念和模型

4、（又称为：科学：构成计算基础的基本概念和模型（又称为：形式理论）形式理论）技术：设计计算系统的工程和技术技术：设计计算系统的工程和技术n形式理论形式理论 有限自动机、正则表达式、正则集合有限自动机、正则表达式、正则集合 上下文无关文法上下文无关文法 下推机下推机 图灵机图灵机 不可判定性不可判定性n与编译原理的关系与编译原理的关系 形式理论是编译原理的理论基础形式理论是编译原理的理论基础 在后面我们要讲到前三个部分在后面我们要讲到前三个部分1.2 1.2 编译原理编译原理课程课程n课程性质课程性质 学科基础课学科基础课n先修课程先修课程 程序设计语言（程序设计语言（Pascal、C等）等）程序

5、设计、数据结构程序设计、数据结构 离散数学离散数学 操作系统操作系统1.31.3编译原理编译原理主要内容主要内容n按照编译程序的主要组成部分进行介绍按照编译程序的主要组成部分进行介绍 词法分析词法分析 语法分析语法分析 语义分析语义分析 代码生成和优化代码生成和优化 符号表和错误处理符号表和错误处理n一个编译程序实例一个编译程序实例 PL/0编译程序分析编译程序分析1.4 1.4 选用教材选用教材n教材教材 金成植：金成植：编译程序设计原理编译程序设计原理n编译程序编译程序 构造原理构造原理 实现技术实现技术n特点特点 采用原理与实例相结合的方法进行介绍采用原理与实例相结合的方法进行介绍 兼顾

6、原理和实现技术兼顾原理和实现技术1.5 为什么要学习编译原理为什么要学习编译原理n编译程序是一个大型综合、复杂的程序，编译程序是一个大型综合、复杂的程序，通过该课程的学习了解一个大型软件的通过该课程的学习了解一个大型软件的设计与实现设计与实现n有助于理解现有的编译程序的实现方法有助于理解现有的编译程序的实现方法n加深对程序设计语言的理解加深对程序设计语言的理解n提高调试程序能力提高调试程序能力n为进一步深造打下基础为进一步深造打下基础1.6 1.6 需要注意的问题需要注意的问题n对课程的难度应该有足够的思想准备对课程的难度应该有足够的思想准备n注意平时的听课和积累注意平时的听课和积累n原理侧重

7、理解原理侧重理解n具体的算法和程序需要实际动手分析具体的算法和程序需要实际动手分析2 2 编译程序与解释程序编译程序与解释程序n语言与程序设计语言语言与程序设计语言n程序设计语言主要内容程序设计语言主要内容n程序设计语言分类程序设计语言分类n编译原理基本概念编译原理基本概念n编译程序与解释程序的异同编译程序与解释程序的异同n使用解释程序的情况使用解释程序的情况2.1 2.1 语言与程序设计语言语言与程序设计语言n语言语言 人们用来交流的工具人们用来交流的工具n程序设计语言程序设计语言 人与计算机交流的工具人与计算机交流的工具n二者的区别二者的区别 对象对象 二义性二义性2.2 2.2 程序设计

8、语言主要内容程序设计语言主要内容n数据定义数据定义 字符集、常量、类型、变量、表达式字符集、常量、类型、变量、表达式n语句语句 顺序、分支和循环顺序、分支和循环n函数函数 过程、函数、子程序过程、函数、子程序n复杂数据类型复杂数据类型 数组、记录、指针等等数组、记录、指针等等2.3 2.3 程序设计语言的分类程序设计语言的分类n按照层次按照层次 高级语言高级语言 低级语言低级语言n按照结构按照结构 过程式语言（过程式语言（C、Pascal）函数式语言（函数式语言（LISP、ML）逻辑式语言（逻辑式语言（Prolog）对象式语言（对象式语言（SmallTalk、Java、C+）2.4 2.4 编

9、译程序基本概念编译程序基本概念n源程序：用程序设计语言编制的程序源程序：用程序设计语言编制的程序n目标程序：与源程序功能等价的目标代目标程序：与源程序功能等价的目标代码码n编译程序：把源程序转换成目标程序的编译程序：把源程序转换成目标程序的程序程序n解释程序：执行源程序得到执行结果的解释程序：执行源程序得到执行结果的程序程序n汇编程序：把汇编源程序转换成目标程汇编程序：把汇编源程序转换成目标程序的程序序的程序2.5 2.5 编译程序与解释程序区别编译程序与解释程序区别源程序源程序数据数据源程序源程序解释程序解释程序计算结果计算结果编译程序编译程序目标程序目标程序2.6 2.6 使用解释程序的情

10、况使用解释程序的情况n不追求执行速度不追求执行速度n有些程序允许执行式改变自身有些程序允许执行式改变自身n人机对话的交互语言人机对话的交互语言n由解释程序到编译程序的自动生成系统由解释程序到编译程序的自动生成系统3 3 编译程序的功能分解与组织结构编译程序的功能分解与组织结构n功能结构图功能结构图n遍的概念遍的概念n源程序的处理过程源程序的处理过程3.1 3.1 功能结构图功能结构图错误处理语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表处理3.1 3.1 功能结构图（续）功能结构图（续）n编译程序的输入：源程序编译程序的输入：源程序n编译程序的输出：目标程序

11、编译程序的输出：目标程序n编译程序的功能模块编译程序的功能模块 词法分析：把源程序变成单词串词法分析：把源程序变成单词串 语法分析：检察源程序是否符合语法结构语法分析：检察源程序是否符合语法结构 语义分析：标识符的含义是否正确语义分析：标识符的含义是否正确 代码生成：生成目标代码代码生成：生成目标代码3.2 3.2 遍的概念遍的概念n遍的概念遍的概念 对源程序或与其等价的中间代码扫描一次对源程序或与其等价的中间代码扫描一次n按遍划分按遍划分 一遍一遍 多遍多遍n一遍特点一遍特点 避免重复工作、速度快、代码质量不高避免重复工作、速度快、代码质量不高n多遍特点多遍特点 结构算法清晰、易于掌握、能够

12、产生好的目标代码结构算法清晰、易于掌握、能够产生好的目标代码3.3 3.3 源程序的处理过程源程序的处理过程n预处理器编译程序汇编程序装配连接扩展程序 源程序 目标汇编程序 可重定位机器代码 可执行机器码可重定位目标文件库3.3 3.3 源程序的处理过程（续）源程序的处理过程（续）n实例实例 以以DOS下的下的C语言处理过程为例语言处理过程为例 C是多遍编译是多遍编译 第一遍处理包含、宏等信息第一遍处理包含、宏等信息 以后各遍进行编译以后各遍进行编译 过程过程 第一遍编译得到标准第一遍编译得到标准C程序程序 经过经过C编译器的到目标程序编译器的到目标程序 经过连接得到可执行程序经过连接得到可执

13、行程序 装入装入DOS执行执行4 4 编译程序复杂性编译程序复杂性n元程序元程序 处理程序的程序处理程序的程序n编译程序复杂性编译程序复杂性 元级程序元级程序 高级语言与低级语言差别大高级语言与低级语言差别大 编译程序要求高编译程序要求高5 5 编译程序的设计与实现编译程序的设计与实现n设计编译程序条件设计编译程序条件n 精通源语言精通源语言n 精通目标语言精通目标语言n 精通编译技术精通编译技术n编译程序的性能编译程序的性能n 可靠性、速度、目标代码速度、占用空间、可靠性、速度、目标代码速度、占用空间、可移植性、可维护性、可扩展性可移植性、可维护性、可扩展性5 5 编译程序的设计与实现（续）

14、编译程序的设计与实现（续）n开发编译程序的途径开发编译程序的途径n 预处理法预处理法n 移植法移植法n 直接移植直接移植n 交叉编译交叉编译n 自展法自展法n 工具法工具法n 例如：例如：LEX、YACCn 理论法理论法6 6 编译程序的测试和维护编译程序的测试和维护n编译程序测试编译程序测试 机械证明机械证明 测试测试 测试用例设计测试用例设计n编译程序维护编译程序维护 长期有效地改正发现的错误长期有效地改正发现的错误7 7 几个经典的编译程序几个经典的编译程序nPascal编译程序编译程序n设计者：设计者：Wirthn使用技术：递归下降、一遍扫描、栈式抽象机使用技术：递归下降、一遍扫描、栈

15、式抽象机n特点：产生特点：产生P代码代码nC编译程序编译程序n设计者：设计者：D.M.Ritchien使用技术：递归下降、二遍扫描、有可选的第三遍使用技术：递归下降、二遍扫描、有可选的第三遍n特点：可移植性好特点：可移植性好nFortran编译程序编译程序n设计者：设计者：Lowry和和Medlockn使用技术：综合使用技术：综合n特点：优化好特点：优化好小结小结n内容内容 编译程序的基本概念和相关知识编译程序的基本概念和相关知识 编译程序的组成和复杂性编译程序的组成和复杂性 几个常见的编译程序几个常见的编译程序n要求要求 掌握编译程序的组成和复杂性掌握编译程序的组成和复杂性 预习标准的预习标

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

17、Turbo Pascal。由于既简洁功能又强，Turbo Pascal成为当时最畅销的编译器之一，而且在PC平台上非常流行。Delphi中的Pascal 1995年Borland发布了Delphi，使Pascal成为一种可视化编程语言。1 Pascal概述（续）n一个Pascal程序实例program circle(input,output);constpi=3.1416;varr,l,s:real;beginread(r);l:=2*pi*r;s:=pi*r*r;write(r,l,s)end.2 数据n字符集n标识符和保留字n常量n变量n运算符2.1 字符集nPascal字符集 字母 数字

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

19、的内容用 括起来例子 this is a comment 这是一个例子2.3 常量n常量 一般常量 程序中的数值 例如：23、-1.2、a 符号常量 定义：在const部分定义 格式：常量名=表达式 举例：const pi=3.14；st=t；2.4 变量n变量 定义：在var部分定义 格式：变量名表：类型；说明：类型名可以是任意Pascal类型 变量名表是多个变量，中间用逗号间隔 举例var x,y:integer;flag:boolean;2.4 变量（续）n 类型主要有四个：整型integer描述一个整数类型实型real描述一个实数类型字符型char描述一个字符类型，值是一个字符布尔型b

20、oolean描述一个逻辑类型，只有两个：true和false。2.5 运算符n算术运算符n关系运算符n逻辑运算符n运算符优先级2.5 运算符（续）n算术运算符+、-、*、/、mod、divn说明 用于算术运算+、-、*整数、实数运算符 mod、div整数运算符/实数运算符n举例m:=n mod 10;x:=y+100;2.5 运算符（续）n关系运算符 用于关系表达式 符号：、=、=、=、举例X+10 yX=12.5 运算符（续）n逻辑运算符 运算符 not、and、or 真值表ABnot AA and bA or bFFTFFFTTFTTFFFTTTFTT2.5 运算符（续）n运算符优先级 两

21、个运算符相邻，先参加高优先级运算 同级运算符自左至右 有扩号先计算括号内3 语句n程序结构n语句n声明语句n简单语句n分支语句n循环语句3.1 程序结构n程序结构 程序首部 声明部分 语句部分n举例3.1 程序结构（续）program pl0(input,output);const norw=11;no.of reserved wordstype symset=set of symbol;var ch:char;last character readprocedure error(n:integer);begin writeln(*,:cc-1,n:2);err:=err+1end error

22、;begin main program for ch:=chr(0)to chr(255)do ssymch:=nul;getsym;end.3.2 语句n语句：数据类型是Pascal 编程的一个基础，另一个则是语句 n分类 声明语句 可执行语句 简单语句 复合语句3.3 声明语句n常量声明 格式：const 常量名=表达式 例如：const pi=3.1416n类型声明 格式：type 类型名=类型定义 例如：Tarray=array1.10 of integer;n变量声明 格式：var 变量列表：类型 例如：var i,length:integer;3.4 简单语句n赋值语句 格式：标识

23、符:=表达式 例子：area:=pi*r*r;nREAD语句 格式：read(变量列表)例子：read(ch1,x,y);readln语句nWRITE 语句 格式：write(输出表)例如：write(x=,x,result=,x+y);writeln语句3.4 简单语句(续)n例子：已知三角形的两边和夹角，求面积。program area(input,output);constpi=3.1416;vara,b,s,alfa:real;beginwriteln(please input a,b,alfa:);read(a,b,alfa);s:=1/2*a*b*sin(alfa);writeln

24、(area is:,s)end.3.5 分支语句n作用 根据条件进行不同的处理n格式If 条件表达式 then 语句1else 语句2 语句1和语句2可以是简单语句，也可以是复合语句3.5 分支语句（续）n举例 if x0 then y:=1else y:=0;3.5 分支语句（续）n举例：求三个数中最大数program maxNumber(input,output);varnum1,num2,num3,max:integer;beginread(num1,num2,num3);if(num1num2)then max:=num1else max:=num2;if(num3max)then m

25、ax:=num3;writeln(the largest number:,max)end.3.5 分支语句（续）nCASE语句 作用 用于多个分支的判断 格式case 表达式 of 值表1：语句1；值表2：语句2；else 语句n；end;3.6 循环语句nfor语句 作用 完成指定次数的循环 格式for 循环变量：=循环初值 to|downto 循环终值 do 循环体；例子for i:=1 to 10 do datai:=1;3.6 循环语句（续）nWhile语句 作用 完成条件循环 格式while 条件表达式 do 循环体 举例i:=0;sum:=0;while I100 do begin

26、 sum:=sum+i;i:=i+1;end;3.6 循环语句（续）nRepeat语句 作用 完成条件循环 格式repeat 循环体；until 条件表达式 说明 与while语句的不同之处在于先执行一次循环再判断条件3.6 循环语句（续）n例子：求n的阶乘program factorial(input,output);varfac:real;n,i:integer;beginread(n);fac:=1;for i:=2 to n dofac:=fac*i;write(fac);end.3.6 循环语句（续）n例子：计算正弦函数program sinx(input,output);const

27、eps=1e-7;varx,term,sun:real;n:integer;beginread(x);n:=1;term:=x;sum:=x;repeatn:=n+2;term:=term*(-x*x)/(n-1)/n;sum:=sum+termuntil abs(term)eps;writeln(result is:,sum)end.小结n本次课程介绍了Pascal语言的 基本数据 语句n作业 输入20个数，统计正数、负数的个数 自学Pascal语言相关内容n答疑时间 周二晚上 单独约时间PASCAL语言程序设计任课教师王养廷主要内容n 过程和函数n 数组n 记录n 指针1 过程和函数n 函

28、数与过程n 过程的定义与调用n 函数的定义与调用n 过程与函数的区别n 形参与实参n 数值参数与变量参数n 变量的作用域1.1 函数与过程n例程例程又称为子程序，它式结构化程序设计的产物例程由一系列语句组成，例程名是唯一的，通过例程名你可以多次调用它。nPascal例程 Pascal中的例程有两种形式：过程和函数。n过程与函数区别 过程相当一个语句 函数相当一个值1.2 过程的定义与调用n过程定义 位置：在变量声明之后，主程序之前。格式：procedure 过程名（形式参数表）；常量定义；类型定义；变量定义；过程或函数定义begin 过程语句体；end;1.2 过程的定义与调用(续)n过程调用

29、 位置：同级过程、函数或同级主程序中 格式：过程名（实际参数表）；要求：实参的个数和类型要与形参匹配1.2 过程的定义与调用（续）n实例 过程定义procedure NumString(n:integer,var s: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 na)then m:=b;max:=m;end;函数调用.x:=max(x,y);.1.4 过程与函数的区别n区别 在程序中的语法成分不同 函数

30、有类型说明 函数要求有返回值n为什么定义两种例程 pascal严格区分语句和表达式，分别设计了两种例程。1.5 形参与实参n形参 过程或函数中，参数表中定义的参数n实参 过程或函数调用中，使用的参数n形参与实参的对应 要求过程或函数参数在个数和类型上要对应 可以使用兼容类型1.6 数值参数和变量参数n数值的传入 把实参的值传给形参n实例 x:=max(x,y);假设：x,y的值分别为10，20 在执行函数调用时，第一步是把两个数值传给形参a,b 这样在函数中参数a,b的值分别为10,201.6 数值参数和变量参数（续）n数值返回 函数或过程执行完成后需要返回结果 一般使用函数来返回数值 对于一

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

32、sta);n变量定义var payday,today,firstday:day;2.1 枚举类型（续）n举例program todaytomorrow(input,output);typeday=(sun,mon,tues,wed,thu,fri,sat);vartoday,tomorrow:day;number:integer;beginread(number);2.1 枚举类型（续）case number of0:today:=sun;1:today:=mon;2:today:=tues;3:today:=wed,4:today:=thu;5:today:=fir;6:today:=sat

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

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

35、现次数。program count(input,output);varnum:arraya.zof integer;ch:char;beginread(ch);while ch?dobeginif(ch=a)and(ch=z)then numch:=numch+1;read(ch)endend.3 记录n概念 描述统一事物的不同属性n类型定义Type Date=record Year:Integer;Month:Byte;Day:Byte;end;n变量定义Var BirthDay:Date;3 记录（续）n使用 BirthDay.Year:=1997;BirthDay.Month:=2;Bi

36、rthDay.Day:=14;n说明 域的概念 域的访问 与类对比（C中的结构）n典型应用 定义一个学生信息3 记录（续）n学生记录的定义Type Student=record name:string;age:integer;sex:integer;end;Var p:Student;n使用p.age:-=20;3 记录（续）n记录与数组的结合n题目：使用记录数组来输入一个班30人的信息，按照总成绩排序。学生信息包括：姓名、性别、年龄、民族（汉、蒙、满）、总成绩。n自己实现该程序，作为上机题目4 指针n概念指针是存放指定类型（或未定义类型）变量内存地址的变量 n类型定义type PointerToInt=Integer;n变量定义Var P:Integer;X:Integer;4 指针（续）n使用 P:=X;X:=10;P:=20;n说明 号的作用 号的作用 空指针nil4 指针（续）n指针空间申请newn指针空间释放disposen举例VarVar P:Integer;BeginBegin New(P);P:=20;ShowMessage(IntToStr(P);Dispose(P);endend;小结n主要内容 函数 复合数据类型：枚举、子界、数组、记录、指针n上机 题目：课上讲解例题、课后习题 时间：第二周n答疑时间 周二晚上 单独约时间