编译原理张晶版 第七章 语法制导翻译和中间代码生成

1、课程名称第七章语法制导翻译和中间代码生成第七章语法制导翻译和中间代码生成7.1概述7.2属性文法和语法制导翻译7.3语义分析7.4中间代码7.5一些语句的翻译第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（1 1）课程名称概述概述 语义处理语义处理程序设计程序设计 语言的语义语言的语义 静态语义是对程序约束的描述，这些约束无法通过抽象语法规则来妥善静态语义是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作用域用域/ /可见性规则两大类可见性规则两

2、大类 类型相容性类型相容性 变量先声明后引用变量先声明后引用 名称相名称相关要求关要求 动态语义动态语义 程序单位描述的计算程序单位描述的计算编译程序的语义处理工作编译程序的语义处理工作 静态语义审查静态语义审查 解释执行动态语义（计算）解释执行动态语义（计算）生成代码生成代码.语语 法法 分分 析析 后后 的的 源源 程程 序序 语义处理语义处理第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（2 2）课程名称概述语义形式化语义形式化 语义建模语义建模 文法模型文法模型- - 属性文法属性文法 命令式或操作式模型命令式或操作式模型 - - 操作语义学操作语义学 应用式模型

3、应用式模型-指称语义学指称语义学 公理式模型公理式模型-公理语义学公理语义学第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（3 3）课程名称属性文法属性文法表达式文法 ET+T| T or T Tn | b ET1 + T2 T1.type = int T2.type= T1.type E.type :=int E T1 or T2 T1.type = bool T2.type= T1.type E.type :=bool T n T.type := int T b T.type := bool 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（4 4

4、）课程名称 操作语义操作语义 描述一段程序的含义是通过执行该段程序所改变的计算机（虚拟描述一段程序的含义是通过执行该段程序所改变的计算机（虚拟计算机）状态来反映。这个计算机的状态与程序执行时的状态相对计算机）状态来反映。这个计算机的状态与程序执行时的状态相对应：包括变量的所有值，可执行程序本身，各种系统定义的内部数应：包括变量的所有值，可执行程序本身，各种系统定义的内部数据结构。计算机里所有的寄存器的值和存储单元的值作为计算机的据结构。计算机里所有的寄存器的值和存储单元的值作为计算机的状态，用一组形式定义的操作来说明执行一条指令相应的状态怎样状态，用一组形式定义的操作来说明执行一条指令相应的状

5、态怎样变化。变化。For (expr1;expr2;expr3) expr1; . Loop:if expr2=0 goto out expr3; goto loop out: .第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（5 5）课程名称公理语义公理语义一个语言的每个语法成分的含义定义为公理和演绎规则，用于推导出该成一个语言的每个语法成分的含义定义为公理和演绎规则，用于推导出该成分执行的效果。分执行的效果。公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执行它的规格说明所描述的计

6、算。在一个证明中，每一个语句表明程序执行它的规格说明所描述的计算。在一个证明中，每一个语句之前之后都有一个逻辑表达式对程序的变量进行约束之前之后都有一个逻辑表达式对程序的变量进行约束, ,以此说明这个语以此说明这个语句的含义。句的含义。 一般的记号一般的记号 P S Q P S Q 如果在语句如果在语句S S执行前执行前P P为真，则在语句为真，则在语句S S执行并终止后执行并终止后Q Q为真。为真。 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（6 6）课程名称 演绎规则的例子 规则 前驱 后继 赋值：x:=expr P(expr)x:=exprP(x) While:

7、 P B S P P while B do S end P (not B) if-then-else B P S1 Q, (not B) P S2 Q P if B then S1 else S2Q 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（7 7）课程名称指称语义指称语义指称语义的基本概念是给每一段程序实体定义一个数学意义上的指称语义的基本概念是给每一段程序实体定义一个数学意义上的对象，和一个从实体实例向数学意义对象的映射的函数对象，和一个从实体实例向数学意义对象的映射的函数特点：特点： 不但对全部程序赋予全文而且对程序设计语法不但对全部程序赋予全文而且对程序设计

