程序设计语言与编译原理 第二章数据类型课件

程序设计语言与编译1第二章数据类型数据类型实质上是对存储器中所存储的数据进行的抽象。它包含了一组值的集合和一组操作。程序设计语言与编译2本章内容1、将类型作为数据结构的抽象表示可以分为三个层次的抽象，即内部类型、用户定义类型和抽象数据类型2、数据类型与编译有关的几个问题3、类型的实现模型程序设计语言与编译32.1

引言1.

数据类型的作用实现了数据抽象从机器的具体特征中解脱出来提高了编程效率程序设计语言与编译4语言的某种特定的数据抽象受到两个因素的影响：语言所面向的机器（只提供定点运算或同时提供浮点运算）；语言所面向的应用领域。程序设计语言与编译52.

数据类型的分类内部类型

自定义类型程序设计语言与编译6语言根据所面向的机器和应用定义了不同的数据类型，这些类型称为内部类型(语言定义类型

)。自Pascal语言开始，语言提供了由用户定义类型的方法。采用这类方法由用户自己定义的数据类型称为用户定义类型(自定义类型)。程序设计语言与编译7第二节内部类型一. 内部类型的特点内部类型反映基本硬件特性在语言级,内部类型是共用某些操作的数据对象的抽象表示程序设计语言与编译二. 内部类型的优越性1.基本表示的不可见性基本位串对程序员是不可见的。优点：导致不同的程序设计风格可写性可读性

可修改性例：25+9=34基本表示00011001+00001001结果001000108程序设计语言与编译编译时能检查变量使用的正确性进行静态类型检查,如非法运算,形实参类型匹配（某些动态特性不一定能查出，如i/j中j=0）编译时可以确定无二义的操作超载(多态)的概念:运算符的意义依赖于操作数的类型。如“+”可以表示整数加或实数加编译时,可拒绝混合运算,或提供类型转换指令合理地使用超载,可以提高语言的可读性和可用性9程序设计语言与编译104.精度控制可以通过数据类型显式定义数据的精度精度说明有利于空间优化精度说明可作为检查的一种手段精度说明有利于程序的修改程序设计语言与编译第三节用户定义类型许多语言除了定义内部类型外，还允许程序员定义新的数据类型，规定基本数据对象的聚合,乃至聚合的聚合。How

todefine?11程序设计语言与编译1.

笛卡尔积定义：N个集合A1,A2,…,An的笛卡尔积表示为A1×A2×…×An，它是一个集合,其元素为(a1,a2,…,an), 其中

ai∈Ai在语言中对应什么构造？12程序设计语言与编译边数表示为任意正多边形任意正多边形

integer

×

real在COBOL和PASCAL中称为记录；在ALGOL每边边长中称为结构。例：对于如前定义的多边形，有两个域no-of-edges和edge-size，Struct

polygon{int

no-of-edges;double

edge-size}t1;若t1是一个边长为7.53的等边三角形(3,3.75)，则可以写为：t1.no-of-edges

=

3;t1.edge-size

=

3.75;注意：语言把笛卡尔积数据对象看成由若干个域组成，每个域有一个唯一的名字；通常用域名来选取域，对它进行

修改；13程序设计语言与编译2. 有限映像（射）定义：从定义域类型DT

（

domaintype

）的值的有限集合，到值域类型

RT

（

range

type ）的值的有限集合的函数称为有限映像（射）

。在语言中对应什么构造？14程序设计语言与编译有限映像（射）的一些特点在高级语言中通常体现为数组构造；值域对象通过下标选取下标越界会出错，动态检查下标可用来选取值域的多个元素（如数组的分割、切片）SNOBOL4的ARRAY构造符并不要求值域集的所有元素是同一类型的例如：Char

array[50]可看成是从0到49的整数到字符集的有限映像15程序设计语言与编译有限映像（射）的一些特点DT到相应值的特定子集的绑定策略：.编译时绑定

(静态数组).对象建立时绑定

