编译6属性文法及语法制导翻译_zss_

1、编译原理编译原理(第三版第三版) 陈火旺等编著22022-3-27第六章 属性文法和语法制导翻译n属性 属性常用来描述事物或人的特征。如：人的姓名，性别等，商品的颜色、重量、单位等。32022-3-276.1 6.1 属性文法属性文法n属性文法属性文法（也称属性翻译文法）（也称属性翻译文法）Knuth在在1968年提出年提出在上下文无关文法的基础上，为每个文法在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关符号（终结符或非终结符）配备若干相关的的“值值”（称为（称为属性属性）。）。n属性代表与文法符号相关信息，如类型、属性代表与文法符号相关信息，如类型、值、代码序列、符

2、号表内容等值、代码序列、符号表内容等n属性可以进行属性可以进行计算计算和和传递传递n语义规则语义规则：对于文法的每个产生式都配备：对于文法的每个产生式都配备了一组了一组属性的计算规则属性的计算规则42022-3-27n属性属性综合属性综合属性：“自下而上自下而上”传递信息传递信息继承属性继承属性：“自上而下自上而下”传递信息传递信息n在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A 都有一套与之相关联的语义规则，每条规则的都有一套与之相关联的语义规则，每条规则的形式为：形式为：b:=f(c1,c2,ck)这里，这里，f是一个函数，而且或者是一个函数，而且或者1. b是是A

3、的一个的一个综合属性综合属性并且并且c1,c2,ck是产生式是产生式右边文法符号的属性，或者右边文法符号的属性，或者2. b是产生式右边某个文法符号的一个是产生式右边某个文法符号的一个继承属性继承属性并且并且c1,c2,ck 是是A或产生式右边任何文法符或产生式右边任何文法符号的属性。号的属性。属性属性b依赖于属性依赖于属性c1,c2,ck。52022-3-27n说明说明终结符只有终结符只有综合属性综合属性，由词法分析器提供，由词法分析器提供非终结符既可有综合属性也可有继承属性，文法非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始开始符号的所有继承属性作为属

4、性计算前的初始值值 对出现在产生式右边的继承属性和出现在产对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符属性计算规则中只能使用相应产生式中的文法符号的属性号的属性62022-3-27n语义规则所描述的工作可以包括语义规则所描述的工作可以包括: 属性计算、静态语义检查、符号表操属性计算、静态语义检查、符号表操作、代码生成等等。作、代码生成等等。例，考虑非终结符例，考虑非终结符A，B和和C，其中，其中，A有有一个继承属性一个继承属性a和一个综合属性和一个综合属性b，B有有综合属性综

5、合属性c，C有继承属性有继承属性d。 产生式产生式ABC可能可能有规则有规则 C.d:=B.c+1 A.b:=A.a+B.c而属性而属性A.a和和B.c在其它地方计算在其它地方计算 72022-3-27 产产 生生 式式 LEn EE1+T ETTT1*FTFF (E)Fdigit语语 义义 规规 则则print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval表表6.16.182022-3-27n综合属性综合属性在语

6、法树中，一个结点的在语法树中，一个结点的综合属性综合属性的值由其的值由其子结点子结点的属性值确定。的属性值确定。使用自底向上的方法在每一个结点处使用语使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值义规则计算综合属性的值n仅仅使用综合属性的属性文法称仅仅使用综合属性的属性文法称S属性属性文法文法92022-3-27 产产 生生 式式 LEn EE1+T ETTT1*FTFF (E)Fdigit语语 义义 规规 则则print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val

7、F.val :=E.val F.val :=digit.lexval102022-3-273*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 产产 生生 式式 语语 义义 规规 则则 LEn print(E.val) EE1+T E.val := E1.val+T.val ET E.val :=T.val TT1*F T.val :=T1.val* F.val TF T.val :=F.va