8、语法 每一个语法成分短语（表达式，命令，声明每一个语法成分短语（表达式，命令，声明） 都都给予含义。给予含义。 每一个语法成分（短语）的含义是以它的自每一个语法成分（短语）的含义是以它的自 成分的含义的术语来定义的。成分的含义的术语来定义的。 即即 语义结构语义结构 平行于语法结构。平行于语法结构。语义函数：语义函数： 程序设计语言的语义利用映射函数来证程序设计语言的语义利用映射函数来证 明。明。 语义函数将短语映射到它的指称。语义函数将短语映射到它的指称。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（8 8）课程名称 例：例： 二进制数语言 110或10101 语法实

9、体 指称（自然数） 6 或 21 语义实体 二进制数文法 Numeral:=0 :=1 := Numeral 0 :=Numeral 1 自然数 Natrual=0,1,2,3, 语义函数 Valuation:NumeralNatural第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（9 9）课程名称 Valuation101 表示把Valuation施用于101 ValuationN - 把它施用于N 定义定义: Valuation（用四个方程)因为有四个形式numeral Valuation0 0 Valuation1 1 ValuationN0 2Valuation

10、 N ValuationN1 2Valuation N+1 所以：所以： Valuation110=2 Valuation11 = 2 (2 Valuation1+1) =2 (2 1+1) =6第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（1010）课程名称属性文法和语法制导翻译属性文法和语法制导翻译 虽然形式语义学虽然形式语义学( (如指称语义学、公理语义学、如指称语义学、公理语义学、操作语义学等操作语义学等) )的研究已取得了许多重大的进展，的研究已取得了许多重大的进展，但目前在实际应用中比较流行的语义描述和语义但目前在实际应用中比较流行的语义描述和语义处理的方法

11、主要还是属性文法和语法制导翻译方处理的方法主要还是属性文法和语法制导翻译方法法 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（1111）课程名称属性文法属性文法属性文法属性文法(attribute grammar)(attribute grammar)是一个三元组是一个三元组:A=(G,V,F),:A=(G,V,F),其中其中 G:G:是一个上下文无关文法是一个上下文无关文法V:V:有穷的属性集有穷的属性集, ,每个属性与文法的一个终结符或非终结每个属性与文法的一个终结符或非终结符相连符相连, ,这些属性代表与文法符号相关信息，如它的类这些属性代表与文法符号相关信息，如

12、它的类型、值、代码序列、符号表内容等等型、值、代码序列、符号表内容等等 . .属性与变量一样，属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的可以进行计算和传递。属性加工的过程即是语义处理的过程。过程。F:F:关于属性的属性断言或一组属性的计算规则关于属性的属性断言或一组属性的计算规则( (称为语义称为语义规则规则) . ) . 断言或语义规则与一个产生式相联断言或语义规则与一个产生式相联, ,只引用该只引用该产生式左端或右端的终结符或非终结符相联的属性产生式左端或右端的终结符或非终结符相联的属性. . 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（12

13、12）课程名称属性有两种属性有两种 继承的和综合的属性继承的和综合的属性 属性通常分为两类：综合属性和继承属性。简单地说，综合属性用属性通常分为两类：综合属性和继承属性。简单地说，综合属性用于于“自下而上自下而上”传递信息，而继承属性用于传递信息，而继承属性用于“自上而下自上而下”传递信息。传递信息。 出现在产生式左边的继承属性和出现在产生式右边的综合属性不出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由生计算器的参数提供属性规则计算或者由生计算器的参数