(执行到分程序时,动态数组).对象处理时绑定(对APL，子集范围可变)16程序设计语言与编译3.序列定义：序列由任意多个数据项组成,这些数据项称为该序列的成分,且类型相同（记为CT）。串的一般操作有4种：连接首项选取尾项选取子串例：串是从所周知的序列，其成分类型为字符；顺序文件的思路也来自序列的概念17程序设计语言与编译递归定义：若数据类型T包含属于同一类型T的成份，那么类型T称为递归类型。递归类型的特点：允许在类型定义中使用被定义类型的名字指针是建立递归数据对象的重要手段18例：二叉树可通过递归类型来定义。它的左子树和右子树分别是另一棵二叉树。程序设计语言与编译5.判定或定义：判定或是一个选择对象结构的构造机制,规定在两个不同选择对象之间作出适当的选择;每一选择对象结构称为变体。19例如：PASCAL和ADA中的变体记录;C和ALGOL68中的联合。程序设计语言与编译结构、共用体举例namenumtypeScoresituationchen0000012teacherHardworkingZhang2000112student90,88,99,8920程序设计语言与编译21结构、共用体举例Struct{ charname[10];Int

num;Chartype[8];Union{ float

score[10];Charsituation[40];}state;}person[2];程序设计语言与编译6.幂集定义：类型T的元素所有子集的集合，称为幂集,记为Powerset(T),T称为基类型。幂集类型的操作：由于具有该类型的变量的值是一个子集，因此它们的基本操作是集合的操作，比如：联合、与、以及测试某个元素是否在一个集合中等。22程序设计语言与编译小结杂的数据对象（新的类型）；可读性（选择名字）可修改性（不修改变量说明）可分性（重复使用）一致性检查例如：struct

{double:radius;double

angle;}complex

c1,

c2,

c3;例如：struct

complex{double:radius;double

angle;}complex

c1,

c2,

c3;23struct

student{

char

name[48];1.程序语言允许程序员以上六种机制in来t

定age义;

复…新的类型可以通过非显式的方};式说明；也可通过显式的方式说明；显示定义有如下优点：程序设计语言与编译可分性可分性概念用得比较普遍，C语言的函数就使用了可分性。把程序中相同的代码“分离”出来，用一个名字来标识，待使用这段代码时，通过该名字调用该段代码即可。程序设计语言与编译内容回顾2.数据类型1.编译时-源程序3.活动记录2.运行时-代码段+活动记录4.别名、副作用1.程序单元1.值的集合+操作的集合2.六种数据类型聚合方式笛卡尔积25有限映射序

列递

归幂

集判

定

或记录、结构数组字符串、顺序文件二叉树联合、变体记录集合程序设计语言与编译1.非结构类型内部类型integer,real,boolean,char有序类型定义新的有序类型的方法枚举型子界型其值不能直接读/写动态检查范围第四节P例A：SCAL语言数据类型结构type

day=(sunday,monday,tuseday,wednesday,thursday,friday,saturday); //枚举type

work_day=monday..friday;//子界var

class_day:work_day;每一元素都有cl唯ass一_d的ay前:=驱su和cc后(cl继ass_day);//后继如:整型,布尔…型…,字符型26构造的一般形式为：array[t1]

of

[t2]元素（值域）的类型；程序设计语言与编译2.聚合构造下标（定义域）的类型；1)数组构造构造符ARRAY允许程序员定义有限映像；数组注意：PASCAL把下标类型不同的数组看成不同的类型typea1=array[1..50]

ofinteger;typea2=array[1..70]

ofinteger;?×=27程序设计语言与编译产生严重问题， 使得形式参数定义的数组和实际参数的数组类型不一致；例：pr!ocedure

sort(var

a:a这rr样ay定[lo义w.的.hi数gh组:in类te型ge会r]of

ctype);解决办法：引入符合数组概念--维数相同，成分类型相同的数组；符合数组可以形、实参数匹配。28var

i:integer;more:boolean;begin

{sort}……end

{sort}程序设计语言与编译2)记录构造构造符RECORD用以定义笛卡尔积，一般形式为：Record

field_1:type_1;field_2:type_2;…field_n:type_n;end记录可以整体访问，也可用圆点“.”作为选择符访问单个的域；假设t，p是前面定义的多边形

t.no_of_edges:=3;t.edge_size:=7.53;p:=t;29程序设计语言与编译标识符域available，记录的判定成分PASCAL例的如变，体如记果录i1和i2被说明变，体则记可录对ite它m们进行如下操作：type

dept=(housvea,rspio1r,it2s:i,tdemru:gs,food,liquor);30month=1..1…2;…item=recorid1.price:=5.24;price:real;casie1.aavvaaiilalbalbel:e=:trbuoeo;lean

ofi1.atmruoeu:n(ta:=mo2u9n;

t:integer;

where:dept);i2.available:=false;i1.wfahlesree::=(lmiqountohr;_expected:month)

end;

i2.price:=324.99;注意：PASCAL允许程序员访问记录结构的所有域，包括标识符域i2。.month_expect:=8;程序设计语言与编译程序的执行结果5.24true29liquorpriceavailableamountwherei1priceavailablemonth_expected324.99false8i231程序设计语言与编译使用变体记录不安全可以对变体赋值可以改变变体标识符标识符域的标识符可省缺变体记录的特点改变一个变体记录的标识符，在概念上建立了一个新记录；变体记录在同一块存储区上重叠存放所有变体；变体记录允许程序员根据每个变体的类型，以不同的观点来解释存储在该区域中的位串；record

