第一章编译程序概述课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第一章编译程序概述,第一章编译程序概述第一章编译程序概述教学要求1.上课时做笔记,2.每班选一位课代表,负责收作业，联系，准备记分册（标上班长、学委电话）,3.有问题及时向老师反馈,4.课堂纪律（上课不允许说话、上机不允许玩游戏,手机打成震动）,教学要求,1.,上课时做笔记,2.,每班选一位课代表,负责收作业，联系，准备记分册（标上班长、学委电话）,3.,有问题及时向老师反馈,4.,课堂纪律（上课不允许说话、上机不允许玩游戏,手机打成震动）,辅导答疑,辅导答疑：,时间：每周周三,11,、,12,节，课前后,地点：博观楼,209,可以另约时间答疑,联系方式：,Tel,：,Email,：,QQ,：,1458920766,个人建议,培养正思维,思维模式,=,行为模式,=,最终结果,目标为了个人进步,培养良好学习习惯,多讨论怎样做好，不讨论为什么没做好,树立目标,目标,=,价值,专业学习目标,周次,星期,节次,实验室,第,2,周,星期三,1-2,基础六,(96,人,),第,4,周,星期四,1-2,基础六,(96,人,),第,7,周,星期四,1-2,基础六,(96,人,),第,9,周,星期三,1-2,基础六,(96,人,),第,13,周,星期四,1-2,基础六,(96,人,),主要内容,引入,编译程序与解释程序,编译程序的功能分解与组织结构,编译程序的复杂性,编译程序的设计与实现,编译程序的测试与维护,几个经典的编译程序,1,引入,计算机科学与技术,编译原理,课程,编译原理,主要内容,选用教材,为什么要学习编译原理,需要注意的问题,1.1,计算机科学与技术,含义,科学：构成计算基础的基本概念和模型（又称为：形式理论）,技术：设计计算系统的工程和技术,形式理论,有限自动机、正则表达式、正则集合,上下文无关文法,下推机,图灵机,不可判定性,与编译原理的关系,形式理论是编译原理的理论基础,在后面我们要讲到前三个部分,1.2,编译原理,课程,课程性质,学科基础课,先修课程,程序设计语言（,Pascal,、,C,等）,程序设计、数据结构,离散数学,操作系统,1.3,编译原理,主要内容,按照编译程序的主要组成部分进行介绍,词法分析,语法分析,语义分析,代码生成和优化,符号表和错误处理,一个编译程序实例,PL/0,编译程序分析,1.4,选用教材,教材,金成植：,编译程序设计原理,编译程序,构造原理,实现技术,特点,采用原理与实例相结合的方法进行介绍,兼顾原理和实现技术,1.5,为什么要学习编译原理,编译程序是一个大型综合、复杂的程序，通过该课程的学习了解一个大型软件的设计与实现,有助于理解现有的编译程序的实现方法,加深对程序设计语言的理解,提高调试程序能力,为进一步深造打下基础,1.6,需要注意的问题,对课程的难度应该有足够的思想准备,注意平时的听课和积累,原理侧重理解,具体的算法和程序需要实际动手分析,2,编译程序与解释程序,语言与程序设计语言,程序设计语言主要内容,程序设计语言分类,编译原理基本概念,编译程序与解释程序的异同,使用解释程序的情况,2.1,语言与程序设计语言,语言,人们用来交流的工具,程序设计语言,人与计算机交流的工具,二者的区别,对象,二义性,2.2,程序设计语言主要内容,数据定义,字符集、常量、类型、变量、表达式,语句,顺序、分支和循环,函数,过程、函数、子程序,复杂数据类型,数组、记录、指针等等,2.3,程序设计语言的分类,按照层次,高级语言,低级语言,按照结构,过程式语言（,C,、,Pascal,）,函数式语言（,LISP,、,ML,）,逻辑式语言（,Prolog,）,对象式语言（,SmallTalk,、,Java,、,C+,）,2.4,编译程序基本概念,源程序：用程序设计语言编制的程序,目标程序：与源程序功能等价的目标代码,编译程序：把源程序转换成目标程序的程序,解释程序：执行源程序得到执行结果的程序,汇编程序：把汇编源程序转换成目标程序的程序,2.5,编译程序与解释程序区别,源程序,数据,源程序,解释程序,计算结果,编译程序,目标程序,2.6,使用解释程序的情况,不追求执行速度,有些程序允许执行式改变自身,人机对话的交互语言,由解释程序到编译程序的自动生成系统,3,编译程序的功能分解与组织结构,功能结构图,遍的概念,源程序的处理过程,3.1,功能结构图,错,误,处,理,语法分析程序,语义分析程序,目标代码生成程序,词法分析程序,中间代码生成程序,代码优化程序,表,处,理,3.1,功能结构图（续）,编译程序的输入：源程序,编译程序的输出：目标程序,编译程序的功能模块,词法分析：把源程序变成单词串,语法分析：检察源程序是否符合语法结构,语义分析：标识符的含义是否正确,代码生成：生成目标代码,3.2,遍的概念,遍的概念,对源程序或与其等价的中间代码扫描一次,按遍划分,一遍,多遍,一遍特点,避免重复工作、速度快、代码质量不高,多遍特点,结构算法清晰、易于掌握、能够产生好的目标代码,3.3,源程序的处理过程,预处理器,编译程序,汇编程序,装配连接,扩展程序,源程序,目标汇编程序,可重定位机器代码,可执行机器码,可重定位目标文件库,3.3,源程序的处理过程（续）,实例,以,DOS,下的,C,语言处理过程为例,C,是多遍编译,第一遍处理包含、宏等信息,以后各遍进行编译,过程,第一遍编译得到标准,C,程序,经过,C,编译器的到目标程序,经过连接得到可执行程序,装入,DOS,执行,4,编译程序复杂性,元程序,处理程序的程序,编译程序复杂性,元级程序,高级语言与低级语言差别大,编译程序要求高,5,编译程序的设计与实现,设计编译程序条件,精通源语言,精通目标语言,精通编译技术,编译程序的性能,可靠性、速度、目标代码速度、占用空间、可移植性、可维护性、可扩展性,5,编译程序的设计与实现（续）,开发编译程序的途径,预处理法,移植法,直接移植,交叉编译,自展法,工具法,例如：,LEX,、,YACC,理论法,6,编译程序的测试和维护,编译程序测试,机械证明,测试,测试用例设计,编译程序维护,长期有效地改正发现的错误,7,几个经典的编译程序,Pascal,编译程序,设计者：,Wirth,使用技术：递归下降、一遍扫描、栈式抽象机,特点：产生,P,代码,C,编译程序,设计者：,D.M.Ritchie,使用技术：递归下降、二遍扫描、有可选的第三遍,特点：可移植性好,Fortran,编译程序,设计者：,Lowry,和,Medlock,使用技术：综合,特点：优化好,小结,内容,编译程序的基本概念和相关知识,编译程序的组成和复杂性,几个常见的编译程序,要求,掌握编译程序的组成和复杂性,预习标准的,Pascal,语言,预习,Turbo Pascal,开发环境,PASCAL,语言基础知识,任课教师,王养廷,复习,编译程序的主要组成部分，每个部分的功能,编译程序为什么复杂,预习标准的,Pascal,语言,预习,Turbo Pascal,开发环境,主要内容,Pascal,概述,数据,语句,1 Pascal,概述,Pascal,历史,Wirth Pascal,Pascal,语言最初由瑞士苏黎士理工学院的尼古拉斯,-,沃斯,(Niklaus Wirth),教授在,1971,年设计,作为,Algol,语言,(1960,年设计,),简化本用于教学目的。,Turbo Pascal,1983,年,Borland,公司推出了世界闻名的,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,数据,字符集,标识符和保留字,常量,变量,运算符,2.1,字符集,Pascal,字符集,字母,数字,其它符号,字符集的引申,多语言的处理（,ASCII,UniCode,）,2.2,标识符和保留字,标识符,定义：以字母开头，后面跟字母、数字组成的字符串。,作用：用来表示各种程序元素的名称,规定：,大小写不敏感,有效长度,8,，超过,8,个不起作用,建议：,采用一个或多个英文单词组成,举例,score,、,charPosition,2.2,表识符和保留字（续）,保留字,Pascal,系统已经使用的单词,主要保留字,例如：,program,、,begin,、,end,、,const,、,var,、,read,、,write,、,if,、,then,、,else,等等,详细内容参考,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,变量（续）,类型主要有四个：,整型,integer,描述一个整数类型,实型,real,描述一个实数类型,字符型,char,描述一个字符类型，值是一个字符,布尔型,boolean,描述一个逻辑类型，只有两个：,true,和,false,。,2.5,运算符,算术运算符,关系运算符,逻辑运算符,运算符优先级,2.5,运算符（续）,算术运算符,+,、,-,、*、,/,、,mod,、,div,说明,用于算术运算,+,、,-,、*整数、实数运算符,mod,、,div,整数运算符,/,实数运算符,举例,m:=n mod 10;,x:=y+100;,2.5,运算符（续）,关系运算符,用于关系表达式,符号：,、,=,、,、,y,X=1,2.5,运算符（续）,逻辑运算符,运算符,not,、,and,、,or,真值表,A,B,not A,A and b,A or b,F,F,T,F,F,F,T,T,F,T,T,F,F,F,T,T,T,F,T,T,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(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=array1.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,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,num1,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|downto,循环终值,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,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,until abs(term)eps;,writeln(result is:,sum),end.,小结,本次课程介绍了,Pascal,语言的,基本数据,语句,作业,输入,20,个数，统计正数、负数的个数,自学,Pascal,语言相关内容,答疑时间,周二晚上,单独约时间,PASCAL,语言程序设计,任课教师,王养廷,主要内容,过程和函数,数组,记录,指针,1,过程和函数,函数与过程,过程的定义与调用,函数的定义与调用,过程与函数的区别,形参与实参,数值参数与变量参数,变量的作用域,1.1,函数与过程,例程,例程又称为子程序，它式结构化程序设计的产物,例程由一系列语句组成，例程名是唯一的，通过例程名你可以多次调用它。,Pascal,例程,Pascal,中的例程有两种形式：过程和函数。,过程与函数区别,过程相当一个语句,函数相当一个值,1.2,过程的定义与调用,过程定义,位置：在变量声明之后，主程序之前。,格式：,procedure,过程名（形式参数表）；,常量定义；,类型定义；,变量定义；,过程或函数定义,begin,过程语句体；,end;,1.2,过程的定义与调用,(,续,),过程调用,位置：同级过程、函数或同级主程序中,格式：过程名（实际参数表）；,要求：实参的个数和类型要与形参匹配,1.2,过程的定义与调用（续）,实例,过程定义,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,过程与函数的区别,区别,在程序中的语法成分不同,函数有类型说明,函数要求有返回值,为什么定义两种例程,pascal,严格区分语句和表达式，分别设计了两种例程。,1.5,形参与实参,形参,过程或函数中，参数表中定义的参数,实参,过程或函数调用中，使用的参数,形参与实参的对应,要求过程或函数参数在个数和类型上要对应,可以使用兼容类型,1.6,数值参数和变量参数,数值的传入,把实参的值传给形参,实例,x:=max(x,y);,假设：,x,y,的值分别为,10,，,20,在执行函数调用时，第一步是把两个数值传给形参,a,b,这样在函数中参数,a,b,的值分别为,10,20,1.6,数值参数和变量参数（续）,数值返回,函数或过程执行完成后需要返回结果,一般使用函数来返回数值,对于一些特殊情况需要使用参数返回结果数值,多个数值,复杂数据类型数值,过程返回值,1.6,数值参数和变量参数（续）,数值参数,不需要返回结果数值的参数,参数定义格式,变量表：类型；,举例,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,枚举类型（续）,举例,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 tomorrow=sun,else tomorrow=succ(day),end.,2.2,子界类型,类型定义,子界类型定义了某种类型的取值范围，这种类型必须是有序类型（如整型、字符型）。,定义举例：,Type,Ten=1.10;,OverHundred=100.1000;,Uppercase=A.Z;,2.2,子界类型（续）,类型说明,定义子界类型时，你不需要指定基类的名字，而只需提供该类型的两个常数。,所用基类必须是有序类型，定义结果将是另一种有序类型。,赋给子界类型变量的值必须是子界定义范围内的值,。,应用,经常用于数组的定义,2.3,数组,数组,用来表示一组相同类型的数据,定义,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,数组应用,举例：输入一串小写字母，以,?,结束，统计每个字母出现次数。,program count(input,output);,var,num:arraya.zof integer;,ch:char;,begin,read(ch);,while ch?do,begin,if(ch=a)and(ch=z),then numch:=numch+1;,read(ch),end,end.,3,记录,概念,描述统一事物的不同属性,类型定义,Type,Date=record,Year:Integer;,Month:Byte;,Day:Byte;,end;,变量定义,Var,BirthDay:Date;,3,记录（续）,使用,BirthDay.Year:=1997;,BirthDay.Month:=2;,BirthDay.Day:=14;,说明,域的概念,域的访问,与类对比（,C,中的结构）,典型应用,定义一个学生信息,3,记录（续）,学生记录的定义,Type,Student=record,name:string;,age:integer;,sex:integer;,end;,Var,p:Student;,使用,p.age:-=20;,3,记录（续）,记录与数组的结合,题目：,使用记录数组来输入一个班,30,人的信息，按照总成绩排序。,学生信息包括：姓名、性别、年龄、民族（汉、蒙、满）、总成绩。,自己实现该程序，作为上机题目,4,指针,概念,指针是存放指定类型（或未定义类型）变量内存地址的变量,类型定义,type PointerToInt=Integer;,变量定义,Var,P:Integer;,X:Integer;,4,指针（续）,使用,P:=X;,X:=10;,P:=20;,说明,号的作用,号的作用,空指针,nil,4,指针（续）,指针空间申请,new,指针空间释放,dispose,举例,Var,P:Integer;,Begin,New(P);,P:=20;,ShowMessage(IntToStr(P);,Dispose(P);,end,;,小结,主要内容,函数,复合数据类型：枚举、子界、数组、记录、指针,上机,题目：课上讲解例题、课后习题,时间：第二周,答疑时间,周二晚上,单独约时间,谢谢观赏,