第六章 语义分析(3).pptx

《第六章 语义分析(3).pptx》由会员分享，可在线阅读，更多相关《第六章 语义分析(3).pptx（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 语义分析语义分析l6.1 语义分析概述语义分析概述l6.2 符号表符号表l6.3 类型的语义分析类型的语义分析l6.4 声明的语义分析声明的语义分析l6.5 程序体的语义分析程序体的语义分析l6.6 属性文法和动作文法属性文法和动作文法内容回顾l什么是语义分析什么是语义分析?建立符号表建立符号表;检查语义错误检查语义错误;l在何处进行分析在何处进行分析?声明部分声明部分 -建立符号表；检查建立符号表；检查“重复声明重复声明”错误错误;体部分体部分 -查找符号表，检查查找符号表，检查“有使用无声明有使用无声明”错误和错误和类型相关的错误类型相关的错误;l怎样进行语义分析怎样进行语义

2、分析?属性文法属性文法动作文法动作文法基于语法树的语义分析基于语法树的语义分析;6.3 类型的语义分析l基本概念基本概念类型等价性类型等价性类型相容性类型相容性l类型的语义分析分析什么类型的语义分析分析什么?l在何处分析在何处分析?l怎样分析怎样分析?6.3 类型的语义分析l类型等价性类型等价性按名等价按名等价按结构等价按结构等价typedef int T110;typedef int T210;T1 a,b;T2 c,d;6.3 类型的语义分析l类型相容性类型相容性具体的编译器定义不同具体的编译器定义不同;常见的三种相容性常见的三种相容性l操作分量相容操作分量相容l赋值相容性赋值相容性l形参

3、和值参相容性形参和值参相容性6.3 类型的语义分析l类型的语义分析分析什么类型的语义分析分析什么?建立类型的内部表示建立类型的内部表示;检查类型定义中的语义错误检查类型定义中的语义错误;l在何处进行语义分析在何处进行语义分析?类型声明类型声明 变量声明变量声明参数声明参数声明类类Pascal语言的抽象语法树语言的抽象语法树 类型声明类型声明 变量声明变量声明 过程声明过程声明 根结点根结点ProK 类型声明类型声明 TypeK 变量声明变量声明VarK 程序体程序体 StmLK 程序头程序头 PheadK 声明声明1 声明声明n 声明声明1 声明声明n 语句语句n 语句语句1 过程声明过程声明

4、1 过程声明过程声明n 语句语句n 语句语句1 形参形参n 形参形参1 过程体过程体StmLK 类C语言的抽象语法树程序程序Root节点节点 Node1节点节点 Node2节点节点 Noden节点节点 Node常量声明常量声明类型声明类型声明变量声明变量声明函数声明函数声明FunNode1FunNode1FunNode1语句语句形参声明形参声明类型的语义分析l怎样分析怎样分析?根据类型的不同，分别建立它们的内部表示根据类型的不同，分别建立它们的内部表示;l类型名类型名;l基本类型；基本类型；l枚举类型；枚举类型；l数组类型；数组类型；l结构类型；结构类型；l联合类型；联合类型；l指针类型；指针

5、类型；l递归类型递归类型6.3 类型的语义分析l类型名类型名 查找符号表，取得名字对应的内部表示查找符号表，取得名字对应的内部表示;l基本类型基本类型 由系统预定义好并存储在符号表中，可以直接引用由系统预定义好并存储在符号表中，可以直接引用NameKindTypePtrinttypeKindintPtrbooltypeKindboolPtrchartypeKindcharPtrrealtypeKindrealPtrintSizeintTySize KindboolSizeboolTyrealSizerealTycharSizecharTy6.3 类型的语义分析l枚举类型枚举类型一般形式一般形式

6、:(id1,idn)常量标识符常量标识符:(id1,intType,constKind,0)(idn,intType,constKind,n-1)建立常量标识符的内部表示建立常量标识符的内部表示;建立枚举类型的内部表示建立枚举类型的内部表示;Size Kind EList1enumTyid1 idn nil 6.3 类型的语义分析l数组类型取得数组的下界Low和上界Up;获取或建立成分类型的内部表示指针;计算数组类型的空间大小:size=sizeof(ElemTyp)(Up-Low+1)建立数组类型的内部表示;Size Kind LowUpElemTyarrayTy6.3 类型的语义分析l结构

