编译原理-刘善梅-第6章 属性文法和语法制导翻译5ppt课件

1、编译原理第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译n属性文法属性文法n基于属性文法的处理方法基于属性文法的处理方法nS-属性文法的自下而上计算属性文法的自下而上计算nL-属性文法和自顶向下的翻译属性文法和自顶向下的翻译6.1 6.1 属性文法属性文法n属性文法也称属性翻译文法）属性文法也称属性翻译文法）nKnuth在在1968年提出年提出 经典巨著：经典巨著：The Art of Computer Programming计算机程序设计的艺术计算机程序设计的艺术计划出七计划出七卷卷第一卷第一卷于于1968年出版，年出版，第

2、二卷第二卷于于1969年出版，年出版，第三卷第三卷于于1973年出版，年出版，第四卷第四卷A已于已于2019年出版。年出版。TEX6.1 6.1 属性文法属性文法n属性文法也称属性翻译文法）属性文法也称属性翻译文法）nKnuth在在1968年提出年提出n在上下文无关文法的基础上，为每个文在上下文无关文法的基础上，为每个文法符号终结符或非终结符配备若干法符号终结符或非终结符配备若干相关的相关的“值值”（称为属性）。（称为属性）。n属性代表与文法符号相关信息，如类型、属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等值、代码序列、符号表内容等n属性可以进行计算和传递属性可以进行计算和传

3、递n语义规则：对于文法的每个产生式都配语义规则：对于文法的每个产生式都配备了一组属性的计算规则备了一组属性的计算规则 产产 生生 式式 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.lexvaln属性属性n综合属性：综合属性：“自下而上传递信息自下而上传递信息n继承属性：继承属性：“自上而下传递信息自上而下传递信息n在一个属性文法中

4、，对应于每个产生式在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条规则的都有一套与之相关联的语义规则，每条规则的形式为：形式为：nb:=f(c1,c2,ck)n这里，这里，f是一个函数，而且或者是一个函数，而且或者n1. b是是A的一个综合属性并且的一个综合属性并且c1,c2,ck是产是产生式右边文法符号的属性，或者生式右边文法符号的属性，或者n2. b是产生式右边某个文法符号的一个继承属是产生式右边某个文法符号的一个继承属性并且性并且c1,c2,ck 是是A或产生式右边任何文法或产生式右边任何文法符号的属性。符号的属性。n属性属性b依赖于属性依赖于属性c1,c2,ck。

5、 产产 生生 式式 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.lexvaln阐明阐明n终结符只有综合属性，由词法分析器提终结符只有综合属性，由词法分析器提供供n F digit n digit .lexvaln非终结符既可有综合属性也可有继承属非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性为属性，文法开始符号的

6、所有继承属性为属性计算前的初始值。性计算前的初始值。n F digit n F.val， digit .lexval属性文法属性文法n阐明阐明n对出现在产生式右边的继承属性和出现对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性相应产生式中的文法符号的属性n F digit n F.val= digit .lexvaln出现在产生式左边的继承属性和出现在出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生产生式右边的综合属性不由所给

7、的产生式的属性计算规则进行计算，它们由其式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计它产生式的属性规则计算或者由属性计算器的参数提供算器的参数提供n语义规则所描述的工作可以包括属性计语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码算、静态语义检查、符号表操作、代码生成等等。生成等等。n例，考虑非终结符例，考虑非终结符A，B和和C，其中，其中，A有一个继承属性有一个继承属性a和一个综合属性和一个综合属性b，B有综合属性有综合属性c，C有继承属性有继承属性d。产生式。产生式ABC可能有规则可能有规则n C.d:=B.c+1n A.b:=A.a+B.cn而

8、属性而属性A.a和和B.c在其它地方计算在其它地方计算 产产 生生 式式 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属性文法举例属性文法举例n综合属性综合属性n在语法树中，一个结点的综合属性的值由在语法树中，一个结点的综合属性的值由其子结点和它本身的属性值确定。其子结点和它本身的属性值确定。n使用自底向上的方法在每一

9、个结点处使用使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值语义规则计算综合属性的值n仅仅使用综合属性的属性文法称仅仅使用综合属性的属性文法称S属性属性文法文法 产产 生生 式式 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.lexvalS属性文法属性文法3*5+4n的带注释的语法树的带注释的语法树 digit.lexv