8、l F (E) F.val :=E.val Fdigit F.val :=digit.lexval112022-3-27n继承属性继承属性在语法树中，一个结点的在语法树中，一个结点的继承属性继承属性由此结点由此结点的的父结点和父结点和/或兄弟结点或兄弟结点的某些属性确定的某些属性确定用继承属性来表示程序设计语言结构中的上用继承属性来表示程序设计语言结构中的上下文依赖关系很方便下文依赖关系很方便122022-3-27产产 生生 式式 语语 义义 规规 则则 DTLL.in := T.type TintT.type := integer TrealT.type := real LL1, idL1.

9、in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) 132022-3-27句子句子real id1，id2，id3的带注释的语法树的带注释的语法树 id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real产产 生生 式式 语语 义义 规规 则则 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid

10、 addtype(id.entry, L.in) 142022-3-276.2 基于属性文法的的处理方法基于属性文法的的处理方法 n由源程序的语法结构所驱动的处理办法就由源程序的语法结构所驱动的处理办法就是是语法制导翻译法语法制导翻译法n语义规则的计算语义规则的计算产生代码产生代码在符号表中存放信息在符号表中存放信息给出错误信息给出错误信息执行任何其它动作执行任何其它动作n对输入符号串的对输入符号串的翻译翻译也就是根据语义规则也就是根据语义规则进行进行计算计算的结果。的结果。 输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序152022-3-276.2 基于属性文法的的处理

11、方法基于属性文法的的处理方法 n依赖图依赖图n树遍历树遍历n一遍扫描一遍扫描162022-3-276.2.1 依赖图依赖图 n在一棵语法树中的结点的继承属性和综合属性在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作之间的相互依赖关系可以由称作依赖图依赖图的一个的一个有向图来描述有向图来描述n为每一个包含过程调用的语义规则引入一个为每一个包含过程调用的语义规则引入一个虚虚综合属性综合属性b，这样把每一个语义规则都写成，这样把每一个语义规则都写成b:=f(c1,c2,ck)的形式的形式n依赖图中依赖图中为每一个属性设置一个结点为每一个属性设置一个结点，如果属，如果属性性b依赖于

12、属性依赖于属性c，则从属性，则从属性c的结点有一条有的结点有一条有向边连到属性向边连到属性b的结点。的结点。172022-3-27for 语法树中每一结点语法树中每一结点n do for 结点结点n的文法符号的每一个属性的文法符号的每一个属性a do 为为a在依赖图中建立一个结点；在依赖图中建立一个结点；for语法树中每一个结点语法树中每一个结点n do for 结点结点n所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则b:=f(c1,c2,ck ) dofor i:=1 to k do 从从ci结点到结点到b结点构造一条有向边；结点构造一条有向边；182022-3-27 EE1E

13、2 E.val:=E1.val+E2.val E1+E2Evalvalval192022-3-27句子句子real id1，id2，id3的的带注释的语法树的依赖图带注释的语法树的依赖图id1L,id2L,id3LrealTD4type5in6 - addtype(id.entry, L.in)7in8 addtype9in10 addtype1entry2entry3entry产产 生生 式式 语语 义义 规规 则则 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addt

14、ype(id.entry, L.in) Lid addtype(id.entry, L.in) 202022-3-27n如果一属性文法不存在属性之间的循环依如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为赖关系，那么称该文法为良定义的良定义的 只处理只处理良定义的良定义的属属性文法性文法212022-3-27属性的计算次序属性的计算次序 n一个依赖图的任何拓扑排序都给出一个语法树一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序中结点的语义规则计算的有效顺序n属性文法说明的翻译是很精确的属性文法说明的翻译是很精确的基础文法用于建立输入符号串的语法分析树基础文法用于

15、建立输入符号串的语法分析树根据语义规则建立依赖图根据语义规则建立依赖图从依赖图的拓扑排序中，我们可以得到计算语义从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序规则的顺序 输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序222022-3-27句子句子real id1，id2，id3的带注释的语法树的带注释的语法树的依赖图的依赖图id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entrya4:=real;a5:=a4addtype (id3.entry,a5);a7:=a5;addtype (id2.entry,a7)

