《第8章 语义分析与中间代码生成PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第8章 语义分析与中间代码生成PPT讲稿.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第8章 语义分析与中间代码生成第1页，共32页，编辑于2022年，星期一5.1 5.1 语义分析的任务语义分析的任务5.2 5.2 语法制导翻译语法制导翻译5.3 5.3 中间代码中间代码教学内容教学内容第2页，共32页，编辑于2022年，星期一词法分析，语法分析词法分析，语法分析：解决单词和语言成分的识别及词法：解决单词和语言成分的识别及词法和语法结构的检查。语法结构可形式化地用一组产生式来描和语法结构的检查。语法结构可形式化地用一组产生式来描述。给定一组产生式，我们能够很容易地将其分析器构造出述。给定一组产生式，我们能够很容易地将其分析器构造出来。来。本章要介绍的是本章要介绍的是语义分析和
2、中间代码生成技术语义分析和中间代码生成技术。程序语言中间代码目标代码程序语言中间代码目标代码翻译翻译翻译翻译第3页，共32页，编辑于2022年，星期一根据语义规则对识别出的各种语法成分析其含义，进行根据语义规则对识别出的各种语法成分析其含义，进行初步翻译，生成相应的中间代码或直接生成目标代码。初步翻译，生成相应的中间代码或直接生成目标代码。（1）确定数据类型）确定数据类型（2）语义检查）语义检查动态语义检查：在运行时刻进行动态语义检查：在运行时刻进行 静态语义检查：在编译时完成静态语义检查：在编译时完成（3）识别含义，进行真正的翻译）识别含义，进行真正的翻译5.15.1语义分析的任务语义分析的
3、任务第4页，共32页，编辑于2022年，星期一类型检查类型检查。控制流检查控制流检查，确保控制语句有合法的转向点。例如，确保控制语句有合法的转向点。例如，C语言中的语言中的break语句使控制跳离包括该语句的最小的语句使控制跳离包括该语句的最小的switch，while或或for语句。如果不存在包括它的这样的语句，则应报错。语句。如果不存在包括它的这样的语句，则应报错。静态语义检查静态语义检查第5页，共32页，编辑于2022年，星期一静态语义检查静态语义检查一致性检查一致性检查。很多情况下要求对象只能被定义一次。很多情况下要求对象只能被定义一次。例如，语言中规定一个标识符在同一作用域中只能被例
4、如，语言中规定一个标识符在同一作用域中只能被说明一次，同一说明一次，同一case语句的标号不能相同，枚举类型的元语句的标号不能相同，枚举类型的元素不能重复出现等。素不能重复出现等。相关名字检查相关名字检查。有的语言中有时规定，同一名字必须。有的语言中有时规定，同一名字必须出现两次或多次。例如，出现两次或多次。例如，Ada语言中，循环或程序块可以语言中，循环或程序块可以有一个名字，它出现在这些结构的开头和结尾，如同语句有一个名字，它出现在这些结构的开头和结尾，如同语句括号一般，编译程序必须检查它们的配对情况。括号一般，编译程序必须检查它们的配对情况。第6页，共32页，编辑于2022年，星期一实际
5、应用中比较流行的语义分析方法：实际应用中比较流行的语义分析方法：基于基于属性文法属性文法的的语法制导翻译方法语法制导翻译方法 5.25.2语法制导翻译语法制导翻译第7页，共32页，编辑于2022年，星期一附加了一组附加了一组属性属性和和运算（语义）规则运算（语义）规则的的文法文法 5.2.1 属性文法属性文法文法符号文法符号X的属性的属性t常用常用X.t来表示来表示 语义规则是根据产生式所语义规则是根据产生式所蕴涵的语义蕴涵的语义操作建立起来的，并与操作建立起来的，并与语义语义分析的目标分析的目标有关有关不同的不同的产生式产生式对应不同的语义规则对应不同的语义规则不同的不同的分析目标分析目标也
6、对应不同的语义规则也对应不同的语义规则 1.属性的表示属性的表示2.语义规则语义规则的表示的表示语义信息语义信息语义之间的关系语义之间的关系静态语义检查、符号表操作、代码生成及打印各种错误信息 第8页，共32页，编辑于2022年，星期一 非终结符非终结符E E、T T及及F F都有一个综合属性都有一个综合属性val,val,符号符号i i有一个综合属性，它的值由词法分析器提供。有一个综合属性，它的值由词法分析器提供。某些非终结符加下标是为了区分一个产生式中同一某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现非终结符多次出现语语 义义 规规 则则E E1+TE T T T1*FT F
7、F (E)F i E.val=E1.val+T.valE.val=T.val T.val=T1.val F.valT.val=F.valF.val=E.val F.val=i.lexval产生式产生式例例5.15.1第9页，共32页，编辑于2022年，星期一5.2.2 语法制导翻译的过程语法制导翻译的过程语法制导翻译：语法制导翻译：将将语义规则语义规则与与语法规则语法规则相结合，在相结合，在语法语法分析分析的过程中通过执行的过程中通过执行语义动作语义动作，计算语义属性值，从，计算语义属性值，从而完成预定的翻译工作。而完成预定的翻译工作。YaccYacc利用的就是语法制导翻译方法，它使用符号利用
8、的就是语法制导翻译方法，它使用符号$表示表示产生式左端的属性，产生式左端的属性，$n$n表示存取产生式右端第表示存取产生式右端第n n个文法符个文法符号相联的属性号相联的属性expr :expr+expr$=$1+$3;第10页，共32页，编辑于2022年，星期一自底向上语法自底向上语法制导翻译制导翻译自顶向下语法自顶向下语法制导翻译制导翻译语法制导翻译的实现语法制导翻译的实现第11页，共32页，编辑于2022年，星期一语法制导翻译分为两种语法制导翻译分为两种处理方法处理方法：（1）语法制导定义（自底向上）：）语法制导定义（自底向上）：对每个产生式编制一个语义子程序，在进行语法分析的过程对每个
9、产生式编制一个语义子程序，在进行语法分析的过程中，中，当一个产生式获得匹配时当一个产生式获得匹配时，就调用相应的语义子程序实现语，就调用相应的语义子程序实现语义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节，不必规定翻译顺序。实现细节，不必规定翻译顺序。（2）翻译方案（自顶向下）：）翻译方案（自顶向下）：在产生式右部的适当位置，插入相应的语义动作，按照分析的在产生式右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。这是一种进程，执行遇到的语义动作。这是一种动作与分析交错动作与分析交错的实现方的实现方案
10、。案。第12页，共32页，编辑于2022年，星期一输入符号串输入符号串 分析树分析树执行执行语义规则语义规则 翻译结果翻译结果翻译步骤翻译步骤（）从分析树得到描述结点属性间依赖关系的（）从分析树得到描述结点属性间依赖关系的依赖图依赖图，由依赖图，由依赖图得到语义规则的得到语义规则的计算次序计算次序（1）分析输入符号串，建立）分析输入符号串，建立分析语法树分析语法树（）进行语义规则的计算，得到翻译结果（）进行语义规则的计算，得到翻译结果 第13页，共32页，编辑于2022年，星期一5.2.3 语法制导定义语法制导定义对每个产生式编制一个对每个产生式编制一个语义子程序语义子程序在进行语法分析的过程
11、中，在进行语法分析的过程中，当一个产生式获得匹配时当一个产生式获得匹配时，就调用相应，就调用相应的语义子程序实现语义检查与翻译的语义子程序实现语义检查与翻译综合属性综合属性继承属性继承属性自底向上自底向上传传递信息递信息自顶向下（自左向自顶向下（自左向右）右）传递信息传递信息第14页，共32页，编辑于2022年，星期一 print(E.val)print(E.val)打印由打印由E E产生的算术表达式的值，可认为产生的算术表达式的值，可认为这条规则定义了这条规则定义了L L的一个的一个虚属性虚属性。L EE E1+TE T T T1*FT FF (E)F iprint(E.val)E.val=
12、E1.val+T.valE.val=T.val T.val=T1.val F.val T.val=F.valF.val=E.valF.val=i.lexval例例5.5.综合属性综合属性语语 义义 规规 则则产生式产生式第15页，共32页，编辑于2022年，星期一一个结点的综合属性值是一个结点的综合属性值是其其子结点子结点的某些属性来决的某些属性来决定的定的+3*4+3*4的注释分析树的注释分析树通常使用通常使用自底向上自底向上的分析方法的分析方法在在每个结点每个结点处使用语义规则来计处使用语义规则来计算综合属性值算综合属性值当一个当一个产生式获得匹配产生式获得匹配时，就时，就调用相应的语义子
13、程序调用相应的语义子程序从从叶结点到根结点叶结点到根结点进行计算进行计算 只含有只含有综合属性综合属性的语法制导的语法制导定义称为定义称为S S属性定义属性定义第16页，共32页，编辑于2022年，星期一5.2.5 S属性定义与自底向上翻译属性定义与自底向上翻译 LRLR分分析析器器可可以以改改造造为为一一个个翻翻译译器器，在在对对输输入入串串进进行语法分析的同时对属性进行计算行语法分析的同时对属性进行计算LRLR分析器增加分析器增加属性值（语义）栈属性值（语义）栈 第17页，共32页，编辑于2022年，星期一步步 骤骤状状 态态 栈栈符符 号号 栈栈属属 性性 值值 栈栈剩余符号串剩余符号串
14、分分 析析 动动 作作10#2+3*4#移进移进205#2+3*4#用用Fi归约归约303#F2+3*4#用用TF归约归约402#T2+3*4#用用ET归约归约501#E2+3*4#移进移进6016#E+23*4#移进移进70165#E+32*4#用用Fi归约归约80163#E+F23*4#用用TF归约归约90169#E+T23*4#移进移进1001697#E+T*234#移进移进11016975#E+T*423#用用Fi归约归约1201697 10#E+T*F234#用用TT*F归约归约130169#E+T2(12)#用用EE+T归约归约1401#E(14)#acc第18页，共32页，编辑于
15、2022年，星期一产生式产生式 enter(id.entry,L.in)语语 义义 规规 则则D TL T int T float L L1,idL idL.in=T.typeT.type=intT.type=floatL1.in=L.in enter(id.entry,L.in)例例5.35.3继承属性继承属性L.inint id1,id2,id3DL.in=intL.in=intL.in=intT.type=intintid2id1id3.，一个结点的继承属性值是一个结点的继承属性值是由其由其父结点或兄弟结点父结点或兄弟结点的的某些属性决定的某些属性决定的第19页，共32页，编辑于2022
16、年，星期一1、文法非终结符既有综合属性，也可有继承属性；、文法非终结符既有综合属性，也可有继承属性；2、开始符号没有继承属性；、开始符号没有继承属性；3、终结符只有综合属性，由词法分析器提供。、终结符只有综合属性，由词法分析器提供。几点说明：几点说明：第20页，共32页，编辑于2022年，星期一生成中间代码的生成中间代码的目的目的(1)便于优化便于优化(2)便于移植便于移植常见的中间代码常见的中间代码形式形式：后缀式后缀式三地址代码三地址代码（四元式、三元式和间接三元式（四元式、三元式和间接三元式）图形图形（抽象语法树、有环无向图）（抽象语法树、有环无向图）中间代码：一种介于中间代码：一种介于
17、源语言和目标语言之间源语言和目标语言之间的中间语言形式的中间语言形式5.5.中间代码中间代码第21页，共32页，编辑于2022年，星期一中缀表示中缀表示后缀表示后缀表示a+b ab+a+b*c abc*+(a+b)*c ab+c*a:=b*c+b*d abc*bd*+:=特点特点1、运算对象出现的顺序和原有顺序（从左到右）相同、运算对象出现的顺序和原有顺序（从左到右）相同2、运算符按实际计算顺序（从左到右）出现、运算符按实际计算顺序（从左到右）出现3、运算符紧跟在运算对象的后面出现，且没有括号、运算符紧跟在运算对象的后面出现，且没有括号优点：简明、便于计值优点：简明、便于计值5.3.1 后缀式
18、后缀式第22页，共32页，编辑于2022年，星期一5.3.1 后缀式后缀式逆波兰逆波兰(后缀后缀)表示的形成表示的形成 为了说明逆波兰为了说明逆波兰(后缀后缀)表示的形成，荷兰学者表示的形成，荷兰学者W.DEJKSTRAW.DEJKSTRA给出下给出下面形象的解释。面形象的解释。波兰表示波兰表示 运算对象运算对象 表达式表达式运算符进栈运算符进栈运运算算符符栈栈退栈退栈比栈顶高进栈，比栈顶低或相同的退栈比栈顶高进栈，比栈顶低或相同的退栈第23页，共32页，编辑于2022年，星期一分别给出下列表达式的后缀表示分别给出下列表达式的后缀表示1.-a+b*(-c+d)2.X:=-(a+b)/(c-d)
19、-(a+b*c)3.a=c b=d4.ab+c ada+bea-bc-d+*+Xab+-cd-/abc*+-:=ac=bd=abc+ad ab+e 第24页，共32页，编辑于2022年，星期一5.3.2 三地址代码三地址代码种类种类（1）x=y op z形式的赋值语句，其中形式的赋值语句，其中op是二元运算符。是二元运算符。（2）x=op y形式的赋值语句，其中形式的赋值语句，其中op是一元运算符。是一元运算符。（3）x=y形式的赋值语句。形式的赋值语句。（4）无无条条件件转转移移语语句句goto L，表表示示下下一一个个要要执执行行的的语语句句是是标标号为号为L的语句。的语句。（5）条条件件
20、转转移移语语句句if x rop y goto L中中，rop为为关关系系运运算算符符，如如果果x和和y满满足足关关系系rop，就就转转而而执执行行标标号号为为L的的语语句句，否否则则顺顺序序执执行行下下一一个语句。个语句。第25页，共32页，编辑于2022年，星期一（6）过过程程调调用用语语句句param x 和和call p,n。源源程程序序中中的的过过程程调调用语句用语句p(x1，x2，xn)可以产生如下的三地址代码：可以产生如下的三地址代码：param x1param x2 param xncall p,n其中其中n为实参个数。过程返回语句形如为实参个数。过程返回语句形如return
21、y，其中，其中y为过程返回为过程返回的一个值。的一个值。第26页，共32页，编辑于2022年，星期一（7）变址赋值：）变址赋值：x=yi，把从，把从y开始的第开始的第i个存储单元的值赋给个存储单元的值赋给x。xi=y，把，把y的值赋给的值赋给x开始的第开始的第i个存储单元。个存储单元。其中，其中，x，y和和i都代表数据对象。都代表数据对象。（8）地址和指针赋值：）地址和指针赋值：x=&y，把，把y的地址赋给的地址赋给x。x=y，把，把y指示的地址单元中的内容赋给指示的地址单元中的内容赋给x。x=y，把，把x指向的存储单元的值置为指向的存储单元的值置为y。第27页，共32页，编辑于2022年，星
22、期一2具体实现具体实现四元式四元式操作符操作符 操作数操作数1 操作数操作数2 结果结果结果：通常是由编译引进的临时变量结果：通常是由编译引进的临时变量例例:X=(A+B)*(C+D)-E+,A,B,T1+,C,D,T2*,T1,T2,T3-,T3,E,T4=,T4,一一,XT1,T2,T3,T4为临时变量，由四元式优化比较方便为临时变量，由四元式优化比较方便T1=A+BT2=C+DT3=T1*T2T4=T3-EX=T4第28页，共32页，编辑于2022年，星期一操作符操作符 左操作符数左操作符数 右操作数右操作数 表达式的三元式：表达式的三元式：w*x+(y+z)(1)*,w,x(2)+,y
23、,z(3)+,(1),(2)第三个三元第三个三元式中的操作数式中的操作数(1)(2)表示第表示第(1)和第和第(2)条三元式的计条三元式的计算结果。算结果。三三元式元式第29页，共32页，编辑于2022年，星期一例：例：A=B+C*D/E F=C*D三元式三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)*,C,D(6)=,F,(5)不便于代码优化：删除某不便于代码优化：删除某些三元式后可能需作一系些三元式后可能需作一系列的修改列的修改 三元式三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)=,F,(1)间接三元式间
24、接三元式执行顺序执行顺序(1)(2)(3)(4)(1)(5)三元式的执行次序用另一张三元式的执行次序用另一张表表示表表示,优化时三元式可以不优化时三元式可以不变，仅仅改变其执行顺序表变，仅仅改变其执行顺序表第30页，共32页，编辑于2022年，星期一例：例：x=y+y z+y z 抽象语法树抽象语法树5.3.3 图形表示图形表示有环无向图有环无向图第31页，共32页，编辑于2022年，星期一重点掌握：重点掌握：语义分析的任务语义分析的任务属性文法、语法制导翻译的含义属性文法、语法制导翻译的含义自底向上和自顶向下语法制导翻译的区别和特点自底向上和自顶向下语法制导翻译的区别和特点生成中间代码的目的，中间代码的几种形式生成中间代码的目的，中间代码的几种形式小结小结第32页，共32页，编辑于2022年，星期一