14、提供。 AX1 X2 XnA的综合属性,计算 S(A):=f(I(X1),I(Xn)Xj的继承属性,计算 T(Xj):=f(I(A),. I(Xn) 1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性. 2)终结符只有综合属性.第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（1313）课程名称 在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A A都有一套与之相关联的语都有一套与之相关联的语义规则，每条规则的形式为义规则，每条规则的形式为b:=f(cb:=f(c1 1,c,c2 2c ck k) )这里，这里，f f是一个函数，而且或

15、者是一个函数，而且或者（1 1）b b是是A A的一个综合属性并且的一个综合属性并且c c1 1,c,c2 2c ck k是产生式右边文法符号的属性是产生式右边文法符号的属性; ;或者或者（2 2）b b是产生式右边某个文法符号的一个继承属性并且是产生式右边某个文法符号的一个继承属性并且c c1 1,c,c2 2c ck k是是A A或或产生式右边任何文法符号的属性。产生式右边任何文法符号的属性。在两种情况下，我们都说属性在两种情况下，我们都说属性b b依赖于属性依赖于属性c c1 1,c,c2 2c ck k 。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（1414）

16、课程名称 一个属性文法的例子一个属性文法的例子 例例7.17.1 非终结符非终结符E E、T T及及F F都有一个综合属性都有一个综合属性valval, ,符号符号digitdigit有一个综合属性，它的有一个综合属性，它的值由词法分析器提供。与产生式值由词法分析器提供。与产生式LEnLEn对应的语义规则仅仅是打印由对应的语义规则仅仅是打印由E E产生的产生的算术表达式的值的一个过程，我们可认为这条规则定义了算术表达式的值的一个过程，我们可认为这条规则定义了L L的一个虚属性。某的一个虚属性。某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现些非终结符加下标是为了区分一个产生式中同一

17、非终结符多次出现语 义 规 则 L EE E1+TE TT T1 * FT FF (E)F digitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval产 生 式第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（1515）课程名称设表达式为设表达式为3 35+45+4，则，则语义动作语义动作打印数值打印数值1919.LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F

18、.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树的带注释的分析树第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（1616）课程名称继承属性继承属性一个结点的继承属性值是由此结点的父结点和一个结点的继承属性值是由此结点的父结点和/ /或兄弟结点的某些或兄弟结点的某些属性来决定的。属性来决定的。例7.2 继承属性继承属性L.in生 产 式语 义 规 则D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real

19、L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（1717）课程名称 DL.in= realL.in= realL.in= realT.type=realrealid2id1id3.Real id1,id2,id3，第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（1818）课程名称例例7.37.3P DSD var V; D | S V := E; S | V x | y | z现在使用两个属性，现在使用两个属性，name和和dl，每当一个

20、新的变量声明时，就把它的，每当一个新的变量声明时，就把它的name属性附属性附给它，给它，name属性是综合属性。属性是综合属性。将所声明的变量都放到一个变量名字清单中（用语义函数将所声明的变量都放到一个变量名字清单中（用语义函数addlist实现），用属性实现），用属性dl综合声明块中声明的所有变量。然后这个综合声明块中声明的所有变量。然后这个dl属性又作为继承属性传到后面的语句属性又作为继承属性传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变量名字清单中部分，每个语句用到的变量都要进行审查，看它是否在变量名字清单中 P DS S.dl = D.dlD1 var V; D2

21、| D1.dl = addlist(V.name, D2.dl) | D1.dl = NULLS1 V := E; S2 | check(V.name, S1.dl); S2.dl = S1.dlV x | y | z V.name = x | V.name = y | V.name = z第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（1919）课程名称var x；var y；x:=e； P D dl=x,y S dl=x,yvar V ； D dl=y V := e ； S x var V ； D dl= y y 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译

22、和中间代码生成（2020）课程名称语法制导的翻译语法制导的翻译 一个翻译是符号串对的一个集合。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。各个编译阶段定义一个翻译，词法分析：（字符串，单词串）语法分析：（单词串，语法树）代码生成（语法树，汇编语言） 设是输入字母表且是输出字母表。定义由语言 L1 *到语言L2 *的一个翻译是由*到 *的一个关系T,使得T的定义域为L1且T的值域为L2 。 使(x,y) T的句子y叫做x的一个输出.第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（2121）课程名称语法制导的翻译语法制导的翻译 直观地说，一个语法制导翻译的基础是一

23、个文法，其中翻译成分依附在直观地说，一个语法制导翻译的基础是一个文法，其中翻译成分依附在每一产生式上。每一产生式上。例例7.47.4： 下列翻译模式，它定义翻译，即对每个输入下列翻译模式，它定义翻译，即对每个输入x x，其输出，其输出y y是是x x的的逆转。定义此翻译的规则是逆转。定义此翻译的规则是 产生式产生式 翻译规则翻译规则 (1)s0s(2)s1s (3)s (1)s=s0(2)s=s1 (3)s= 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（2222）课程名称 输入输出对可由(,)表示，其中是输入句子形式而是输出句子形式。 (S,S)开始用产生式s0s来扩

24、展得到(0S,S0). 再用一次规则(1)，得到(00S,S00)。 再用规则(2)，就得到(001S,S100). 然后应用规则(3)并得到(001,100)。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（2323）课程名称 例例7.57.5： 把下述产生式定义的算术表达式映射到后缀波兰表示：把下述产生式定义的算术表达式映射到后缀波兰表示： EE+T E T T TF T F F (E) F a E=ET+ E=T T=TF T=F F=E F=a 产生式 翻译规则翻译规则第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（2424）课程名称确定输入

25、a+aa的输出： (E,E)(E+T,ET+) (T+T,TT+) (F+T,FT+) (a+T,aT+) (a+TF,aFF+) (a+FF,aFF+) (a+aF,aaF+) (a+aa,aaa+)第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（2525）课程名称 定义：定义： 一个语法制导的翻译模式是一个五元组一个语法制导的翻译模式是一个五元组T=(N, , ， R,S),其中其中 (1) N是非终结符的有限集。是非终结符的有限集。 (2) 是有限的输入字母表。是有限的输入字母表。 (3) 是有限的输出字母表。是有限的输出字母表。 (4) R是形如是形如A, 的规则

26、的有限集的规则的有限集,其中其中 (N )*, (N )*且且 中那组非终结符是中那组非终结符是 中中那组非终结符那组非终结符的置换。的置换。 (5) S是是N中一个特别的非终结符，即开始符。中一个特别的非终结符，即开始符。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（2626）课程名称 定义：定义： 若若T= (N,T= (N, , , , , R,S) R,S)是是SDTS,SDTS, (T)(T)则称为语法制导的翻则称为语法制导的翻译译(SDT)(SDT)，文法，文法GiGi=(N,=(N, ,P,S) ,P,S)，其中，其中P=AP=A| |A A, , 属于属

27、于R)R)，称为称为SDTS TSDTS T的基础（或输入）文法。文法的基础（或输入）文法。文法G G0 0=( N, =( N, ,P,P ,S),S), ，其中其中P P =A =A | | A A, , 属于属于R R ，称为，称为T T的输出文法。的输出文法。 把语法制导的翻译方法看成是将输入文法把语法制导的翻译方法看成是将输入文法GiGi中的推中的推导树变换成输出文法导树变换成输出文法G G0 0中的推导树。给了输入句子中的推导树。给了输入句子x x，可以按，可以按如下方式得到如下方式得到x x的一个翻译：先为推导的一个翻译：先为推导x x构造一棵推导树，再构造一棵推导树，再变换该树

