编译原理语义1(属性文法和语法制导翻译).pptx

《编译原理语义1(属性文法和语法制导翻译).pptx》由会员分享，可在线阅读，更多相关《编译原理语义1(属性文法和语法制导翻译).pptx（33页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第 9 9 讲讲西北农林科技大学本科教程西北农林科技大学本科教程 主讲教师：赵建邦主讲教师：赵建邦 第四章第四章 语义分析和中间代码生成语义分析和中间代码生成l4.1 4.1 语义分析概述语义分析概述l4.2 4.2 属性文法属性文法l4.3 4.3 几种常见的中间语言几种常见的中间语言l4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l4.5 4.5 控制语句的翻译控制语句的翻译l4.6 4.6 数组元素的翻译数组元素的翻译l4.7 4.7 过程或函数调用语句的翻译过程或函数调用语句的翻译l4.8 4.8 说明语句的翻译说明语句的翻译l4.9 4.9 递归下降语法制导翻译方法简

2、介递归下降语法制导翻译方法简介u第四章第四章语义分析和中间代码生成语义分析和中间代码生成l4.1 4.1 语义分析概述语义分析概述l4.2 4.2 属性文法属性文法l4.3 4.3 几种常见的中间语言几种常见的中间语言u重点掌握重点掌握l语法翻译制导思想语法翻译制导思想l逆波兰表示法逆波兰表示法l三地址代码（四元式、三元三地址代码（四元式、三元式）式）本讲目标本讲目标 4.1 4.1 语义分析概述语义分析概述u4.1.1 语义分析的内容语义分析的内容l语义分析包括两部分：语义分析包括两部分：1.1.静态静态语义审查（编译阶段）语义审查（编译阶段）(1)类型检查：检查运算的合法性和运算分量类型的

3、相容性，类型检查：检查运算的合法性和运算分量类型的相容性，必要时进行类型转换。必要时进行类型转换。(2)控制流检查：保证控制语句有合法的转向点。控制流检查：保证控制语句有合法的转向点。(3)一致性一致性检查：变量重复声明、检查：变量重复声明、case语句相同入口等。语句相同入口等。2.2.生成生成目标代码或目标代码或中间代码中间代码 生成中间代码的好处：生成中间代码的好处：(1)使得编译结构在逻辑上更为简单明确使得编译结构在逻辑上更为简单明确 (2)容易实现目标代码的优化容易实现目标代码的优化 4.1 4.1 语义分析概述语义分析概述u4.1.1 如何实现语义分析？如何实现语义分析？l语义分析

4、不像词法分析和语法分析那样，分别可以用正规文语义分析不像词法分析和语法分析那样，分别可以用正规文法和上下文无关文法形式化地进行描述法和上下文无关文法形式化地进行描述l语义分析的描述工具：属性文法语义分析的描述工具：属性文法l语义分析的实现方式：语法制导翻译语义分析的实现方式：语法制导翻译 其中，属性文法是语法制导翻译的基础其中，属性文法是语法制导翻译的基础4.1 4.1 语义分析概述语义分析概述u4.1.2 语法制导翻译方法（原理）语法制导翻译方法（原理）l语法制导翻译的方法就是语法制导翻译的方法就是为每个产生式配上一个翻译子程序为每个产生式配上一个翻译子程序(称语义动作或称语义动作或语义子程

5、序语义子程序)，并在语法分析的同时执行这些，并在语法分析的同时执行这些子程序。子程序。l语义子程序的作用：描述一个产生式所对应的翻译工作。语义子程序的作用：描述一个产生式所对应的翻译工作。如：改变变量的值，查、填符号表、发现语义错误、如：改变变量的值，查、填符号表、发现语义错误、产生中间代码等。产生中间代码等。l所以所以，在语法分析过程中，当每一个产生式获得匹配（，在语法分析过程中，当每一个产生式获得匹配（对应对应自顶向下推导自顶向下推导）或成功规约（）或成功规约（对应于自底向上对应于自底向上）时，此产生）时，此产生式相应的语义子程序进入工作，最终完成翻译工作。式相应的语义子程序进入工作，最终

