《第六章_属性文法和语法制导翻译.ppt》由会员分享，可在线阅读，更多相关《第六章_属性文法和语法制导翻译.ppt（76页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章第六章属性文法和语法制导翻译属性文法和语法制导翻译内容内容属性文法属性文法基于属性文法的处理方法基于属性文法的处理方法S-属性文法的自下而上计算属性文法的自下而上计算L-属性文法和自顶向下翻译属性文法和自顶向下翻译自下而上计算继承属性自下而上计算继承属性第六章第六章属性文法和语法制导翻译属性文法和语法制导翻译语义语义：一组规则：一组规则，用它可以定义一个程序的意用它可以定义一个程序的意义义。描述方法：描述方法：自然语言描述：隐藏错误、二义性和不完整性自然语言描述：隐藏错误、二义性和不完整性形式描述：形式描述：F 操作语义操作语义(PL/1)(PL/1)F 指称语义指称语义(ADA)(AD
2、A)F 代数语义代数语义(PASCAL)(PASCAL)属性文法属性文法第六章第六章属性文法和语法制导翻译属性文法和语法制导翻译编译中的语义处理包括两个功能编译中的语义处理包括两个功能：（1）审查每个语法结构的静态语义，即验证）审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。也称为语法结构合法的程序是否真正有意义。也称为静态语义分析或静态审查静态语义分析或静态审查；（2）如果静态语义正确，则执行真正的翻译，）如果静态语义正确，则执行真正的翻译，即即生成中间代码生成中间代码或生成实际的目标代码。或生成实际的目标代码。以上工作普遍基于以上工作普遍基于属性文法和语法制导翻属性文法
3、和语法制导翻译方法译方法。6.1属性文法属性文法属性文法属性文法（也称属性翻译文法）（也称属性翻译文法）Knuth在在1968年提出年提出在在上上下下文文无无关关文文法法的的基基础础上上，为为每每个个文文法法符符号号（终终结结符符或或非非终终结结符符）配配备备若若干干相相关关的的“值值”（称为（称为属性属性）。）。属属性性代代表表与与文文法法符符号号相相关关信信息息，如如类类型型、值值、代码序列、符号表内容等代码序列、符号表内容等属性可以进行计算和传递属性可以进行计算和传递语语义义规规则则：对对于于文文法法的的每每个个产产生生式式都都配配备备了了一一组属性的计算规则组属性的计算规则6.1属性文
4、法属性文法属性属性综合属性综合属性：“自下而上自下而上”传递信息传递信息继承属性继承属性：“自上而下自上而下”传递信息传递信息在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A 都都有一套与之相关联的语义规则，每条规则的形式有一套与之相关联的语义规则，每条规则的形式为：为：b:=f(c1,c2,ck)这里，这里，f是一个函数，而且或者是一个函数，而且或者1.b是是A的的一一个个综综合合属属性性并并且且c1,c2,ck是是产产生生式式右右边边文法符号的属性，或者文法符号的属性，或者2.b是是产产生生式式右右边边某某个个文文法法符符号号的的一一个个继继承承属属性性并并且且c1,
5、c2,ck是是A或产生式右边任何文法符号的属性。或产生式右边任何文法符号的属性。在两种情况下，属性在两种情况下，属性b依赖于属性依赖于属性c1,c2,ck。6.1属性文法属性文法说明说明终结符只有综合属性终结符只有综合属性，由词法分析器提供，由词法分析器提供非非终终结结符符既既可可有有综综合合属属性性也也可可有有继继承承属属性性，文文法法开开始始符符号号的的所所有有继继承承属属性性作作为为属属性性计计算算前前的的初初始始值值对对出出现现在在产产生生式式右右边边的的继继承承属属性性和和出出现现在在产产生生式式左左边边的的综综合合属属性性都都必必须须提提供供一一个个计计算算规规则则。属属性性计计算
6、算规规则则中中只只能能使使用用相相应应产产生生式式中中的的文文法法符符号号的的属性属性出出现现在在产产生生式式左左边边的的继继承承属属性性和和出出现现在在产产生生式式右右边边的的综综合合属属性性不不由由所所给给的的产产生生式式的的属属性性计计算算规规则则进进行行计计算算，它它们们由由其其它它产产生生式式的的属属性性规规则则计计算算或或者由属性计算器的参数提供者由属性计算器的参数提供6.1属性文法属性文法语语义义规规则则所所描描述述的的工工作作可可以以包包括括属属性性计计算算、静静态态语语义义检检查查、符符号号表表操操作作、代代码码生生成成等等等。等。例例，考考虑虑非非终终结结符符A，B和和C，
7、其其中中，A有有一一个个继继承承属属性性a和和一一个个综综合合属属性性b，B有有综综合合属属性性c，C有有继继承承属属性性d。产产生生式式ABC可能有规则可能有规则C.d:=B.c+1A.b:=A.a+B.c而属性而属性A.a和和B.c在其它地方计算在其它地方计算n属性文法的例子：简单算术表达式求值的语义描述。属性文法的例子：简单算术表达式求值的语义描述。非终结符非终结符E、T及及F都有一个都有一个综合属性综合属性val，符号符号digit有一个综合属性有一个综合属性lexval，它的值由词法分析器提供。，它的值由词法分析器提供。与产生式与产生式LE对应的语义规则仅仅是打印由对应的语义规则仅仅
8、是打印由E产生的算术表产生的算术表达式的值的一个过程，我们可认为这条规则定义了达式的值的一个过程，我们可认为这条规则定义了L的一个的一个虚属性虚属性。某些某些非终结符加下标非终结符加下标是为了区分一个产生式中同一非终结符是为了区分一个产生式中同一非终结符多次出现多次出现语语义义规规则则 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产生式产生式6.1属性文法属性
9、文法综合属性综合属性在语法树中，一个结点的综合属性的值由其子在语法树中，一个结点的综合属性的值由其子结点的属性值确定。结点的属性值确定。使用自底向上的方法在每一个结点处使用语义使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值规则计算综合属性的值仅仅使用综合属性的属性文法称仅仅使用综合属性的属性文法称S属性文属性文法法结点属性值的计算正好和自底向上分析建立分析树结点同步进行。表达式表达式3*5+4n的带注释的语法树的带注释的语法树(语义动作打印数值语义动作打印数值19)digit.lexval=3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15
10、E.val=15+digit.lexval=4F.val=4T.val=4E.val=19nL6.1属性文法属性文法继承属性继承属性在语法树中，一个结点的继承属性由此结点的在语法树中，一个结点的继承属性由此结点的父结点和父结点和/或兄弟结点的某些属性确定或兄弟结点的某些属性确定用继承属性来表示程序设计语言结构中的上下用继承属性来表示程序设计语言结构中的上下文依赖关系很方便文依赖关系很方便6.1属性文法属性文法产产生生式式语语义义规规则则DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,idL1.in:=L.inaddtype(id.t
11、ype,L.in)Lidaddtype(id.type,L.in)句子句子realid1，id2，id3的带注释的语法树的带注释的语法树id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real6.2基于属性文法的处理方法基于属性文法的处理方法语法制导翻译即基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。由由源源程程序序的的语语法法结结构构所所驱驱动动的的处处理理办办法法就就是是语语法制导翻译法法制导翻译法语义规则的计算可能产生代码、在符号表中存
12、放信息、给出错误信息或执行其他动作。对输入符号串的翻译就是根据语义规则进行计算的结果。输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序6.2.1依赖图依赖图在在一一棵棵语语法法树树中中的的结结点点的的继继承承属属性性和和综综合合属属性性之之间间的的相相互互依依赖赖关关系系可可以以由由称称作作依依赖赖图图的的一一个个有有向向图来描述图来描述为为每每一一个个包包含含过过程程调调用用的的语语义义规规则则引引入入一一个个虚虚综综合属性合属性b，这样把每一个语义规则都写成这样把每一个语义规则都写成b:=f(c1,c2,ck)的形式的形式依依赖赖图图中中为为每每一一个个属属性性设设置置
13、一一个个结结点点，如如果果属属性性b依依赖赖于于属属性性c，则则从从属属性性c的的结结点点有有一一条条有有向向边边连到属性连到属性b的结点。的结点。6.2.1依赖图依赖图依赖图的构造算法：for语法树中每一结点语法树中每一结点ndofor结点结点n的文法符号的每一个属性的文法符号的每一个属性ado为为a在依赖图中建立一个结点在依赖图中建立一个结点；for语法树中每一个结点语法树中每一个结点ndofor结点结点n所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则b:=f(c1,c2,ck)dofori:=1tokdo从从ci结点到结点到b结点构造一条有向边结点构造一条有向边；EE1E2
14、E.val:=E1.val+E2.valE1+E2Evalvalval句子句子realid1，id2，id3的带注释的语法树的的带注释的语法树的依赖图依赖图id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entry6.2.1依赖图依赖图如果一属性文法不存在属性之间的循环依如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为赖关系，那么称该文法为良定义的良定义的6.2.1依赖图依赖图属性的计算次序属性的计算次序一个依赖图的任何一个依赖图的任何拓扑排序拓扑排序都给出一个语法树中都给出一个语法树中结点的语义规则计算的有效顺序结点的语义规则计
15、算的有效顺序属性文法说明的翻译是很精确的属性文法说明的翻译是很精确的基础文法用于建立输入符号串的语法分析树基础文法用于建立输入符号串的语法分析树根据计算语义规则建立依赖图根据计算语义规则建立依赖图从依赖图的拓扑排序中，我们可以得到计算语义从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序规则的顺序输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序句子句子realid1，id2，id3的带注释的语法树的带注释的语法树的依赖图的依赖图id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entrya4:=real;a5:=a4ad
16、dtype(id3.entry,a5);a7:=a5;addtype(id2.entry,a7);a9:=a7addtype(id1.entry,a9);6.2.2树遍历的属性计算方法树遍历的属性计算方法通过树遍历的方法计算属性的值通过树遍历的方法计算属性的值假假设设语语法法树树已已经经建建立立起起了了，并并且且树树中中已已带带有有开开始符号的继承属性和终结符的综合属性始符号的继承属性和终结符的综合属性以某种次序遍历语法树，直至计算出所有属性以某种次序遍历语法树，直至计算出所有属性深度优先，从左到右的遍历深度优先，从左到右的遍历无循环的属性文法计算算法：无循环的属性文法计算算法：While 还
17、有未被计算的属性还有未被计算的属性 doVisitNode(S)/*S是开始符号是开始符号*/procedure VisitNode(N:Node);begin if N是一个非终结符是一个非终结符 then /*假设它的产生式为假设它的产生式为NX1Xm*/for i:=1 to m do if not Xi VT then/*即即Xi是非终结符是非终结符*/begin 计算计算Xi的所有能够计算的继承属性；的所有能够计算的继承属性；VisitNode(Xi)end;计算计算N的所有能够计算的综合属性的所有能够计算的综合属性end产产 生生 式式语语 义义 规规 则则SXYZZ.h:=S.a
18、X.c:=Z.gS.b:=X.d-2Y.e:=S.bXxX.d:=2*X.cYyY.f:=Y.e*3ZzZ.g:=Z.h+1例例:考虑属性的文法考虑属性的文法G G。其中，其中，S S有继承属性有继承属性a a，综综合属性合属性b b；X X有继承属性有继承属性c c、综合属性综合属性d d；Y Y有继承有继承属性属性e e、综合属性综合属性f f；Z Z有继承属性有继承属性h h、综合属性综合属性g g 假设假设S.a的初始值为的初始值为0，输入串为，输入串为xyzS:a=0XYZxyzZ:h=0g=1X:c=1d=2S:a=0,b=0Y:e=0f=06.2.3一遍扫描的处理方法一遍扫描的处
19、理方法一遍扫描的处理方法是在语法分析的同时一遍扫描的处理方法是在语法分析的同时计算属性值计算属性值所采用的语法分析方法所采用的语法分析方法属性的计算次序属性的计算次序L属性文法属性文法适合于一遍扫描的自上而下分适合于一遍扫描的自上而下分析析S属性文法属性文法适合于一遍扫描的自下而上分适合于一遍扫描的自下而上分析析6.2.3一遍扫描的处理方法一遍扫描的处理方法所谓所谓语法制导翻译法语法制导翻译法，直观上说就是为文，直观上说就是为文法中每个产生式配上一组语义规则，并且法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则在语法分析的同时执行这些语义规则语义规则就被计算的时机语义规则就
20、被计算的时机在自上而下语法分析中，一个产生式匹配输入在自上而下语法分析中，一个产生式匹配输入串成功时串成功时在自下而上分析中，当一个产生式被用于进行在自下而上分析中，当一个产生式被用于进行归约时归约时6.2.4抽象语法树抽象语法树在语法树中去掉那些对翻译不必要的信息，在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种从而获得更有效的源程序中间表示。这种经变换后的语法树称之为经变换后的语法树称之为抽象语法树抽象语法树(AbstractSyntaxTree)BS1S2if_then_elseq SifBthenS1elseS2q 3*5+4*54+3建立表达式的抽象语法树建
21、立表达式的抽象语法树mknode(op,left,right)建建立立一一个个运运算算符符号号结结点点，标标号号是是op，两两个个域域left和和right分别指向左子树和右子树。分别指向左子树和右子树。mkleaf(id,entry)建建立立一一个个标标识识符符结结点点，标标号号为为id，一一个个域域eutry指指向向标标识识符符在在符符号号表中的入口。表中的入口。mkleaf(num,ral)建建立立一一个个数数结结点点，标标号号为为num，一个域一个域ral用于存放数的值。用于存放数的值。建立抽象语法树的语义规则建立抽象语法树的语义规则产产生生式式语语义义规规则则EE1+TE.nptr:
22、=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,E1.nptr,T.nptr)ETE.nptr:=T.nptrT(E)T.nptr:=E.nptrTidT.nptr:=mkleaf(id,id.entry)TnumT.nptr:=mkleaf(num,num.val)a4c的抽象语法树的抽象语法树EnptrTnptrEnptrToentryforaETnptrid-Tnptridid-idnum4+Toentryforc6.3S-属性文法的自下而上计算属性文法的自下而上计算S-属性文法属性文法：只含有综合属性：只含有综合属性综合属性可以在分析输入符
23、号串的同时由综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属就由栈中正在归约的产生式右边符号的属性值来计算。性值来计算。6.3S-属性文法的自下而上计算属性文法的自下而上计算在分析栈中使用一个附加的域来存放综合在分析栈中使用一个附加的域来存放综合属性值属性值假设语义规则假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于是对应于产生式产生式AXYZ的的 产生式产生式 代代 码
24、码 段段 LEnprint(valtop)EE1+Tvalntop:=valtop-2+valtopETTT1*Fvalntop:=valtop-2*valtopTFF(E)valntop:=valtop-1Fdigit翻译输入翻译输入3*5+4n3*5+4n所做的移动所做的移动输入输入 stateval用到的产生式用到的产生式3*5+4n *5+4n 3 3*5+4n F 3Fdigit*5+4n T 3TF5+4nT*3-+4nT*53-5+4nT*F3-5 Fdigit+4nT 15TT*F翻译输入翻译输入3*5+4n3*5+4n所做的移动所做的移动输入输入stateval用到的产生式用
25、到的产生式+4nE 15ET4nE+15-nE+415-4nE+F15-4 FdigitnE+T15-4 TFnE 19EE+TEn19-L 19LEn6.4L-属性文法和自顶向下翻译属性文法和自顶向下翻译通过深度优先的方法对语法树进行遍历，通过深度优先的方法对语法树进行遍历，计算属性文法的所有属性值计算属性文法的所有属性值LL（1）：）：自上而下分析方法，深度优先建自上而下分析方法，深度优先建立语法树立语法树6.4L-属性文法和自顶向下翻译属性文法和自顶向下翻译一个属性文法称为一个属性文法称为L-属性文法属性文法，如果对于，如果对于每个产生式每个产生式AX1X2Xn，其每个语义规则其每个语义
26、规则中的每个属性或者是综合属性，或者是中的每个属性或者是综合属性，或者是Xj(1 j n)的一个继承属性且这个继承属的一个继承属性且这个继承属性仅依赖于：性仅依赖于：(1)产生式产生式Xj的左边符号的左边符号X1，X2，Xj-1的属的属性；性；(2)A的继承属性。的继承属性。S-属性文法一定是属性文法一定是L-属性文法属性文法6.4L-属性文法和自顶向下翻译属性文法和自顶向下翻译产产生生式式语语义义规规则则ALML.i:=l(A.i)M.i:=m(l.s)AQRR.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)上述文法不是上述文法不是L-属性文法，属性文法，Q的继承属性的继承属
27、性Q.i依赖于它右边的文法符号的属性依赖于它右边的文法符号的属性R.s6.4.1翻译模式翻译模式翻翻译译模模式式：给给出出了了使使用用语语义义规规则则进进行行计计算算的的次次序序，这这样样就就可可把把某某些些实实现现细细节节表表示出来示出来在在翻翻译译模模式式中中，和和文文法法符符号号相相关关的的属属性性和和语语义义规规则则（这这里里我我们们也也称称语语义义动动作作），用用花花括括号号括括起起来来，插插入入到到产产生生式式右右部部的合适位置上的合适位置上n翻译模式示例：翻译模式示例：把带加号和减号的中缀表达把带加号和减号的中缀表达式翻译成相应的后缀表达式式翻译成相应的后缀表达式ETRRaddo
28、pTprint(addop.lexeme)R1|Tnumprint(num.val)-ETR9print(9)TR5print(5)print(-)+T2 print(2)Rprint(+)输入串输入串9-5+2后缀表达式后缀表达式95-2+6.4.1翻译模式翻译模式设计翻译模式时，必须保证当某个动作引设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。用一个属性时它必须是有定义的。L-属性文法本身就能确保每个动作不会引属性文法本身就能确保每个动作不会引用尚未计算出来的属性。用尚未计算出来的属性。6.4.1翻译模式翻译模式建立翻译模式建立翻译模式:当只需要综合属性时：当只需要综合
29、属性时：为每一个语义规则建立为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾的产生式右边的末尾产生式产生式语义规则语义规则TT1*FT.val:=T1.valF.val建立产生式和语义动作：建立产生式和语义动作：TT1*FT.val:=T1.valF.val6.4.1翻译模式翻译模式建立翻译模式建立翻译模式:如果既有综合属性又有继承属性，在建立翻译模式时就如果既有综合属性又有继承属性，在建立翻译模式时就必须保证：必须保证：1.产生式产生式右边的符号的继承属性必须在这个符号以前的动作中右边的符号的继承属性必须在这个符号以前的动
30、作中计算出来计算出来。2.一个动作不能引用这个动作右边的符号的综合属性一个动作不能引用这个动作右边的符号的综合属性。3.产生式左边非终结符的综合属性只有在它所引用的所有属性产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。都计算出来以后才能计算。计算这种属性的动作通常可放在产生计算这种属性的动作通常可放在产生式右端的末尾式右端的末尾。如下列翻译模式不满足条件如下列翻译模式不满足条件1：SA1A2A1.in:=1;A2.in:=2Aaprint(A.in)6.4.1翻译模式翻译模式基于数学格式语言基于数学格式语言EQN给定输入给定输入Esub1.valE1.val识别输
31、入并进行格式安放的识别输入并进行格式安放的L-L-属性文法属性文法产产生生式式语语义义规规则则SBB.ps:=10S.ht:=B.htBB1B2B1.ps:=B.psB2.ps:=B.psB.ht:=max(B1.ht,B2.ht)BB1subB2B1.ps:=B.psB2.ps:=shrink(B.ps)B.ht:=disp(B1.ht,B2.ht)BtextB.ht:=text.hB.ps翻译模式翻译模式S B.ps:=10BS.ht:=B.htB B1.ps:=B.psB1B2.ps:=B.psB2B.ht:=max(B1.ht,B2.ht)B B1.ps:=B.psB1subB2.ps
32、:=shrink(B.ps)B2B.ht:=disp(B1.ht,B2.ht)B textB.ht:=text.hB.ps6.4.2自顶向下翻译自顶向下翻译动作是在处于相同位置上的符号被展开动作是在处于相同位置上的符号被展开（匹配成功）时执行的。（匹配成功）时执行的。为了构造不带回溯的自顶向下语法分析，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归必须消除文法中的左递归当当消除一个翻译模式的基本文法的左递归消除一个翻译模式的基本文法的左递归时同时考虑属性时同时考虑属性适合带综合属性的翻适合带综合属性的翻译模式译模式6.4.2自顶向下翻译自顶向下翻译关于算术表达式的左递归文法相应的翻
33、译关于算术表达式的左递归文法相应的翻译模式模式EE1+TE.val:=E1.val+T.valEE1-TE.val:=E1.val-T.valETE.val:=T.valT(E)T.val:=E.valTnumT.val:=num.val消除左递归，构造新的翻译模式消除左递归，构造新的翻译模式ETR.i:=T.valRE.val:=R.sR+TR1.i:=R.i+T.val R1R.s:=R1.sR-TR1.i:=R.i-T.valR1R.s:=R1.sR R.s:=R.iT(E)T.val:=E.valTnumT.val:=num.val计算表达式计算表达式9 95 52 2 ETRnumn
34、um.val=9T.val=9R.i=9-TRnumnum.val=5T.val=5R.i=4+TRnumnum.val=2T.val=2R.i=6 R.s=6R.s=6R.s=6E.s=6自顶向下分析一般方法自顶向下分析一般方法假设有翻译模式：假设有翻译模式：AA1YA.a:=g(A1.a,Y.y)AXA.a:=f(X.x)它的每个文法符号都有一个综合属性，用小写它的每个文法符号都有一个综合属性，用小写字母表示，字母表示，g和和f是任意函数。是任意函数。q消除左递归：消除左递归：AXRRYR|q翻译模式变为翻译模式变为：AXR.i:=f(X.x)RA.a:=R.sRYR1.i:=g(R.i,
35、Y.y)R1R.s:=R1.sR R.s:=R.iXYYXA A.a=f(X.x)Y1A A.a=g(f(X.x),Y1.y)Y2A A.a=g(g(f(X.x),Y1.y),Y2.y)XYY AXR R.i=f(X.x)Y1R R.i=g(f(X.x),Y1.y)Y2R R.i=g(g(f(X.x),Y1.y),Y2.y)R.s=g(g(f(X.x),Y1.y),Y2.y)R.s=g(g(f(X.x),Y1.y),Y2.y)R.s=g(g(f(X.x),Y1.y),Y2.y)A.a=g(g(f(X.x),Y1.y),Y2.y)构造抽象语法树的构造抽象语法树的属性文法定义转化属性文法定义转化成
36、翻译模式成翻译模式 EE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,E1.nptr,T.nptr)ETE.nptr:=T.nptr构造抽象语法树的构造抽象语法树的属性文法定义转化属性文法定义转化成翻译模式成翻译模式 ETR.i:=T.nptrRE.nptr:=R.sR+TR1.i:=mknode(+,R.i,T.nptr)R1R.s:=R1.sRTR1.i:=mknode(,R.i,T.nptr)R1R.s:=R1.sR R.s:=R.iT(E)T.nptr:=E.nptrTidT.nptr:=mkleaf(id,id.en
37、try)TnumT.nptr:=mkleaf(num,num.val)使用继承属性构造使用继承属性构造a a4 4c c的抽象语法树的抽象语法树ETRidToentryforaidT.nptr-Tnumnum4T.nptrR.i-R+TRidToentryforcidT.nptrR.i+R.i R.sR.sR.sE.nptr6.4.3递归下降翻译器的设计递归下降翻译器的设计如何在递归下降分析中实现翻译模式，构如何在递归下降分析中实现翻译模式，构造造递归下降翻译器递归下降翻译器设计递归下降翻译器的方法设计递归下降翻译器的方法6.4.3递归下降翻译器的设计递归下降翻译器的设计设计递归下降翻译器的方
38、法：设计递归下降翻译器的方法：1.对每个非终结符对每个非终结符A构造一个函数过程构造一个函数过程，对对A的每的每个继承属性设置一个形式参数个继承属性设置一个形式参数，函数的返回值为函数的返回值为A的综合属性的综合属性（作为记录，或指向记录的一个指针，（作为记录，或指向记录的一个指针，记录中有若干域，每个属性对应一个域）。为了记录中有若干域，每个属性对应一个域）。为了简单，我们假设每个非终结只有一个综合属性。简单，我们假设每个非终结只有一个综合属性。A对应的函数过程中，为出现在对应的函数过程中，为出现在A的产生式中的每一的产生式中的每一个文法符号的每一个属性都设置一个局部变量个文法符号的每一个属
39、性都设置一个局部变量。2.非终结符非终结符A对应的函数过程中，根据当前的输入对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。符号决定使用哪个产生式候选。6.4.3递归下降翻译器的设计递归下降翻译器的设计设计递归下降翻译器的方法：设计递归下降翻译器的方法：3.每个产生式对应的程序代码中，按照从左到每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结右的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作：符和语义动作分别作以下工作：qi)对于带有综合属性对于带有综合属性x的终结符的终结符X，把把x的值存入为的值存入为X.x设置的设置的变量中。然后产
40、生一个匹配变量中。然后产生一个匹配X的调用，并继续读入一个输入符的调用，并继续读入一个输入符号。号。qii)对于每个非终结符对于每个非终结符B，产生一个右边带有函数调用的赋值语产生一个右边带有函数调用的赋值语句句c=B(b1,b2,bk)，其中，其中，b1,b2,bk是为是为B的继承属性设置的继承属性设置的变量，的变量，c是为是为B的综合属性设置的变量。的综合属性设置的变量。qiii)对于语义动作，把动作的代码抄进分析器中，用代表属性对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用。的变量来代替对属性的每一次引用。构造抽象语法树的构造抽象语法树的属性文法定义转化
41、属性文法定义转化成翻译模式成翻译模式 ETR.i:=T.nptrRE.nptr:=R.sR+TR1.i:=mknode(+,R.i,T.nptr)R1R.s:=R1.sRTR1.i:=mknode(,R.i,T.nptr)R1R.s:=R1.sR R.s:=R.iT(E)T.nptr:=E.nptrTidT.nptr:=mkleaf(id,id.entry)TnumT.nptr:=mkleaf(num,num.val)递归下降翻译器实现递归下降翻译器实现非终结符非终结符E、R、T的函数及其参数类型的函数及其参数类型functionE:AST-node;functionR(in:AST-node
42、):AST-node;functionT:AST-node;用用oddop代表和代表和RoddopTR1.i:=mknode(addop,lexme,R.i,T.nptr)R1R.s:=R1.sR R.s:=R.i递归下降翻译器实现递归下降翻译器实现产生式产生式RaddopTR|的分析过程的分析过程procedareR;beginifsym=addopthenbeginadvance;T;Rendelsebegin/*donothing*/endend;functionR(in:AST-node):AST-node;varnptr,i1,s1,s:AST-node;addoplexeme:ch
43、ar;beginifsym=addopthenbegin/*产生式产生式RaddopTR*/addoplexeme:=lexval;advance;nptr:=T;i1:=mknode(addoplexeme,in,nptr);s1:=R(i1)s:=s1endelses:=in;returnsend;6.5自下而上计算继承属性自下而上计算继承属性在自下而上的分析过程中实现在自下而上的分析过程中实现L-属性文法属性文法的方法的方法可实现任何基于可实现任何基于LL（1）文法的文法的L-属性文属性文法，还可以实现许多（不是所有）基于法，还可以实现许多（不是所有）基于LR（1）文法的文法的L-属性文
44、法属性文法6.5.1从翻译模式中去掉嵌入在产生式中间的动从翻译模式中去掉嵌入在产生式中间的动作作要求把所有的语义动作都放在产生式的末要求把所有的语义动作都放在产生式的末尾尾转换方法，它可以使所有嵌入的动作都出转换方法，它可以使所有嵌入的动作都出现在产生式的末尾现在产生式的末尾加入新的产生式加入新的产生式M 把嵌入在产生式中的每个语义动作用不同的把嵌入在产生式中的每个语义动作用不同的标记非终结符标记非终结符M代替，并把这个动作放在产代替，并把这个动作放在产生式生式M 的末尾的末尾6.5.1从翻译模式中去掉嵌入在产生式中间的动从翻译模式中去掉嵌入在产生式中间的动作作翻译模式翻译模式ETRRTpri
45、nt()R|Tprint()R|Tnumprint(num.val)转换为转换为ETRRTMR|TNR|Tnumprint(num.val)M print()N print()6.5.2分析栈中的继承属性分析栈中的继承属性属性位置能预测L归约时，T恰在右部下面例:int p,q,r D T L.in:=T.type LT int T.type:=integerT real T.type:=realL L1.in:=L.in L1,id addtype(id.entry,L.in)L id addtype(id.entry,L.in)DTLL,rL,qpint type ininin6.5.2分
46、析栈中的继承属性分析栈中的继承属性DTLL,rL,qpint type ininin产 生 式代 码 段D TL T int valtop:=integer T real valtop:=real L L1,id addtype(valtop,valtop3)L id addtype(valtop,valtop1)6.5.3模拟继承属性的计算模拟继承属性的计算属性的位置不能预测 S aACC.i:=A.s S bABCC.i:=A.s C cC.s:=g(C.i)增加标记非终结符 S aACC.i:=A.s S bABMCM.i:=A.s;C.i:=M.s C cC.s:=g(C.i)M M.
47、s:=M.i6.5.3模拟继承属性的计算模拟继承属性的计算继承属性是某个综合属性的一个函数S aACC.i:=f(A.s)C cC.s:=g(C.i)增加标记非终结符，把f(A.s)的计算移到对标记非终结符归约时进行。S aANCN.i:=A.s;C.i:=N.sN N.s:=f(N.i)C cC.s:=g(C.i)6.5.4用综合属性代替继承属性用综合属性代替继承属性有时，改变基础文法可能避免继承属性。例如，一个Pascal的说明由一标识符序列后跟类型组成，如,m,n:integer。这样的说明的文法可由下面形式的产生式构成DL：T （左边L的类型属性要继承右边T的类型属性）Tinteger
48、|charLL,id|id如果非终结符L从第一个产生式中它的右边T中继承了类型，则我们得到的属性文法就不是L属性的，因此，基于这个属性文法的翻译工作不能在语法分析的同时进行。6.5.4用综合属性代替继承属性用综合属性代替继承属性一个解决的方法是一个解决的方法是重新构造文法重新构造文法使类型作为标识符表的最后一个元素：使类型作为标识符表的最后一个元素：DidLL,idL|:TTinteger|char改成从右向左归约这这样样，类类型型可可以以通通过过综综合合属属性性L.type进进行行传传递递，当当通通过过L产产生生每每个个标标识识符符时时，它它的的类类型就可以填入到符号表中。型就可以填入到符号
49、表中。练习练习例1：有文法：S(L)|aLL,S|S 给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义)，它输出配对括号的个数。如对于句子(a,(a,a)，输出是2。解：加入新开始符号S和产生式SS，设num 为综合属性，代表值属性，则语法制导定义如下：产生式 语义规则 SS print(S.num)S(L)S.num:=L.num+1 Sa S.num:=0 LL1,S L.num:=L1.num+S.num LS L.num:=S.num练习练习例2：构造属性文法，能对下面的文法，只利用综合属性获得类型信息。DL,id|LLTidTint|real解：属性文法（语法制导）定义：产生式 语义规则 D L,id D.type:=L.type addtype(id.entry,L.type)D L D.type:=L.type L T id L.type:=T.type addtype(id.entry,T.type)T int T.type:=integer T real T.type:=real