28、到输出文法中的一棵树，然后取此输出树的边缘作变换该树到输出文法中的一棵树，然后取此输出树的边缘作为为x x的一个翻译。的一个翻译。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（2727）课程名称语义制导翻译中的规则语义制导翻译中的规则A A, , 对应于每一个文法产生式对应于每一个文法产生式A A 都有与之相都有与之相关联的一套语义描述关联的一套语义描述 属性文法属性文法(attribute grammar)(attribute grammar)是一个三元是一个三元组组:A=(G,V,F) :A=(G,V,F) 属性文法可以看作是关于语言翻译的高级规范说属性文法可以看作

29、是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来译顺序的工作中解脱出来第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（2828）课程名称语法制导翻译实现从概念上讲，语法制导翻译即基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算输入符号串 分析树 属性依赖图 语义规则的计算顺序第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（2929）课程名称依赖图由称为依赖图的一个有向图 描述分析树中

30、的继承属性和属性中间的相互依赖关系。 依赖图的构造算法：依赖图的构造算法： for分析树中每一个结点n do for 结点的文法符号的每一个属性a do 为a在依赖图中建立一个结点； for 分析树中每一个结点n do for结点n所用产生式对应的每一个语义规则 b:=f(c1,c2,ck) do for i :=1 to k do 从ci结点到b结点构造一条有向边 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（3030）课程名称依赖图-例7.2 例例7.2 7.2 继承属性继承属性L.inL.in生 产 式语 义 规 则D TL T int T real L L1,i