6、完成翻译工作。l那么，语法制导翻译分为自顶向下和自底向上两种。那么，语法制导翻译分为自顶向下和自底向上两种。4.1 4.1 语义分析概述语义分析概述u4.1.2 语法制导翻译方法（实例）语法制导翻译方法（实例）l假定有一个自底向上的假定有一个自底向上的LRLR分析器，原始功能是规约输入串。分析器，原始功能是规约输入串。如：如：“#7+9*5#”。现在将它的功能加以扩大，使其在规约输。现在将它的功能加以扩大，使其在规约输入串的同时调用语义子程序计算输入串的语义。入串的同时调用语义子程序计算输入串的语义。产生式产生式 语义动作语义动作(0)SE print valTOP(1)EE(1)+E(2)v

7、alTOP=valTOP+valTOP+2(2)EE(1)*E(2)valTOP=valTOP*valTOP+2(3)E(E(1)valTOP=valTOP+1(4)Ei valTOP=lexval (注：注：lexval为为i的整型内部值的整型内部值)图图4-1 扩充后的扩充后的LR分析栈分析栈注意语义栈的功能：完成语义动作后，保存语义值注意语义栈的功能：完成语义动作后，保存语义值1.1.状态栈、符号栈和状态栈、符号栈和语义栈三者同步变化语义栈三者同步变化2.2.在用某一规则进行在用某一规则进行归约，栈顶保存归约，栈顶保存文法文法符号符号之后之后，调用相应，调用相应语义子程序完成语义语义子程

8、序完成语义动作，将改变的动作，将改变的语义语义值值保存在语义栈中保存在语义栈中表表4.1 表达式表达式“7+9*5#”的语义分析和计值过程的语义分析和计值过程产生式产生式 语义动作语义动作(0)SE print valTOP(1)EE(1)+E(2)valTOP=valTOP+valTOP+2(2)EE(1)*E(2)valTOP=valTOP*valTOP+2(3)E(E(1)valTOP=valTOP+1(4)Ei valTOP=lexval (注：注：lexval为为i的整型内部值的整型内部值)规约时，先对产生式右部的语义值进行综合，其结果作为左部符规约时，先对产生式右部的语义值进行综合

9、，其结果作为左部符号的语义值保存在语义栈中。号的语义值保存在语义栈中。4.2 4.2 属性文法属性文法u4.2.1 文法的属性文法的属性 属性属性是指与是指与文法符号的类型和值等有关的一些信息，文法符号的类型和值等有关的一些信息，在编译在编译中用属性描述处理对象的中用属性描述处理对象的特征特征 对于对于一棵等待翻译的语法树，它的各个结点都是文法中的一一棵等待翻译的语法树，它的各个结点都是文法中的一个个符号符号:X:X，该，该X X可以是可以是终结符终结符或或非终结符非终结符l文法符号文法符号X X的属性一般包括三种：的属性一般包括三种：X.type:X的类型的类型X.place:X的存储位置的

10、存储位置X.val:X的值的值u4.2.1 文法的属性文法的属性l文法符号的属性文法符号的属性按照语法分析方向（推导还是规约）分为两按照语法分析方向（推导还是规约）分为两种：继承属性和综合属性种：继承属性和综合属性 1.1.继承属性继承属性：用于：用于“自顶向下自顶向下”传递传递信息，信息，继承属性由相应继承属性由相应语法树中结点的父结点属性计算得到，即语法树中结点的父结点属性计算得到，即沿语法树向下传递沿语法树向下传递，由根结点到分枝由根结点到分枝(子子)结点，它反映了对上下文依赖的结点，它反映了对上下文依赖的特性。特性。2.2.综合属性综合属性：用于用于“自底向上自底向上”传递传递信息，综

11、合信息，综合属性由相应属性由相应语法分析树中语法分析树中结点的分枝结点结点的分枝结点(即子结点即子结点)属性计算得到属性计算得到，其传，其传递方向与继承属性相反，即递方向与继承属性相反，即沿语法分析树向上传递沿语法分析树向上传递，从分枝结，从分枝结点到根点到根结点。结点。4.2 4.2 属性文法属性文法u4.2 属性文法属性文法l属性文法属性文法是经过扩展了的常规文法，适用于定义语义。即在是经过扩展了的常规文法，适用于定义语义。即在语言的文法中增加了属性信息：语言的文法中增加了属性信息：1.1.将文法符号的语义以将文法符号的语义以“属性属性”的形式附加到各个文法符号的形式附加到各个文法符号上；

12、上；2.2.根据产生式所包含的含义，给出每个文法符号属性的求值根据产生式所包含的含义，给出每个文法符号属性的求值规则。规则。l所以，从而形成一种带有语义属性的上下文无关文法，即所以，从而形成一种带有语义属性的上下文无关文法，即属属性文法。性文法。属性有助于更详细地指定文法中的代码生成动作属性有助于更详细地指定文法中的代码生成动作。4.2 4.2 属性文法属性文法例如，简单算术表达式求值的属性文法如下：例如，简单算术表达式求值的属性文法如下：产生式产生式 语义规则语义规则 (1)SE print(E.val)(2)EE(1)+T E.val=E(1).val+T.val (3)ET E.val=

13、T.val (4)TT(1)*F T.val=T(1).val*F.val (5)TT(1)T.val=T(1).val (6)F(E)F.val=E.val (7)Fi F.val=i.lexvallexval是词法分析送来的整型内部值是词法分析送来的整型内部值4.2 4.2 属性文法（综合属性）属性文法（综合属性）表达式左侧的非终结符语义值来自于右侧语义的计算，表达式左侧的非终结符语义值来自于右侧语义的计算，因此称为综合属性因此称为综合属性再举一例说明属性文法。一简单变量类型说明的文法再举一例说明属性文法。一简单变量类型说明的文法GD如下：如下：GD:Dint L|float L LL,i

14、d|id4.2 4.2 属性文法（继承属性）属性文法（继承属性）产生式产生式语义规则语义规则代码段代码段(1)DTLL.in=T.type(2)TintT.type=intvaltop=int(3)TfloatT.type=floatvaltop=float(4)LL(1)，id L(1).in=L.in;addtype(id.entry，L.in)addtype(valtop,valtop+3)(5)Lidaddtype(id.entry，L.in)addtype(valtop,valtop+1)4.2 4.2 属性文法（继承属性）属性文法（继承属性）属性属性L.inL.in被确定后将随被确

15、定后将随语法树的逐步生成而传语法树的逐步生成而传递到下边的有关结点使递到下边的有关结点使用，这种结点属性称为用，这种结点属性称为继承属性继承属性输入串输入串语义栈语义栈产生式产生式int a,ba,b inta,b TTint,b Ta,b TLLidb TL,TL,bTLLL,idDDTLinta,b的分析过程u4.3.1 抽象语法树抽象语法树l抽象语法树是一种较为流行的中间语言表示形式。抽象语法树是一种较为流行的中间语言表示形式。l每一个叶子结点表述运算对象，其它内部结点表示运算符。每一个叶子结点表述运算对象，其它内部结点表示运算符。l抽象语法树由语法树去掉一切不必要的信息得来。抽象语法树

16、由语法树去掉一切不必要的信息得来。4.3 4.3 几种常见的中间语言几种常见的中间语言图图4-4 x=ab*c的语法树的语法树(a)抽象语法树；抽象语法树；(b)普通语法树图普通语法树图u4.3.1 抽象语法树抽象语法树l问题问题1 1：什么是抽象语法？：什么是抽象语法？由于语法规则由于语法规则中包含的某些符号可能起中包含的某些符号可能起标点符号作用也可能标点符号作用也可能起注释作用起注释作用:(1)赋值赋值语句语法规则：语句语法规则：S V=e 其中其中的赋值号的赋值号“=”仅起标点符号作用，其目的是把仅起标点符号作用，其目的是把V与与e分开；分开；(2)(2)条件条件语句语法规则：语句语法

17、规则：Sif(e)S1;else S2 其中的其中的if和和else起注释起注释作用，作用，而而“；”仅起标点符号仅起标点符号作用。作用。在在把语法规则中本质部分抽象出来而将非本质部分去掉后，把语法规则中本质部分抽象出来而将非本质部分去掉后，便便得到得到抽象语法规则抽象语法规则4.3 4.3 几种常见的中间语言几种常见的中间语言VeeS1 S2u4.3.1 抽象语法树抽象语法树l问题问题2 2：如何将表达式的普通语法树化简为抽象语法树？：如何将表达式的普通语法树化简为抽象语法树？解答：化简过程为：解答：化简过程为：(1)(1)去掉与单非产生式相关的子树，上提终结符结点；去掉与单非产生式相关的子

18、树，上提终结符结点；(2)(2)如果子树中有运算符结点，上提运算符取代父节点；如果子树中有运算符结点，上提运算符取代父节点；(3)(3)去掉括号，上提运算符，让其取代父节点。去掉括号，上提运算符，让其取代父节点。课堂练习：对于文法课堂练习：对于文法GS,构造构造i*(i+i)的语法树并化简。的语法树并化简。4.3 4.3 几种常见的中间语言几种常见的中间语言GE:EE+T|TTT*F|FF(E)|i（3.1）u4.3.2 1.表达式的逆波兰表示法表达式的逆波兰表示法l逆波兰表示法是波兰逻辑学家逆波兰表示法是波兰逻辑学家卢卡西维奇卢卡西维奇(Lukasiewicz)发明的发明的一种一种表示表达式

19、的表示表达式的方法方法，又称后缀表示法。，又称后缀表示法。l例如：例如：a+b 表示成表示成 ab+a*(b+c)表示成表示成 abc+*(a+b)*(a-c)-d 表示成表示成 ab+ac-*d-l优点：优点：1.表达式中无括号表达式中无括号 2.运算不需要考虑优先级，扫描一遍即可完成运算运算不需要考虑优先级，扫描一遍即可完成运算l特点特点：1.标识符出现的顺序和原有顺序相同；标识符出现的顺序和原有顺序相同；2.运算符是按照实际计算顺序出现的；运算符是按照实际计算顺序出现的；3.运算符紧跟在运算对象的后面。运算符紧跟在运算对象的后面。4.3 4.3 几种常见的中间语言几种常见的中间语言思考：

20、逆波兰式如何计算？思考：逆波兰式如何计算？u4.3.2 2.程序语句的逆波兰表示法程序语句的逆波兰表示法l由于控制语句需要跳转，因此定义如下转移操作：由于控制语句需要跳转，因此定义如下转移操作：(1)BL：转向某标号；：转向某标号；(2)BT：条件为真时转移；：条件为真时转移；(3)BF：条件为假时转移；：条件为假时转移；(4)BR：无条件转移：无条件转移。l程序语句的逆波兰表示主要程序语句的逆波兰表示主要掌握掌握如下几类：如下几类：(1)赋值语句；赋值语句；(2)GOTO语句；语句；(3)条件语句；条件语句；(4)循环语句。循环语句。4.3 4.3 几种常见的中间语言几种常见的中间语言l(1

21、)赋值语句赋值语句 “=”的的逆波兰表示为逆波兰表示为 =例如例如，赋值语句，赋值语句“x=a+b*c”可按逆波兰式写可按逆波兰式写为为 “xabc*+=”。l(2)GOTO语句语句。转向语句。转向语句“GOTO”的逆波兰表示的逆波兰表示为为 BL其中，其中，“BL”为单目后缀运算符，为单目后缀运算符，“”则为则为BL的一个运算分量的一个运算分量。例如，转向语句例如，转向语句 GOTO 10，逆波兰表示为，逆波兰表示为“10BL”，意为无，意为无条件转向标号为条件转向标号为10 的语句处。的语句处。4.3 4.3 几种常见的中间语言几种常见的中间语言l(3)条件条件语句语句 BR表示无条件转移

22、单目后缀表示无条件转移单目后缀运算符，运算符，例如，例如，“BR”表示无条件转移到表示无条件转移到“”处，这里的顺序号是处，这里的顺序号是BR的一个的一个特殊运算分量，用来表示逆波兰式中单词符号的顺序号特殊运算分量，用来表示逆波兰式中单词符号的顺序号(即第几即第几个单词个单词)BT和和BF表示按条件转移的两个双目后缀运算符表示按条件转移的两个双目后缀运算符l例如：例如：BT BF 分别表示当分别表示当e为真或假时转移到顺序号处。其中，布尔表达式为真或假时转移到顺序号处。其中，布尔表达式e的逆波兰式和顺序号是两个特殊的运算分量。的逆波兰式和顺序号是两个特殊的运算分量。4.3 4.3 几种常见的中

23、间语言几种常见的中间语言此逆波兰式也可写在一行上，即：此逆波兰式也可写在一行上，即：mn13BFki1+=18BRki1=例如，条件语句例如，条件语句if(mn)k=i+1；else k=i1的的逆波兰式表示为逆波兰式表示为(1)(18)为单词编号为单词编号)实例：条件语句的逆波兰表示实例：条件语句的逆波兰表示(1)m n (4)13 BF(6)k i 1+=(11)18 BR(13)k i 1 =(18)if语句的后继语句语句的后继语句l(4)循环语句循环语句 for循环语句为循环语句为for(i=m；i=n；i+)S 其中其中，i为循环控制变量，为循环控制变量，m为初值，为初值，n为终值，