10、al=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.val F (E) F.val :=E.val Fdigit F.val :=digit.lexvaln继承属性继承属性n在语法树中，一个结点的继承属性由此在语法树中，一个

11、结点的继承属性由此结点的父结点和结点的父结点和/或兄弟结点和其本身的或兄弟结点和其本身的某些属性确定某些属性确定n用继承属性来表示程序设计语言结构中用继承属性来表示程序设计语言结构中的上下文依赖关系很方便的上下文依赖关系很方便产产 生生 式式 语语 义义 规规 那么那么 DTLL.in := T.type TintT.type := integer TrealT.type := real LL1, idL1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) 句子句子real id1，id2，id3的带注释的语法的带注释的

12、语法树树 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 addtype(id.entry, L.in) 第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译n属性文法属性文法n基于属性文法的处理方法基于属性文法的处理方法nS-属性文法的自下而上计算属性文

13、法的自下而上计算nL-属性文法和自顶向下的翻译属性文法和自顶向下的翻译6.2 基于属性文法的处理方法基于属性文法的处理方法 n这种由源程序的语法结构所驱动的处理办法就这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法是语法制导翻译法n语义规则的计算语义规则的计算n产生代码产生代码n在符号表中存放信息在符号表中存放信息n给出错误信息给出错误信息n执行任何其它动作执行任何其它动作n对输入符号串的翻译也就是根据语义规则进行对输入符号串的翻译也就是根据语义规则进行计算的结果。计算的结果。 输入串输入串语法树语法树按照语义规则计算属性按照语义规则计算属性基于属性文法的处理过程通常为：基于属性文法的

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

15、属性性b依赖于属性依赖于属性c，则从属性，则从属性c的结点有一条有向的结点有一条有向边连到属性边连到属性b的结点。的结点。对于一棵给定的语法树，依赖图按以下步骤构造：对于一棵给定的语法树，依赖图按以下步骤构造：for 语法树中每一结点语法树中每一结点n do for 结点结点n的文法符号的每一个属性的文法符号的每一个属性a do 为为a在依赖图中建立一个结点；在依赖图中建立一个结点；for语法树中每一个结点语法树中每一个结点n do for 结点结点n所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则b:=f(c1,c2,ck ) dofor i:=1 to k do 从从ci结点到

16、结点到b结点构造一条有向边；结点构造一条有向边； EE1E2 E.val:=E1.val+E2.val E1+E2Evalvalval句子句子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,

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

18、的语法分析树n根据语义规则建立依赖图根据语义规则建立依赖图n从依赖图的拓扑排序中，我们可以得到计算语义从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序规则的顺序 。用这个顺序计算语义规则就得到输。用这个顺序计算语义规则就得到输入串的翻译入串的翻译输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序n拓扑序：一个有向非循环图的拓扑排序是图中结拓扑序：一个有向非循环图的拓扑排序是图中结点的任何顺序点的任何顺序m1，m2， ，mk，使得边必，使得边必须是从序列中前面的结点指向后面的结点。须是从序列中前面的结点指向后面的结点。句子句子real id1，id2，id3的带注释的语法树

19、的带注释的语法树的依赖图的依赖图id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entrya4:=real;a5:=a4addtype (id3.entry,a5);a7:=a5;addtype (id2.entry,a7);a9:=a7addtype (id1.entry,a9);6.2 基于属性文法的的处理方法基于属性文法的的处理方法 n依赖图依赖图n树遍历树遍历n一遍扫描一遍扫描6.2.2 树遍历的属性计算方法树遍历的属性计算方法n通过树遍历的方法计算属性的值通过树遍历的方法计算属性的值 n假设语法树已建立，且树中已带有开始符假设语法

20、树已建立，且树中已带有开始符号的继承属性和终结符的综合属性号的继承属性和终结符的综合属性 n以某种次序遍历语法树，直至计算出所有以某种次序遍历语法树，直至计算出所有属性属性n深度优先，从左到右的遍历深度优先，从左到右的遍历 产产 生生 式式语语 义义 规规 那么那么 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、综合属性、综合属

21、性d；Y有继承属有继承属性性e、综合属性、综合属性f；Z有继承属性有继承属性h、综合属性、综合属性g 假设假设S.a的初始值为的初始值为0，输入串为，输入串为xyzS:a=0XYZxyzZ:h=0 g=1X:c=1 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 6.2 基于属性文法的的处理方法基于属性文法的的处理方法 n依赖图依赖图n树遍历树遍历n一遍扫描一遍扫描6