price:realcase

boolean

ofPASCAL变体记录的缺点

true:(amount:integer;

where:dept);false:(mouth_expected:month)end32程序设计语言与编译3)集合构造PASCAL语言的SET构造符是幂集构造受限制的形式，基类型只能是有序类型，而不能是实数、集合类型。例:type

vegetable=(bean,cabbage,carrot,celery,lettuce,onion,mushroom,zucchizi);var

my_salad,leftover:set

ofvegetable;33程序设计语言与编译4)

文件构造PASCAL文件是任意类型的诸元素的序列；例:type

patterGne=tr操ec作or把d

下…一en个d;

元素读到缓冲区

tape=file

ofpattern;var

t1,t2:tape;PASCAL文件仅能顺序处理；只能进行

PUT

和

GET 操作；put操作把缓冲区中的元素附加到文件末尾34程序设计语言与编译3.指针指针是PASCAL的第三类数据类型，是非结构的，可用来构造递归结构；指针可引用匿名数据对象，这类对象由建立语句NEW显示分配在堆上；空指针nil的使用；指针的操作:赋值,比较(相等或不等)

PASCAL指针只能指向匿名数据对象，不能指向在栈上分配的的单元35程序设计语言与编译36指针例子type

tree_ref=

binary_tree_node;binary_tree_node=recordinfo:char;left,right:tree_refend;pointer=

node;node=recorddata:integer;next:pointerend;程序设计语言与编译Pascal类型非结构类型指针类型

(递归)结构类型内部类型整型实型

字符型布尔型枚举类型子界类型记录类型(迪卡尔积)变体记录(判定或)数组集合37文件4.小结程序设计语言与编译第六节C语言数据类型结构1.非结构类型：分为内部类型和用户自定义类型非结构内部类型有整型、实型和字符型类型类型标志符数值范围占用字节数基本型int-32768

327672短整型Short-32768

327672长整型Long-231

(231-1)4无符号整型Unsigned0

655352无符号短整型Unsignedshort0

655352无符号长整型Unsignedlong0

(232-1)438程序设计语言与编译实型又称浮点型，其值是实数的一个子集，分为单精度和双精度两种类型浮点型数据类型的特性DF数能的点节类型类型标志符用字数表示数值有效位值范围阶的范围单精度型loat47-1038~1038-38~38双精度型ouble815~16-10308~10308-308~308字符型数据的值是一个有限字符集的元素；在C语言中，int类型与char类型在存储中没有本质区别；注意：C语言中没有布尔（bool)类型；0表示false，非

0表示true。39程序设计语言与编译或用户自定义的非结构类型（1）定义了一个用户自定义的非结构类新型类在型C语bo言ol中称为枚举类型（enum）enum

bool

{false,

true};（2）bool数据类序：

false<true（3）定义ty了pe一de个f

顺enum

{false,

tr（ue4}型）b的可oo取对l;值这为个f类al型se40的变和量tr进ue行赋值和比较等操作enum

bool

{false,

true};bool

b;b

=

true;if(b

==

true)

{……}程序设计语言与编译2.

聚合构造（1）数组实现有限映像说明的格式<类型说明符>

<数组名>

[常量表达式]例如：int

intarr[5];char

chararr[255];bool

boolarr[3];注意：C语言中数组的下标总是从0开始。41程序设计语言与编译可以定义多维数组说明的格式<类型说明符>

<数组名>

[常量表达式]…[常量表达式]例如：float

farr[3][4];char

c[2][2][2];数组a[3][4]的存放次序为：a[0][0]

a[0][1]

a[0][2]

a[0][3]a[1][0]

a[1][1]

a[1][2]

a[1][3]a[2][0]

a[2][1]

a[2][2]

a[2][3]C语言的数组按行存放对数组名的处理相当于指针int

a[10];int

*pa;pa

=

a;42程序设计语言与编译（2）结构C语言中构造符struct支持笛卡尔积说明的格式stru成员表列<类型ct

<结构体名>

{成员表列}；由若干个成员类型说明组成：标识符>

<成员名>；例如：struct

student

{int

num;char

name[2];char

sex;int

age;float

score;char

addr[30];}43程序设计语言与编译注意：C语言中结构不能整体赋值和输出，只能对其中的各个成员分别进行操作。在内存中，结构的各成员依次存放；结构体可以嵌套；44例如：struct