24、为终值，S为为循环体；循环体；循环循环语句语句不能直接用逆波兰表示不能直接用逆波兰表示，因而将其，因而将其展开为等价的条展开为等价的条件语句后再用逆波兰表示件语句后再用逆波兰表示l例如例如：i=m；10：if(i=n)S；i=i+1；goto 10 4.3 4.3 几种常见的中间语言几种常见的中间语言一起来完成一起来完成逆波兰式逆波兰式翻译翻译u4.3.3 三地址代码三地址代码l三地址代码语句的一般形式：三地址代码语句的一般形式：x=y op z 其中，其中，x、y和和z为名字、常量或编译时产生的临时为名字、常量或编译时产生的临时变量；变量；op为运算符，如定点运算符、浮点运算符和逻辑运算符为

25、运算符，如定点运算符、浮点运算符和逻辑运算符等。等。l三地址代码的语句中通常包含三个地址，两个用来存放操作三地址代码的语句中通常包含三个地址，两个用来存放操作数（或操作对象），一个用来存放运算结果。如果一个表达数（或操作对象），一个用来存放运算结果。如果一个表达式中有多于三个的操作对象，该表达式可以用若干个三地址式中有多于三个的操作对象，该表达式可以用若干个三地址代码来表示。代码来表示。例如，表达式例如，表达式x+y*z的三地址代码为的三地址代码为4.3 4.3 几种常见的中间语言几种常见的中间语言t1=y*z t2=x+t1u4.3.3 三地址代码三地址代码l三地址代码语句的具体实现：三地址