31、dL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（3131）课程名称例7.2 Real id1,id2,id3分析树的依赖图 5678910T4DLLLRealtypeininin3 entry2 entryentryid3id2id1.1第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（3232）课程名称 依赖图中的结点由数字来标识。从代表T.type的

32、结点4有一条有向边连到代表L.in的结点5，因为根据产生式ETL的语义规则L1.in=L.in，可知L1.in依赖于L.in，所以有两条向下的有向边分别进入结点7和9。每一个与L产生式有关的语义规则addtype(id. Entry, L.in)都产生一个虚属性，结点 6、8和10都是为这些虚属性构造的。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（3333）课程名称良定义的属性文法。 很显然，一条求值规则只有在其各变元值均已求得的情况下很显然，一条求值规则只有在其各变元值均已求得的情况下才可以使用。但有时候可能会出现一个属性对另一个属性的才可以使用。但有时候可能会出现

33、一个属性对另一个属性的循环依赖关系。从事贸易如，循环依赖关系。从事贸易如，p p、c c1 1、c c2 2都是属性，若有下求都是属性，若有下求值规则：值规则：p: = fp: = f1 1(c(c1 1) )、c c1 1: = f: = f2 2(c(c2 2) )、c c2 2: = f: = f3 3(p)(p)时，就无时，就无法对法对p p求值。如果一属性文法不存在属性之间的循环依赖关求值。如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。为了设计编译程序，我们只系，那么称该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。处理良定义的属性文法。 第七章

34、第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（3434）课程名称属性的计算顺序属性的计算顺序一个有向非循环图的拓扑序是图中结点的任何顺序一个有向非循环图的拓扑序是图中结点的任何顺序m m1 1, m, m2 2, , , m, mk k，使得，使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果边必须是从序列中前面的结点指向后面的结点。也就是说，如果m mi immj j是是m mi i到到m mj j的一条边，那么在序列中的一条边，那么在序列中m mi i必须出现在必须出现在m mj j之前。之前。 一个依赖图的任何拓扑排序都给出一个分析树中结点的语一个依赖图的任何

35、拓扑排序都给出一个分析树中结点的语义规则计算的有效顺序。义规则计算的有效顺序。这就是说，在拓扑排序中，在一这就是说，在拓扑排序中，在一个结点，语义规则个结点，语义规则b:=f(cb:=f(c1 1,c,c2 2, ,c ck k) )中的属性中的属性c c1 1,c,c2 2, ,c ck k在计算在计算b b以前都是可用的。以前都是可用的。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（3535）课程名称属性文法属性文法说明的翻译是很精确的。最基本的文法用于建立输入符号串的分析树。依赖说明的翻译是很精确的。最基本的文法用于建立输入符号串的分析树。依赖图如上面讨论的那样建

36、立。从依赖图的拓扑排序中，我们可以得到计算语义规则的图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。例例7.2Real id1,id2,id37.2Real id1,id2,id3分析树的依赖图分析树的依赖图每一条边都是从序号较低的结点指向序号较高的结点。历此，依赖图的一个拓扑排序每一条边都是从序号较低的结点指向序号较高的结点。历此，依赖图的一个拓扑排序可以从低序号到高序号顺序写出。从这个拓扑排序中我们可以得到下列程序，用可以从低序号到高序号顺序写出。从这个拓扑排

37、序中我们可以得到下列程序，用a an n来代表依赖图中与序号来代表依赖图中与序号n n的结点有关的属性：的结点有关的属性：a4: = reala5: = a4 addtype (id3, entry, a5); a7: = a5; addtype (id2,entry, a7)a9: = a7 addtype (id1,entry, a9)这些语义规则的计算将把这些语义规则的计算将把realreal类型填入到每个标识符对应的符号表项中。类型填入到每个标识符对应的符号表项中。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（3636）课程名称 属性计算方法属性计算方法树遍历的

38、属性计算方法树遍历的属性计算方法设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历（或称遍）。用多次遍历（或称遍）。 一遍扫描的处理方法一遍扫描的处理方法与树遍历的属性计算文法不同，一遍扫描的处理方法是在语法分析的同时计与树遍历的属性计算文法不同，一遍扫描的处理方法是