16、;a9:=a7addtype (id1.entry,a9);232022-3-276.2 基于属性文法的的处理方法基于属性文法的的处理方法 n依赖图依赖图n树遍历树遍历n一遍扫描一遍扫描242022-3-276.2.2 树遍历的属性计算方法树遍历的属性计算方法n通过树遍历的方法计算属性的值通过树遍历的方法计算属性的值 假设语法树已建立，且树中已带有开始符号的假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性继承属性和终结符的综合属性 以某种次序遍历语法树，直至计算出所有属性以某种次序遍历语法树，直至计算出所有属性n深度优先，从左到右的遍历深度优先，从左到右的遍历 252022-

17、3-27While 还有未被计算的属性还有未被计算的属性 doVisitNode(S) /*S是开始符号是开始符号*/procedure VisitNode (N:Node) ;begin if N是一个非终结符是一个非终结符 then /*假设它的产生式为假设它的产生式为NX1Xm*/ for i :=1 to m do if Xi VN then /*即即Xi是非终结符是非终结符*/ begin 计算计算Xi的所有能够计算的的所有能够计算的继承属性继承属性； VisitNode (Xi) end; 计算计算N的所有能够计算的的所有能够计算的综合属性综合属性end262022-3-27产产

18、生生 式式语语 义义 规规 则则 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.bXx X.d :=2*X.cYy Y.f := Y.e*3Zz Z.g :=Z.h+1 例例 考虑属性文法考虑属性文法G。其中，。其中，S有继承属性有继承属性a，综合，综合属性属性b；X有继承属性有继承属性c、综合属性、综合属性d；Y有继承属有继承属性性e、综合属性、综合属性f；Z有继承属性有继承属性h、综合属性、综合属性g 272022-3-27假设假设S.a的初始值为的初始值为0，输入串为，输入串为xyzS:a=0XYZxyzZ:h=0 g=1X:c=1

19、d=2S:a=0, b=0Y:e=0 f=0产产 生生 式式语语 义义 规规 则则 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.bXx X.d :=2*X.cYy Y.f := Y.e*3Zz Z.g :=Z.h+1 282022-3-276.2 基于属性文法的的处理方法基于属性文法的的处理方法 n依赖图依赖图n树遍历树遍历n一遍扫描一遍扫描292022-3-276.2.3 一遍扫描的处理方法一遍扫描的处理方法 n一遍扫描的处理方法是一遍扫描的处理方法是在语法分析的同在语法分析的同时计算属性值时计算属性值 所采用的语法分析方法所采用的语法

20、分析方法属性的计算次序属性的计算次序nL属性文法属性文法适合于一遍扫描的自上而下适合于一遍扫描的自上而下分析分析nS属性文法属性文法适合于一遍扫描的自下而上适合于一遍扫描的自下而上分析分析 302022-3-27n所谓所谓语法制导翻译法语法制导翻译法，直观上说就是为，直观上说就是为文法中每个产生式配上一组语义规则，文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规并且在语法分析的同时执行这些语义规则则 n语义规则被计算的时机语义规则被计算的时机在自上而下语法分析中，一个产生式匹配输在自上而下语法分析中，一个产生式匹配输入串成功时入串成功时在自下而上分析中，当一个产生式被用于进

21、在自下而上分析中，当一个产生式被用于进行归约时行归约时312022-3-276.2.4 抽象语法树抽象语法树 n在语法树中去掉那些对翻译不必要的信息，在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种从而获得更有效的源程序中间表示。这种经变换后的语法树称之为经变换后的语法树称之为抽象语法树抽象语法树(Abstract Syntax Tree)BS1S2if_then_elseq Sif B then S1 else S2q 3*5+4*54+3322022-3-27建立表达式的抽象语法树建立表达式的抽象语法树 nmknode (op,left,right) 建立一个建立

22、一个运算符运算符号结点号结点，标号是，标号是op，两个域，两个域left和和right分分别指向左子树和右子树。别指向左子树和右子树。nmkleaf (id,entry) 建立一个建立一个标识符结点标识符结点，标号为标号为id，一个域，一个域eutry指向标识符在符指向标识符在符号表中的入口。号表中的入口。nmkleaf (num,val) 建立一个建立一个数结点数结点，标，标号为号为num，一个域，一个域val用于存放数的值。用于存放数的值。332022-3-27建立抽象语法树的语义规则建立抽象语法树的语义规则产产 生生 式式 语语 义义 规规 则则 EE1+TE.nptr := mknod