26、代码语句的具体实现：在在编译程序中，三地址代码语言的具体实现通常有三种编译程序中，三地址代码语言的具体实现通常有三种表示表示方法方法：四元式、三元式和间接三元：四元式、三元式和间接三元式。式。l(1)四元式四元式 四四元式是具有四个域的记录元式是具有四个域的记录(即结构体即结构体)结构，这四个域为结构，这四个域为 (op,arg1,arg2,result)其中，其中，op为运算符；为运算符；arg1、arg2及及result为为指针指针，它们可指向它们可指向有关名字在符号表中的登记项或一临时变量有关名字在符号表中的登记项或一临时变量(个别指针也个别指针也可空缺可空缺)。4.3 4.3 几种常见

27、的中间语言几种常见的中间语言四元式还有一个数字标记，用来记录当前四元式的编号。在四元式还有一个数字标记，用来记录当前四元式的编号。在跳转时使用。跳转时使用。x=y op z 对应对应(op,y,z,x)x=y 对应对应(uminus,y,_,x)x=y 对应对应(=,y,_,x)par x1 对应对应(par,x1,_,_)call P 对应对应(call,_,_,P)goto L 对应对应(j,_,_,L)if x rop y goto L 对应对应(jrop,x,y,L)常用的三地址语句与相应的四元式对应如下：常用的三地址语句与相应的四元式对应如下：4.3 4.3 几种常见的中间语言几种常