39、在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无无算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无无需构造实际的语法树。需构造实际的语法树。因为一遍扫描的处理方法与语法分析器的相互作用，它与下面两个因素密切因为一遍扫描的处理方法与语法分析器的相互作用，它与下面两个因素密切相关：相关：（1 1）所采用的语法分析方法）所采用的语法分析方法（2 2）属性的计算次序。）属性的计算次序。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（3737）课程名称例：定义定点二进制数的例：定义定点二进制数的CFG:CFG:(1) NSS(2) SSB(

40、3) SB(4) B0(5) B1 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（3838）课程名称 非终结符非终结符N N表示整个二进制数的数值，综合属表示整个二进制数的数值，综合属性性v v附加在附加在N N上：上：N v N v 非终结符非终结符B B 表示一个二进制数字，它有自己的表示一个二进制数字，它有自己的值值v v ，但该值分配给，但该值分配给N N的值与它的位置有关，的值与它的位置有关，是与是与2 2成比例，比例因子成比例，比例因子f f是从是从S S继承的属性继承的属性, ,所所以：以：B v f B v f 非终结符非终结符S S 表示一个二进制数字

41、串，它也有值，但该值与表示一个二进制数字串，它也有值，但该值与串的位置有关，与串的位置有关，与f f有关与串的长度有关与串的长度l l有关有关: S : S f v lf v l第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（3939）课程名称构造数值的属性断言可以如下构造数值的属性断言可以如下: : N vS f1 v 1 l1 S f 2 v 2 l2 v=v1+v2; f 1 =1; f2=2-l2 S f v l S f1v1 l 1B f 2v2 f1=2f ; f 2=f; v=v 1+v2;l=l1+1 B f v l=1 B f v0 v=0 1 v=f第

42、七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（4040）课程名称 N v S i1 l1 “” S i2 l2 v= i1+ 2-l2 i2 S i l S i1 l 1 Bi2 i =2 i1+ i2; ;l=l1+1 B i l=1 B i “0” i =0 “1” i =1第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（4141）课程名称 在某些情况下可用一遍扫描实现属性文法的语义规则计算。也就是说在语法分析的同时完成语义规则的计算，无须明显地构造语法树或构造属性之间的依赖图。因为单遍实现对于编译效率非常重要 具体的实现希望在单遍扫描中完成翻译

43、具体的实现希望在单遍扫描中完成翻译研究怎样实现这种翻译器。一个一般的属性文法的翻译器可能是很难建立的，然而有一大类属性文法的翻译器是很容易建立的 s-属性属性 适用于适用于自底向上的计算自底向上的计算 L-属性属性 适用于自顶向下的分析，也可用于适用于自顶向下的分析，也可用于自底向上。自底向上。 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（4242）课程名称S属性文法的自下而上计算S属性文法，它只含有综合属性。 综合属性可以在分析输入符号串的同时自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边

44、符号的属性值来计算。 S属性文法的翻译器通常可借助于LR分析器实现。在S属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（4343）课程名称产生式 语义规则） （.）1 . 1.） . .l）1* . 1. ）F . F.）（）（） . . ）ii .:.LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。 LR分析器增加语义栈增加语义栈 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（4444）课程名称 *的分析和计值过程步骤 动作

45、状态栈 语义栈(值栈) 符号栈 余留输入串） 3*） 3 *） *） *） *） *） *） *） *） * ） * ） （）（） * #） （）（） ） （）（） ）接受）接受 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（4545）课程名称BOTTOMBOTTOMUPUP语义处理是作类型检查，对二目运算符的运算对象语义处理是作类型检查，对二目运算符的运算对象进行类型匹配审查。进行类型匹配审查。(LR(LR分分析）：增加语义栈析）：增加语义栈 归约归约时进行语义动作时进行语义动作. .例7.7GE: (1) E T+TT+T(2) E (2) E T or TT or

46、 T(3) T (3) T n n(4) T (4) T b b 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（4646）课程名称E ET T1 1 + T+ T2 2 if T if T1 1. .type = type = intint and T and T2 2. .type= type= intint then E then E. .type :=type :=intint else error else error E E T T1 1 or Tor T2 2 if T if T1 1. .type = type = boolbool and T and T

