语法制导翻译及属性文法-编译原理-06-(一)

1、2021-10-171第第6章章 语法制导翻译语法制导翻译与属性文法与属性文法语法制导翻译概述语法制导翻译概述属性文法属性文法综合属性与继承属性综合属性与继承属性S_属性文法属性文法L_属性文法属性文法翻译模式翻译模式2021-10-1726.1 语法制导翻译概述语法制导翻译概述v语法语法制导制导翻译的概念描述翻译的概念描述在进行语法分析的同时，完成相应的语义处理在进行语法分析的同时，完成相应的语义处理EE1 + E2E.val:=E1.val+E2.valv语法结构具有规定的语义语法结构具有规定的语义v？如何根据被识别出的语法成分进行语？如何根据被识别出的语法成分进行语义处理，有哪些工作要做

2、义处理，有哪些工作要做2021-10-1731. 语义分析的任务语义分析的任务v语义检查语义检查例如：类型、运算、维数、越界例如：类型、运算、维数、越界v翻译翻译例如：变量的存储分配、表达式的求值、语句的例如：变量的存储分配、表达式的求值、语句的翻译翻译v总目标总目标生成等价的生成等价的(中间中间)代码代码2021-10-1742. 代码结构代码结构v朴素理解：我们编写的程序在如何工作？朴素理解：我们编写的程序在如何工作？v计算学科：对信息描述（数据表示）和变换计算学科：对信息描述（数据表示）和变换算法的系统研究算法的系统研究v变换：源、目标以及源与目标的对应关系变换：源、目标以及源与目标的对

3、应关系n语句的代码结构（源、目标）语句的代码结构（源、目标）n语句分类语句分类n说明语句说明语句符号表的查填符号表的查填n可执行语句可执行语句生成指令代码生成指令代码2021-10-1753. 典型处理方法典型处理方法(1/3)v对应每一个产生式编制一个语义子程序，对应每一个产生式编制一个语义子程序，当一个产生式获得匹配时，调用相应的语当一个产生式获得匹配时，调用相应的语义子程序实现语义检查与翻译义子程序实现语义检查与翻译EE1 + TE.val:=E1.val+T.valTT1 * FT.val:=T1.val*F.valF idF.val:=id.valv适应在完成归约的时候进行适应在完成

4、归约的时候进行2021-10-1763. 典型处理方法典型处理方法(2/3)v在产生式的右部的适当位置，插入相应的在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行语义动作，按照分析的进程，执行遇到遇到的的语义动作语义动作D T L.in := T.type LT int T.type := integer T real T.type := real L L1.in := L.in L1,idL idv适应在进行推导时完成适应在进行推导时完成2021-10-1773. 典型处理方法典型处理方法(3/3)v对应语法基本分析方法对应语法基本分析方法Top-down：派生过程中完成：

5、派生过程中完成Bottom-up：归约时完成：归约时完成v语义语义语法成分的语义可以用相应文法符号的属性来表语法成分的语义可以用相应文法符号的属性来表示，通过属性的计算，来完成翻译示，通过属性的计算，来完成翻译2021-10-178v属性文法是属性文法是Knuth在在1968年提出的年提出的v属性文法的特点属性文法的特点是一种接近形式化的语义描述方法是一种接近形式化的语义描述方法长于描述静态语义、短于描述动态语义长于描述静态语义、短于描述动态语义每个语法符号有相应的属性符号每个语法符号有相应的属性符号每个产生式有相应计算属性的规则每个产生式有相应计算属性的规则v属性变量属性变量:=属性表达式属

6、性表达式2021-10-179属性文法举例属性文法举例产生式产生式 属性（计算）规则属性（计算）规则/语义规则语义规则E E1 + E2E E1 * E2E (E1)E idE.val := E1.val + E2.valE.val := E1.val * E2.valE.val := E1.valE.val := id .val2021-10-1710v三元组：三元组：A（G，V，F）G 是上下文无关文法是上下文无关文法V 属性的有穷集属性的有穷集F 关于属性的计算规则关于属性的计算规则v属性及其计算规则属性及其计算规则语义信息作为终结符和非终结符的属性语义信息作为终结符和非终结符的属性语义

7、分析成为产生式相关属性计算：每个产生式语义分析成为产生式相关属性计算：每个产生式设置语义规则，描述各属性的关系设置语义规则，描述各属性的关系计算规则计算规则2021-10-1711v根据文法符号的语义，为文法符号设置属根据文法符号的语义，为文法符号设置属性，用来表示文法符号的语义性，用来表示文法符号的语义终结符使用单词的属性终结符使用单词的属性 （id.val）v保留字：保留字：if, begin, function,v常数：常数：40.12, 232, 80, “TCP/IP”v标识符：标识符：sum, tcc, id 语法变量根据实际需要设定属性语法变量根据实际需要设定属性v表达式表达式E

8、：E.type， E.val2021-10-1712vL E vE E1 + T | T vT T1 * F | FvF ( E ) | digit任务：任务：完成一个输入表完成一个输入表达式值的计算和达式值的计算和显示显示翻译翻译2021-10-1713L E E E1 + TE TT T1 * FT FF ( E )F digitprint( E.val )E.val := E1.val + T.valE.val := T.valT.val := T1.val * F.valT.val := F.valF.val := E.valF.val := digit.lexval（L L的虚属性）

9、的虚属性）lexval lexval 是单词是单词 digit digit 的属性的属性2021-10-1714v说明语句的文法说明语句的文法D T LT intT real L L1,idL idreal operand, length, sumint add, sub, mult2021-10-1715D T LT intT realL L1,idL idL.in := T.typeT.type := integerT.type := realL1.in := L.inaddtype( id.entry, L.in )addtype( id.entry, L.in )entry id en

