《编译6属性文法和语法制导翻译(zss).ppt》由会员分享，可在线阅读，更多相关《编译6属性文法和语法制导翻译(zss).ppt（76页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理编译原理(第三版第三版)陈火旺等编著（2012201220122012年年年年9 9 9 9月月月月-12-12-12-12月）月）月）月）主讲：朱世松主讲：朱世松计算机学院计算机学院22023/2/22第六章 属性文法和语法制导翻译n属性 属性常用来描述事物或人的特征。如：人的姓名，性别等，商品的颜色、重量、单位等。32023/2/226.1 6.1 属性文法属性文法n属性文法属性文法（也称属性翻译文法）（也称属性翻译文法）Knuth在在1968年提出年提出在在上上下下文文无无关关文文法法的的基基础础上上，为为每每个个文文法法符符号号（终终结结符符或或非非终终结结符符）配配备备若若干
2、干相相关关的的“值值”（称为（称为属性属性）。）。n属属性性代代表表与与文文法法符符号号相相关关信信息息，如如类类型型、值、代码序列、符号表内容等值、代码序列、符号表内容等n属性可以进行属性可以进行计算计算和和传递传递n语语义义规规则则：对对于于文文法法的的每每个个产产生生式式都都配配备备了一组了一组属性的计算规则属性的计算规则42023/2/22n属性属性综合属性综合属性：“自下而上自下而上”传递信息传递信息继承属性继承属性：“自上而下自上而下”传递信息传递信息n在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A 都有一套与之相关联的语义规则，每条规则的都有一套与之相关联
3、的语义规则，每条规则的形式为：形式为：b:=f(c1,c2,ck)这里，这里，f是一个函数，而且或者是一个函数，而且或者1.b是是A的的一一个个综综合合属属性性并并且且c1,c2,ck是是产产生生式式右边文法符号的属性，或者右边文法符号的属性，或者2.b是是产产生生式式右右边边某某个个文文法法符符号号的的一一个个继继承承属属性性并并且且c1,c2,ck是是A或或产产生生式式右右边边任任何何文文法法符符号的属性。号的属性。属性属性b依赖于属性依赖于属性c1,c2,ck。52023/2/22n说明说明终结符只有终结符只有综合属性综合属性，由词法分析器提供，由词法分析器提供非非终终结结符符既既可可有
4、有综综合合属属性性也也可可有有继继承承属属性性，文文法法开开始始符符号号的的所所有有继继承承属属性性作作为为属属性性计计算算前前的的初初始始值值对对出出现现在在产产生生式式右右边边的的继继承承属属性性和和出出现现在在产产生生式式左左边边的的综综合合属属性性都都必必须须提提供供一一个个计计算算规规则则。属属性性计计算算规规则则中中只只能能使使用用相相应应产产生生式式中中的的文文法法符符号的属性号的属性62023/2/22n语义规则所描述的工作可以包括语义规则所描述的工作可以包括:属属性性计计算算、静静态态语语义义检检查查、符符号号表表操操作、代码生成等等。作、代码生成等等。例例，考考虑虑非非终终
5、结结符符A，B和和C，其其中中，A有有一一个个继继承承属属性性a和和一一个个综综合合属属性性b，B有有综综合合属属性性c，C有有继继承承属属性性d。产产生生式式ABC可能有规则可能有规则C.d:=B.c+1A.b:=A.a+B.c而属性而属性A.a和和B.c在其它地方计算在其它地方计算72023/2/22产产生生式式LEnEE1+TETTT1*FTFF(E)Fdigit语语义义规规则则print(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表
6、表6.16.182023/2/22n综合属性综合属性在语法树中，一个结点的在语法树中，一个结点的综合属性综合属性的值由其的值由其子结点子结点的属性值确定。的属性值确定。使用自底向上的方法在每一个结点处使用语使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值义规则计算综合属性的值n仅仅使用综合属性的属性文法称仅仅使用综合属性的属性文法称S属性属性文法文法92023/2/22产产生生式式LEnEE1+TETTT1*FTFF(E)Fdigit语语义义规规则则print(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val
7、:=F.valF.val:=E.valF.val:=digit.lexval102023/2/223*5+4n的带注释的语法树的带注释的语法树digit.lexval=3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19nL 产产生生式式语语义义规规则则LEnprint(E.val)EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.val*F.valTF T.val:=F.valF(E)F.val:=E.valF
8、digitF.val:=digit.lexval112023/2/22n继承属性继承属性在语法树中，一个结点的在语法树中，一个结点的继承属性继承属性由此结点由此结点的的父结点和父结点和/或兄弟结点或兄弟结点的某些属性确定的某些属性确定用继承属性来表示程序设计语言结构中的上用继承属性来表示程序设计语言结构中的上下文依赖关系很方便下文依赖关系很方便122023/2/22产产生生式式语语义义规规则则DTLL.in:=T.type TintT.type:=integer TrealT.type:=real LL1,idL1.in:=L.inaddtype(id.entry,L.in)Lidaddtyp
9、e(id.entry,L.in)132023/2/22句子句子realid1，id2，id3的带注释的语法树的带注释的语法树id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real产产生生式式语语义义规规则则DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,idL1.in:=L.inaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in)142023/2/226.2基于属性文法的的处理方法基于属性文法的的处理方法n由由源源程程序序的的语语
10、法法结结构构所所驱驱动动的的处处理理办办法法就就是是语法制导翻译法语法制导翻译法n语义规则的计算语义规则的计算产生代码产生代码在符号表中存放信息在符号表中存放信息给出错误信息给出错误信息执行任何其它动作执行任何其它动作n对对输输入入符符号号串串的的翻翻译译也也就就是是根根据据语语义义规规则则进行进行计算计算的结果。的结果。输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序152023/2/226.2基于属性文法的的处理方法基于属性文法的的处理方法n依赖图依赖图n树遍历树遍历n一遍扫描一遍扫描162023/2/226.2.1依赖图依赖图n在在一一棵棵语语法法树树中中的的结结点点
11、的的继继承承属属性性和和综综合合属属性性之之间间的的相相互互依依赖赖关关系系可可以以由由称称作作依依赖赖图图的的一一个个有向图来描述有向图来描述n为为每每一一个个包包含含过过程程调调用用的的语语义义规规则则引引入入一一个个虚虚综合属性综合属性b，这样把每一个语义规则都写成，这样把每一个语义规则都写成b:=f(c1,c2,ck)的形式的形式n依依赖赖图图中中为为每每一一个个属属性性设设置置一一个个结结点点，如如果果属属性性b依依赖赖于于属属性性c，则则从从属属性性c的的结结点点有有一一条条有有向边连到属性向边连到属性b的结点。的结点。172023/2/22for语法树中每一结点语法树中每一结点n
12、dofor结点结点n的文法符号的每一个属性的文法符号的每一个属性ado为为a在依赖图中建立一个结点；在依赖图中建立一个结点；for语法树中每一个结点语法树中每一个结点ndofor结点结点n所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则b:=f(c1,c2,ck)dofori:=1tokdo从从ci结点到结点到b结点构造一条有向边；结点构造一条有向边；182023/2/22EE1E2E.val:=E1.val+E2.valE1+E2Evalvalval192023/2/22句子句子realid1，id2，id3的的带注释的语法树的依赖图带注释的语法树的依赖图id1L,id2L,id
13、3LrealTD4type5in6-addtype(id.entry,L.in)7in8 addtype9in10 addtype1entry2entry3entry产产生生式式语语义义规规则则DTLL.in:=T.typeTint T.type:=integerTrealT.type:=realLL1,idL1.in:=L.inaddtype(id.entry,L.in)Lid addtype(id.entry,L.in)202023/2/22n如果一属性文法不存在属性之间的循环依如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为赖关系，那么称该文法为良定义的良定义的只处理只处理良定
14、义的良定义的属属性文法性文法212023/2/22属性的计算次序属性的计算次序n一个依赖图的任何拓扑排序都给出一个语法树一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序中结点的语义规则计算的有效顺序n属性文法说明的翻译是很精确的属性文法说明的翻译是很精确的基础文法用于建立输入符号串的语法分析树基础文法用于建立输入符号串的语法分析树根据语义规则建立依赖图根据语义规则建立依赖图从依赖图的拓扑排序中，我们可以得到计算语义规从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序则的顺序输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序222023/2/22句子句子
15、realid1，id2，id3的带注释的语法树的带注释的语法树的依赖图的依赖图id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entrya4:=real;a5:=a4addtype(id3.entry,a5);a7:=a5;addtype(id2.entry,a7);a9:=a7addtype(id1.entry,a9);232023/2/226.2基于属性文法的的处理方法基于属性文法的的处理方法n依赖图依赖图n树遍历树遍历n一遍扫描一遍扫描242023/2/226.2.2树遍历的属性计算方法树遍历的属性计算方法n通过树遍历的方法计算属性的
16、值通过树遍历的方法计算属性的值假假设设语语法法树树已已建建立立，且且树树中中已已带带有有开开始始符符号号的的继承属性和终结符的综合属性继承属性和终结符的综合属性以某种次序遍历语法树，直至计算出所有属性以某种次序遍历语法树，直至计算出所有属性n深度优先，从左到右的遍历深度优先，从左到右的遍历252023/2/22While 还有未被计算的属性还有未被计算的属性 doVisitNode(S)/*S是开始符号是开始符号*/procedure VisitNode(N:Node);begin if N是一个非终结符是一个非终结符 then /*假设它的产生式为假设它的产生式为NX1Xm*/for i:=
17、1 to m do if Xi VN then/*即即Xi是非终结符是非终结符*/begin 计算计算Xi的所有能够计算的的所有能够计算的继承属性继承属性；VisitNode(Xi)end;计算计算N的所有能够计算的的所有能够计算的综合属性综合属性end262023/2/22产产 生生 式式语语 义义 规规 则则SXYZZ.h:=S.aX.c:=Z.gS.b:=X.d-2Y.e:=S.bXxX.d:=2*X.cYyY.f:=Y.e*3ZzZ.g:=Z.h+1例例考虑属性文法考虑属性文法G。其中，。其中，S有继承属性有继承属性a，综合，综合属性属性b；X有继承属性有继承属性c、综合属性、综合属性
18、d；Y有继承属有继承属性性e、综合属性、综合属性f；Z有继承属性有继承属性h、综合属性、综合属性g272023/2/22假设假设S.a的初始值为的初始值为0，输入串为，输入串为xyzS:a=0XYZxyzZ:h=0 g=1X:c=1 d=2S:a=0,b=0Y:e=0 f=0产产生生式式语语义义规规则则SXYZZ.h:=S.aX.c:=Z.gS.b:=X.d-2Y.e:=S.bXxX.d:=2*X.cYyY.f:=Y.e*3ZzZ.g:=Z.h+1282023/2/226.2基于属性文法的的处理方法基于属性文法的的处理方法n依赖图依赖图n树遍历树遍历n一遍扫描一遍扫描292023/2/226.
19、2.3一遍扫描的处理方法一遍扫描的处理方法n一遍扫描的处理方法是一遍扫描的处理方法是在语法分析的同在语法分析的同时计算属性值时计算属性值所采用的语法分析方法所采用的语法分析方法属性的计算次序属性的计算次序nL属性文法属性文法适合于一遍扫描的自上而下适合于一遍扫描的自上而下分析分析nS属性文法属性文法适合于一遍扫描的自下而上适合于一遍扫描的自下而上分析分析302023/2/22n所谓所谓语法制导翻译法语法制导翻译法，直观上说就是为文，直观上说就是为文法中每个产生式配上一组语义规则，并且法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则在语法分析的同时执行这些语义规则n语义规则被
20、计算的时机语义规则被计算的时机在自上而下语法分析中，一个产生式匹配输在自上而下语法分析中，一个产生式匹配输入串成功时入串成功时在自下而上分析中，当一个产生式被用于进在自下而上分析中，当一个产生式被用于进行归约时行归约时312023/2/226.2.4抽象语法树抽象语法树n在语法树中去掉那些对翻译不必要的信息，在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种从而获得更有效的源程序中间表示。这种经变换后的语法树称之为经变换后的语法树称之为抽象语法树抽象语法树(AbstractSyntaxTree)BS1S2if_then_elseq Sif B then S1 else
21、S2q 3*5+4*54+3关键字、操作符不作叶关键字、操作符不作叶节点节点322023/2/22建立表达式的抽象语法树建立表达式的抽象语法树nmknode(op,left,right)建建立立一一个个运运算算符符号号结结点点，标标号号是是op，两两个个域域left和和right分分别指向左子树和右子树。别指向左子树和右子树。nmkleaf(id,entry)建建立立一一个个标标识识符符结结点点，标标号号为为id，一一个个域域eutry指指向向标标识识符符在在符符号表中的入口。号表中的入口。nmkleaf(num,val)建建立立一一个个数数结结点点，标标号号为为num，一个域，一个域val用
22、于存放数的值。用于存放数的值。332023/2/22建立抽象语法树的语义规则建立抽象语法树的语义规则产产生生式式语语义义规规则则EE1+TE.nptr:=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)342023/2/22a4c的抽象语法树的抽象语法树E nptrT nptrE nptrTo entry for aET nptrid
23、-T nptridid-idnum4+To entry for c352023/2/22一遍扫描的处理方法一遍扫描的处理方法n一遍扫描的处理方法是在语法分析的同一遍扫描的处理方法是在语法分析的同时计算属性值时计算属性值所采用的语法分析方法所采用的语法分析方法属性的计算次序属性的计算次序nL属性文法适合于一遍扫描的自上而下属性文法适合于一遍扫描的自上而下分析分析nS属性文法属性文法适合于一遍扫描的自下而上适合于一遍扫描的自下而上分析分析362023/2/226.3S-属性文法的自下而上计算属性文法的自下而上计算nS-属性文法属性文法：只含有综合属性：只含有综合属性n综合属性可以在分析输入符号串的
24、同时由综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。自下而上的分析器来计算。n分析器可以保存与栈中文法符号有关的综分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属就由栈中正在归约的产生式右边符号的属性值来计算。性值来计算。372023/2/22n在分析栈中使用一个附加的域来存放综合在分析栈中使用一个附加的域来存放综合属性值属性值n假设语义规则假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应是对应于产生式于产生式AXYZ的的382023/2/22产生式产生式 代代 码码 段段 L
25、Enprint(valtop)EE1+Tvalntop:=valtop-2+valtopETTT1*Fvalntop:=valtop-2*valtopTFF(E)valntop:=valtop-1Fdigit 产产生生式式语语义义规规则则LEnprint(E.val)EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.val*F.valTF T.val:=F.valF(E)F.val:=E.valFdigitF.val:=digit.lexval392023/2/22输入输入 stateval 用到的产生式用到的产生式3*5+4n#-*5+
26、4n#3-3*5+4n#F-3Fdigit*5+4n#T-3TF5+4n#T*-3-+4n#T*5-3-5产生式产生式 代代 码码 段段LEnprint(valtop)EE1+Tvalntop:=valtop-2+valtopETTT1*Fvalntop:=valtop-2*valtopTFF(E)valntop:=valtop-1Fdigit402023/2/22输入输入 stateval 用到的产生式用到的产生式+4n#T*5-3-5+4n#T*F-3-5 Fdigit+4n#T-15 TT*F+4n#E-15 ET4n#E+-15-n#E+4-15-4产生式产生式 代代 码码 段段LEn
27、print(valtop)EE1+Tvalntop:=valtop-2+valtopETTT1*Fvalntop:=valtop-2*valtopTFF(E)valntop:=valtop-1Fdigit412023/2/22输入输入 stateval用到的产生式用到的产生式n#E+4-15-4n#E+F-15-4Fdigitn#E+T-15-4TFn#E-19EE+T#En-19-#L-19LEn产生式产生式 代代 码码 段段LEnprint(valtop)EE1+Tvalntop:=valtop-2+valtopETTT1*Fvalntop:=valtop-2*valtopTFF(E)va
28、lntop:=valtop-1Fdigit422023/2/22一遍扫描的处理方法一遍扫描的处理方法n一遍扫描的处理方法是在语法分析的同一遍扫描的处理方法是在语法分析的同时计算属性值时计算属性值所采用的语法分析方法所采用的语法分析方法属性的计算次序属性的计算次序nL属性文法属性文法适合于一遍扫描的自上而下适合于一遍扫描的自上而下分析分析nS属性文法适合于一遍扫描的自下而上属性文法适合于一遍扫描的自下而上分析分析432023/2/226.4L-属性文法和自顶向下翻译属性文法和自顶向下翻译n通过深度优先的方法对语法树进行遍历，通过深度优先的方法对语法树进行遍历，计算属性文法的所有属性值计算属性文法
29、的所有属性值nLL(1)：自上而下分析方法，深度优先建立：自上而下分析方法，深度优先建立语法树语法树442023/2/22n一个属性文法称为一个属性文法称为L-属性文法属性文法，如果对于每，如果对于每个产生式个产生式AX1X2Xn，其每个语义规则中，其每个语义规则中的每个属性的每个属性或者或者是综合属性，是综合属性，或者或者是是Xj(1 j n)的一个继承属性且这个继承属性的一个继承属性且这个继承属性仅依赖于：仅依赖于：(1)产生式产生式Xj的左边符号的左边符号X1，X2，Xj-1的属性；的属性；(2)A的继承属性。的继承属性。nS-属性文法一定是属性文法一定是L-属性文法属性文法452023
30、/2/22非非L-属性文法属性文法产产生生式式语语义义规规则则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)462023/2/226.4.1翻译模式翻译模式n翻翻译译模模式式：给给出出了了使使用用语语义义规规则则进进行行计计算算的的次次序序，这这样样就就可可把把某某些些实实现现细细节节表表示出来示出来n在在翻翻译译模模式式中中，和和文文法法符符号号相相关关的的属属性性和和语语义义规规则则（语语义义动动作作），用用花花括括号号括括起起来来，插插入入到到产产生生式式右右部部的的合合适适位位置置上上472023/2/22q翻
31、译模式示例：把带加号和减号的中缀翻译模式示例：把带加号和减号的中缀表达式翻译成相应的后缀表达式表达式翻译成相应的后缀表达式ETRRaddopTprint(addop.lexeme)R1|Tnumprint(num.val)例：例：9-5+2-ETR9print(9)TR5print(5)print(-)+T2print(2)Rprint(+)把语义动作连起来：把语义动作连起来：952+482023/2/22设计翻译模式的原则设计翻译模式的原则n设计翻译模式时，必须保证当某个动作引用设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。一个属性时它必须是有定义的。nL-属性文法本身就
32、能确保每个动作不会引用属性文法本身就能确保每个动作不会引用尚未计算出来的属性。尚未计算出来的属性。492023/2/22建立翻译模式建立翻译模式n当只需要当只需要综合属性综合属性时：为每一个语义规则时：为每一个语义规则建立一个包含赋值的动作，并建立一个包含赋值的动作，并把这个动作把这个动作放在相应的放在相应的产生式右边末尾产生式右边末尾产生式产生式语义规则语义规则TT1*FT.val:=T1.valF.val建立产生式和语义动作：建立产生式和语义动作：TT1*FT.val:=T1.valF.val502023/2/22建立翻译模式建立翻译模式n如果既有如果既有综合属性综合属性又有又有继承属性继
33、承属性，在建立，在建立翻译模式时就必须保证：翻译模式时就必须保证：1.产生式右边的符号的产生式右边的符号的继承属性继承属性必须在这个必须在这个符号以前的动作中计算出来。符号以前的动作中计算出来。2.一个动作不能引用这个动作右边的符号的一个动作不能引用这个动作右边的符号的综合属性综合属性。3.产生式左边非终结符的产生式左边非终结符的综合属性综合属性只有在它只有在它所引用的所有属性都计算出来以后才能计所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生算。计算这种属性的动作通常可放在产生式右端的式右端的末尾末尾。512023/2/22建立翻译模式建立翻译模式SA1A2A1.in
34、:=1;A2.in:=2Aaprint(A.in)（参见（参见P151）深度优先时，无法打印A.in522023/2/22基于数学格式语言基于数学格式语言EQNn给定输入给定输入Esubn.valEn.valEn.val532023/2/22识别输入并进行格式安放的识别输入并进行格式安放的L-属性文法属性文法 产生式产生式 语义规则语义规则SB B.ps:=10 S.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.
35、ht)BtextB.ht:=text.hB.psEn.valEsubn.val542023/2/22翻译模式翻译模式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:=shrink(B.ps)B2B.ht:=disp(B1.ht,B2.ht)B textB.ht:=text.hB.ps1.产生式右边的符号的产生式右边的符号的继承属性继承属性必须在这个符必须在这个符号以前的动作中计算出来。号以前的动作中计算出来。2.一个动作不能引用这个动作右边的符号的一个动
36、作不能引用这个动作右边的符号的综综合属性合属性。3.产生式左边非终结符的产生式左边非终结符的综合属性综合属性只有在它所只有在它所引用的所有属性都计算出来以后才能计算。计引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常放在产生式右端的算这种属性的动作通常放在产生式右端的末尾末尾。552023/2/226.4.2自顶向下翻译自顶向下翻译n动作是在处于相同位置上的符号被展开动作是在处于相同位置上的符号被展开（匹配成功）时执行的。（匹配成功）时执行的。n为了构造不带回溯的自顶向下语法分析，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归必须消除文法中的左递归n当消除一个翻译模式的
37、基本文法的左递归当消除一个翻译模式的基本文法的左递归时同时考虑时同时考虑属性属性适合带适合带综合属性综合属性的翻的翻译模式译模式562023/2/22n关于算术表达式的左递归文法相应的翻译关于算术表达式的左递归文法相应的翻译模式模式EE1+TE.val:=E1.val+T.valEE1-TE.val:=E1.val-T.valETE.val:=T.valT(E)T.val:=E.valTnumT.val:=num.valETRR+TR1R-TR1R T(E)Tnum572023/2/22n消除左递归，构造新的翻译模式消除左递归，构造新的翻译模式ETR.i:=T.valRE.val:=R.sR+
38、TR1.i:=R.i+T.val R1R.s:=R1.sR-TR1.i:=R1R.s:=R1.sR R.s:=R.iT(E)T.val:=E.valTnumT.val:=num.valETRR+TR1R-TR1R T(E)TnumR.i:R前面子表达式前面子表达式的值的值R.s:分析完分析完R时子表时子表达式的值达式的值582023/2/22计算表达式计算表达式952ETRnumnum.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.val=6ET R.i:=T.v
39、alR E.val:=R.sR+T R1.i:=R.i+T.valR1R.s:=R1.sR-TR1.i:=R1R.s:=R1.sR R.s:=R.iT(E)T.val:=E.valTnumT.val:=num.val592023/2/22一般方法一般方法n假设有翻译模式：假设有翻译模式：AA1YA.a:=g(A1.a,Y.y)AXA.a:=f(X.x)它的每个文法符号都有一个综合属性，用小写它的每个文法符号都有一个综合属性，用小写字母表示，字母表示，g和和f是任意函数。是任意函数。q消除左递归：消除左递归：AXR RYR|q翻译模式变为翻译模式变为：A XR.i:=f(X.x)RA.a:=R.
40、sR Y R1.i:=g(R.i,Y.y)R1R.s:=R1.sR R.s:=R.iR.i:R前面子表达式前面子表达式的值的值R.s:分析完分析完R时子表时子表达式的值达式的值602023/2/22XYYXA 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)AA1YA.a:=g(A1.a,Y.y)AXA.a:=f(X.x)自下而上计算属性值自下而上计算属性值612023/2/22XYY 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
41、.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)A X R.i:=f(X.x)R A.a:=R.sR Y R1.i:=g(R.i,Y.y)R1 R.s:=R1.sR R.s:=R.i自上而下计算属性值自上而下计算属性值622023/2/22构造抽象语法树的属性文法定义转化成构造抽象语法树的属性文法定义转化成翻译模式翻译模式EE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,
42、E1.nptr,T.nptr)ETE.nptr:=T.nptr632023/2/22构造抽象语法树的属性文法定义转化成构造抽象语法树的属性文法定义转化成翻译模式翻译模式ETR.i:=T.nptrRE.nptr:=R.sR+TR1.i:=mknode(+,R.i,T.nptr)R1R.s:=R1.sR-TR1.i:=mknode(,R.i,T.nptr)R1R.s:=R.sR R.s:=R.iT(E)T.nptr:=E.nptrTidT.nptr:=mkleaf(id,id.entry)Tnum T.nptr:=mkleaf(num,num.val)642023/2/22使用继承属性构造使用继承
43、属性构造a4c的抽象语法树的抽象语法树ETRidTo entry for aidT.nptr-Tnumnum4T.nptrR.i-R+TRidTo entry for cidT.nptrR.i+R.i R.sR.sR.sE.nptrETR.i:=T.nptrRE.nptr:=R.sR+TR1.i:=mknode(+,R.i,T.nptr)R1R.s:=R1.sR-TR1.i:=mknode(,R.i,T.nptr)R1R.s:=R.sR R.s:=R.iT(E)T.nptr:=E.nptrTidT.nptr:=mkleaf(id,id.entry)TnumT.nptr:=mkleaf(num,
44、num.val)652023/2/226.4.3递归下降翻译器的设计递归下降翻译器的设计n如何在递归下降分析中实现翻译模式，构如何在递归下降分析中实现翻译模式，构造造递归下降翻译器递归下降翻译器662023/2/22设计递归下降翻译器的方法设计递归下降翻译器的方法n1.对每个非终结符对每个非终结符A构造一个函数过程，对构造一个函数过程，对A的每的每个个继承属性继承属性设置一个设置一个形式参数形式参数函数的函数的返回值返回值为为A的的综合属性综合属性（作为记录，或（作为记录，或指向记录的一个指针，记录中有若干域，每个指向记录的一个指针，记录中有若干域，每个属性对应一个域）。为了简单，我们假设每个
45、属性对应一个域）。为了简单，我们假设每个非终结只有一个综合属性非终结只有一个综合属性A对应的函数过程中，为出现在对应的函数过程中，为出现在A的产生式中的的产生式中的每一个文法符号的每一个每一个文法符号的每一个属性属性都设置一个都设置一个局部局部变量变量。672023/2/22设计递归下降翻译器的方法设计递归下降翻译器的方法n2.非终结符非终结符A对应的函数过程中，根据当前的对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。输入符号决定使用哪个产生式候选。682023/2/22设计递归下降翻译器的方法设计递归下降翻译器的方法n3.每个产生式对应的程序代码中，按照从左到右每个产生式对应的
46、程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结符和的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作：语义动作分别作以下工作：i)对于带有综合属性对于带有综合属性x的终结符的终结符X，把，把x的值存入的值存入为为X.x设置的变量中。然后产生一个匹配设置的变量中。然后产生一个匹配X的调的调用，并继续读入一个输入符号。用，并继续读入一个输入符号。ii)对于每个非终结符对于每个非终结符B，产生一个右边带有函数，产生一个右边带有函数调用的赋值语句调用的赋值语句c=B(b1,b2,bk)，其中，其中，b1,b2,bk是为是为B的的继承属性继承属性设置的变量，设置的变量，c是
47、为是为B的的综合属性综合属性设置的变量。设置的变量。iii)对于语义动作，把动作的代码抄进分析器中，对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用。用代表属性的变量来代替对属性的每一次引用。692023/2/22构造抽象语法树的属性文法定义转化成构造抽象语法树的属性文法定义转化成翻译模式翻译模式ETR.i:=T.nptrRE.nptr:=R.sR+TR1.i:=mknode(+,R.i,T.nptr)R1R.s:=R1.sR-TR1.i:=mknode(,R.i,T.nptr)R1R.s:=R.sR R.s:=R.iT(E)T.nptr:=E.nptrTidT
48、.nptr:=mkleaf(id,id.entry)Tnum T.nptr:=mkleaf(num,num.val)702023/2/22n非终结符非终结符E、R、T的函数及其参数类型的函数及其参数类型function E:AST-node;function R(in:AST-node):AST-node;function T:AST-node;n用用oddop代表和代表和RoddopTR1.i:=mknode(addop.lexme,R.i,T.nptr)R1R.s:=R1.sR R.s:=R.i712023/2/22产生式产生式RaddopTR|的分析过程的分析过程procedareR;b
49、eginifsym=addopthenbeginadvance;T;Rendelsebegin/*donothing*/endend;722023/2/22functionR(in:AST-node):AST-node;varnptr,i1,s1,s:AST-node;addoplexeme:char;beginifsym=addopthenbegin/*产生式产生式RaddopTR*/addoplexeme:=lexval;advance;nptr:=T;i1:=mknode(addoplexeme,in,nptr);s1:=R(i1)s:=s1endelses:=in;returnsend
50、;RoddopT R1.i:=mknode(addop.lexme,R.i,T.nptr)R1R.s:=R1.sR R.s:=R.i732023/2/226.5自下而上计算继承属性自下而上计算继承属性n在自下而上的分析过程中实现在自下而上的分析过程中实现L-属性文法的属性文法的方法方法n可实现任何基于可实现任何基于LL(1)文法的文法的L-属性文法，属性文法，还可以实现许多（不是所有）基于还可以实现许多（不是所有）基于LR(1)文文法的法的L-属性文法属性文法742023/2/226.5.1从翻译模式中去掉嵌入在产生式从翻译模式中去掉嵌入在产生式中间的动作中间的动作n要求把所有的语义动作都放在