47、2 2. .type= type= boolbool then E then E. .type :=type :=boolbool else error else error T T n T.type := int n T.type := int T T b T.type := bool b T.type := bool 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（4747）课程名称w =n + n# 4ninto#-2Tinto#-5+-2Tinto#-4nint5+-2Tinto#-6Tint5+-2Tinto#-1Eint0#- GE:的 LR(0)分分析析表表

48、 action GOTO 状状态态+ o n b # E T 0 S4 S3 1 2 1 acc 2 s5 s7 3 r4 r4 r4 r4 r4 4 r3 r3 r3 r3 r3 5 s4 s3 6 6 r1 r1 r1 r1 r1 7 s4 s3 8 8 r2 r2 r2 r2 r2 GE: (1) E T+TT+T(2) E (2) E T or TT or T(3) T (3) T n n(4) T (4) T b b第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（4848）课程名称w =n +b4ninto#-2Tinto#-5+-2Tinto#-3bbool5

49、+-2Tinto#-6Tbool5+-2Tinto#-1Eerroro#-第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（4949）课程名称L L属性文法和自顶向下翻译属性文法和自顶向下翻译一个属性文法称为一个属性文法称为L L属性文法，如果对于每个产生式属性文法，如果对于每个产生式AXAX1 1X X2 2X Xn n，其每个语义规，其每个语义规则中的每个属性或者是综合属性，或者是则中的每个属性或者是综合属性，或者是X Xj j（1jn1jn）的一个继承属性且这）的一个继承属性且这个继承属性仅依赖于：个继承属性仅依赖于：（1 1）产生式）产生式X Xj j在左边符号在左

50、边符号X X1 1，X X2 2，X Xj-1j-1的属性；的属性；（2 2）A A的继承属性。的继承属性。S S属性文法一定是属性文法一定是L L属性文法，因为（属性文法，因为（1 1）、（）、（2 2）限制只用于继承属性。）限制只用于继承属性。L L属性文法允许一次遍历就计算出所有属性值。属性文法允许一次遍历就计算出所有属性值。LLLL（1 1）这种自上而下分析文法的分析过程，从概念上说可以看成是深度优先建立）这种自上而下分析文法的分析过程，从概念上说可以看成是深度优先建立语法树的过程，因此，我们可以在自上而下语法分析的同时实现语法树的过程，因此，我们可以在自上而下语法分析的同时实现L L