28、见的中间语言u关于四元式：关于四元式：l约定：约定：(1)凡只需一个运算量的算符一律使用凡只需一个运算量的算符一律使用arg1;(2)如果如果op是一个算术或逻辑运算符，则是一个算术或逻辑运算符，则result总是一个新引进总是一个新引进的临时变量，它用来存放运算的临时变量，它用来存放运算结果结果。l例如，赋值语句例如，赋值语句a=b*(c+d)相应的四元式代码为相应的四元式代码为4.3 4.3 几种常见的中间语言几种常见的中间语言(+,c,d,t1)(*,b,t1,t2)(=,t2,_,a)由上例也可看出，四元式出现的顺序与表达式计值的顺由上例也可看出，四元式出现的顺序与表达式计值的顺序是一

29、致的，四元式之间的联系是通过临时变量实现的序是一致的，四元式之间的联系是通过临时变量实现的4.3 4.3 几种常见的中间语言几种常见的中间语言u4.3.3 三地址代码三地址代码l(2)三元式三元式 例如，相应于赋值语句例如，相应于赋值语句a=(b+c)*(b+c)的三元式的三元式代码为：代码为：(+,b,c)(+,b,c)(*,)(=,a,)三元式的顺序号必须有，它有两个作用：三元式的顺序号必须有，它有两个作用：1.代表运算次序；代表运算次序；2.保存三元式运算结果。保存三元式运算结果。4.3 4.3 几种常见的中间语言几种常见的中间语言u4.3.3 三地址代码三地址代码l三元式相对于四元式的