22、.2.3 一遍扫描的处理方法一遍扫描的处理方法 n一遍扫描的处理方法是在语法分析的同时计算一遍扫描的处理方法是在语法分析的同时计算属性值属性值 n一遍扫描的处理方法与语法分析器相互作用，一遍扫描的处理方法与语法分析器相互作用，它与以下两个因素密切相关：它与以下两个因素密切相关：n所采用的语法分析方法所采用的语法分析方法n属性的计算次序属性的计算次序nL属性文法适合于一遍扫描的自上而下分析属性文法适合于一遍扫描的自上而下分析nS属性文法适合于一遍扫描的自下而上分析属性文法适合于一遍扫描的自下而上分析 按照一遍扫描的编译程序模型理解语法制导按照一遍扫描的编译程序模型理解语法制导翻译法翻译法n语法制

23、导翻译法：为文法中每个产生式语法制导翻译法：为文法中每个产生式配上一组语义规则，并且在语法分析的配上一组语义规则，并且在语法分析的同时执行这些语义规则同时执行这些语义规则 n语义规则被计算的时机语义规则被计算的时机n在自上而下语法分析中，一个产生式匹在自上而下语法分析中，一个产生式匹配输入串成功时配输入串成功时n在自下而上分析中，当一个产生式被用在自下而上分析中，当一个产生式被用于进行归约时于进行归约时一遍扫描的处理方法一遍扫描的处理方法 n一遍扫描的处理方法是在语法分析的同一遍扫描的处理方法是在语法分析的同时计算属性值时计算属性值 n所采用的语法分析方法所采用的语法分析方法n属性的计算次序属

24、性的计算次序nL属性文法适合于一遍扫描的自上而下属性文法适合于一遍扫描的自上而下分析分析nS属性文法适合于一遍扫描的自下而上属性文法适合于一遍扫描的自下而上分析分析 6.3 S-属性文法的自下而上计算属性文法的自下而上计算 nS-属性文法：只含有综合属性属性文法：只含有综合属性n综合属性可以在分析输入符号串的同时由综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。自下而上的分析器来计算。n分析器可以保存与栈中文法符号有关的综分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属就由栈中正在归约的

25、产生式右边符号的属性值来计算。性值来计算。 n在分析栈中使用一个附加的域来存放综合在分析栈中使用一个附加的域来存放综合属性值属性值 n假设语义规则假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应是对应于产生式于产生式AXYZ的的 6.3 S-属性文法的自下而上计算属性文法的自下而上计算 产生式产生式 代代 码码 段段 LEnLEnprint(valtop) print(valtop) EE1+TEE1+Tvalntop := valtop-valntop := valtop-2+valtop 2+valtop ETETTT1TT1* *F Fvalntop := valtop-valn

26、top := valtop-22* *valtop valtop TFTFF (E)F (E)valntop :=valtop-1valntop :=valtop-1Fdigit Fdigit 产 生 式 语 义 规 那么 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 :=E.val Fdigit F.val :=digit.lexval产生式产生式 代代 码码 段段 (0)LEn(0)LEnprint(

27、valtop) print(valtop) (1)EE1+T(1)EE1+Tvalntop := valtop-valntop := valtop-2+valtop 2+valtop (2)ET(2)ET(3)TT1(3)TT1* *F Fvalntop := valtop-valntop := valtop-22* *valtop valtop (4)TF(4)TF(5)F (E)(5)F (E)valntop :=valtop-1valntop :=valtop-1(6)Fdigit (6)Fdigit 输入输入 statesym val 用到的产生式用到的产生式 3*5+4n 0 # -

28、 *5+4n 05#3 -3 *5+4n 03 #F -3 Fdigit *5+4n 02 #T -3 TF 5+4n 027#T* -3 - +4n 0275 #T*5 -3 - 5产生式产生式 代代 码码 段段 (0)LEn(0)LEnprint(valtop) print(valtop) (1)EE1+T(1)EE1+Tvalntop := valtop-valntop := valtop-2+valtop 2+valtop (2)ET(2)ET(3)TT1(3)TT1* *F Fvalntop := valtop-valntop := valtop-22* *valtop valtop

