编译原理第02章.

第二章数据类型数据类型实质上是对(存储器中所存储的)数据进行的抽象。数据类型包含一组值和一组操作。本章内容1、将类型作为数据的抽象表示可以分为三个层次的抽象，即内部类型、用户定义类型和抽象数据类型2、数据类型与编译有关的几个问题3、类型的实现模型2.1引言1.数据类型的作用实现了数据抽象把程序员从机器的具体特征中解脱出来提高了编程效率语言的某种特定的数据抽象受到两个因素的影响：语言所面向的机器（只提供定点运算或同时提供浮点运算）；语言所面向的应用领域。2.数据类型的分类内部类型自定义类型语言根据所面向的机器和应用定义了不同的数据类型，这些类型称为内部类型(语言定义类型、基本类型)。自Pascal语言开始，语言提供了由用户定义类型的方法。采用这类方法由用户自己定义的数据类型称为用户定义类型(自定义类型)。2.2内部类型一.内部类型的特点.反映基本硬件特性.在语言级,同一类型数据的操作使用共用的抽象表示(如+、-、*、/）1.基本表示的不可见性基本位串对程序员是不可见的。25+9结果34基本表示00011001+00001001结果00100010二.内部类型的优越性从而具有优点：不同的程序设计风格可写性可读性可修改性2.编译时能检查变量使用的正确性能够进行静态类型检查如非法运算；形、实参类型匹配3.编译时可以确定无二义的操作合理地使用超载,可以提高可读性和可用性运算符的意义依赖于操作数的类型。“+”可以表示整数或实数加编译时,拒绝混合运算,或提供类型转换指令4.精度控制可以通过数据类型显式定义数据的精度floatdouble2.3用户定义类型语言除内部类型外，还允许用户借助于语言提供的数据的组合(聚合)机制，定义新的数据类型。许多语言允许程序员规定基本数据对象的聚合(乃至聚合的聚合)1.笛卡尔积n个集合A1，A2，…，An的笛卡儿积:A1×A2×…×An它是一个集合，其元素是有序的n元式（a1，a2，…，an）例一个正多边形用一个整数(正多边形边数)和一个实数(边的长度)来描述，那么任意正多边形都是笛卡儿积integer×real的一个元素。笛卡儿积：Pascal语言的记录C语言的结构2.有限映像①定义：从定义域类型DT值的有限集合，到值域类型RT值的有限集合的函数（映射）称为有限映像。array[1..50]ofchar整数1至50到字符集的有限映像②值域对象通过下标选取③下标越界会出错，需要进行动态检查(C语言？)④SNOBOL4的ARRAY构造符不要求值域集的所有元素是同一类型的（异质数组）⑤DT到相应值的特定子集的绑定策略：.编译时绑定(静态数组C).对象建立时绑定(半动态数组ALGOL).对象处理时绑定(动态数组APL)①任意多个数据项组成,数据项称为该序列的成分,且类型相同②串是序列③顺序文件的思想也是来自序列的概念,只能顺序读写3.序列若数据类型T包含属于同一类型T的成分--递归类型。①在类型定义中使用被定义类型的名字②指针是建立递归数据对象的重要手段4.递归一个选择对象结构的构造机制规定在两个不同选择对象之间作出适当的选择。每一选择对象结构称为变体。PASCAL的变体记录;C的联合5.判定或类型T的元素所有子集的集合，称为幂集,T称为基类型。若语言缺乏集合类型，只好使用链表或其他机制来实现。6.幂集语言允许程序员利用数据聚合机制，定义复杂的数据对象。语言允许程序员利用数据聚合机制，定义以复杂的数据对象作为基本项的聚合(聚合的聚合)。structstudent{charname[48];intage;…};匿名记录vara:recordx:integer;y:array[1..10]ofcharend;显式命名typecomplex=recordradius:real;angle:realend;varc1,c2,c3:complex;匿名类型用户定义类型显式命名的优点:①可读性(选择名字)②可修改性(不修改变量说明)③可分性(重复使用)④一致性检查可分性可分性概念用得比较普遍，C语言的函数就使用了可分性。把程序中相同的代码“分离”出来，用一个名字来标识需要执行这段代码时，通过该名字调用该段代码即可。2.4PASCAL类型结构一.非结构类型1.内部类型integer,real,boolean,char2.有序类型每一元素都有唯一的前驱和后继如:整型,布尔型,字符型3.定义新的有序类型的方法枚举型其值不能直接读/写子界型动态检查范围typecolor=(red,yellow,green,white);traffic=red..green;子界varlight:color;night:=succ(green);有序例：1.数组构造构造符ARRAY定义有限映象array[t1]of[t2]t1是定义域类型（有序类型）t2是值域类型二.聚合构造typerow=array[5..9]ofreal;varmy:array[3..8]ofrow;或varmy:array[3..8,5..9]ofreal;PASCAL可定义多维数组2.记录构造①构造符RECORD定义笛卡尔积②记录可以整体访问（赋值）用圆点“.”作为选择符访问单个的域(分量、成分、字段）记录结构的一般形式为recordfield_1:type_l；field_2:type_2；…field_n:type_nend③PASCAL的变体记录typedept=(house,sports,drugs,food,liquor);month=1..12;item=recordprice:real;caseavailable:booleanoftrue:(amount:integer;where:dept);false:(month_expected:month)end;vari1,i2:item:……i1.price:=5.24;i1.available:=true;i1.amount:=29;i1.where:=liquor;i2.price:=324.99;i2.available:=false;i2.month_expect:=8;priceavailableamountwhere5.24true29liquorpriceavailablemonth_expected324.99false8i1i2④使用变体记录不安全同一存储区实际上可能对应两个不同的变体，i1.price:=5.24;i1.available:=true;i1.amount:=29;i1.where:=liquor;i1.available:=false;i1.month_expect=?SET构造符构造受限制的幂集基类型只能是有序类型typevegetable=(bean,cabbage,celery,lettuce,onion,mushroom,zucchizi);varmy_salad,leftover:setofvegetable;3.集合构造PASCAL文件是任意类型元素的序列PASCAL文件仅能顺序处理put和get进行写/读操作typepattern=record…end;tape=fileofpattern;vart1,t2:tape;4.文件构造指针可引用匿名数据对象空指针的使用指针的操作:赋值,比较PASCAL指针只能指向匿名数据对象三.指针typetree_ref=binary_tree_node;二叉树binary_tree_node=recordinfo:char;left,right:tree_refend;pointer=node;线性表node=recorddata:integer;next:pointerend;指针例子四.小结(P36图2-4)Pascal语言数据类型非结构型指针类型（递归）结构型内部类型整形实型字符型布尔型枚举类型子界类型记录类型（笛卡儿积）变体记录（判定或）数组类型（有限映象）集合类型（幂集）文件类型（序列）2.5ADA类型结构自学2.6C类型结构一.非结构类型1.内部类型整型:int,short,long,unsigned实型又称为浮点型，float,double字符型数据的值是有限字符集的元素。浮点型数据范围类型占字节数数值的有效位数据范围float47位-1038～1038double815~16位-10308～10308阶的范围分别为-38～38-308～308思考最接近于0的正的double数为？C语言没有布尔型。0表示false，非0表示true。思考C语言为什么没有布尔类型？2.用户定义类型枚举类型实例enumbool{false，true};默认元素从0开始对应，可以显示改变顺序enumbool{false=1，true=2};1.数组数组构造实现有限映像intintarr[5];下标从0开始二维数组按行存放,floatfarr[3][4]；可以定义多维数组对数组名的处理相当于指针二.聚合构造inta[10];int*pa;pa=a;等价于pa=&a[0];例子构造符struct支持笛卡尔积structstudent{charname[20];//聚合的聚合charsex;…charaddr[30];};structstudentwenyu;//定义结构变量2.结构结构变量不能整体输入和输出。对其中的各个成分分别进行操作。可以把一个结构变量直接赋值给另一个结构体变量内存中，各个成员变量依次存储C的结构体可以嵌套structdate{intm；intd；inty；}；structstudent{charname[20]；charsex；structdatebirthday；…}wenyu；引用时可以依次找到最低一级的成员wenyu.birthday.day=12；构造符union(联合、共用体)支持判定或联合把不同类型的变量存放在同一段内存单元中C的联合是不安全的。3.联合uniondata{inti；charc;floatf;}；C语言把文件看成一个字符序列文件是由字符(字节）数据顺序组成的文件FILE是由语言预定义的有丰富的文件操作4.文件指针是C语言的第3类数据类型。指针可用来构造结构数据，支持递归没有空指针，可以对指针赋0值表示空指针可用来定义递归类型的数据三.指针structPointer{intdata;structPointer*next;};structPointer*head;空类型是C语言的第4类数据类型不允许定义空类型变量若函数的返回类型为void,则表示该函数没有返回值可以定义空类型指针变量，其值是地址该地址对应存储单元的数据类型不确定四.空类型voidC语言不支持用户定义类型构造机制的幂集。C数据类型小结C语言数据类型非结构型指针类型（递归）结构型枚举类型空类型结构类型（笛卡儿积）文件（序列）数组类型（有限映象）整形内部类型实型字符型单精度型双精度型联合类型（判定或）第七节抽象数据类型1.用户定义类型与内部类型的异同①都建立某种基本表示的抽象内部类型:对二进制位串的抽象；用户定义类型:对内部类型和已定义的用户定义类型的数据作为基本表示的抽象②每一类型都关联一组操作③内部类型隐蔽了基本表示，不能对它的成分进行操作;而用户定义类型具有更高级别的抽象，可以对其成分进行操作。满足下述特性的用户定义类型称为:抽象数据类型①在定义该类型的程序单元中,建立与有关的基本操作;②对使用该类型的程序单元而言,该类型的表示是隐蔽的。2.抽象数据类型自学了解一.SIMULA67的类机制自学了解二.CLU的抽象数据类型三.ADA语言的抽象数据类型自学了解自学了解四.Modula2语言的抽象数据类型类class支持封装(信息隐蔽)继承多态五.C++的抽象数据类型类定义的一般形式为class类名{private:数据声明；函数定义；protected：数据声明；函数定义；public：数据声明；函数定义；};被封装和隐蔽的部分包括私有段和保护段所有成员(函数与数据)、公有段函数的实现，类外不可见(保护成员可