7、体结构体对每个域名标识符，建立其类型的内部表示对每个域名标识符，建立其类型的内部表示;将所有域的指针链起来形成一个链，表示结构将所有域的指针链起来形成一个链，表示结构体体;将各个域的将各个域的size的和作为结构体的的和作为结构体的size;建立结构体的内部表示建立结构体的内部表示;Size Kind BodystructTy6.3 类型的语义分析l联合体联合体对每个域名标识符，建立其类型的内部表示对每个域名标识符，建立其类型的内部表示(每个域每个域的偏移都是的偏移都是0);将所有域的指针链起来形成一个链，表示联合体将所有域的指针链起来形成一个链，表示联合体;将将size最大的域的最大的域的s

8、ize作为联合体的作为联合体的size;建立联合体的内部表示建立联合体的内部表示;Size Kind BodyunionTy6.3 类型的语义分析l指针类型指针类型取得基类型的指针取得基类型的指针;建立指针类型的内部表示建立指针类型的内部表示;l递归类型递归类型Typedef struct treenode int val;struct treenode*left;struct treenode*right;TreeNode;方法方法:回填回填;第六章第六章 语义分析语义分析l6.1 语义分析概述语义分析概述l6.2 符号表符号表l6.3 类型的语义分析类型的语义分析l6.4 声明的语义分析声

9、明的语义分析l6.5 程序体的语义分析程序体的语义分析l6.6 属性文法和动作文法属性文法和动作文法6.4 声明的语义分析声明的语义分析l一般过程一般过程收集被声明的标识符的属性收集被声明的标识符的属性;建立被声明标识符的内部表示建立被声明标识符的内部表示;检查重复声明错误检查重复声明错误;将被声明标识符的内部表示插入符号表将被声明标识符的内部表示插入符号表;l程序设计语言的声明程序设计语言的声明 常量声明常量声明类型声明类型声明变量声明变量声明函数声明函数声明标号声明标号声明(可选可选)类类Pascal语言的抽象语法树语言的抽象语法树 类型声明类型声明 变量声明变量声明 过程声明过程声明 根

10、结点根结点ProK 类型声明类型声明 TypeK 变量声明变量声明VarK 程序体程序体 StmLK 程序头程序头 PheadK 声明声明1 声明声明n 声明声明1 声明声明n 语句语句n 语句语句1 过程声明过程声明1 过程声明过程声明n 语句语句n 语句语句1 形参形参n 形参形参1 过程体过程体StmLK 类型声明类型声明TypeK类C语言的抽象语法树程序程序Root节点节点 Node1节点节点 Node2节点节点 Noden节点节点 Node常量声明常量声明类型声明类型声明变量声明变量声明函数声明函数声明FunNode1FunNode1FunNode1语句语句形参声明形参声明6.4 声

11、明的语义分析l常量声明常量声明一般形式一般形式:#define id number内部表示内部表示:l建立建立 number值的内部表示值的内部表示;l建立建立 number类型的内部表示类型的内部表示;l建立建立 id的内部表示的内部表示;TypePtrKindValueconstKind6.4 声明的语义分析l类型声明类型声明一般形式一般形式:typedef id type;内部表示内部表示:l建立建立 type的内部表示的内部表示;l建立建立 id的内部表示的内部表示;TypePtrKindtypeKind6.4 声明的语义分析l变量声明变量声明一般形式一般形式:type id;内部表示

12、内部表示:l建立建立 type的内部表示的内部表示;l获取获取l确定存取方式确定存取方式:dir/indirl建立建立 id的内部表示的内部表示;lCurrentOffset+=sizeof(type)TypePtrKindAccessLevelOffsetvarKind6.4 声明的语义分析l函数函数/过程声明过程声明一般形式一般形式:type id(params)body 分析过程分析过程:l建立建立 type的内部表示的内部表示;lCurrentOffset=0;l建立参数的内部表示建立参数的内部表示(层数为层数为CurrentLevel+1)；l将参数内部表示链成表将参数内部表示链成表

13、;l建立建立 id 的内部表示的内部表示(层数为层数为 CurrentLevel);lCurrentLevel+;lCode属性需要等待代码生成后回填属性需要等待代码生成后回填;lSize 需要等函数的局部变量全部处理完后才能确定需要等函数的局部变量全部处理完后才能确定;TypePtrKindClassLevelParamCode Size ForwardroutKindactual6.4 声明的语义分析l标号声明标号声明不同的程序设计语言具有不同的标号处理机制不同的程序设计语言具有不同的标号处理机制;标号相关的语法结构标号相关的语法结构:l标号声明标号声明l标号定位标号定位;l跳转语句跳转语