29、 (4)TF(4)TF(5)F (E)(5)F (E)valntop :=valtop-1valntop :=valtop-1(6)Fdigit (6)Fdigit 输入输入 statesym val 用到的产生式用到的产生式 +4n 0275 #T*5 -3 - 5 +4n 02710#T*F -3 - 5 Fdigit +4n 02 #T -15 TT*F +4n 01 #E -15 ET 4n 016 #E+ -15- n 0165 #E+4 -15- 4产生式产生式 代代 码码 段段 (0)LEn(0)LEnprint(valtop) print(valtop) (1)EE1+T(1)

30、EE1+Tvalntop := valtop-valntop := valtop-2+valtop 2+valtop (2)ET(2)ET(3)TT1(3)TT1* *F Fvalntop := valtop-valntop := valtop-22* *valtop valtop (4)TF(4)TF(5)F (E)(5)F (E)valntop :=valtop-1valntop :=valtop-1(6)Fdigit (6)Fdigit 输入输入 statesym val 用到的产生式用到的产生式 n 0165 #E+4 -15- 4 n 0163 #E+F -15- 4Fdigit n

31、 0169 #E+T -15- 4TF n 01#E -19EE+T #En -19- #L -19 LEn产生式产生式 代代 码码 段段 (0)LEn(0)LEnprint(valtop) print(valtop) (1)EE1+T(1)EE1+Tvalntop := valtop-valntop := valtop-2+valtop 2+valtop (2)ET(2)ET(3)TT1(3)TT1* *F Fvalntop := valtop-valntop := valtop-22* *valtop valtop (4)TF(4)TF(5)F (E)(5)F (E)valntop :=v

32、altop-1valntop :=valtop-1(6)Fdigit (6)Fdigit 第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译n属性文法属性文法n基于属性文法的处理方法基于属性文法的处理方法nS-属性文法的自下而上计算属性文法的自下而上计算nL-属性文法和自顶向下的翻译属性文法和自顶向下的翻译一遍扫描的处理方法一遍扫描的处理方法 n一遍扫描的处理方法是在语法分析的同一遍扫描的处理方法是在语法分析的同时计算属性值时计算属性值 n所采用的语法分析方法所采用的语法分析方法n属性的计算次序属性的计算次序nS属性文法适合于一遍扫描的自下而上属性文法适合于一遍扫描的自下而上分析分析

33、n L属性文法适合于一遍扫描的自上而属性文法适合于一遍扫描的自上而下分析下分析6.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译 n通过深度优先的方法对语法树进行遍历，通过深度优先的方法对语法树进行遍历，从而计算属性文法的所有属性值。从而计算属性文法的所有属性值。nL-属性文法允许一次遍历就计算出所有属属性文法允许一次遍历就计算出所有属性值性值nLL(1)：自上而下分析方法，深度优先建立：自上而下分析方法，深度优先建立语法树语法树n我们可以在自上而下语法分析的同时实现我们可以在自上而下语法分析的同时实现L属性文法的计算属性文法的计算n一个属性文法称为一个属性文法称为L-属性文法，如果对于

34、属性文法，如果对于每个产生式每个产生式AX1X2Xn，其每个语义规，其每个语义规则中的每个属性或者是综合属性，或者是则中的每个属性或者是综合属性，或者是Xj(1jn)的一个继承属性且这个继承属性的一个继承属性且这个继承属性仅依赖于：仅依赖于：n(1) 产生式产生式Xj的左边符号的左边符号X1，X2，Xj-1的属性；的属性；n(2) A的继承属性。的继承属性。nS-属性文法一定是属性文法一定是L-属性文法属性文法 L-属性文法属性文法非非L-属性文法例子属性文法例子产产 生生 式式 语语 义义 规规 那么那么 ALM L.i := l(A.i) M.i :=m(L.s) AQR R.i := r

35、(A.i) Q.i :=q(R.s) A.s :=f(Q.s) 6.4.1 翻译模式翻译模式 n语义规则：给出了属性计算的定义，没有属性计语义规则：给出了属性计算的定义，没有属性计算的次序等实现细节算的次序等实现细节n翻译模式：给出了使用语义规则进行计算的次序，翻译模式：给出了使用语义规则进行计算的次序，这样就可把某些实现细节表示出来这样就可把某些实现细节表示出来n在翻译模式中，和文法符号相关的属性和语义规在翻译模式中，和文法符号相关的属性和语义规则这里我们也称语义动作），用花括号则这里我们也称语义动作），用花括号 括起括起来，插入到产生式右部的合适位置上来，插入到产生式右部的合适位置上产生式