51、属性文法的属性文法的计算。计算。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（5050）课程名称例（中缀表达式翻译成相应的后缀表达式）例（中缀表达式翻译成相应的后缀表达式）ETRETRRaddop T print(addopRaddop T print(addop. Lexeme) R. Lexeme) R1 1|Tnum print(num.valTnum print(num.val) 翻译模式（翻译模式（Translation schemesTranslation schemes）适合语法制导翻译的另一种描述形）适合语法制导翻译的另一种描述形式。翻译模式给出了使用语

52、义规则进行计算的次序，可把某些实现细节式。翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号括起来，插入到产生式右部的合适位们也称语义动作），用花括号括起来，插入到产生式右部的合适位置上置上。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（5151）课程名称输入串95 + 2的语法树，每个语义动作都作为相应产生式左部符号的结点的儿子，按深度优先次序执行图中的动作后，打印输出952+。 ET R9 print(9) -

53、 T print(-) R 5 print(5) + T print(+) R 2 print(2) 第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（5252）课程名称L L属性文法在自顶向下分析中的实现属性文法在自顶向下分析中的实现 带左递归的文法的翻译模式EE1 + T E.val: = E1.val + T.valEE1T E.val: = E1.valT.valET E.val: = T.valT(E) T.val: = E.valTnum T.val: = num.val第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（5353）课程名称消除

54、左递归的同时考虑属性，构造新的消除左递归的同时考虑属性，构造新的翻译模式翻译模式 ETR.i: =T.val R E.val: = R.sR + T R1.i:=R.i + T.val R1 R.s: = R1.sR- T R1.i: = R.i -T.val R1 R.s: = R1.sRR.s: = R.iT(E) T.val: =E.valTnum T.val: = num.val第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（5454）课程名称计算表达式计算表达式9-5+29-5+2.ER.i=9T.val=5T.val=9R.i=4 R.i=6T.val=2nu

55、m.val=9num.val=5num.val=2_+第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（5555）课程名称在上页的翻译模式中，每个数都是由在上页的翻译模式中，每个数都是由T T产生的，并且产生的，并且T.valT.val的值就是的值就是由属性由属性num.valnum.val给出的数的词法值。子表达式给出的数的词法值。子表达式9 95 5中的数字中的数字9 9是由是由最左边的最左边的T T生成的，但是减号和生成的，但是减号和5 5是由根的右子结点是由根的右子结点R R生成的。继生成的。继承属性承属性R.iR.i从从T.valT.val得到值得到值9 9。计算

56、。计算9 95 5并把结果并把结果4 4传递到中间的传递到中间的R R结点这是通过产生式中嵌入的下面动作实现：结点这是通过产生式中嵌入的下面动作实现：RR1 1.i: = R.i.i: = R.iT.valT.val 类似的动作把类似的动作把2 2加到加到9 95 5的值上，在最下面的的值上，在最下面的R R结点处产生结果结点处产生结果R.iR.i6 6。这个结将成为根结点处。这个结将成为根结点处E.valE.val的值的值,R,R的的综合属性综合属性s s在图中没有在图中没有表示出来，它用来向上复制这一结果一直到树根。表示出来，它用来向上复制这一结果一直到树根。 第七章第七章 语法制导翻译和

57、中间代码生成（语法制导翻译和中间代码生成（5656）课程名称 对于自顶向下分析，我们假设动作是在处于相同位置对于自顶向下分析，我们假设动作是在处于相同位置上的符号被展开（匹配成功）时执行的。如图中的第上的符号被展开（匹配成功）时执行的。如图中的第二个产生式中，第一个动作（对二个产生式中，第一个动作（对R R1 1.i.i赋值）是在赋值）是在T T被完被完全展开成终结符号后执行的，第二个动作是在全展开成终结符号后执行的，第二个动作是在R R1 1被完被完全展开成终结符号后执行的。正如前面我们所讨论的，全展开成终结符号后执行的。正如前面我们所讨论的，一个符号的继承属性必须由出现在这个符号之前的动一

58、个符号的继承属性必须由出现在这个符号之前的动作来计算，产生式左边非终结符的综合属性必须在它作来计算，产生式左边非终结符的综合属性必须在它所依赖的所有属性都计算出来以后才能计算。所依赖的所有属性都计算出来以后才能计算。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（5757）课程名称转换左递归翻译模式的方法推广到一般转换左递归翻译模式的方法推广到一般 假设翻译模式假设翻译模式1 1：AAAA1 1Y Y A.a: = g(AA.a: = g(A1 1。a, Y.y)a, Y.y)AXAX A.a: = f(X.x) A.a: = f(X.x)每个文法符号都有一个综合属性，用

59、相每个文法符号都有一个综合属性，用相应的小写字母表示，应的小写字母表示，g g和和f f是任意函数是任意函数 消除左递归，文法转换成：消除左递归，文法转换成：AXR RYRAXR RYR再考虑语义动作，翻译模式变为再考虑语义动作，翻译模式变为2 2AXAXR.i: = f(X.x)R.i: = f(X.x) R R A.a: =R.sA.a: =R.sRYRYRR1 1.i: = g(R.i,Y.y).i: = g(R.i,Y.y) R R1 1R.s: = RR.s: = R1 1.s.sRRR.s: = R.iR.s: = R.i第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间

60、代码生成（5858）课程名称 翻译模式翻译模式1 1和翻译模式和翻译模式2 2的结果是一样的。可以给的结果是一样的。可以给出串出串XYXY1 1Y Y2 2两棵带注释的语法树看出来，一棵是根据两棵带注释的语法树看出来，一棵是根据翻译模式翻译模式1 1自下而上计算属性的。一棵是根据翻译自下而上计算属性的。一棵是根据翻译模式模式2 2自上而下计算的。自上而下计算的。第七章第七章 语法制导翻译和中间代码生成（语法制导翻译和中间代码生成（5959）课程名称 AA1YA.a: = g(A1。a, Y.y)AX A.a: = f(X.x)A.a=g(g(f(X.x,Y1.y),Y2.y)A.a=g(f(X