第05章-语义分析上课件.ppt

1、1编译原理电子教案韶关学院计算机系程细柱第第0505章章 语义分析语义分析主要内容：主要内容：.语义分析基础语义分析基础.符号表符号表.类型分析类型分析.声明和执行体的语义分析声明和执行体的语义分析2编译原理电子教案韶关学院计算机系程细柱5.1 5.1 语义分析基础语义分析基础 语义分析的内容语义分析的内容 标识符的内部表示标识符的内部表示 类型的内部表示类型的内部表示 值的内部表示值的内部表示3编译原理电子教案韶关学院计算机系程细柱5.1.1 5.1.1 语义分析的内容语义分析的内容语法和语义的区别语法和语义的区别:语法：语法：关于什么样的字符串才是该语言在组关于什么样的字符串才是该语言在组

2、 成结构上合法的程序的法规。成结构上合法的程序的法规。语义：语义：关于结构上合法的程序的意义的法关于结构上合法的程序的意义的法 则。则。4编译原理电子教案韶关学院计算机系程细柱 语义种类语义种类:静态语义：静态语义：在编译阶段能检查的语义。在编译阶段能检查的语义。动态语义：动态语义：只有在目标代码执行阶段才能只有在目标代码执行阶段才能 检查的语义。检查的语义。5编译原理电子教案韶关学院计算机系程细柱 语义分析的语义分析的内容内容：类型分析；类型分析；标识符相关信息。标识符相关信息。语义分析的功能：语义分析的功能：检查语义错误；检查语义错误；构造标识符属性表（符号表）。构造标识符属性表（符号表）