36、产生式 语义规则语义规则 ETR Raddop T R1 | print(addop.lexeme) Tnum print(num.val) ETR Raddop T print(addop.lexeme) R1 | Tnum print(num.val)q翻译模式示例：它把带加号和减号的中翻译模式示例：它把带加号和减号的中缀表达式翻译成相应的后缀表达式缀表达式翻译成相应的后缀表达式 ETR Raddop T print(addop.lexeme) R1 | Tnum print(num.val) 例：例：9-5+2-ETR9print(9)TR5print(5)print(-)+T2prin

37、t(2)Rprint(+) 设计翻译模式的原则设计翻译模式的原则n设计翻译模式时，必须保证当某个动作引设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。用一个属性时它必须是有定义的。nL-属性文法本身就能确保每个动作不会引属性文法本身就能确保每个动作不会引用尚未计算出来的属性。用尚未计算出来的属性。 n如何将属性文法改造成翻译模式？如何将属性文法改造成翻译模式？n将属性文法改造成翻译模式实际上是把语将属性文法改造成翻译模式实际上是把语义规则用括起来，放在正确的位置义规则用括起来，放在正确的位置建立翻译模式建立翻译模式n当只需要综合属性时：为每一个语义规则当只需要综合属性时：为每

38、一个语义规则建立一个包含赋值的动作，并把这个动作建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾放在相应的产生式右边的末尾n 产生式产生式 语义规则语义规则n TT1*FT.val:=T1.valF.valn建立产生式和语义动作：建立产生式和语义动作：n TT1*F T.val:=T1.valF.val建立翻译模式建立翻译模式n如果既有综合属性又有继承属性，在建立翻译模如果既有综合属性又有继承属性，在建立翻译模式时就必须保证：式时就必须保证：n1. 产生式右边的符号的继承属性必须在这个符号产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。以前的动作中计算出来。n2.

39、一个动作不能引用这个动作右边的符号的综合一个动作不能引用这个动作右边的符号的综合属性。属性。n3. 产生式左边非终结符的综合属性只有在它所引产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。种属性的动作通常可放在产生式右端的末尾。n SA1A2A1.in:=1; A2.in:=2n Aa print(A.in)建立翻译模式建立翻译模式nSA1A2A1.in:=1; A2.in:=2n Aa print(A.in)n不满足第不满足第1条：产生式右边的符号的继承属性必条：产生式右边的符

40、号的继承属性必须在这个符号以前的动作中计算出来须在这个符号以前的动作中计算出来n修改如下：修改如下：n S A1.in:=1; A1 A2.in:=2 A2n Aa print(A.in)排版软件排版软件TeXTeX、LaTeXLaTeXaacbb242 基于数学格式语言基于数学格式语言EQN n给定输入给定输入n E sub n .valnEQN语言把语言把E, n 和和.val分别按不同的大分别按不同的大小放在相关的位置上小放在相关的位置上En.val识别输入并进行格式安放的识别输入并进行格式安放的L-属性文法属性文法 产生式产生式 语义规则语义规则 SB SB B.ps :=10B.ps

41、 :=10 S.ht :=B.htS.ht :=B.htBB1B2BB1B2 B1.ps :=B.psB1.ps :=B.ps B2.ps :=B.psB2.ps :=B.ps B.ht := max(B1.ht, B.ht := max(B1.ht, B2.ht)B2.ht)BB1 sub B2BB1 sub B2B1.ps :=B.psB1.ps :=B.ps B2.ps :=shrink(B.ps)B2.ps :=shrink(B.ps) B.ht :=disp(B1.ht, B.ht :=disp(B1.ht, B2.ht)B2.ht)Btext Btext B.ht :=text.h

42、B.ht :=text.hB.psB.psEn.valE sub n .val翻译模式翻译模式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. 一个动作不能引用这个动作右边的符