23、e( +, E1.nptr, T.nptr ) EE1-TE.nptr := mknode( -, E1.nptr, T.nptr ) ETE.nptr := T.nptr T (E) T.nptr := E.nptr TidT.nptr := mkleaf ( id, id.entry ) Tnum T.nptr := mkleaf ( num, num.val ) 342022-3-27 a4c的抽象语法树的抽象语法树E nptrT nptrE nptrTo entry for aET nptrid-T nptridid-idnum4+To entry for c352022-3-27一遍

24、扫描的处理方法一遍扫描的处理方法 n一遍扫描的处理方法是在语法分析的同一遍扫描的处理方法是在语法分析的同时计算属性值时计算属性值 所采用的语法分析方法所采用的语法分析方法属性的计算次序属性的计算次序nL属性文法适合于一遍扫描的自上而下属性文法适合于一遍扫描的自上而下分析分析nS属性文法属性文法适合于一遍扫描的自下而上适合于一遍扫描的自下而上分析分析 362022-3-276.3 S-属性文法的自下而上计算属性文法的自下而上计算 nS-属性文法属性文法：只含有综合属性：只含有综合属性n综合属性可以在分析输入符号串的同时由综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。自下而上的分析器

25、来计算。n分析器可以保存与栈中文法符号有关的综分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属就由栈中正在归约的产生式右边符号的属性值来计算。性值来计算。 372022-3-27 (以下有关以下有关LR分析方法略分析方法略)n在分析栈中使用一个附加的域来存放综合在分析栈中使用一个附加的域来存放综合属性值属性值 n假设语义规则假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应是对应于产生式于产生式AXYZ的的 Sm Z.z Z Sm-1 Y.y Y Sm-2 X.x X S0 # TOP Sm-

26、2 A.a A S0 # TOP 382022-3-27产生式产生式 代代 码码 段段 LEnprint(valtop) EE1+Tvalntop := valtop-2+valtop ETTT1*Fvalntop := valtop-2*valtop TFF (E)valntop :=valtop-1Fdigit 产产 生生 式式 语语 义义 规规 则则 LEn print(E.val) EE1+T E.val := E1.val+T.val ET E.val :=T.val TT1*F T.val :=T1.val* F.val TF T.val :=F.val F (E) F.val :

27、=E.val Fdigit F.val :=digit.lexval392022-3-27 输入输入 state val 用到的产生式用到的产生式 3*5+4n # - *5+4n #3 -3 *5+4n #F -3 Fdigit *5+4n #T -3 TF 5+4n #T* -3 - +4n #T*5 -3 - 5产生式产生式 代代 码码 段段 LEnprint(valtop) EE1+Tvalntop := valtop-2+valtop ETTT1*Fvalntop := valtop-2*valtop TFF (E)valntop :=valtop-1Fdigit 402022-3-

28、27 输入输入 state val 用到的产生式用到的产生式 +4n #T*5 -3 - 5 +4n #T*F -3 - 5 Fdigit +4n #T -15 TT*F +4n #E -15 ET 4n #E+ -15- n #E+4 -15- 4产生式产生式 代代 码码 段段 LEnprint(valtop) EE1+Tvalntop := valtop-2+valtop ETTT1*Fvalntop := valtop-2*valtop TFF (E)valntop :=valtop-1Fdigit 412022-3-27 输入输入 stateval 用到的产生式用到的产生式 n #E+

29、4-15- 4 n #E+F-15- 4Fdigit n #E+T-15- 4TF n #E-19EE+T #En-19- #L-19 LEn产生式产生式 代代 码码 段段 LEnprint(valtop) EE1+Tvalntop := valtop-2+valtop ETTT1*Fvalntop := valtop-2*valtop TFF (E)valntop :=valtop-1Fdigit 422022-3-27一遍扫描的处理方法一遍扫描的处理方法 n一遍扫描的处理方法是在语法分析的同一遍扫描的处理方法是在语法分析的同时计算属性值时计算属性值 所采用的语法分析方法所采用的语法分析方法