3、。语义分析的实现：语义分析的实现：与语法分析相结合。与语法分析相结合。6编译原理电子教案韶关学院计算机系程细柱5.1.2 标识符的内部表示标识符的内部表示Z 标识符种类：标识符种类：常量名、类型名、变量名、函数名、过程名、域名。常量名、类型名、变量名、函数名、过程名、域名。typedeftypedef enumenum=(=(constKind,typeKind,varKindconstKind,typeKind,varKind,procKind,funcKind,fieldKindprocKind,funcKind,fieldKind)Z 标识符属性（标识符属性（AttributeIRAtt

4、ributeIR）：）：常量：常量：consKindTypePtrKindValue类型：类型：typeKindTypePtrKind TypePtr：指类型的内部表示；指类型的内部表示；Value：常量值。常量值。TypePtr：指类型的内部表示；指类型的内部表示；7编译原理电子教案韶关学院计算机系程细柱 Access：等于等于dir(直接变量直接变量)或或indir(间接变量间接变量)；Level：表示变量所在的层数；表示变量所在的层数；Off：表示变量在过程等中的偏移量。表示变量在过程等中的偏移量。变量：变量：varKindTypePtrKindAccessLeveloff Off：表示

5、域名在记录中的偏移量；表示域名在记录中的偏移量；HostType：表示域名对应类型的内部表示。表示域名对应类型的内部表示。域名：域名：fieldKindTypePtrKindOffHostType8编译原理电子教案韶关学院计算机系程细柱 Parm：表示值参信息表地址；表示值参信息表地址；Class：为为actual时表示实在过程时表示实在过程/函数名，为函数名，为formal时表示形参过程时表示形参过程/函数名；函数名；Code：表示过程表示过程/函数的目标代码地址；函数的目标代码地址；Size：表示本过程表示本过程/函数的空间大小；函数的空间大小；Forward：为为true时表示向前声明。

6、时表示向前声明。过函：过函：routKindTypePtrKindLevel ParmClassCode Size ForwardactualroutKindTypePtrKindLevel ParmClassOffformal9编译原理电子教案韶关学院计算机系程细柱b 例，有声明如下：例，有声明如下：const const paipai=3.14;=3.14;type vector=array1.10 OF integer;type vector=array1.10 OF integer;varvar x,y:real;x,y:real;r,s:vector;r,s:vector;设当前层数

7、和可用设当前层数和可用offsetoffset值分别为值分别为L L和和0 0，构造标识符，构造标识符 paipai,vector,x,y,r,vector,x,y,r 和和s s 的属性表示。的属性表示。pai：consKindrealPtr3.14vector：typeKindaPtrx：varKindrealPtrdirL0y：varKindrealPtrdirL1r：varKindaPtrdirL2s：varKindaPtrdirL1210编译原理电子教案韶关学院计算机系程细柱符号表的符号表的C语言描述如下语言描述如下(见见p154)：Typedef enumconsKind,type

8、Kind,varKindconsKind,typeKind,varKind,fieldKind,procKind,funcKindfieldKind,procKind,funcKind idKIND;Typedef enumdir,indir AccessKIND;Typedef enumformal,acttual paramKIND;Typedef structstruct idNAME id_name;idATTRIBUTE id_attribute;/标识符属性域标识符属性域 symbolTABLE *next symbolTABLE/符号表符号表11编译原理电子教案韶关学院计算机系程

9、细柱 Typedef structstruct idTYPE*id_type;idKIND id_kind;idBODY id_body;/标识符的标识符的BODYBODY idATTRIBUTE;/标识符属性域标识符属性域 Typedef structstruct constidBODY const_id_body;/常量常量属性属性 varidBODY var_id_body;/变量变量属性属性 profunidBODY profunc_id_body;/过函过函 idBODY;/标识符的标识符的BODYBODY12编译原理电子教案韶关学院计算机系程细柱 Typedef structstr

10、uct constTYPE Const_value;constidBODY;/常量常量属性域属性域BODY Typedef structstruct AccessKIND access_mode;int var_id_level;int var_id_offset;varidBODY;/变量变量属性域属性域BODY13编译原理电子教案韶关学院计算机系程细柱 Typedef structstruct int pro_id_level;paramKIND param_kind;profuncBOX profunc_box;/过函过函BOX profuncidBODY;/过程函数名的过程函数名的BO

11、DY14编译原理电子教案韶关学院计算机系程细柱 Typedef union union structstruct paramLIST*param_list;codeADDR code_addr;int space_size;boolean forward;actual_profunc_box;/实在过函实在过函 structstruct intint Off;Off;formal_profunc_box;/形参过函形参过函 profuncBOX;/过函过函BOX15编译原理电子教案韶关学院计算机系程细柱5.1.3 5.1.3 类型的内部表示类型的内部表示(p155p155)Z 类型的种类：类型

12、的种类：标准、枚举、数组、记录、联合、指针类型等。标准、枚举、数组、记录、联合、指针类型等。TypeKindTypeKind=(=(intTy,boolTy,charTy,realTy,voidTyintTy,boolTy,charTy,realTy,voidTy,enumTy,enumTy,arrayTy,recordTy,unionTy,pointerTyarrayTy,recordTy,unionTy,pointerTy)Z 内部表示：内部表示：(TypeIRTypeIR)标准类型：标准类型：KindSizeenum:EListKindSize EList：枚举表内部表示地址；枚举表内部

13、表示地址；ElemType：数组元素类型指针；数组元素类型指针；array:ElemTypeKindSizeLowUp16编译原理电子教案韶关学院计算机系程细柱RecBodyKindSizerecord:BaseTypeKindSizePointer：RecBody：指向记录类型的域表链；指向记录类型的域表链；UniBody：指向联合类型的域表链；指向联合类型的域表链；BaseType：指针的基类型。指针的基类型。NextOffFieldNameRecBody:FieldTypeUniBodyKindSizeunion:17编译原理电子教案韶关学院计算机系程细柱b例例，有如下的类型定义：，有如

14、下的类型定义：(P158)(P158)at=array1.10 of array 1.100 of integer;at=array1.10 of array 1.100 of integer;其内部表示如下：其内部表示如下：atPtr:arrayTy1000110arrayTy1001intPty10018编译原理电子教案韶关学院计算机系程细柱rtrt=record =record x x:real:real;a a:at:at;endendutut=union =union s s:at:at;u u:rt:rt;endend其内部表示如下：其内部表示如下：recordTy1001real

15、Ptrx0atPtra1 rtPtr:unionTy1001atPtrsrtPtru utPtr:19编译原理电子教案韶关学院计算机系程细柱类型内部结构的类型内部结构的C语言描述如下：语言描述如下：Typedef structstruct int size;TypeKind type_kind;union struct intTy;struct boolTy;struct charTy;struct realTy;struct IdList*EnumBody;enumTy;struct int Low;int Up;TYPEIR*ElemType;arrayTy;struct RecBodyI

16、R*RecBody;recordTy;struct UniBodyIR*UniBody;unionTy;struct TYPEIR *BaseType;pointerTy;Type_Body;TYPEIR20编译原理电子教案韶关学院计算机系程细柱 Typedef structstruct String Name;IdList*Next IdList;/枚举表内部表示地址；枚举表内部表示地址；Typedef structstruct String FieldName;TYPEIR*FieldType;int Off;RecBodyIR *Next;RecBodyIR;/记录类型的域表链；记录类型

17、的域表链；Typedef structstruct String FieldName;TYPEIR*FieldType;UniBodyIR *Next;UniBodyIR;/联合类型的域表链；联合类型的域表链；21编译原理电子教案韶关学院计算机系程细柱5.1.4 5.1.4 运行时值的表示运行时值的表示Z非结构类型有：非结构类型有：整型、实型、布尔类型、字符类型、整型、实型、布尔类型、字符类型、枚举类型、子界类型、指针类型枚举类型、子界类型、指针类型Z有序类型：有序类型：以上类型，除以上类型，除实型实型、指针指针外外22编译原理电子教案韶关学院计算机系程细柱有序类型的常量表示：有序类型的常量表

18、示：Z 整型常量：整型常量：ord(Nord(N)=N)=NZ 布尔常量：布尔常量：ord(falseord(false)=0,)=0,ord(trueord(true)=1)=1Z 字符常量：字符常量：ord(Cord(C)=ASC(C)=ASC(C)Z 枚举常量：枚举常量：设有枚举类型设有枚举类型(D,A,B),D,A,B),则有则有 ord(Dord(D)=0,ord(A)=1,ord(B)=2)=0,ord(A)=1,ord(B)=2Z 子界常量：子界常量：设有子界类型设有子界类型C C1 1.C.C2 2,则值空间则值空间 为为 ord(Cord(C1 1).ord(C).ord(C

19、2 2)23编译原理电子教案韶关学院计算机系程细柱5.2 符号表符号表Z 标识符的作用：标识符的作用：为语义检查和代码生成提供为语义检查和代码生成提供标识符的语义信息。标识符的语义信息。声明部分：声明部分：定义了各种对象及对应的属性和定义了各种对象及对应的属性和 使用规则。使用规则。程序体：程序体：对所定义的对象进行各种操作。对所定义的对象进行各种操作。$idididnameidnameidnameidname AttributeIRAttributeIRZ 必要性必要性 TokenToken：新表新表符号表符号表（种类、类型等信息）：（种类、类型等信息）：24编译原理电子教案韶关学院计算机系

20、程细柱Z 有关符号表的操作：有关符号表的操作：添加、作用域删除、查询添加、作用域删除、查询Z 处理符号表的模块：处理符号表的模块：定义符号表数据结构定义符号表数据结构 定义符号表上的操作定义符号表上的操作Z 标识符的处理思想：标识符的处理思想：遇到定义性标识符时，在符号表中填写被定遇到定义性标识符时，在符号表中填写被定义标识符的符号项；义标识符的符号项；当遇到使用性标识符时，用该标识符查符号当遇到使用性标识符时，用该标识符查符号表求得其属性。表求得其属性。25编译原理电子教案韶关学院计算机系程细柱标识符的作用域：标识符的作用域：标识符有效的最大程序段。标识符有效的最大程序段。嵌套作用域规则：嵌

21、套作用域规则：当存在标识符的嵌套声明时，最当存在标识符的嵌套声明时，最近定义的属性为标识符的当前属性。近定义的属性为标识符的当前属性。局部化单位：局部化单位：允许有声明的程序段。允许有声明的程序段。P:P:VarVar x,y,z x,y,zVarVar x,m,n x,m,nx:=1;x:=1;m:=x+1;m:=x+1;y:=x+1;y:=x+1;x:=0;x:=0;Q:Q:26编译原理电子教案韶关学院计算机系程细柱符号表的种类：符号表的种类：全局符号表、局部符号表。全局符号表、局部符号表。符号表的操作特点：符号表的操作特点：在在声明部分，定义标识符，要加入符号表；声明部分，定义标识符，要

22、加入符号表；在表达式或语句中，使用标识符，应查表在表达式或语句中，使用标识符，应查表 查其属性；查其属性；每个标识符在其作用域结束后，要删掉该每个标识符在其作用域结束后，要删掉该 属性表项；属性表项；体现嵌套作用规则和局部化。体现嵌套作用规则和局部化。27编译原理电子教案韶关学院计算机系程细柱5.2.1 符号表查找技术符号表查找技术常用符号表查表法：常用符号表查表法：顺序查表法顺序查表法 折半查表法折半查表法 散列查表法散列查表法常用符号表结构：常用符号表结构：二叉树局部符号表二叉树局部符号表 外拉链散列式全局符号表外拉链散列式全局符号表 嵌套式全局符号表嵌套式全局符号表28编译原理电子教案韶

23、关学院计算机系程细柱一、顺序查表法一、顺序查表法 表构造法：表构造法：依次添加表元素依次添加表元素 表结构：表结构：数组、链表数组、链表 查表法：查表法：按表的顺序查按表的顺序查 PascalPascal语言描述：语言描述：SymbTable=ARRAY 0.N OF Iterm;Iterm=RECORD id:String;Attrib:AttributeIR ENDSymbTable=RECORD id:String;Attrib:AttributeIR;Next:SymbTable END 优点：优点：简单简单 缺点：缺点：查表速度慢查表速度慢 平均查表速度：平均查表速度：(N+1)/2

24、(N+1)/229编译原理电子教案韶关学院计算机系程细柱二、折半查表法二、折半查表法 数据结构：数据结构：排序的数组、链表和二叉树排序的数组、链表和二叉树 特点：特点：查表时每次比较中间关键字且速度较快查表时每次比较中间关键字且速度较快 PascalPascal语言描述：语言描述：SymbTable=RECORD id:String;Attrib:AttributeIR;Left,Right:SymbTable END例：例：数组数组 AB,BB,DA,ED,FF,GA,ZAEDBBABDAGAFFZA30编译原理电子教案韶关学院计算机系程细柱 查表速度：查表速度：loglog2 2(N+1)

25、(N+1)查表算法：查表算法：while(lowwhile(lowhigh)high)mid=(low+high)/2;mid=(low+high)/2;midvaluemidvalue=LmidLmid;if(aif(a=midvaluemidvalue)return(midreturn(mid););if(aif(a midvalue)thenmidvalue)then high=mid-1;high=mid-1;else low=mid+1 else low=mid+1 ;return(-1);return(-1);AB BB DA ED FF GA ZABB31编译原理电子教案韶关学院

26、计算机系程细柱 三、散列查表法三、散列查表法 主要思想：主要思想：定义散列函数定义散列函数,H:H:KeyWordKeyWord 0,N-1 0,N-1 特点：特点：速度最快；速度最快；关键问题：关键问题：1 1）表区不出现空单元；）表区不出现空单元；2 2）把不同的关键字散）把不同的关键字散列到表的不同位置上。列到表的不同位置上。例：例：关键字表为关键字表为AOB,BOA,EWP,LOK,NOB,NYQ,OKN,WXTAOB,BOA,EWP,LOK,NOB,NYQ,OKN,WXT，散例，散例函数定义为：函数定义为：H(sH(s)=D)=D1 1(s)+D(s)+D2 2(s)+D(s)+D3

27、 3(s)+D(s)+D4 4(s)+D(s)+D5 5(s)-33(s)-33，其，其中中D Di i(s(s)表示表示s s的的ASCASC码中第码中第i i位数字，如位数字，如:AOB:657966 OKN:797578 AOB:657966 OKN:797578 WXT:878884 WXT:878884 H(AOB)=6+5+7+9+6-33=0,H(AOB)=8+7+8+8+8-33=6 H(AOB)=6+5+7+9+6-33=0,H(AOB)=8+7+8+8+8-33=6 AOB BOA OKN LOK NOB EWP WXT NYQ01234567H(WXT)=632编译原理电

28、子教案韶关学院计算机系程细柱 散列冲突：散列冲突：如果对不同的关键字如果对不同的关键字s1s1和和s2s2有有H(s1)=H(s2)H(s1)=H(s2)，则则称为散列冲突。称为散列冲突。分类：分类：直接散列法直接散列法、再散列法再散列法(线性再散列、随机再散列、线性再散列、随机再散列、加散列码的再散列法加散列码的再散列法)和和拉链法拉链法。外拉链法的外拉链法的PascalPascal语言描述：语言描述：SymbTable=ARRAY 0.N-1 OF SubTable;SubTable=RECORD id:String;Attrib:AttributeIR;Next:SubTable END

29、第第1个子表个子表第第n个子表个子表0：N-1：33编译原理电子教案韶关学院计算机系程细柱5.2.2 符号表的局部化符号表的局部化 标识符的作用域：标识符的作用域：每个标识符都有其作用域，每个标识符的每个标识符都有其作用域，每个标识符的声明只是在其作用域内有效。声明只是在其作用域内有效。嵌套声明示例：嵌套声明示例：在在PascalPascal语言中允许过程嵌套使用，在语言中允许过程嵌套使用，在C C语语言中分程序也是可嵌套的。言中分程序也是可嵌套的。例：例：BEGIN a,b,c:real;BEGIN b,d:boolean;BEGIN t,z:string END END BEGIN a,f

30、:integer;BEGIN t,z:char END END END符号表的树型结构：符号表的树型结构：a,b,c b,d a,f t,z t,z 注：注：查表时只要从当前符号表开始按箭头方向查表即可。查表时只要从当前符号表开始按箭头方向查表即可。34编译原理电子教案韶关学院计算机系程细柱 局部化方法：局部化方法：每层声明产生一个符号表，当退出局部化单位每层声明产生一个符号表，当退出局部化单位时有两种处理：删除相应的符号表或不删除表。时有两种处理：删除相应的符号表或不删除表。分类：分类：二叉式局部符号表、散列式全局符号表、顺序式全局二叉式局部符号表、散列式全局符号表、顺序式全局符号表。符号表

31、。例例:A x:integer;b:boolean;a:char Bx:real;Ca:real;A层符号表：层符号表：xintegerb booleanacharxrealB层符号表：层符号表：arealC层符号表：层符号表：35编译原理电子教案韶关学院计算机系程细柱5.2.3 5.2.3 二叉式局部符号表二叉式局部符号表组织结构：组织结构：每个局部化单位构造一个符号表，每每个局部化单位构造一个符号表，每个符号表采用二叉树结构。个符号表采用二叉树结构。实现方法：实现方法：用栈用栈(Scope)Scope)来保存活跃的局部化单来保存活跃的局部化单位的符号表地址。位的符号表地址。36编译原理电子

32、教案韶关学院计算机系程细柱局部化实现原理：局部化实现原理：n 进入局部化区：进入局部化区：创建一个新的空符号表，其地址压创建一个新的空符号表，其地址压 入入scopescope栈；栈；n 遇定义性标识符：遇定义性标识符：其属性加入当前栈顶符号表中；其属性加入当前栈顶符号表中；n 遇使用性标识符：遇使用性标识符：从栈顶符号表依次往下查找；从栈顶符号表依次往下查找；n 退出局部化区：退出局部化区：删掉栈顶符号表。删掉栈顶符号表。例例1：BEGIN a,b,c:real;BEGIN b,d:boolean;BEGIN t,z:string END END BEGIN a,f:integer;BEGI

33、N t,z:char END END END符号表的结构：符号表的结构：scope栈栈符号表符号表a b cb dt z37编译原理电子教案韶关学院计算机系程细柱 符号表局部化示例：符号表局部化示例：1 BEGIN A:integer；2 BEGIN A:real;3 BEGIN A:boolean;A:=false END;A:=0.55;END;A:=100 END分程序分程序3声明时：声明时：A:boolean A:real A:integer210分程序分程序3退出时：退出时：A:real A:integer10 简单评价：简单评价：对于局部符号表采用散列法末必合适，而采对于局部符号表

34、采用散列法末必合适，而采用二叉树方法可能更好些。用二叉树方法可能更好些。38编译原理电子教案韶关学院计算机系程细柱5.2.4 散列式全局符号表散列式全局符号表 组织结构：组织结构：整个程序用一个符号表，采用外拉链散列表。整个程序用一个符号表，采用外拉链散列表。符号表系统：符号表系统：1)1)全局散列表；全局散列表；2)2)一组外拉链子表。一组外拉链子表。局部化局部化实现原理：实现原理：n 给每个局部化单位定义唯一编号给每个局部化单位定义唯一编号n n；n 同名标识符被登记到同一拉链表中；同名标识符被登记到同一拉链表中；n 拉链表中的每个标识符带有相应的局部化编号；拉链表中的每个标识符带有相应的