14、句;标号相关的语义错误标号相关的语义错误l标号重复定位标号重复定位;l标号有使用无定位标号有使用无定位;lGoto语句转入结构语句语句转入结构语句,过程体过程体/函数体函数体;l标号重复声明标号重复声明;l标号有定位无声明标号有定位无声明;第六章第六章 语义分析语义分析l6.1 语义分析概述语义分析概述l6.2 符号表符号表l6.3 类型的语义分析类型的语义分析l6.4 声明的语义分析声明的语义分析l6.5 程序体的语义分析程序体的语义分析l6.6 属性文法和动作文法属性文法和动作文法6.5 程序体的语义分析l一般性检查语句中的标识符是否有声明;类型相关的语义错误;l程序体中不同元素有不同的细

15、节需要处理赋值语句条件语句循环语句函数调用语句表达式变量 6.5 程序体的语义分析l赋值语句赋值语句一般形式一般形式:var=Expression一般分析过程一般分析过程:l用用var查符号表，取得其类型属性查符号表，取得其类型属性;l计算计算 Expression结果值的类型属性结果值的类型属性;l检查检查 var 的类型和的类型和 Expression 的类型是否赋值相容的类型是否赋值相容;6.5 程序体的语义分析l条件语句条件语句一般形式一般形式:if Exp S1 else S2 一般过程一般过程:l检查检查 Exp 是否是是否是 boolean 类型类型;6.5 程序体的语义分析l循

16、环语句循环语句不同的循环不同的循环lWhile Exp S检查检查 Exp 是否是是否是 boolean类型类型;lFor i=E1 to E2 S检查检查 i、E1和和E2的类型是否兼容的类型是否兼容;6.5 程序体的语义分析l函数调用函数调用一般形式一般形式:f(E1,.,En)一般过程一般过程:l在符号表中查找在符号表中查找 f的属性的属性;l检查检查 f是不是是不是“routeKind”;l分析分析 Ei(i=1,n)的类型的类型;l检查实参的个数和形参的个数是否相同检查实参的个数和形参的个数是否相同;l检查第检查第i个实参的类型与第个实参的类型与第i个形参的类型是否兼容个形参的类型是

17、否兼容6.5 程序体的语义分析l表达式表达式检查检查“运算分量是否类运算分量是否类型相容型相容”;求表达式的结果类型求表达式的结果类型;求表达式的种类求表达式的种类l数据数据l地址（指针）地址（指针）l过程过程/函数函数x *(f(5)+ai )(1)在符号表中查找在符号表中查找 x；(2)x:(t1,varKind,L1,off1,dir)(3)在符号表中查找在符号表中查找 f；(4)f:(t2,routeKind,L2,paramL,)(5)在符号表中查找在符号表中查找 a(6)a:(t3,varKind,L3,Off3,indir)(7)检查检查 t3 是否是数组类型是否是数组类型arr

18、ayType;(8)检查检查 t2 是否和是否和 t3.elemTy 加运算加运算“+”兼容兼容;如果兼容，则得到如果兼容，则得到(result type t,种类种类1);(9)检查检查 t1 和和 t 是否是否 乘运算乘运算“*”兼容兼容;如果兼容，则得到如果兼容，则得到(结果类型结果类型t，种类，种类c)(10)Return(t,c)6.5 程序体的语义分析l变量变量一般形式一般形式:V id|VExp|V.id|*V标识符情形标识符情形(id):l查找符号表取得查找符号表取得id的属性：的属性：(type,种类种类)；数组下标变量数组下标变量VExp:l检查检查V的种类是否是的种类是否

19、是arrayKind？l表达式表达式Exp 的类型与的类型与V的下标类型是否一致？的下标类型是否一致？l返回返回(ElemType,种类种类)；6.5 程序体的语义分析l变量变量结构结构/联合的域名联合的域名V.id:l检查检查V的种类是否是结构体或联合体？的种类是否是结构体或联合体？lid是否是是否是V的一个域？的一个域？l返回返回(fieldType,种类种类)*V:l检查检查V的种类是否是指针的种类是否是指针pointTy？l返回返回(BaseType,种类种类)Some Issuesl符号表常量声明常量声明向符号表中添加常量标识符；向符号表中添加常量标识符；类型声明类型声明向符号表中添

