语法制导翻译与属性文法实用教案

会计学1语法语法(yf)制导翻译与属性文法制导翻译与属性文法第一页，共97页。2022-4-202nE.val=E1.val+T.val问题(wnt)第1页/共97页第二页，共97页。2022-4-203处理以及符号表的访问等。图图6.1 编译器前端的逻辑编译器前端的逻辑(lu j)结构结构第2页/共97页第三页，共97页。2022-4-204n将静态检查和中间(zhngjin)代码生成结合到语法分析中进行的技术称为语法制导翻译 。第3页/共97页第四页，共97页。2022-4-205在语法分析的过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作(或调用相应的语义子程序)。第4页/共97页第五页，共97页。2022-4-206递的。第5页/共97页第六页，共97页。2022-4-207第6页/共97页第七页，共97页。2022-4-208n算及翻译工作同产生式相关联？第7页/共97页第八页，共97页。2022-4-209nnF digitF.val:=digit.lexvaln适宜在完成归约的时候进行第8页/共97页第九页，共97页。2022-4-2010nT real T.type := real nL L1.inh := L.inh L1,idaddtype(id.entry,L.inh) nL idaddtype(id.entry,L.inh)n适宜在进行推导(tudo)时完成第9页/共97页第十页，共97页。2022-4-2011据结构，用于描述语义信息，语义规则类似于计算，用于收集、传递和计算语义信息的。n属性通常被保存在分析树的相关节点中第10页/共97页第十一页，共97页。2022-4-2012n注释分析树：节点带有属性值的分析树第11页/共97页第十二页，共97页。2022-4-2013第12页/共97页第十三页，共97页。2022-4-2014F (E) Fval := EvalF digit Fval := digitlexval第13页/共97页第十四页，共97页。2022-4-2015(yush)又称为属性文法，属性文法的语义规则单纯根据常数和其它属性的值来定义某个属性的值第14页/共97页第十五页，共97页。2022-4-2016表达式项n消除左递归之后的算数表达式文法的一个子集：n TFT T *FT1 T Fdigit 第15页/共97页第十六页，共97页。2022-4-2017产生式产生式语义规则语义规则TFT T .inh := F.valT.val:= T .syn T *FT1T1.inh := T .inhF.valT .syn := T1.synT T .syn := T .inhFdigitF.val:=digit.lexval第16页/共97页第十七页，共97页。2022-4-2018第17页/共97页第十八页，共97页。2022-4-2019nT T .syn := T .inhnFdigitF.val:=digit.lexval 第18页/共97页第十九页，共97页。2022-4-2020而依赖图则可以帮助我们确定如何将这些属性值计算出来。第19页/共97页第二十页，共97页。2022-4-2021第20页/共97页第二十一页，共97页。2022-4-2022构造一条从节点ci到节点b的有向边；第21页/共97页第二十二页，共97页。2022-4-2023第22页/共97页第二十三页，共97页。2022-4-2024序。n例6.4 图6.4的拓扑排序为：n 1， 2， 3，4，5，6，7，8，9，10，11，12，13第23页/共97页第二十四页，共97页。2022-4-2025第24页/共97页第二十五页，共97页。2022-4-2026n这两种方法都不必显式构造依赖图，因此时空效率更高。第25页/共97页第二十六页，共97页。2022-4-2027第26页/共97页第二十七页，共97页。2022-4-2028n Xi本身的综合属性或继承属性，但前提是Xi的属性不能在依赖图中形成回路。nL-属性定义又称为L-属性文法。第27页/共97页第二十八页，共97页。2022-4-2029产生式产生式语义规则语义规则TFT T .inh := F.valT.val:= T .syn T *FT1T1.inh := T .inhF.valT .syn := T1.synT T .syn := T .inhFdigitF.val:=digit.lexval第28页/共97页第二十九页，共97页。2022-4-2030例例6.7 不是不是(b shi)L-属性定义的语法制属性定义的语法制导定义导定义产生式产生式语义规则语义规则ABCA.syn := B.bB.inh:=f(C.c, A.syn)语义规则语义规则B.inh:=f(C.c, A.syn)定义了一个继承属性，所以整个语定义了一个继承属性，所以整个语法制导定义就不是法制导定义就不是S-属性定义了。此外，虽然这条语义规则是合属性定义了。此外，虽然这条语义规则是合法的属性定义规则，但不满足法的属性定义规则，但不满足L-属性定义的要求。这是因为：属属性定义的要求。这是因为：属性性B.inh的定义中用到了属性的定义中用到了属性C.c，而，而C在产生式的右部处在在产生式的右部处在B的右的右边边(yu bian)。虽然在。虽然在L-属性定义中可以使用兄弟节点的属性来属性定义中可以使用兄弟节点的属性来定义某个属性，但这些兄弟节点必须是左兄弟节点才行。因此，定义某个属性，但这些兄弟节点必须是左兄弟节点才行。因此，该语法制导定义也不是该语法制导定义也不是L-属性定义。属性定义。 第29页/共97页第三十页，共97页。2022-4-2031L-属性定义属性定义(dngy)中的属性计算中的属性计算visit(N) for N的每个子节点的每个子节点(ji din)M(从左到右从左到右) 计算节点计算节点(ji din)M的继承属性的继承属性; visit (M); 计算节点计算节点(ji din)N的综合属性的综合属性;第30页/共97页第三十一页，共97页。2022-4-2032抽象语法树是表示程序层次结构的树，它把分析树中对抽象语法树是表示程序层次结构的树，它把分析树中对语义无关紧要的成分去掉，是分析树的抽象形式语义无关紧要的成分去掉，是分析树的抽象形式 ，也称，也称作语法结构树，或结构树。作语法结构树，或结构树。 语法树是常用的一种中间表示形式。语法树是常用的一种中间表示形式。 把语法分析和翻译分开。语法分析过程中完成翻译有把语法分析和翻译分开。语法分析过程中完成翻译有许多优点，但也有一些不足：许多优点，但也有一些不足： 1. 1.适于语法分析的文法可能不完全反映语言成分的自适于语法分析的文法可能不完全反映语言成分的自然层次结构；然层次结构； 2. 2. 由于语法分析方法的限制，对分析树结点由于语法分析方法的限制，对分析树结点(ji (ji din)din)的访问顺序和翻译需要的访问顺序不一致。的访问顺序和翻译需要的访问顺序不一致。 6.3.5 6.3.5 属性属性(shxng)(shxng)计算示例计算示例抽象语法树的构造抽象语法树的构造 第31页/共97页第三十二页，共97页。2022-4-2033 产生式产生式Sif B then S1 else S2的语法树的语法树 if-then-else | B S1 S2 赋值语句的语法树赋值语句的语法树 assignment variable expression 在语法树中，运算符号和关键字都不在叶结点在语法树中，运算符号和关键字都不在叶结点(ji din)，而是在内部结点，而是在内部结点(ji din)中出现。中出现。语法语法(yf)树树第32页/共97页第三十三页，共97页。2022-4-2034构造表达式的语法树使用的函数构造表达式的语法树使用的函数 1. mknode(op, left, right) 建立一个标记为建立一个标记为op的运算的运算符结点，两个域符结点，两个域left和和right分别是指向分别是指向(zh xin)左左右运算对象的指针。右运算对象的指针。 2mkleaf(id, entry) 建立一个标记为建立一个标记为id的标识符结的标识符结点，其域点，其域entry是指向是指向(zh xin)该标识符在符号表中该标识符在符号表中相应表项的指针。相应表项的指针。 3. mkleaf(num, val) 建立一个标记为建立一个标记为num的数结点，的数结点，其域其域val用于保存该数的值。用于保存该数的值。构造构造(guzo)表达式的语法树表达式的语法树第33页/共97页第三十四页，共97页。2022-4-2035构造表达式语法树的语法制导构造表达式语法树的语法制导(zhdo)定义定义产生式产生式语义规则语义规则 T T1 * FT.node := mknode(*, T1.node, F.node) T T1 / FT.node := mknode(/, T1.node, F.node) T FT.node := F.node F (E) F.node:= E.node F idF.node := mkleaf(id, id.entry) F numF.node := mkleaf(num, num.val)第34页/共97页第三十五页，共97页。2022-4-2036图图6.5 3*x/y的语法的语法(yf)树的树的构造构造第35页/共97页第三十六页，共97页。2022-4-20373*x/y的抽象的抽象(chuxing)语法树语法树的构造步骤的构造步骤 p1:=mkleaf(num,3)； p2:=mkleaf(id, entry-x)； p3:=mknode(*, p1, p2)； p4:=mkleaf(id, entry-y)； p5:=mknode(/, p3, p4)； 图图6.5的语法树是自底向上构造的，对于那些为便的语法树是自底向上构造的，对于那些为便于进行自顶向下分析而设计的文法来说，使用同样于进行自顶向下分析而设计的文法来说，使用同样的步骤照样可以的步骤照样可以(ky)建立图建立图6.5中的抽象语法树。中的抽象语法树。当然，分析树的结构可能大不相同，而且可能需要当然，分析树的结构可能大不相同，而且可能需要引入继承属性来传递语义信息。引入继承属性来传递语义信息。第36页/共97页第三十七页，共97页。2022-4-2038在自顶向下分析在自顶向下分析(fnx)过程中构造过程中构造语法树语法树产生式产生式语义规则语义规则 T FT T.node := T .synT .inh := F.node T *FT1T1.inh := mknode(*, T .inh, F.node)T .syn:= T1.syn T /FT1T1.inh := mknode(/, T .inh, F.node)T .syn:= T1.syn T T .syn := T .inh F (E)F.node := E.node F idF.node := mkleaf(id, id.entry) F numF.node := mkleaf(num, num.val)第37页/共97页第三十八页，共97页。2022-4-2039根据根据(gnj)表表6.6的语法制导定义构造的语的语法制导定义构造的语法树法树第38页/共97页第三十九页，共97页。2022-4-2040l 定义定义l 翻译模式是语法制导定义的一种便翻译模式是语法制导定义的一种便于于(biny)(biny)实现的书写形式。其中属性实现的书写形式。其中属性与文法符号相关联，语义规则或语义动与文法符号相关联，语义规则或语义动作用花括号作用花括号 括起来，并可被插入括起来，并可被插入到产生式右部的任何合适的位置上。到产生式右部的任何合适的位置上。l 这是一种语法分析和语义动作交错这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分的表示法，它表达在按深度优先遍历分析树的过程中何时执行语义动作。析树的过程中何时执行语义动作。l 翻译模式给出了使用语义规则进行翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译计算的顺序。可看成是分析过程中翻译的注释。的注释。6.4 翻译翻译(fny)模模式式第39页/共97页第四十页，共97页。2022-4-2041 将中缀表达式翻译成后缀表达式：将中缀表达式翻译成后缀表达式： ETR Raddop T print(addop.lexeme)R1| Tnumprint(num.val) 把语义动作看成终结符号把语义动作看成终结符号(fho)，输入，输入3+4-5,其分析其分析树如图树如图6.8，当按深度优先遍历它，执行遍历中访问的语，当按深度优先遍历它，执行遍历中访问的语义动作，将输出义动作，将输出 3 4 + 5 -它是输入表达式它是输入表达式3+4-5的后缀式。的后缀式。例例6.10 一个简单的翻译一个简单的翻译(fny)模式模式第40页/共97页第四十一页，共97页。2022-4-2042图图6.8 3+4-5的带语义动作的带语义动作(dngzu)的的分析树分析树第41页/共97页第四十二页，共97页。2022-4-2043l 前提前提语法制导定义是语法制导定义是L-属性定义属性定义l 保证语义动作不会引用还没计算出来的属保证语义动作不会引用还没计算出来的属性值性值l1. 只需要综合属性的情况只需要综合属性的情况l 为每一个语义规则建立一个包含赋值的为每一个语义规则建立一个包含赋值的动作，并把该动作放在相应的产生式右部的动作，并把该动作放在相应的产生式右部的末尾末尾(mwi)。l 例如：例如：TT1*F Tval:=T1val*Fvall 转换成：转换成：l TT1*FTval:=T1val*Fval翻译模式的设计翻译模式的设计 根据语根据语法制导法制导(zhdo)定义定义第42页/共97页第四十三页，共97页。2022-4-20442. 既有综合属性又有继承属性既有综合属性又有继承属性 产生式右边的符号的继承属性必须在这个产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。符号以前的动作中计算出来。 一个动作不能引用这个动作右边符号的综一个动作不能引用这个动作右边符号的综合属性。合属性。 产生式左边非终结符号的综合属性只有在产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常计算。计算这种属性的动作通常(tngchng)可放在产生式右端的末尾。可放在产生式右端的末尾。翻译模式的设计翻译模式的设计 根据语法根据语法制导制导(zhdo)定义定义第43页/共97页第四十四页，共97页。2022-4-2045 下面下面(xi mian)的翻译模式不满足要求：的翻译模式不满足要求： SA1A2 A1in:=1; A2in:=2 A a print(Ain) /*A.in尚无定义尚无定义*/ 例例6.11 从从L-属性制导定义建立一个满足上面属性制导定义建立一个满足上面 要求的翻译模式。要求的翻译模式。 使用文法产生的语言是数学排版语言使用文法产生的语言是数学排版语言EQN E sub 1val编排结果编排结果第44页/共97页第四十五页，共97页。2022-4-2046 B表示盒子表示盒子 BB1B2代表两个相邻盒子的并列，且代表两个相邻盒子的并列，且B1位位于于B2的左边。的左边。 BB1 sub B2代表盒子代表盒子B1后随下标盒子后随下标盒子B2，下标盒子下标盒子 B2以较小的字体和较低的位置出现。以较小的字体和较低的位置出现。 B(B1)代表一个由括号括起来的盒子代表一个由括号括起来的盒子B1，主要是为了对多个盒子或下标进行分组。在主要是为了对多个盒子或下标进行分组。在EQN中，使用花括号进行分组，此处使用圆括中，使用花括号进行分组，此处使用圆括号是为了避免号是为了避免(bmin)跟语义动作外面的花括跟语义动作外面的花括号产生冲突。号产生冲突。 Btext代表文本字符串，即任意字符组成的代表文本字符串，即任意字符组成的串。串。该文法是二义性的文法，将该文法是二义性的文法，将“并列并列”和和“下标下标”看看成是左结合的，并令成是左结合的，并令“下标下标”的优先级高于的优先级高于“并列并列”的话，则可以对该文法所描述的语言进行自底的话，则可以对该文法所描述的语言进行自底向上的语法分析。向上的语法分析。第45页/共97页第四十六页，共97页。2022-4-2047 属性设置属性设置 point size用于表示盒子中文本的尺寸用于表示盒子中文本的尺寸(以点来计算，也就是字号以点来计算，也就是字号)。如果。如果(rgu)标准盒子的尺寸为标准盒子的尺寸为p，则下标盒子的尺寸，则下标盒子的尺寸为为0.7p。属性。属性B.ps表示盒子表示盒子B的尺寸，该的尺寸，该属性是继承属性。属性是继承属性。 每个盒子都有一个基线每个盒子都有一个基线(baseline)，用，用来表示每个文本底部的垂直位置。来表示每个文本底部的垂直位置。 height用来表示从盒子的顶部到基线的用来表示从盒子的顶部到基线的距离。属性距离。属性B.ht表示盒子表示盒子B的高度的高度height，该属性是综合属性。该属性是综合属性。 depth用来表示从基线到盒子底部的距用来表示从基线到盒子底部的距离。用属性离。用属性B.dp表示盒子表示盒子B的深度的深度depth，该属性也是综合属性。该属性也是综合属性。第46页/共97页第四十七页，共97页。2022-4-2048表表6.7 对盒子进行排版的语法制导对盒子进行排版的语法制导(zhdo)定义定义产生式产生式语义规则语义规则S BB.ps:=10S.ht := B.htS.dp:= B.dpB B1B2B1.ps := B.psB2.ps := B.psB.ht := max(B1.ht, B2.ht)B.dp := max(B1.dp, B2.dp)BB1 sub B2B1.ps:=B.psB2.ps:=0.7B.psB.ht:=max(B1.ht, B2.ht-0.25B.ps)B.dp:=max(B1.dp, B2.dp+0.25B.ps)B (B1)B1.ps:=B.psB.ht:=B1.htB.dp:=B1.dpB textB.ht:=getheight(B.ps,text.lexval)B.dp:=getdepth(B.ps,text.lexval)第47页/共97页第四十八页，共97页。2022-4-2049SB.ps:=10B S.ht := B.ht;S.dp:= B.dpBB1.ps:=B.psB1B2 .ps:=B.ps B2B.ht:=max(B1.ht,B2.ht)BB1.ps:=B.psB1subB2.ps:=0.7B.ps B2B.ht:=max(B1.ht,B2.ht-0.25B.ps);B.dp:=max(B1.dp,B2.dp+0.25B.ps);B(B1.ps:=B.psB1)B.ht:=B1.ht; B.dp:=B1.dp;BtextB.ht:=getheight(B.ps,text.lexval); B.dp:=getdepth(B.ps,text.lexval)从表从表6.7构造构造(guzo)的翻译模式的翻译模式第48页/共97页第四十九页，共97页。2022-4-2050T F T .inh := F.nodeT T.node := T .synT *F T1.inh := mknode(*, T .inh,F.node) T1T .syn := T1.synT /F T1.inh := mknode(/, T .inh,F.node) T1T .syn := T1.synT T .syn := T .inhF (E )F.node := E.nodeF id F.node := mkleaf(id, id.entry)F num F.node := mkleaf(num, num.val)从表从表6.6构造的翻译构造的翻译(fny)模式模式第49页/共97页第五十页，共97页。2022-4-2051在分析栈中使用一个附加在分析栈中使用一个附加(fji)(fji)的域来存放的域来存放综合属性值。下图为一个带有综合属性值域的综合属性值。下图为一个带有综合属性值域的分析栈：分析栈：stackval.XX.xY.Y.y.ZZ.ztop6.4.2 S-属性属性(shxng)定义的自底向上计算定义的自底向上计算第50页/共97页第五十一页，共97页。2022-4-2052 A b:=f(c1,c2,ck) b是是A的综合属性，的综合属性，ci (1 i k)是是 中符号的属性。综中符号的属性。综合属性的值是在自底向上的分析过程中，每次归约之合属性的值是在自底向上的分析过程中，每次归约之前前(zhqin)进行计算的。进行计算的。 AXYZ A a:=f(X x,Y y,Z z)A aX x Y y Z z第51页/共97页第五十二页，共97页。2022-4-2053topstackval.XX.xYY.yZZ.zstackval.AA.atop实现时，将定义式实现时，将定义式 A.a:=f(X.x, Y.y, Z.z) (抽象抽象)变变成成stackntop.val:=f(stacktop-2.val, stacktop-1.val, stacktop.val) (具体可执行代码具体可执行代码(di m)。在执行代码在执行代码(di m)段之前执行：段之前执行： ntop:=top-r+1 r是句柄的长度是句柄的长度执行代码执行代码(di m)段后执行：段后执行： top:=ntop;第52页/共97页第五十三页，共97页。2022-4-2054例例6.14 用用LR分析器实现分析器实现(shxin)台式台式计算器计算器与表与表6.2对比对比LEnprint(stacktop-1.val);top:=top-1;EE1+Tstacktop-2.val:= stacktop-2.val + stacktop.val; top:=top-2;ETTT1*Fstacktop-2.val:= stacktop-2.val stacktop.val; top:=top-2;TFF(E) stacktop-2.val:= stacktop-1.val;top:=top-2;Fdigit第53页/共97页第五十四页，共97页。2022-4-2055表表6.8 翻译翻译(fny)输入输入6+7*8n上的移上的移动序列动序列输入输入 state val 使用使用(shyng)的产生式的产生式6+7*8n - - +7*8n 6 6 +7*8n F 6 Fdigit +7*8n T 6 TF +7*8n E 6 ET 7*8n E+ 6+ *8n E+7 6+7第54页/共97页第五十五页，共97页。2022-4-2056 *8n E+F 6+7 F digit *8n E+T 6+7 T F 8n E+T* 6+7* n E+T*8 6+7*8 n E+T*F 6+7*8 F digit n E+T 6+56 TT*F n E 62 E E+T En 62 L 62 L En第55页/共97页第五十六页，共97页。2022-4-2057 采用自底向上分析，例如采用自底向上分析，例如LRLR分析，首先给出分析，首先给出S-S-属性定义，然后，把属性定义，然后，把S-S-属性定义变成可执行的属性定义变成可执行的代码段，这就构成了翻译程序。象一座建筑，语代码段，这就构成了翻译程序。象一座建筑，语法分析是构架，归约处有一个法分析是构架，归约处有一个“挂钩挂钩”，语义分，语义分析和翻译的代码段（语义子程序）就挂在这个钩析和翻译的代码段（语义子程序）就挂在这个钩子上。这样子上。这样(zhyng)(zhyng)，随着语法分析的进行，随着语法分析的进行，归约前调用相应的语义子程序归约前调用相应的语义子程序, ,完成翻译的任务。完成翻译的任务。S-属性定义属性定义(dngy)小结小结第56页/共97页第五十七页，共97页。2022-4-2058l 用翻译用翻译(fny)(fny)模式构造自顶向下的翻译模式构造自顶向下的翻译(fny)(fny)。l1. 1. 从翻译从翻译(fny)(fny)模式中消除左递归模式中消除左递归 l 对于一个翻译对于一个翻译(fny)(fny)模式，若采用自顶向下分模式，若采用自顶向下分析，必须消除左递归和提取左公因子，在改写基础文析，必须消除左递归和提取左公因子，在改写基础文法时考虑属性值的计算。法时考虑属性值的计算。l 对于自顶向下语法分析，假设语义动作是在与之对于自顶向下语法分析，假设语义动作是在与之处于同一位置的文法非终结符被展开时执行的，而且处于同一位置的文法非终结符被展开时执行的，而且不考虑继承属性的处理（很简单）。不考虑继承属性的处理（很简单）。6.4.3 L-属性属性(shxng)定义的自顶向定义的自顶向下翻译下翻译第57页/共97页第五十八页，共97页。2022-4-2059l 例例6.15 考虑考虑(kol)如下将中缀表达式翻译为后缀表达如下将中缀表达式翻译为后缀表达式的翻译模式中的两个产生式：式的翻译模式中的两个产生式：lE E1+T print(+);lE TllE TRlR +T print(+); RlR 只有只有(zhyu)简单语义动作时的左递简单语义动作时的左递归消除归消除第58页/共97页第五十九页，共97页。2022-4-2060l 设有如下左递归翻译模式：设有如下左递归翻译模式：l AA1YA.a:=g(A1.a,Y.y) l AX A.a:=f(X.x)l假设每个非终结符都有一个综合属性，用相应假设每个非终结符都有一个综合属性，用相应(xingyng)的小写字母表示，的小写字母表示，g和和f是任意函数。是任意函数。 l 消除左递归后，文法转换成消除左递归后，文法转换成l AX Rl RY R|S-属性定义属性定义(dngy)的左递归消除的左递归消除第59页/共97页第六十页，共97页。2022-4-2061l 再考虑语义动作，翻译模式变为：再考虑语义动作，翻译模式变为： l AX Ri:=f(Xx) l R Aa:=Rs l RY R1i:=g(Ri,Yy) l R1 Rs:=R1s l R Rs:=Ri l经过转换的翻译模式使用经过转换的翻译模式使用R的继承属性的继承属性i和综合和综合(zngh)属性属性s。l转换前后的结果是一样的转换前后的结果是一样的,l为什么？为什么？S-属性属性(shxng)定义的左递归消除定义的左递归消除AA1Y A.a:=g(A1.a,Y.y) AX A.a:=f(X.x)引入继承引入继承(jchng)属性属性R.i来收集应用函数来收集应用函数g的计算结果。其的计算结果。其初始值为初始值为A.a:=f(X.x）引入综合属性引入综合属性R.s在在R结束生成结束生成Y时复制时复制R.i的值。的值。第60页/共97页第六十一页，共97页。2022-4-2062A a=g(g(f(X x),Y1 y),Y2 y)A a=g(f(X x),Y1 y)A a=f(X x)Y2Y1X(a)输入输入(shr)：XY1Y2第61页/共97页第六十二页，共97页。2022-4-2063AR i=f(X x)R i=g(f(X x),Y1 y)R i=g(g(f(X x),Y1 y),Y2 y)Y2Y1X(b)第62页/共97页第六十三页，共97页。2022-4-2064L-属性定义的递归下降翻译器的构造：属性定义的递归下降翻译器的构造：1对每个非终结符对每个非终结符A构造一个函数构造一个函数A，将非终结，将非终结符符A的各个继承属性当作函数的各个继承属性当作函数A的形式参数，而的形式参数，而将非终结符将非终结符A的综合属性集当作函数的综合属性集当作函数A的返回值，的返回值，为了便于讨论为了便于讨论(toln)，假设每个非终结符只具，假设每个非终结符只具有一个综合属性。有一个综合属性。2在函数在函数A的过程体中，不仅要进行语法分析，的过程体中，不仅要进行语法分析，而且要处理相应的语义属性。函数而且要处理相应的语义属性。函数A的代码首先的代码首先根据当前输入确定用哪个产生式展开根据当前输入确定用哪个产生式展开A，然后按，然后按照照3中所给的方法对各产生式进行编码。中所给的方法对各产生式进行编码。2. L-属性定义属性定义(dngy)的递归下降翻译法的递归下降翻译法 第63页/共97页第六十四页，共97页。2022-4-20653与每个产生与每个产生(chnshng)式对应的程序代码的工作过程为：按式对应的程序代码的工作过程为：按照从左到右的次序，依次对产生照从左到右的次序，依次对产生(chnshng)式右部的记号、非终式右部的记号、非终结符和语义动作执行如下的动作：结符和语义动作执行如下的动作：1) 对带有综合属性对带有综合属性x的符号的符号X，将，将x的值保存在的值保存在X.x中，并生成一中，并生成一个函数调用来匹配个函数调用来匹配X，然后继续读入下一个输入符号；，然后继续读入下一个输入符号；2) 对非终结符对非终结符B，生成一个右部带有函数调用的赋值语句，生成一个右部带有函数调用的赋值语句c:=B(b1,b2,bk)，其中，其中，b1,b2,bk是代表是代表B的继承属性的变的继承属性的变量，量，c是代表是代表B的综合属性的变量；的综合属性的变量；3) 对于语义动作，将其代码复制到语法分析器中，并将对属性的对于语义动作，将其代码复制到语法分析器中，并将对属性的引用改为对相应变量的引用。引用改为对相应变量的引用。2. L-属性定义属性定义(dngy)的递归下降翻译法的递归下降翻译法 第64页/共97页第六十五页，共97页。2022-4-2066 例例 6.16 6.16 function T:syntax_tree_node; function T (inh: syntax_tree_node):syntax_tree_node; function F:syntax_tree_node; function T:syntax_tree_node;var node, syn: syntax_tree_node;beginnode := F;syn := T (node);return syn end;第65页/共97页第六十六页，共97页。2022-4-2067function T (inh: syntax_tree_node):syntax_tree_node;var node,inh1,syn1: syntax_tree_node; oplexeme:char;beginif lookahead = * then begin/* 匹配匹配(ppi)产生式产生式T *FT */ oplexeme := lexval; match(*); node := F; inh1:=mknode(*, inh, node); syn1 := T (inh1); syn := syn1endelse if lookahead = / then begin/* 匹配匹配(ppi)产生式产生式T /FT */oplexeme := lexval;match(/); node := F;inh1:=mknode(/, inh, node); syn1 := T (inh1); syn := syn1end else syn := inh; return syn end; 第66页/共97页第六十七页，共97页。2022-4-2068function F:syntax_tree_node;var node: syntax_tree_node;begin if lookahead = ( then begin/* 匹配匹配(ppi)产生式产生式F (E) */match(); node := E;match()endelse if lookahead = id then begin/* 匹配匹配(ppi)产生式产生式F id */match(id); node := mkleaf(id, id.entry) endelse if lookahead = num then begin/* 匹配匹配(ppi)产生式产生式F num */match(num); node := mkleaf(num, num.val)end return node end; 第67页/共97页第六十八页，共97页。2022-4-2069第68页/共97页第六十九页，共97页。2022-4-2070（程序自身控制(kngzh)对栈的操作）。注：语义与语法栈不同步。第69页/共97页第七十页，共97页。2022-4-2071n Fide8n Fnume9第70页/共97页第七十一页，共97页。2022-4-2072-#语义栈语义栈语法语法(yf)栈栈3*x/y#输入输入(shr)串串例例6.17 对输入对输入(shr)串串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作1. 初始化初始化T第71页/共97页第七十二页，共97页。2022-4-2073-#语义栈语义栈语法语法(yf)栈栈3*x/y#输入输入(shr)串串例例6.17 对输入对输入(shr)串串3*x/y的的翻译翻译语法分析动作和语义操作语法分析动作和语义操作2. 选产生式选产生式的右部进栈的右部进栈e2e1FT 第72页/共97页第七十三页，共97页。2022-4-2074-#语义栈语义栈语法语法(yf)栈栈3*x/y#输入输入(shr)串串例例6.17 对输入对输入(shr)串串3*x/y的的翻译翻译语法分析动作和语义操作语法分析动作和语义操作3.选择产生式选择产生式,num3不进栈，调不进栈，调用用e9，调用，调用e9后，叶结点后，叶结点F.node被压入语义栈被压入语义栈 e2e1e9T F.node第73页/共97页第七十四页，共97页。2022-4-2075-#语义栈语义栈语法语法(yf)栈栈3*x/y#输入输入(shr)串串例例6.17 对输入对输入(shr)串串3*x/y的翻的翻译译语法分析动作和语义操作语法分析动作和语义操作4.执行动作执行动作e1，F.node出栈，出栈，T .inh被压入栈被压入栈 e2e1T T .inh第74页/共97页第七十五页，共97页。2022-4-2076-#语义栈语义栈语法语法(yf)栈栈3*x/y#输入输入(shr)串串例例6.17 对输入对输入(shr)串串3*x/y的的翻译翻译语法分析动作和语义操作语法分析动作和语义操作5.选择产生式选择产生式,*不进栈不进栈 e2T e5e4FT .inh第75页/共97页第七十六页，共97页。2022-4-2077-#语义栈语义栈语法语法(yf)栈栈3*x/y#输入输入(shr)串串例例6.17 对输入对输入(shr)串串3*x/y的翻的翻译译语法分析动作和语义操作语法分析动作和语义操作6.选择产生式选择产生式,idx不进栈，调用不进栈，调用e8，调用调用e8后，叶结点后，叶结点F.node被压入语被压入语义栈义栈 e2T e5e4T .inhF.nodee8第76页/共97页第七十七页，共97页。2022-4-2078-#语义栈语义栈语法语法(yf)栈栈3*x/y#输入输入(shr)串串例例6.17 对输入对输入(shr)串串3*x/y的的翻译翻译语法分析动作和语义操作语法分析动作和语义操作7.执行动作执行动作e5，F.node和和T .inh均均被弹出栈，新的被弹出栈，新的T .inh被压入栈被压入栈 T .inhe2T e5e4第77页/共97页第七十八页，共97页。2022-4-2079-#语义栈语义栈语法语法(yf)栈栈3*x/y#输入输入(shr)串串例例6.17 对输入对输入(shr)串串3*x/y的翻的翻译译语法分析动作和语义操作语法分析动作和语义操作8.选择产生式选择产生式, /不进栈不进栈 T .inhe2e4T e4e3F第78页/共97页第七十九页，共97页。2022-4-2080-#语义栈语义栈语法语法(yf)栈栈3*x/y#输入输入(shr)串串例例6.17 对输入对输入(shr)串串3*x/y的翻的翻译译语法分析动作和语义操作语法分析动作和语义操作9.选择产生式选择产生式,idy不进栈，调用不进栈，调用e8，调用，调用e8后，叶结点后，叶结点F.node被压被压入语义栈入语义栈 T .inhF.nodee2e4T e4e3e8第79页/共97页第八十页，共97页。2022-4-2081-#语义栈语义栈语法语法(yf)栈栈3*x/y#输入输入(shr)串串例例6.17 对输入对输入(shr)串串3*x/y的的翻译翻译语法分析动作和语义操作语法分析动作和语义操作10.执行动作执行动作e3，F.node和和T .inh均均被弹出栈，新的被弹出栈，新的T .inh被压入栈被压入栈 T .inhe2e4T e4e3第80页/共97页第八十一页，共97页。2022-4-2082-#语义栈语义栈语法语法(yf)栈栈3*x/y#输入输入(shr)串串例例6.17 对输入对输入(shr)串串3*x/y的的翻译翻译语法分析动作和语义操作语法分析动作和语义操作11.选择产生式，选择产生式，T .inh被弹出栈，被弹出栈，T .syn被压入栈被压入栈 e2e4e6e4T .inh第81页/共97页第八十二页，共97页。2022-4-2083-#语义栈语义栈语法语法(yf)栈栈3*x/y#输入输入(shr)串串例例6.17 对输入对输入(shr)串串3*x/y的的翻译翻译语法分析动作和语义操作语法分析动作和语义操作12.依次执行动作依次执行动作e6,e4,e4,e2, 最终语义栈中只有最终语义栈中只有T.node, 代表代表3*x/y的语法树的根结点的语法树的根结点 T.node第82页/共97页第八十三页，共97页。2022-4-2084第83页/共97页第八十四页，共97页。2022-4-2085第84页/共97页第八十五页，共97页。2022-4-2086第85页/共97页第八十六页，共97页。2022-4-2087计算的，亦即翻译模式可能包含如下片断：n AB.inh := f(A.inh);BC第86页/共97页第八十七页，共97页。2022-4-2088第87页/共97页第八十八页，共97页。2022-4-2089第88页/共97页第八十九页，共97页。2022-4-2090第89页/共97页第九十页，共97页。2022-4-2091保证保证(bozhng)在在B的子树被归约时，的子树被归约时，B.ps的值出现在分的值出现在分析栈中的已知位置析栈中的已知位置归约归约B1之前，之前，B.ps可以在可以在栈中找到，所以栈中找到，所以B1.ps := B.ps 可以省略。但归约可以省略。但归约B2之前，无法确定其之前，无法确定其前有几个前有几个B1，因此，因此，无法预测无法预测B.ps在栈中的在栈中的位置。位置。第90页/共97页第九十一页，共97页。2022-4-2092栈顶的下标。第91页/共97页第九十二页，共97页。2022-4-2093产产 生生 式式 语语 义义 规规 则则 S LB B.ps := L.syn; S.ht := B.ht ; S.dp := B.dp L L.syn := 10 B B1 MB2 B1.ps := B.ps; M.inh := B.ps;B2.ps := M.syn;B.ht := max(B1.ht, B2.ht ) M M.syn := M.inh B B1 sub NB2 B1.ps :=B.ps; N.inh := B.ps;B2.ps := N.syn; B.ht := disp (B1.ht, B2.ht);B.dp:=max(B1.dp, B2.dp) N N.syn := 0.7 N.inhB text B.ht := getheight(B.ps,text.lexval);B.dp:= getdepth(B.ps,text.lexval)第92页/共97页第九十三页，共97页。2022-4-2094产产 生生 式式 代代 码码 段段S LB stackntop.val2 := stacktop.val2stackntop.val3 := stacktop.val3 L stackntop.val1 := 10 B B1 MB2 stackntop.val2 := max(stacktop-2.val2, stacktop.val2)stackntop.val3 := max(stacktop-2.val3, stacktop.val3) M stackntop.val1 := stacktop-1.val1 B B1 sub NB2 stackntop.val2:= max(stacktop-3.val2, stacktop.val2-0.25stacktop-4.val1)stackntop.val3 := max(stacktop-3.val3, stacktop.val3+0.25stacktop-4.val1) N stackntop.val1 := 0.7stacktop-2.val1 B text stackntop.val2 := getheight(stacktop-1.val1,text.lexval)stackntop.val3 := getdepth(stacktop-1.val1,text.lexval) 第93页/共97页第九十四页，共97页。2022-4-2095第94页/共97页第九十五页，共97页。2022-4-2096该语义动作的执行时机，这就是翻译模式。翻译模式给语义分析的实现提供了更好的支持。第95页/共97页第九十六页，共97页。2022-4-2097第96页/共97页第九十七页，共97页。