student

me,

you;strcpy(,

“john”);me.sex

=

‘M’;me.age

=

21;me.score

=

80;strcpy(me.addr,

“UESTC”);程序设计语言与编译（3）联合C语言中构造符union（联合）支持判定或联合结构举例：union

data

{int

i;char

c;float

f;}union

data

a,b,c;a.i

=

2;45a.c

=

‘s’;a.f

=

3.14;C语言中联合中没有标识符域；单元中的值的类型，取决于程序员的使用；程序设计语言与编译（4）文件C语言中文件是一个字符序列；

分为ASCII码文件和二进制文件；C语言中文件的预定义格式如下：typedef

struct

{int

_fd;int

_cleft;int

_mode;char

*_next;char

*_buf;}

FILE;文件名缓冲区中剩下的字符数文件操作模式下一个字符指针缓冲区指针46程序设计语言与编译3.

指针C语言中的指针是第三种数据类型，是非结构类型；；可用来构造结构类型支持递归；利用指针定义递归结构的例子：struct

tree

{char

day;struct

tree

*lchild;struct

tree

*rchild;};struct

tree

*my_tree;47程序设计语言与编译空类型C语言中有一种特殊的数据类型void，称为空类型；是一种非结构类型；有两个主要用途：用来表示一个无返回值的函数用来表示不确定类型的指针例：void

main例()如{：void

*p;int

i;

表示这是一个指针，它的值i

=

1;

是一个地址，但不指明p指向的值是什么类型。}48程序设计语言与编译5.

C数据类型小结C数据类型非结构型结构型指针类型

(递归)数组类型联合类型（判定或（有限映象）结构类型（笛卡尔积）（文件）（序列）空类型内部类型 枚举类型整型 实型 字符型单精度型双精度型49程序设计语言与编译50第八节抽象数据类型用户定义类型与内部类型的异同都建立某种基本表示的抽象内部类型:对二进制位串的抽象；用户定义类型:对内部类型和已定义的用户定义类型的数据作为基本表示的抽象每一类型都关联一组操作内部类型隐蔽了基本表示，不能对它的成分进行操作;用户定义类型具有更高级别的抽象，可以对其基本表示的成分进行操作。能不能仿照内部类型，隐藏用户自定义类型的内部信息？程序设计语言与编译512.抽象数据类型的定义满足下述特性的用户定义类型称为抽象数据类型:①

在实现该类型的程序单元中,建立与表示有关的基本操作;②

对使用该类型的程序单元来说,该类型的表示是隐蔽的。3.

在描述实现的程序单元中进行修改1.

对象的表示是被保护的，外界不能对它进行直接操作2.

隐蔽了表示的细节，通过过程来访问抽象数据对象程序设计语言与编译521.

SIMULA 67的类机制2. CLU的抽象数据类型-簇3. Ada的抽象数据类型4. Modula-2的抽象数据类型程序设计语言与编译class<类名>{

private:私有段数据定义；私有段函数定义；protected:保护段数据定义；保护段函数定义；public:公有段数据定义；公有段函数定义；}C++语言类定义的一般形式5. C++语言的抽象数据类型C++语言中的抽象数据类型称为类（class），类的实例称为对象（object）；53C++的类满足抽象数据类型的条件（1）和（2）?程序设计语言与编译54类的实例是对象，对象继承类中的数据和方法封装、继承、多态C++支持重载和多态C++的继承性通过派生类来实现虚函数、抽象类程序设计语言与编译第九节类型检查语言按类型可分为 无类型语言

、 弱类型语言

和强类型语言；对数据对象的类型和使用的操在作编是译否时匹进行配的的检一查致性检查称为类型检查；语言的类型检查分为静态检查（staticchecking）和动态检查（dyna语m言ic的c类he型c检ki查ng不）能;全部在编译时完静态检查使程序成更，正有确些更要有在效运行时才能完成动态检查在使运编行程时方进便行,的但检影查响了可读性,且降低了执55语言的没行类有效型类率检型查定全义部在编译时完成程序设计语言与编译④

Pascal没有严格规定类型的一致性规则frocedure

who_knows(i,j:integer;pr);var

k:boolean;p

ocedure如:

a:=b+c;56且a、b、c均属于子界类型1..10begin

k:=j<i;if

k

then

f(k)

else

f(j)end;PASCAL是非强类型语言理由：①

编译时,不能确定一个过程中的过程参数和子程序参数类型②

Pascal的子界类型不能静态检查③