30、属性的计算次序属性的计算次序nL属性文法属性文法适合于一遍扫描的自上而下适合于一遍扫描的自上而下分析分析nS属性文法适合于一遍扫描的自下而上属性文法适合于一遍扫描的自下而上分析分析 432022-3-276.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译 n通过深度优先的方法对语法树进行遍历，通过深度优先的方法对语法树进行遍历，计算属性文法的所有属性值计算属性文法的所有属性值nLL(1)：自上而下分析方法，深度优先建立：自上而下分析方法，深度优先建立语法树语法树442022-3-27n一个属性文法称为一个属性文法称为L-属性文法属性文法，如果对于，如果对于每个产生式每个产生式AX1X2X

31、n，其每个语义规则，其每个语义规则中的每个属性中的每个属性或者或者是综合属性，是综合属性，或者或者是是Xj(1 j n)的一个继承属性且这个继承属性的一个继承属性且这个继承属性仅依赖于：仅依赖于：(1) 产生式产生式Xj的左边符号的左边符号X1，X2，Xj-1的属性；的属性；(2) A的继承属性。的继承属性。nS-属性文法一定是属性文法一定是L-属性文法属性文法452022-3-27非非L-属性文法属性文法产产 生生 式式 语语 义义 规规 则则 ALM L.i := l(A.i) M.i :=m(L.s) AQR R.i := r(A.i) Q.i :=q(R.s) A.s :=f(Q.s)

32、 462022-3-276.4.1 翻译模式翻译模式 n翻译模式翻译模式：给出了使用语义规则进行计：给出了使用语义规则进行计算的次序，这样就可把某些实现细节表算的次序，这样就可把某些实现细节表示出来示出来n在翻译模式中，和文法符号相关的属性在翻译模式中，和文法符号相关的属性和语义规则（和语义规则（语义动作语义动作），用花括号），用花括号 括起来，插入到产生式右部的合适位置括起来，插入到产生式右部的合适位置上上472022-3-27q翻译模式示例：把带加号和减号的中缀翻译模式示例：把带加号和减号的中缀表达式翻译成相应的后缀表达式表达式翻译成相应的后缀表达式 ETR Raddop T print(

33、addop.lexeme) R1 | Tnum print(num.val) 例：例：9-5+2-ETR9print(9)TR5print(5)print(-)+T2print(2)Rprint(+) 把语义动作连起来：把语义动作连起来：9 5 2 +482022-3-27设计翻译模式的原则设计翻译模式的原则n设计翻译模式时，必须保证当某个动作引用设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。一个属性时它必须是有定义的。nL-属性文法本身就能确保每个动作不会引用属性文法本身就能确保每个动作不会引用尚未计算出来的属性。尚未计算出来的属性。 492022-3-27建立翻译模式建

34、立翻译模式n当只需要当只需要综合属性综合属性时：为每一个语义规则时：为每一个语义规则建立一个包含赋值的动作，并建立一个包含赋值的动作，并把这个动作把这个动作放在相应的放在相应的产生式右边末尾产生式右边末尾 产生式产生式 语义规则语义规则 TT1*FT.val:=T1.valF.val建立产生式和语义动作：建立产生式和语义动作： TT1*F T.val:=T1.valF.val502022-3-27建立翻译模式建立翻译模式n如果既有如果既有综合属性综合属性又有又有继承属性继承属性，在建立，在建立翻译模式时就必须保证：翻译模式时就必须保证：1. 产生式右边的符号的产生式右边的符号的继承属性继承属性

35、必须在这个必须在这个符号以前的动作中计算出来。符号以前的动作中计算出来。2. 一个动作不能引用这个动作右边的符号的一个动作不能引用这个动作右边的符号的综合属性综合属性。3. 产生式左边非终结符的产生式左边非终结符的综合属性综合属性只有在它只有在它所引用的所有属性都计算出来以后才能计所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生算。计算这种属性的动作通常可放在产生式右端的式右端的末尾末尾。512022-3-27建立翻译模式建立翻译模式SA1A2A1.in:=1; A2.in:=2 Aa print(A.in)（参见（参见P151）深度优先时，无法打印A.in522022