43、号的综一个动作不能引用这个动作右边的符号的综合属性。合属性。3. 产生式左边非终结符的综合属性只有在它所产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常放在产生式右端的末尾。算这种属性的动作通常放在产生式右端的末尾。n刚刚讲的翻译模式中有很多时候把语义规刚刚讲的翻译模式中有很多时候把语义规则放在产生式的中间，我们能不能建立一则放在产生式的中间，我们能不能建立一种翻译模式，把所有的语义动作都放在产种翻译模式，把所有的语义动作都放在产生式的末尾呢？生式的末尾呢？建立翻译模式建立翻译模式E T RR + T p

44、rint(+) R | - T print(-) R | T numprint(num.val)第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译n属性文法属性文法n基于属性文法的处理方法基于属性文法的处理方法nS-属性文法的自下而上计算属性文法的自下而上计算nL-属性文法和自顶向下的翻译属性文法和自顶向下的翻译6.4.2 自顶向下翻译自顶向下翻译 n为了构造不带回溯的自顶向下语法分析，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归必须消除文法中的左递归n当消除一个翻译模式的基本文法的左递归当消除一个翻译模式的基本文法的左递归时同时考虑属性时同时考虑属性适合带综合属性的翻适

45、合带综合属性的翻译模式译模式 n动作是在处于相同位置上的符号被展开动作是在处于相同位置上的符号被展开匹配成功时执行的。匹配成功时执行的。 自顶向下翻译自顶向下翻译n关于算术表达式的左递归文法相应的翻译关于算术表达式的左递归文法相应的翻译模式模式nEE1+T E.val:=E1.val+T.valnEE1-T E.val:=E1.val-T.valnET E.val:=T.valnT(E)T.val:=E.valnTnum T.val:=num.valE T RR + T R1R - T R1R T ( E )T numn消除左递归，构造新的翻译模式消除左递归，构造新的翻译模式 n E T R.

46、i:=T.valn RE.val:=R.snR +n TR1.i:=R.i+T.valn R1R.s:=R1.snR -n TR1.i:=R.i-T.valn R1R.s:=R1.snR R.s:=R.inT ( E ) T.val:=E.valnT num T.val:=num.valE T RR +TR1R -TR1R T ( E )T numR.i: R前面子表达式前面子表达式 的值的值R.s: 分析完分析完R时子表时子表 达式的值达式的值计算表达式计算表达式952 ETRnumnum.val=9T.val=9R.i=9-TRnumnum.val=5T.val=5R.i=4+TRnumn

47、um.val=2T.val=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 一般方法一般方法n假设有翻译模式：假设有翻译模式：n AA1Y A.a:=g(A1.a,Y.y) n AXA.a:=f(X.x)n它的每个文法符号都有一个综合属性，用小它的每个文法符号都有一个综合属性，用小写

48、字母表示，写字母表示，g和和f是任意函数。是任意函数。q消除左递归：消除左递归：q AXRq RYR | q翻译模式变为翻译模式变为 ：qA XR.i:=f (X.x)q R A.a:=R.sqR Y R1.i:=g(R.i,Y.y) R1R.s:=R1.sqR R.s:=R.iR.i: R前面子表达式前面子表达式 的值的值R.s: 分析完分析完R时子表时子表 达式的值达式的值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)句型句型XYY的翻译

49、过的翻译过程程依据没消除左依据没消除左递归的翻译模式自底递归的翻译模式自底向上翻译向上翻译句型句型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)A X R.i:=f (X.x) R

50、 A.a:=R.sR Y R1.i:=g(R.i,Y.y) R1 R.s:=R1.sR R.s:=R.i作业作业nP203 -3，76.4.3 递归下降翻译器的设计递归下降翻译器的设计 n介绍如何在递归下降分析中实现翻译模式，介绍如何在递归下降分析中实现翻译模式，构造递归下降翻译器构造递归下降翻译器 n（这部分内容自学）（这部分内容自学）设计递归下降翻译器的方法设计递归下降翻译器的方法n 1. n对每个非终结符对每个非终结符A构造一个函数过程，对构造一个函数过程，对A的每个继的每个继承属性设置一个形式参数承属性设置一个形式参数n函数的返回值为函数的返回值为A的综合属性作为记录，或指向记的综合属性作为记录，或指向记录的一个指针，记录中有若干域，每个属性对应一个录的一个指针，记录中有若干域，每个属性对应一个域）。为了简单，我们假设每个非终结只有一个综合域）。为了简单，我们假设每个非终结只