变体记录的标识符可以在运行时改变程序设计语言与编译第九节类型转换将一个类型的值转换成另一个类型的值，称为类型转换；类型转换分为拓展（widening）和收缩（narrowing）；转换之后的类型值的集合包含转换之前的编译器整自型动→生实成型类型转换的代码；类型值的集转合换；之例前如的：类型值的集合包含转换57在某些语言之中后，的类类型型值转的换集的合要；求例和如规：则是隐式的，它由实型→整型一般来说，语言对基本类型提供适当的类型转换，而对复合类型或用户自定义类型不提供转换；截断舍入法程序设计语言与编译一些语言规定的转换规则：①

FORTRAN语言：转换规则隐式给出；转换规则根据类型和类型之间的优先级来确定；由低级类型向高级类型转换；FORTRAN的类型优先级为：COMPLEX>DOUBLE

PRECISION>REAL>INTEGER②

PASCAL语言：只允许整数到实数，以及子界类型到整数的转换；其他的转换必须显示处理var

r:real;i:integer;i:=r;？应写为var

r:real;i:integer;i:=round(r);58程序设计语言与编译③

ALGOL

68语言：完全的、形式化的隐式转换规则；它一共给出6种隐式转换规则；④

Ada语言：必须显示转换；59程序设计语言与编译隐式转换发生在下述的情况下：混合运算：级别低的类型向级别高的类型值转换将表达式的值赋给变量：表达式的值向变量类型的值转换。实参向函数形参传值：实参的值向形参的值进行转换。函数返回值：返回值向函数返回类型的值进行转换。注意语言规定的转换规则程序设计语言与编译第十节类型等价若T1和T2是两个类型，T1的任何值都可以赋予T2类型的变量，反之亦然，T1类型的实参可以对应类型T2的形参，反之亦然，则称T1和T2是相容的，或等价的；61程序设计语言与编译第十节类型等价有两种类型的相容性概念：①名字等价:两个变量的类型名相同62struct

RecA{

char

x;int

y;};typedef

struct

RecA

RecA

;struct

RecA

a;RecA

b;struct

RecA

c;struct{

char

x;int

y;}d;a和c是名字等价，b和d与其他任何变量都不是名字等价。struct{

char

x;int

y;}d，e;struct{

char

x;int

y;}

d;struct{

char

x;int

y;}

e;程序设计语言与编译不等价第十节类型等价有两种类型的相容性概念：②结构等价两个变量的类型具有相同的结构。63struct

Rec1{

char

x;int

y;char

z[10];};struct

Rec2{

char

x;int

y;char

z[10];};struct

Rec3{int

y;char

x;char

z[10];};Rec1和Rec2是结构等价，

Rec1和Rec3不是结构等价。struct

Rec1{

char

x;int

y;}；struct

Rec2{

char

a;int

b;}；程序设计语言与编译64第十节类型等价两种相容性实现时的比较①名字等价的实现比较简单②结构等价的实现需要的模式匹配过程可能十分复杂程序设计语言与编译第十一节实现模型在实现模型中，数据用描述符和数据对象来表示；描述符用来描述数据对象的所有属性只考虑原理性的实现，不考虑效率以PASCAL语言为例描述符:描述数据对象的所有属性数据数据对象(存储区及其值)65程序设计语言与编译整数变量的表示integer描述符

数据对象real66内部类型和用户定义的非结构类型的实现模型描述符一般由“类型”和一个指针组成实型变量的表示描述符 数据对象子界的描述符必须包括子界的界值布尔型和字符型可以压缩存储程序设计语言与编译67结构类型的实现模型笛卡尔积各成分顺序排列（数据）描述符包含:类型名、构造符、若干三元式。每个域对应一个三元式(选择符名,域类型,指针)每个成分占整数个可编址的存储单元(字编址或字节编址）程序设计语言与编译type

t=record

a:real；b:integer；end；数据对象浮点值定点值trecordarealbinteger描述符类型名构造符选择符类型引用

选择符类型引用域1域268程序设计语言与编译69有限映像为每一成分分配整数个可编址的存储单元描述符包括:类型名、构造符、定义域

的基类型、下界、上界、成分类型、单元个数、首地址内情向量

；程序设计语言与编译地址公式的计算若定义域类型是子界m..n，每个元素占k个存储单元，那么，按照k*(i-m)计算a[i]从首地址b到所分配的存储之间的位移。a[i]的地址可以写成b+k*(i-m）=

b-k*m+k*i

=

b'+

k*i其中，b’=b-k*m

是编译时能计算出的程序设计语言与编译例：type

a=array[1..10]

of

real;aarrayinteger110real1描述符类型名构造符基类型下界上界成分类型单元个