36、-3-27基于数学格式语言基于数学格式语言EQN n给定输入给定输入 E sub n .valEn.valEn.val532022-3-27识别输入并进行格式安放的识别输入并进行格式安放的L-属性文法属性文法 产生式产生式 语义规则语义规则 SB B.ps :=10 S.ht :=B.htBB1B2 B1.ps :=B.ps B2.ps :=B.ps B.ht := max(B1.ht, B2.ht)BB1 sub B2B1.ps :=B.ps B2.ps :=shrink(B.ps) B.ht :=disp(B1.ht, B2.ht)Btext B.ht :=text.hB.psEn.val

37、E sub n .val542022-3-27翻译模式翻译模式S B.ps:=10 B S.ht:=B.ht B B1.ps:=B.ps B1 B2.ps:=B.ps B2 B.ht:=max(B1.ht,B2.ht) B B1.ps:=B.ps B1 sub B2.ps:=shrink(B.ps) B2 B.ht:=disp(B1.ht,B2.ht) B textB.ht:=text.hB.ps1. 产生式右边的符号的产生式右边的符号的继承属性继承属性必须在这个符必须在这个符号以前的动作中计算出来。号以前的动作中计算出来。2. 一个动作不能引用这个动作右边的符号的一个动作不能引用这个动作右边

38、的符号的综综合属性合属性。3. 产生式左边非终结符的产生式左边非终结符的综合属性综合属性只有在它所只有在它所引用的所有属性都计算出来以后才能计算。计引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常放在产生式右端的算这种属性的动作通常放在产生式右端的末尾末尾。552022-3-276.4.2 自顶向下翻译自顶向下翻译 n动作是在处于相同位置上的符号被展开动作是在处于相同位置上的符号被展开（匹配成功）时执行的。（匹配成功）时执行的。 n为了构造不带回溯的自顶向下语法分析，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归必须消除文法中的左递归n当消除一个翻译模式的基本文法的左递

39、归当消除一个翻译模式的基本文法的左递归时同时考虑时同时考虑属性属性适合带适合带综合属性综合属性的翻的翻译模式译模式 562022-3-27n关于算术表达式的左递归文法相应的翻译关于算术表达式的左递归文法相应的翻译模式模式EE1+TE.val:=E1.val+T.valEE1-T E.val:=E1.val-T.valET E.val:=T.valT(E)T.val:=E.valTnumT.val:=num.valE T RR + T R1R - T R1R T ( E )T num572022-3-27n消除左递归，构造新的翻译模式消除左递归，构造新的翻译模式 E TR.i:=T.val RE

40、.val:=R.sR + TR1.i:=R.i+T.val R1R.s:=R1.sR - TR1.i:=R.i-T.val R1R.s:=R1.sR R.s:=R.iT ( E )T.val:=E.valT numT.val:=num.valE T RR +TR1R -TR1R T ( E )T numR.i: R前面子表达式前面子表达式 的值的值R.s: 分析完分析完R时子表时子表 达式的值达式的值582022-3-27计算表达式计算表达式952 ETRnumnum.val=9T.val=9R.i=9-TRnumnum.val=5T.val=5R.i=4+TRnumnum.val=2T.va

41、l=2R.i=6 R.s=6R.s=6R.s=6E.val=6E T R.i:=T.val R E.val:=R.s R + T R1.i:=R.i+T.val R1 R.s:= R1.s R - T R1.i:=R.i-T.val R1 R.s:= R1.s R R.s:=R.i T ( E ) T.val:=E.val T num T.val:=num.val 592022-3-27一般方法一般方法n假设有翻译模式：假设有翻译模式： AA1YA.a:=g(A1.a,Y.y) AXA.a:=f(X.x)它的每个文法符号都有一个综合属性，用小写它的每个文法符号都有一个综合属性，用小写字母表示，