20、加枚举常量标识符向符号表中添加枚举常量标识符;向符号表中添加枚举类型标识符；向符号表中添加枚举类型标识符；enumother向符号表中添加类型标识符向符号表中添加类型标识符;变量声明变量声明向符号表中添加变量标识符向符号表中添加变量标识符;函数声明函数声明 -function id -parameters -declaration -statements向符号表中添加函数标识符向符号表中添加函数标识符;向符号表中添加各个参数向符号表中添加各个参数;向符号表中添加局部标识符向符号表中添加局部标识符;查找符号表查找符号表;l层数 和 偏移量 (L,Off)常量声明常量声明(L,Off)类型声明类型

21、声明(L,Off)(L,Off+sizeof(type1)变量声明变量声明type1 x1;typen xn;(L,Off+sizeof(type1)+sizeof(typen)函数声明函数声明 -function id -(ti a1,tm am)-declaration -statements(L,Off+sizeof(type1)+sizeof(typen)(L+1,0)(L+1,sizeof(t1)+sizeof(tm)(L,Off+sizeof(type1)+sizeof(typen)(L,Off)练 习l在下列程序的红点处填上（在下列程序的红点处填上（Level,Offset）信息

22、，）信息，假设在假设在0点的信息为点的信息为(L,Off)。typedef struct char name30;int age;Student;Student Lee;int i;int GetAge(Student S)return S.age;void SetAge(int i)Lee.age=i;void main()student Lee;SetAge(10);int i=20;Lee.age=i;int j=30;Lee.age=i;1234567891011121306.6 属性文法和动作文法属性文法和动作文法l如何形式描述静态语义和实现静态语义分析呢如何形式描述静态语义和实现静

23、态语义分析呢?l语法制导的方法语法制导的方法(Syntax directed methods)属性文法属性文法=CFG+属性属性,由由Knuth引入并被广泛使用引入并被广泛使用;动作文法动作文法=CFG+动作动作,由金成植教授引入由金成植教授引入;l属性文法和动作文法可以被自动实现，实现程序称属性文法和动作文法可以被自动实现，实现程序称为语义分析器为语义分析器;Attribute Grammar(属性文法)l概述概述在在CFG的基础上的基础上,描述静态语义描述静态语义(相关属性相关属性);一种规范定义一种规范定义(specification);广泛应用静态语义描述、程序转换广泛应用静态语义描述

24、、程序转换、程序分析、程序分析、数据流分析等领域数据流分析等领域,是一种非常有用的抽象描述是一种非常有用的抽象描述方式方式;l在编译器中的应用在编译器中的应用语义检查语义检查代码生成代码生成l一个例子一个例子Attribute Grammar(属性文法)l主要思想主要思想给定一个上下文无关文法给定一个上下文无关文法 G第一步：根据需要，为它的符号第一步：根据需要，为它的符号(非终极符和终极非终极符和终极符符)定义一些属性定义一些属性l属性可以根据需要选定，如值，类型，语法树，代码等属性可以根据需要选定，如值，类型，语法树，代码等第二步：对每个产生式，定义其中符号的属性的计第二步：对每个产生式，

25、定义其中符号的属性的计算规则算规则;属性文法的例子符符号号属性定义属性定义产生式产生式属性计算规则属性计算规则Etype,class E1 E2+Tif(E2.type=T.type)then E1.type=E2.type;E1.class=Data else error;Ttype,classE TE.type=T.type;E.class=T.classFtype,classT1 T2*F if(T2.type=F.type)then T1.type=T2.type;T1.class=Data else error;ntype,classT FT.type=F.type;T.class=

26、F.classidtype,classF idF.type=id.type;F.class=id.class+*F nF.type=n.type;F.class=n.class()F (E)F.type=E.type;F.class=E.classEET+10FTF*aFb(int,data)(int,data)(int,data)(int,data)(int,data)(int,data)(int,data)(int,data)(int,data)(int,data)Action Grammar(动作文法)l主要思想主要思想给定一个上下文无关文法给定一个上下文无关文法G;在在G的产生式右部的

27、适当位置插入一些动作符的产生式右部的适当位置插入一些动作符;每个动作符相当于一个函数或过程每个动作符相当于一个函数或过程;l动作文法的定义依赖于语法分析方法动作文法的定义依赖于语法分析方法;l例子例子:输入一个由输入一个由0、1和和a构成的字符串，统计其中构成的字符串，统计其中0和和1的个数的个数LL(1)分析的动作文法VT=0,1,aVN=S,LS=SP:S L L 0 L L 1 L L a VT=0,1,aVN=S,LS=SP:S L L 0 L L 1 L L ainit()sum0=0;sum1=1;add1()sum1+;print()printf(sum0,sum1);add0(

28、)sum0+;LL动作文法的工作过程VT=0,1,aVN=S,LS=SP:(1)S L (2)L 0 L (3)L 1 L (4)L a 分析栈分析栈输入串输入串动作动作S01a#推导推导(1)L 01a#sum0=0;sum1=0;L 01a#推导推导(2)0 L 01a#匹配匹配 L 1a#sum0=1;L 1a#推导推导(3)1 L 1a#匹配匹配 L a#sum1=1L a#推导推导(4)a a#匹配匹配#“1,1”#接受接受LR分析的动作文法VT=0,1,aVN=S,LS=SP:S L L 0 L L 1 L L a VT=0,1,aVN=S,LS=SP:S L L D L D 1

29、D 0 L ainit()sum0=0;sum1=1;add1()sum1+;print()printf(sum0,sum1);add0()sum0+;LR动作文法的工作过程VT=0,1,aVN=S,LS=SP:(1)S L (2)L D L (3)D 1 (4)D 0 (5)L a符号栈输入串动作sum0=0;sum1=001a#shift01a#Reduce(4)D 1a#sum0=1D1a#ShiftD1a#Reduce(3)DDa#sum1=1DDa#ShiftDDa#Reduce(5)DDL#Reduce(2)DL#Reduce(2)L#Reduce(1)S#Accept 描述表达式

30、计算的动作文法(1)E1)E T T(2)E(2)E T+T+E E(3)T(3)T F F(4)T(4)T F*T F*T(5)5)F F n n(6)6)F F(E)(E)初始初始:栈栈v v为空，为空，top=0;top=0;OutOut()print(vtop()print(vtop）add()vtop-1=vtop-1+vtopadd()vtop-1=vtop-1+vtop；top=top-1top=top-1mult()vtop-1=vtop-1*vtopmult()vtop-1=vtop-1*vtop；top=top-1top=top-1push()top=top+1;vtop=

31、val_lexpush()top=top+1;vtop=val_lex描述生成表达式抽象语法树的动作文法(1)E1)E T T(2)E(2)E T+T+E E(3)T(3)T F F(4)T(4)T F*T F*T(5)5)F F n n(6)F(6)F id id(7)F(7)F(E)(E)makenodemakenode(ope)(ope)new(newnode);new(newnode);*newnode.kind=ope;*newnode.kind=ope;*newnode.son1=stop-1*newnode.son1=stop-1*newnode.son2=stop;*newno

32、de.son2=stop;pop(s,2);pop(s,2);push(newnode,s);push(newnode,s);makeleafmakeleaf(class,seman)(class,seman)new(newnode);new(newnode);*newnode.kind=class;*newnode.kind=class;*newnode.val=seman;*newnode.val=seman;push(newcode,s);push(newcode,s);第六章 总结l语义分析的主要功能语义分析的主要功能l关于符号表关于符号表建立符号表的目的建立符号表的目的;标识符、类型

33、、值的内部表示标识符、类型、值的内部表示;理解变量的层数、偏移量的含义理解变量的层数、偏移量的含义;理解标识符的作用域的概念理解标识符的作用域的概念;掌握符号表的组织技术掌握符号表的组织技术;l掌握在语义分析时建立符号表的技术掌握在语义分析时建立符号表的技术向表中添加一个新的表项向表中添加一个新的表项;检查重复声明错误检查重复声明错误;获取标识符的属性，检查无声明的错误获取标识符的属性，检查无声明的错误;第六章总结l程序中不同语法结构语义分析的主要任务程序中不同语法结构语义分析的主要任务声明部分声明部分l常量常量Constantl类型类型Typel变量变量Variablel函数函数/过程过程Function/procedure体部分体部分l语句语句Statementsl表达式表达式Expressionsl变量变量variablesl了解属性文法和动作文法的主要思想了解属性文法和动作文法的主要思想