35、局部化编号；n 深层标识符靠近拉链表的前端。深层标识符靠近拉链表的前端。39编译原理电子教案韶关学院计算机系程细柱例例2：1 BEGIN A:integer；2 BEGIN A:real;3 BEGIN A:boolean;A:=false END;A:=0.55;END;A:=100 ENDA(3)A(2)A(1)40编译原理电子教案韶关学院计算机系程细柱5.2.5 嵌套式全局符号表嵌套式全局符号表 组织结构：组织结构：整个程序一个表，采用线性组织方式，用栈记录整个程序一个表，采用线性组织方式，用栈记录每个局部化单位符号表的头地址。每个局部化单位符号表的头地址。具体实现：具体实现：n 进入局

36、部化单位：进入局部化单位：登记符号表头地址；登记符号表头地址；L:=L+1;L:=L+1;ScopeLScopeL:=top;:=top;n 定义性标识符：定义性标识符：登记标识符属性到符号表中；登记标识符属性到符号表中；n 使用性标识符：使用性标识符：从本层依次往下查；从本层依次往下查；n 退出局部化单位：退出局部化单位：关闭本层符号表；有关闭本层符号表；有删除式删除式和和保留式保留式两种处理方式，见下页：两种处理方式，见下页：41编译原理电子教案韶关学院计算机系程细柱删除式和保留式：删除式和保留式：1)1)删除式：删除式：top:=top:=ScopeLScopeL;L:=L-1;L:=L