42、字母表示，g和和f是任意函数。是任意函数。q消除左递归：消除左递归： AXR RYR | q翻译模式变为翻译模式变为 ：A XR.i:=f (X.x) RA.a:=R.sR Y R1.i:=g(R.i,Y.y) R1R.s:=R1.sR R.s:=R.iR.i: R前面子表达式前面子表达式 的值的值R.s: 分析完分析完R时子表时子表 达式的值达式的值602022-3-27XYY XA 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)自下而上计算属性

43、值自下而上计算属性值612022-3-27XYY 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)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自上而下计算属性值自上而下计算属性值n本章结

44、束622022-3-27632022-3-27构造抽象语法树的属性文法定义转化成构造抽象语法树的属性文法定义转化成翻译模式翻译模式 EE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,E1.nptr,T.nptr)ETE.nptr:=T.nptr642022-3-27构造抽象语法树的属性文法定义转化成构造抽象语法树的属性文法定义转化成翻译模式翻译模式 E TR.i:=T.nptr RE.nptr:=R.sR + TR1.i:=mknode(+,R.i,T.nptr) R1R.s:=R1.sR - TR1.i:=mknode(,R

45、.i,T.nptr) R1R.s:=R.sR R.s:=R.iT ( E ) T.nptr:=E.nptrT idT.nptr:=mkleaf(id,id.entry)T num T.nptr:=mkleaf(num,num.val)652022-3-27使用继承属性构造使用继承属性构造a4c的抽象语法树的抽象语法树ETRidTo entry for aidT.nptr-Tnumnum4T.nptrR. i-R+TRidTo entry for cidT.nptrR. i+R. i R. sR. sR. sE.nptrE T R.i:=T.nptr R E.nptr:=R.sR + T R1.

46、i:=mknode(+,R.i,T.nptr) R1 R.s:=R1.sR - T R1.i:=mknode(,R.i,T.nptr) R1 R.s:=R.sR R.s:=R.iT ( E ) T.nptr:=E.nptrT id T.nptr:=mkleaf(id,id.entry)T num T.nptr:=mkleaf(num,num.val)662022-3-276.4.3 递归下降翻译器的设计递归下降翻译器的设计 n如何在递归下降分析中实现翻译模式，构如何在递归下降分析中实现翻译模式，构造造递归下降翻译器递归下降翻译器 672022-3-27设计递归下降翻译器的方法设计递归下降翻译器

47、的方法n 1. 对每个非终结符对每个非终结符A构造一个函数过程，对构造一个函数过程，对A的的每个每个继承属性继承属性设置一个设置一个形式参数形式参数函数的函数的返回值返回值为为A的的综合属性综合属性（作为记录，或（作为记录，或指向记录的一个指针，记录中有若干域，每个指向记录的一个指针，记录中有若干域，每个属性对应一个域）。为了简单，我们假设每个属性对应一个域）。为了简单，我们假设每个非终结只有一个综合属性非终结只有一个综合属性A对应的函数过程中，为出现在对应的函数过程中，为出现在A的产生式中的产生式中的每一个文法符号的每一个的每一个文法符号的每一个属性属性都设置一个都设置一个局局部变量部变量。

48、682022-3-27设计递归下降翻译器的方法设计递归下降翻译器的方法n2. 非终结符非终结符A对应的函数过程中，根据当前的对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。输入符号决定使用哪个产生式候选。692022-3-27设计递归下降翻译器的方法设计递归下降翻译器的方法n3. 每个产生式对应的程序代码中，按照从左到右每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结符和的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作：语义动作分别作以下工作：i) 对于带有综合属性对于带有综合属性x的终结符的终结符X，把，把x的值存入的值存入为为X.x设置的变量中。然后产生一个匹配设置的变量中。然后产生一个匹配X的调的调用，并继续读入一个输入符号。用，并继续读入一个输入符号。ii) 对于每个非终结符对于每个非终结符B，产生一个右边带有函数，产生一个右边带有函数调用的赋值语句调用的赋值语句c=B(b1,b2,bk)，其中，其中，b1,b2,bk是为是为B的的继承属性继承属性设置的变量，设置的变量，c是为是为B的的综合属性综合属性设置的变量。设置的变量。iii) 对于语义动作，把动作的代码抄进分析