30、优点：三元式相对于四元式的优点：(1)三元式无需生成临时变量三元式无需生成临时变量 (2)三元式占用的存储空间较少三元式占用的存储空间较少l三元式相对于四元式三元式相对于四元式的缺点：的缺点：使用三元式不利于代码优化，因为改变一个三元式编号或胜使用三元式不利于代码优化，因为改变一个三元式编号或胜省略一个三元式，需要修改大量的三元式序号和内容。省略一个三元式，需要修改大量的三元式序号和内容。4.3 4.3 几种常见的中间语言几种常见的中间语言u4.3.3 三地址代码三地址代码l(3)间接三元式间接三元式 间接三元式的提出是为了优化三元式代码：间接三元式的提出是为了优化三元式代码：作为中间代码，通

31、常不直接使用三元式表示，而是另设一张作为中间代码，通常不直接使用三元式表示，而是另设一张间接码表，也称执行表。间接码表，也称执行表。先给出三元式表，再按照三元式的执行顺序，依次排列三元先给出三元式表，再按照三元式的执行顺序，依次排列三元式的执行编号，通过式的执行编号，通过“三元式表三元式表+执行表执行表”的组合来给出中间代的组合来给出中间代码，就是间接三元式。码，就是间接三元式。4.3 4.3 几种常见的中间语言几种常见的中间语言u4.3.3 三地址代码三地址代码l(3)间接三元式举例间接三元式举例 例如，相应于赋值例如，相应于赋值语句：语句：x=(a-b)*c;b=a-b;y=c*(a-b)4.3 4.3 几种常见的中间语言几种常见的中间语言按照三元式表示，可写成：按照三元式表示，可写成：(-,a,b)(*,c)(=,x)(=,b)(-,a,b)(*,c,)(=,y)按照间接三元式：按照间接三元式：(-,a,b)(*,c)(=,x)(=,b)(=,y)