10、try id 的属性：可以是它在符号表中的地址的属性：可以是它在符号表中的地址addtype addtype 在符号表中为变量填加类型信息在符号表中为变量填加类型信息2021-10-1716E E1 + TE.val := E1.val + T.valE TE.val := T.valT T1 * FT.val := T1.val * F.valT intT.type := integer2021-10-1717Ax1x2xn适应：归约分析适应：归约分析A.sc1c2cnA.in2021-10-1718v设设 AX1X2Xn 为一个产生式为一个产生式A.s=f(c1,c2,ck)c1,c2,c

11、k是是X1，X2，Xn的属性和的属性和A的继承属性的继承属性A.s是根据其子结点的属性值计算出来的是根据其子结点的属性值计算出来的如：例如：例6-1 E.val、T.typev这种属性叫做综合这种属性叫做综合(Synthesized)属性属性2021-10-1719AX1X2XnXi.in=f(c,c1,c2,ck)Ax1x2xnxk1kin派生分析较自然派生分析较自然Xi.inc1c2ckcnc2021-10-1720v设设AX1X2Xn为一个产生式，为一个产生式，Xi的属性的属性Xi.in=f(c,c1,c2,ci-1)c,c1,c2,ci-1是是A, X1，X2，Xi-1的属性的属性如：

12、如： 中的中的L.inv这种属性叫做继承这种属性叫做继承(Inherited)属性属性2021-10-1721v语言中的标识符、常数（数值的、符号语言中的标识符、常数（数值的、符号的）、常量，它们的属性是用户给定的、的）、常量，它们的属性是用户给定的、固有不变的固有不变的n固有固有(Inherent)(Inherent)属性（单词属性）属性（单词属性）u归类于综合属性归类于综合属性2021-10-1722v综合属性综合属性自底向上按照语义规则来计算各结点的综自底向上按照语义规则来计算各结点的综合属性值合属性值在归约时进行计算在归约时进行计算v继承属性继承属性根据依赖关系决定计算顺序根据依赖关系

13、决定计算顺序依赖图依赖图(P214/140陈陈-略略)的任意一个拓扑排的任意一个拓扑排序（序（Topological Sort)v固有属性固有属性(在词法分析时计算，现不考虑在词法分析时计算，现不考虑)2021-10-1723L Print(19)E.val=19T.val=4+E.val=15T.val=15*F.val=3F.val=4F.val=5T.val=3digit.lexval=3digit.lexval=5digit.lexval=4( id.entry, L.in )( id.entry, L.in )D T L.in := T.type LT int T.type := i

14、nteger T real T.type := real ( id.entry, L.in ).type=real.in=real.in=real.in=realL L1.in := L.in L1,idaddtype ( id.entry, L.in )L idaddtype ( id.entry, L.in )2021-10-1725vS-属性定义：仅包含综合属性的属性属性定义：仅包含综合属性的属性文法（语法制导定义）文法（语法制导定义）vS-attributed DefinitionvS-attributed Grammarv如：算术表达式求值的属性文法如：算术表达式求值的属性文法202

15、1-10-1726DT LL.in := T.type继承继承TintT.type := integer固有固有TrealT.type := real固有固有LL1,id L1.in := L.in继承继承 addtype(id.entry, L.in)L id addtype(id.entry, L.in)2021-10-1727v包含综合属性和继承属性的属性文法（语包含综合属性和继承属性的属性文法（语法制导定义）法制导定义）vL-attributed DefinitionvL-attributed Grammarv如：算术表达式求值的属性文法、说明语如：算术表达式求值的属性文法、说明语句的

16、属性文法句的属性文法2021-10-1728v其属性可用深度优先的顺序从左至右计算其属性可用深度优先的顺序从左至右计算对于所有对于所有 AX1 X2 XnXi属性计算仅使用属性计算仅使用X1、X2、Xi-1 的的属性和属性和A的继承属性的继承属性vS-属性文法为特殊的属性文法为特殊的L-属性文法属性文法2021-10-1729语法制导定义语法制导定义 ：D T LL.in := T.typeT intT.type := integerT realT.type := realL L1 ,idL1.in := L.inaddtype(id.entry, L.in)L idaddtype(id.en

17、try, L.in)上述动作的执行时机分析上述动作的执行时机分析(依照自顶向下分析依照自顶向下分析)2021-10-1730v将语义动作中将语义动作中继承继承属性的计算前移，使它出现在属性的计算前移，使它出现在其相应文法符号其相应文法符号之前之前D T LT intT realL L1 , idL id2021-10-1731v将语义动作插入到产生式的某个位置将语义动作插入到产生式的某个位置v特征特征规定在语法分析中使用语义规则进行计规定在语法分析中使用语义规则进行计算的次序算的次序保证当动作使用某属性时，该属性必须保证当动作使用某属性时，该属性必须是有效的是有效的最左派生最左派生v表示形式：

18、表示形式：2021-10-1732vreal id1,id2的处理过程的处理过程DTL.in:=T.typeLrealT.type:=realL.in:=T.typeLrealL.in=realL realL.in=real L1.in:=L.inL1,id2addtype(id2.entry,L.in) realL1.in=real L1,id2addtype(id2.entry,L.in) realL1.in=real id1addtype(id1.entry,L1.in),id2addtype(id2.entry,L.in) real id1(id1.entry,real),id2(id2.entry,real)2021-10-1733v语义动作被嵌入到产生式右部的适当位置，语义动作被嵌入到产生式右部的适当位置，相当于在推导过程中完成语义处理相当于在推导过程中完成语义处理2021-10-17341. 下列文法是一个二进制数的文法。试根据该文法，下列文法