37、-1;2)2)保留式：保留式：L:=L-1;L:=L-1;scope栈栈符号表符号表Top：10图图1：符号表：符号表scope栈栈符号表符号表Top：0图图2：删除式：删除式scope栈栈符号表符号表Top：0图图3：保留式：保留式42编译原理电子教案韶关学院计算机系程细柱 嵌套式全局符号表例：嵌套式全局符号表例：Proc P()VAR i,j,k:int；Proc Q()VAR x,y:real;Proc R()VAR a,b:bool;BEGIN END BEGIN END Proc S()VAR c,e:char;BEGIN END BEGIN END k:int j:int i:in

38、t y:real x:real a:bool b:boolscope栈栈符号表符号表top21043编译原理电子教案韶关学院计算机系程细柱5.2.6 5.2.6 符号表界面函数符号表界面函数 创建空符号表创建空符号表(CreateTable)PROCEDURE CreateTable();BEGIN L:=L+1;top:=top+1;ScopeL:=top;Off:=initOff END 作废一个符号表作废一个符号表(DestroyTable)PROCEDURE DestroyTable();BEGIN top:=ScopeL;L:=L-1 END 登记符号表登记符号表(Enter)PRO

39、CEDURE Enter(id:String;Atrrib:AttributeIR;VAR Entry:SymbTable;VAR Present:Boolean)注：注：如果如果Present为为false，则，则登记登记id和和Atrrib，返回登记项，返回登记项地址于地址于Entry。44编译原理电子教案韶关学院计算机系程细柱 寻找表项地址寻找表项地址(FindEntry)PROCEDURE FindEntry(id:String;Flag:(One,Total);VAR Entry:SymbTable;VAR Present:Boolean)注：注：查查id登记项地址于登记项地址于En

40、try，如果，如果Presen为为false，表示，表示没找到；其中没找到；其中One、Total分别表示当前表或整个表。分别表示当前表或整个表。查询属性查询属性(FindAttrib)PROCEDURE FindAttrib(Entry:SymbTable;VAR Atrrib:AttributeIR）设置属性设置属性(SetAttribFied)PROCEDURE SetAttribFied(Entry:SymbTable;FieldName:String;FieldValue:FieldIR）注：注：将域值将域值FieldValue赋给表赋给表项地址项地址Entry处的属性域处的属性域FieldName。