属性文法和语法制导翻译

《属性文法和语法制导翻译》由会员分享，可在线阅读，更多相关《属性文法和语法制导翻译（81页珍藏版）》请在装配图网上搜索。

1、属性文法和语法制导翻译属性文法和语法制导翻译授课：胡静授课：胡静语义分析语义分析面向语法的定义面向语法的定义所处位置所处位置分析技术分析技术 LL分析方法分析方法 计算最左推导计算最左推导 自顶向下的构造推导自顶向下的构造推导 LL的分析表指出要对最左边的非终结符进行扩展时，所选的产的分析表指出要对最左边的非终结符进行扩展时，所选的产生式。生式。LR分析方法分析方法 计算最右推导计算最右推导 自底向上的构造推导自底向上的构造推导 使用使用LR的状态集合和符号栈的状态集合和符号栈 LR分析表指出针对每一个状态，采用何种动作（移进分析表指出针对每一个状态，采用何种动作（移进/归约），归约），并且下

2、一个转入的状态是什么。并且下一个转入的状态是什么。我们可以使用这些技术来构造我们可以使用这些技术来构造 ASTAST AST 复习复习 推导：使用的产生式的序列推导：使用的产生式的序列 S E+S 1+S 1+E 1+2 分析树：描述推导的图分析树：描述推导的图 并不能表示产生式使用的顺序并不能表示产生式使用的顺序 抽象语法树抽象语法树(AST)：从分析树中去掉了那些不必要的信息。：从分析树中去掉了那些不必要的信息。ASTAST的数据结构的数据结构潜在的潜在的ASTAST构造构造 LL/LR分析技术都潜在的构造出了分析技术都潜在的构造出了AST 分析树在推导过程中可以得到分析树在推导过程中可以

3、得到 LL parsing:应用产生式的序列潜在的描述了应用产生式的序列潜在的描述了AST LR parsing：应用归约的序列潜在的描述了：应用归约的序列潜在的描述了AST 我们希望从分析过程中明确的创建我们希望从分析过程中明确的创建AST：在分析器中添加一定的代码来明确的创建在分析器中添加一定的代码来明确的创建ASTAST AST 的构造的构造 LL分析分析:对非终结符进行扩展对非终结符进行扩展 Example:ASTAST的构造的构造 LR分析分析 我们也需要添加一些代码使得我们也需要添加一些代码使得AST可以明确的被构造可以明确的被构造出来。出来。LR分析中分析中AST的构造方法：的构

4、造方法：将树的一部分存放在堆栈里将树的一部分存放在堆栈里 对每个在堆栈中的非终结符对每个在堆栈中的非终结符B，将以，将以B作为根节点的自作为根节点的自树也存放在堆栈里树也存放在堆栈里 当分析器使用产生式当分析器使用产生式B 实施一个归约操作时，为实施一个归约操作时，为B构造一个构造一个AST的结点的结点LRLR分析中分析中ASTAST的构造的构造问题问题 代码的结构混乱：进行语法分析的代码和构造代码的结构混乱：进行语法分析的代码和构造AST的的代码混在一起代码混在一起 语法分析器的生成器：语法分析器的生成器：产生的语法分析器需要包含产生的语法分析器需要包含AST的构造代码的构造代码 如何使用语

5、法分析器的自动生成器构造不同的如何使用语法分析器的自动生成器构造不同的AST数数据结构？据结构？我们需要在分析阶段同时的进行其他的动作。我们需要在分析阶段同时的进行其他的动作。比如，语义检查比如，语义检查Syntax-Directed DefinitionSyntax-Directed Definition 解决方法解决方法:syntax-directed definition 扩展每个文法的产生式，使得每个产生式都和语义动扩展每个文法的产生式，使得每个产生式都和语义动作（代码）相关联：作（代码）相关联：S E+S action 语法分析器的生成器将这些代码加入到生成的语法分语法分析器的生成器

6、将这些代码加入到生成的语法分析器中。析器中。当使用产生式进行归约时，对应的动作就会被执行。当使用产生式进行归约时，对应的动作就会被执行。语义动作语义动作 动作：用程序设计语言编写的代码动作：用程序设计语言编写的代码 和语法分析器的生成器的程序设计语言相同和语法分析器的生成器的程序设计语言相同 例如：例如：Yacc=actions written in C CUP=actions written in Java 动作需要访问语法分析栈！动作需要访问语法分析栈！语法分析器的生成器将状态栈进行扩展，用那些用户定义的结构语法分析器的生成器将状态栈进行扩展，用那些用户定义的结构（分析树）去替换原先的符号

7、（分析树）去替换原先的符号 动作代码应该可以引用状态动作代码应该可以引用状态 需要一套命名机制需要一套命名机制命名机制命名机制 我们需要对那些在语义动作代码中可能用到的文法的我们需要对那些在语义动作代码中可能用到的文法的符号进行命名。符号进行命名。需要分别引用出现在不同地方的同一个非终结符号需要分别引用出现在不同地方的同一个非终结符号 E E1+E2 需要对左边需要对左边/右边的符号进行区别右边的符号进行区别 E0 E+E命名机制：命名机制：YaccYacc Yacc:使用关键字使用关键字:$1引用右边的第一个符号，引用右边的第一个符号，$2引用右边的引用右边的第二个符号，以此类推第二个符号，

8、以此类推 关键字关键字$引用左边的非终结符引用左边的非终结符 Yacc的例子的例子 expr:=expr PLUS expr$=$1+$3;构造构造 ASTAST 使用语义动作构造使用语义动作构造AST AST在分析过程中自底向上的构造在分析过程中自底向上的构造例子例子 分析栈保存了每个非终结符的值分析栈保存了每个非终结符的值ASTAST的设计的设计 保证保证AST的抽象性的抽象性 并不是对每个分析树中的结点都要引入一个并不是对每个分析树中的结点都要引入一个AST的结点。的结点。AST AST 的设计的设计 不要使用一个单一的类不要使用一个单一的类AST_node 例如对于像例如对于像if,w

9、hile,+,*,ID,NUM：class AST_node int node_type;AST_node children;String name;int value;etc 问题：必须要为每个不同的结点保留不同问题：必须要为每个不同的结点保留不同fields来保存其特性。来保存其特性。不可扩展，对不可扩展，对Java的类型检查没有帮助的类型检查没有帮助使用类的继承使用类的继承 使用子类解决问题使用子类解决问题 对每一个对每一个“感兴趣的感兴趣的”文法中非终结符的集合使用一文法中非终结符的集合使用一个抽象类，个抽象类，(例如，产生式例如，产生式)E E+E|E*E|-E|(E)另一个例子另一

10、个例子 可以使用可以使用syntax-directed定义在语法分析的时候进行定义在语法分析的时候进行语义检查语义检查 例如，类型检查例如，类型检查 好处：有效率好处：有效率 一个简单的编译过程可以完成多个任务一个简单的编译过程可以完成多个任务 坏处：代码结构混乱坏处：代码结构混乱 将语法分析和语义检查过程混在一起将语法分析和语义检查过程混在一起 当当AST结构改变的时候进行检查结构改变的时候进行检查 只能是自底向上的过程中只能是自底向上的过程中类型声明的例子类型声明的例子值的传递值的传递 当创建当创建AST的时候，也要把值属性进行传递。的时候，也要把值属性进行传递。另一个例子另一个例子值的传

11、递值的传递 值要两个方向传递：自顶向下和自底向上值要两个方向传递：自顶向下和自底向上构造方法构造方法 从语义检查阶段可以单独的构造从语义检查阶段可以单独的构造AST 反复检查反复检查AST并且进行语义检查并且进行语义检查(或其他动作或其他动作)只有当只有当树被建立起来并且他的结构是稳定的时候才能做。树被建立起来并且他的结构是稳定的时候才能做。这个过程有更多的灵活性，不容易出现错误这个过程有更多的灵活性，不容易出现错误属性文法属性文法目录目录 虽然形式语义学的研究已经取得了许多重大进展，但目前在虽然形式语义学的研究已经取得了许多重大进展，但目前在实际应用中比较流行的语义描述和语义处理的方法主要还

12、是实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译。属性文法和语法制导翻译。本章研究内容：本章研究内容：上下文无关文法所产生的语言的翻译。上下文无关文法所产生的语言的翻译。把属性附加到代表语法结构的文法符号上，可以将语义信息和程把属性附加到代表语法结构的文法符号上，可以将语义信息和程序设计语言的结构联系起来。序设计语言的结构联系起来。属性的值是用与文法产生式相关联的属性的值是用与文法产生式相关联的“语义规则语义规则”来计算的。来计算的。涉及的概念涉及的概念 属性文法：关于语言翻译的高层次规格说明，隐蔽了具体实现细属性文法：关于语言翻译的高层次规格说明，隐蔽了具体实现细

13、节，不显式的说明翻译发生的顺序节，不显式的说明翻译发生的顺序(属性文法属性文法)语法制导翻译：指明了语义规则的计算顺序，说明实现细节。语法制导翻译：指明了语义规则的计算顺序，说明实现细节。语义规则计算可完成的工作语义规则计算可完成的工作 生成代码生成代码 在符号表中保存信息在符号表中保存信息 发出错误信息发出错误信息 对输入符号串翻译的过程就是对语义规则求值的过程对输入符号串翻译的过程就是对语义规则求值的过程属性文法属性文法 是在上下文无关文法的基础上，为每个文法符号（终是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的结符或非终结符）配备若干相关的“值值”。属性代表

14、与文法符号相关的信息，如类型、值、代码属性代表与文法符号相关的信息，如类型、值、代码序列、符号表内容序列、符号表内容 属性可以代表任何对象：字符串，数组，类型，内存属性可以代表任何对象：字符串，数组，类型，内存单元或其他对象单元或其他对象 语法制导定义语法制导定义=文法文法+符号的相关属性集符号的相关属性集 属性分为两个子集：综合属性、继承属性属性分为两个子集：综合属性、继承属性 如果把文法符号的结点看成记录，包含若干存储信息如果把文法符号的结点看成记录，包含若干存储信息的域，那么属性就相当于域的名字的域，那么属性就相当于域的名字属性文法属性文法 分析树节点上属性值由产生式的语义规则来定义分析

15、树节点上属性值由产生式的语义规则来定义 综合属性值：通过分析树中其子节点的属性值计算出来的综合属性值：通过分析树中其子节点的属性值计算出来的 继承属性值：由该节点的兄弟节点及父节点的属性值计算出来的继承属性值：由该节点的兄弟节点及父节点的属性值计算出来的 依赖图依赖图 语义规则建立了属性间的依赖关系，这种关系用图来表示就是依语义规则建立了属性间的依赖关系，这种关系用图来表示就是依赖图赖图 依赖图表示了语义规则的计算顺序依赖图表示了语义规则的计算顺序 注释分析数注释分析数 每个节点都有属性值的分析树叫做注释分析树每个节点都有属性值的分析树叫做注释分析树 计算节点属性的过程称为注释或者装饰分析树计

16、算节点属性的过程称为注释或者装饰分析树属性文法属性文法 在语法制导定义中，每个产生式在语法制导定义中，每个产生式A都有一个形如都有一个形如b=f(c1,c2,.,ck)的语义规则集合与之相关联，其中的语义规则集合与之相关联，其中f是函数，并且满足下面是函数，并且满足下面条件之一条件之一 b是是A的一个综合属性，且的一个综合属性，且c1,c2,.,ck是该产生式文法符号的属性是该产生式文法符号的属性 b是产生式右部某个文法符号的一个继承属性，且是产生式右部某个文法符号的一个继承属性，且c1,c2,.,ck是是A或者产生式右边任何文法符号的属性或者产生式右边任何文法符号的属性 在这两种情况下，我们

17、说属性在这两种情况下，我们说属性b依赖于依赖于c1,c2,.,ck。特别要强调的是：特别要强调的是：终结符只有综合属性，它们由词法分析器提供；终结符只有综合属性，它们由词法分析器提供；非终结符既可有综合属性也可有继承属性，文法开始符号的所有非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。继承属性作为属性计算前的初始值。关于属性文法的说明关于属性文法的说明 通常，这种函数的被写为表达式。通常，这种函数的被写为表达式。其他的语义规则被写为过程调用或者程序段其他的语义规则被写为过程调用或者程序段定义产生式定义产生式左部非终结符的虚综合属性值左部非终结符的虚综合

18、属性值 一般说来，对于出现在一般说来，对于出现在产生式右边的继承属性产生式右边的继承属性和出现在产生和出现在产生式式左边的综合属性左边的综合属性都必须提供一个计算规则。都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内这有助于在产生式范围内“封装封装”属性的依赖性。属性的依赖性。出现在产生式左边的继承属性和出现在产生式右部的综合属出现在产生式左边的继承属性和出现在产生式右部的综合属性不由所给产生式的属性计算规则进行计算，它们由其他产性不由所给产生式的属性计算规则进行计算，它们由其他产生式的属性规

19、则计算或由属性计算器的参数提供。生式的属性规则计算或由属性计算器的参数提供。继承属性和综合属性的计算举例继承属性和综合属性的计算举例 对于产生式对于产生式ABC来讲来讲 直观上来讲，这个产生式可以计算直观上来讲，这个产生式可以计算A的综合属性、的综合属性、B和和C的继承属性。的继承属性。那么对于那么对于A的继承属性，可能需要根据某个类似于的继承属性，可能需要根据某个类似于XA的产生式求的。的产生式求的。同样的同样的B和和C的综合属性可能需要根据某个类似于的综合属性可能需要根据某个类似于B，以及以及C 的产生式求的。的产生式求的。属性文法举例属性文法举例产生式产生式语义规则语义规则LEnprin

20、t(E.val)EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.val*F.val TFT.val:=F.valF(E)F.val:=E.valFdigitF.val:=digit.lexvalS-S-属性文法属性文法 S-属性文法属性文法 在语法树中，一个结点的综合属性的值由其子结点的在语法树中，一个结点的综合属性的值由其子结点的属性值决定。属性值决定。仅使用综合属性的属性文法称为仅使用综合属性的属性文法称为S-属性定义属性定义 S属性定义的分析树的分析方法属性定义的分析树的分析方法自底向上的在每个自底向上的在每个节点用语义规则来计算

21、综合属性值。节点用语义规则来计算综合属性值。综合属性举例综合属性举例LnE产生式产生式语义规则语义规则LEnprint(E.val)EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.val*F.val TFT.val:=F.valF(E)F.val:=E.valFdigitF.val:=digit.lexval3*5+4ET+TF*TFFdigitdigitdigit.lexval=3.val=5.val=4.val=3.val=3.val=15.val=4.val=4.val=15.val=19.val=5继承属性继承属性 在语法树中，

22、一个结点的继承属性由此结点的父结点在语法树中，一个结点的继承属性由此结点的父结点和和/或兄弟结点的某些属性确定。或兄弟结点的某些属性确定。继承属性在程序设计语言中的作用继承属性在程序设计语言中的作用 表示程序设计语言上下文结构的依赖性表示程序设计语言上下文结构的依赖性 对于赋值号，其左边和右边的标识符在操作的时候需要对于赋值号，其左边和右边的标识符在操作的时候需要提供的属性不同，这时候就要跟踪标识符的继承属性。提供的属性不同，这时候就要跟踪标识符的继承属性。如果在赋值号左边，则需要地址，右边则需要值。如果在赋值号左边，则需要地址，右边则需要值。虽然我们总是可以只用综合属性来改写语法制导定义，虽

23、然我们总是可以只用综合属性来改写语法制导定义，但是使用带有继承属性的属性文法有时更为自然。但是使用带有继承属性的属性文法有时更为自然。继承属性的例子继承属性的例子DLT产生式产生式语义规则语义规则DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,idL1.in:=L.in addtype(id.entry,L.in)Lidaddtype(id.entry,L.in)real id1,id2,id3realid3,L.in=real.in=real.type=realid2,L.in=realid1语法制导翻译语法制导翻译 基于属性文法

24、的处理过程通常是：基于属性文法的处理过程通常是：对符号串进行语法分析，对符号串进行语法分析，构造语法分析树构造语法分析树 根据需要遍历语法树并在语法树的各结点处按语义规根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。则进行计算。这种由源程序的语法结构驱动的处理办法就是语法制这种由源程序的语法结构驱动的处理办法就是语法制导翻译法。导翻译法。在某些情况下，在进行语法分析的同时完成语义规则在某些情况下，在进行语法分析的同时完成语义规则的计算而无须明显地构造语法树或构造属性之间的依的计算而无须明显地构造语法树或构造属性之间的依赖图。（一遍处理，赖图。（一遍处理，L-属性文法）属性文法）输入符

25、号串输入符号串分析树分析树依赖图依赖图语义规格的语义规格的计算顺序计算顺序依赖图依赖图 依赖图是有向图依赖图是有向图 表示了分析树中各节点属性间的依赖关系。其中属性包括继承属表示了分析树中各节点属性间的依赖关系。其中属性包括继承属性和综合属性性和综合属性 表示了节点属性的计算先后顺序。如果分析树中某个节点的属性表示了节点属性的计算先后顺序。如果分析树中某个节点的属性b依赖于属性依赖于属性c，那么在该节点处，那么在该节点处b的语义规则必须在的语义规则必须在c的语义规则的语义规则之后计算。之后计算。依赖图的构造方法依赖图的构造方法 为每个包括过程调用的语义规则引入一个虚综合属性为每个包括过程调用的

26、语义规则引入一个虚综合属性b，把每条，把每条语义规则都变成语义规则都变成b=f(c1,c2,.,ck)的形式的形式 依赖图的每个结点表示一个属性依赖图的每个结点表示一个属性 边表示属性间的依赖关系。如果属性边表示属性间的依赖关系。如果属性b依赖于属性依赖于属性c，那么从，那么从c到到b就有一条有向边就有一条有向边依赖图举例依赖图举例DLTrealid3,L.in=real.in=real.type=realid2,L.in=realid1DLTrealid3,Lid2,Lid1typeinyinyinyentryentryentry12345678910如果一属性文法不存在属性如果一属性文法不

27、存在属性之间的循环依赖关系，那么之间的循环依赖关系，那么称该文法为良定义的称该文法为良定义的产生式产生式语义规则语义规则DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,idL1.in:=L.in addtype(id.entry,L.in)Lidaddtype(id.entry,L.in)属性的计算顺序属性的计算顺序 无环有向图的拓扑排序无环有向图的拓扑排序 无环有向图中节点无环有向图中节点m1,m2,mk的拓扑排序是：若的拓扑排序是：若mimj是从是从mi到到mj的边，那么在此排序中的边，那么在此排序中mi先于先于mj 依赖图的任

28、何拓扑排序都给出了一个分析树中各节点依赖图的任何拓扑排序都给出了一个分析树中各节点语义规则计算的正确顺序，即在计算语义规则计算的正确顺序，即在计算f之前，语义规则之前，语义规则b=f(c1,c2,.,ck)中的依赖属性中的依赖属性c1,c2,.,ck都是已知的都是已知的 属性文法所说明的翻译可以按照下面的步骤进行属性文法所说明的翻译可以按照下面的步骤进行 最基本的文法用于构造输入串的分析树最基本的文法用于构造输入串的分析树 用前面的方法构造依赖图用前面的方法构造依赖图 从依赖图的拓扑排序可以得到语义规则的计算顺序从依赖图的拓扑排序可以得到语义规则的计算顺序 按该顺序计算语义规则即可得到输入串的

29、翻译按该顺序计算语义规则即可得到输入串的翻译属性文法计算顺序举例属性文法计算顺序举例 a4:=real a5:=a4 addtype(id3.entry,a5)a7:=a5 addtype(id2.entry,a7)a9:=a7 addtype(id1.entry,a9)DLTrealid3,Lid2,Lid1typeinyinyinyentryentryentry12345678910计算语义规则的方法计算语义规则的方法 分析树法：分析树法：在编译时，这种方法从分析树所构成的依赖图的拓扑排序中得到在编译时，这种方法从分析树所构成的依赖图的拓扑排序中得到语义规则的计算顺序。语义规则的计算顺序。

30、如果分析树的依赖图中有环路，这种方法将失败如果分析树的依赖图中有环路，这种方法将失败 基于规则的方法基于规则的方法 对于每一个产生式，计算该产生式所关联的属性的顺序在编译器对于每一个产生式，计算该产生式所关联的属性的顺序在编译器构造时已经预先确定好了构造时已经预先确定好了 忽略规则的方法忽略规则的方法 选择计算顺序时不考虑语义规则。如果翻译是在语法分析过程中选择计算顺序时不考虑语义规则。如果翻译是在语法分析过程中进行的，那么计算顺序的选择就由语法分析方法来确定。进行的，那么计算顺序的选择就由语法分析方法来确定。后两种方法在编译时都不必显式的构造依赖图后两种方法在编译时都不必显式的构造依赖图树遍

31、历的属性计算方法树遍历的属性计算方法 通过树遍历计算属性值的方法都假设语法树已经建立，通过树遍历计算属性值的方法都假设语法树已经建立，并且数中已带有开始符号的继承属性和终结符的综合并且数中已带有开始符号的继承属性和终结符的综合属性。属性。最常用的遍历方法是深度优先，从左到右的遍历方法最常用的遍历方法是深度优先，从左到右的遍历方法 只要文法的属性是非循环定义的，则每次扫描至少有只要文法的属性是非循环定义的，则每次扫描至少有一个属性值被计算出来。一个属性值被计算出来。如果语法树有如果语法树有n个结点（因此最多有个结点（因此最多有O(n)个属性），最个属性），最坏的情况整个遍历需要坏的情况整个遍历需

32、要O(n2)时间。时间。树遍历的举例树遍历的举例产生式产生式语义规则语义规则SXYZZ.h:=S.aX.c:=Z.gS.b:=X.d 2Y.e:=S.b XxX.d:=2*X.cYyY.f:=Y.e*3ZzZ.g:=Z.h+1S有继承属性有继承属性a，综合属性，综合属性bX有继承属性有继承属性c，综合属性，综合属性dY有继承属性有继承属性e，综合属性，综合属性fZ有继承属性有继承属性h，综合属性，综合属性g假设假设S.a的初始值为的初始值为0SZYXxyza=0初始状态初始状态SZYXxyza=0第一遍扫描第一遍扫描h=0g=1SZYXxyza=0第二遍扫描第二遍扫描h=0g=1c=1d=2S

33、ZYXxyza=0第三遍扫描第三遍扫描h=0g=1b=0e=0f=0c=1d=2一遍扫描的处理方法一遍扫描的处理方法 在语法分析的同时计算属性值，而不是语法分析构造语法树在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树。之后进行属性的计算，而且无需构造实际的语法树。一遍扫描的处理方法与语法分析器密切相关的因素：一遍扫描的处理方法与语法分析器密切相关的因素：所采用的语法分析方法所采用的语法分析方法 属性的计算顺序属性的计算顺序 L-属性文法可用于一遍扫描的自顶向下分析，而属性文法可用于一遍扫描的自顶向下分析，而S-属性文法适属性文法适合于一遍扫描的

34、自底向上分析。合于一遍扫描的自底向上分析。此时的语法制导翻译可理解为：直观上说为文法中每个产生此时的语法制导翻译可理解为：直观上说为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义式配上一组语义规则，并且在语法分析的同时执行这些语义规则规则 在自顶向下语法分析中，若一个产生式匹配输入串成功在自顶向下语法分析中，若一个产生式匹配输入串成功 在自底向上语法分析中，当一个产生式被用于进行归约时在自底向上语法分析中，当一个产生式被用于进行归约时抽象语法树的构造抽象语法树的构造 用抽象语法树作为中间表示，可以把翻译从语法分析用抽象语法树作为中间表示，可以把翻译从语法分析中分离出来中分离

35、出来 语法树是分析树的压缩形式，去掉了那些对翻译不必语法树是分析树的压缩形式，去掉了那些对翻译不必要的信息，对表示语言的结构很有用。要的信息，对表示语言的结构很有用。表达式的抽象语法树的构造表达式的抽象语法树的构造 为每个运算符和运算对象建立节点来为子表达式构造为每个运算符和运算对象建立节点来为子表达式构造子树。子树。运算符节点的字节点分别是表示该运算符各运算对象运算符节点的字节点分别是表示该运算符各运算对象的子表达式组成的子树的根的子表达式组成的子树的根表达式语法树的构造方法表达式语法树的构造方法 运算符节点（用记录实现，也可以用对象实现）运算符节点（用记录实现，也可以用对象实现）一个域标识

36、运算符，其余域包含指向运算对象的指针一个域标识运算符，其余域包含指向运算对象的指针 将运算符称为该节点的标记将运算符称为该节点的标记 构造的过程（方法）构造的过程（方法）mknode(op,left,right)：建立一个标记为：建立一个标记为op的运算符节的运算符节点，其中两个域点，其中两个域left和和right是指向其左右运算对象的指是指向其左右运算对象的指针针 mkleaf(id,entry)：建立标记为：建立标记为id的标识符节点，的标识符节点，entry是指向该标识符在标识符表中的相应表项的指针是指向该标识符在标识符表中的相应表项的指针 mkleaf(num,value)：建立标记

37、为：建立标记为num的数节点，域的数节点，域val保存该数的值。保存该数的值。抽象语法树的例子抽象语法树的例子产生式产生式语义规则语义规则EE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1 TE.nptr:=mknode(-,E1.nptr,T.nptr)ETE.nptr:=T.nptrT(E)T.nptr:=E.nptr TidT.nptr:=mkleaf(id ,id.entry)TnumT.nptr:=mkleaf(num,num.val)表达式的无环有向图表达式的无环有向图 表达式的无环有向图（表达式的无环有向图（dag）可以识别表达式中的公共子）可以识别

38、表达式中的公共子表达式表达式 无环有向图的组成无环有向图的组成 叶子节点：表达式中的操作数（操作符的运算对象）叶子节点：表达式中的操作数（操作符的运算对象）内部节点：表达式中的操作符（运算符）内部节点：表达式中的操作符（运算符）子树：表达式中的每一个子表达式子树：表达式中的每一个子表达式 和抽象语法树的区别：和抽象语法树的区别：代表公共子表达式的节点具有多个代表公共子表达式的节点具有多个“父结点父结点”在省城抽象语法树时，在省城抽象语法树时，mknode和和mkleaf之前先查看是否已之前先查看是否已经存在需要创建的节点，如果存在，则返回以创建的节点经存在需要创建的节点，如果存在，则返回以创建

39、的节点而不是新创建一个节点而不是新创建一个节点S S属性文法的自底向上计算属性文法的自底向上计算S-S-属性文法的特点属性文法的特点 S-属性文法，只有综合属性属性文法，只有综合属性 也就是说产生式左边的文法的综合属性要根据产生式也就是说产生式左边的文法的综合属性要根据产生式右边符号的综合属性来进行计算。右边符号的综合属性来进行计算。适用于那些需要类似于表达式，需要计算结果的文法。适用于那些需要类似于表达式，需要计算结果的文法。综合属性可以在分数输入符号串的同时由自底向上的综合属性可以在分数输入符号串的同时由自底向上的分析器来计算。分析器来计算。分析器保存与栈中文法符号有关的综合属性分析器保存

40、与栈中文法符号有关的综合属性 每当归约时，新的属性值就由栈中正在归约的产生式每当归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。右边符号的属性值来计算。S-S-属性文法翻译器的实现属性文法翻译器的实现 S-属性文法的翻译器通常可借助于属性文法的翻译器通常可借助于LR分析器实现。分析器实现。在自底向上的分析方法中，我们使用栈来存放已经分析过了在自底向上的分析方法中，我们使用栈来存放已经分析过了的子树，现在我们可以在分析栈中使用一个附加域来存放综的子树，现在我们可以在分析栈中使用一个附加域来存放综合属性值。合属性值。假设综合属性是刚好在每次归约前计算的假设综合属性是刚好在每次归约

41、前计算的S3S2S1ZYXZ.zY.yX.x状态栈状态栈符号栈符号栈valtopAXYZS-S-属性文法计算举例属性文法计算举例产生式产生式语义规则语义规则LEnprint(valtop)EE1+Tvaltop:=valtop-2+valtopETTT1*Fvaltop:=valtop-2*valtop TFF(E)valtop:=valtop-1Fdigit我们要控制两个变量我们要控制两个变量top和和ntop。当右边带有当右边带有r个符号的产生式被归约时，执行相应个符号的产生式被归约时，执行相应的代码段之前，先将的代码段之前，先将top-r+1赋给赋给ntop，在代码段，在代码段被执行之后

42、将被执行之后将ntop的值赋给的值赋给top代码段刚刚好在归约前执行。代码段刚刚好在归约前执行。这是利用归约提供一个这是利用归约提供一个“挂挂钩钩”，使得用户把一个语义动，使得用户把一个语义动作与一个产生式联系起来。作与一个产生式联系起来。翻译模式可以提供一种与分析翻译模式可以提供一种与分析器相互穿插动作的描述方法。器相互穿插动作的描述方法。L-L-属性文法和自顶向下翻译属性文法和自顶向下翻译L L属性文法定义属性文法定义 在语法分析过程中进行翻译时，属性的计算顺序将与分析方在语法分析过程中进行翻译时，属性的计算顺序将与分析方法建立分析树节点的顺序相关。有一种能够描述许多自顶向法建立分析树节点

43、的顺序相关。有一种能够描述许多自顶向下和自底向上翻译方法的自然顺序下和自底向上翻译方法的自然顺序深度优先顺序。深度优先顺序。L属性定义属性定义 一个属性文法是一个属性文法是L-属性文法，如果对于每一个产生式属性文法，如果对于每一个产生式AX1X2Xn，其右部符号，其右部符号Xj(1jn)的每个属性值仅依赖于下列属性的每个属性值仅依赖于下列属性 产生式中产生式中Xj左边的符号左边的符号X1X2Xj-1的属性的属性 A的继承属性的继承属性 L属性的计算属性的计算 可以使用深度优先顺序来计算可以使用深度优先顺序来计算 LL(1)的分析过程，从概念上说可以看成是深度优先建立语法树的分析过程，从概念上说

44、可以看成是深度优先建立语法树的过程的过程L 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)语法制导翻译语法制导翻译 语法制导翻译给出了使用语义规则进行计算的次序，语法制导翻译给出了使用语义规则进行计算的次序，这样就可以把某些细节表示出来。这样就可以把某些细节表示出来。在语法制导翻译中，和文法符号相关的属性和语义规在语法制导翻译中，和文法符号相关的属性和语义规则（这里也称语义动作），用则（这里也称语义动作），用“”括起来，插入到括起来，插入到产生式右部合适的位置上

45、。产生式右部合适的位置上。语法制导翻译给出了使用语义规则进行计算的顺序。语法制导翻译给出了使用语义规则进行计算的顺序。语法制导翻译举例语法制导翻译举例ETRRaddop T print(addop.lexeme)R1|Tnum print(num.val)ERT9print(9)-Tprint(-)R5print(5)+Tprint(+)2print(2)R9-5+29-5+2按深度优先遍历之后按深度优先遍历之后95-2+95-2+L-L-属性定义的语法制导翻译属性定义的语法制导翻译 设计设计L属性定义的语法制导翻译需要注意以下几点：属性定义的语法制导翻译需要注意以下几点：基本设计原则：当某个

46、动作引用一个属性时，这个属基本设计原则：当某个动作引用一个属性时，这个属性是可用的。也就是说，一个动作不会引起一个没有性是可用的。也就是说，一个动作不会引起一个没有计算出来的属性。计算出来的属性。只有综合属性时只有综合属性时 为每一个语义规则建立一个赋值动作，并把该动作放在为每一个语义规则建立一个赋值动作，并把该动作放在产生式右部的末尾产生式右部的末尾 TT1*F T.val:=T1.val F.val TT1*F T.val:=T1.val F.valL-L-属性定义的语法制导翻译属性定义的语法制导翻译 同时存在综合属性和继承属性时：同时存在综合属性和继承属性时：产生式右部符号的继承属性必须

47、在这个符号以前的动作中计算出产生式右部符号的继承属性必须在这个符号以前的动作中计算出来来 一个动作不能引用该动作右部符号的综合属性一个动作不能引用该动作右部符号的综合属性 产生式左部非终结符的综合属性只有在其引用的所有属性值都计产生式左部非终结符的综合属性只有在其引用的所有属性值都计算出来以后才能计算。计算该属性的动作通常放在产生式右部的算出来以后才能计算。计算该属性的动作通常放在产生式右部的末尾。末尾。下面的翻译模式不符合上面的定义：下面的翻译模式不符合上面的定义：SA1A2 A1.in:=1;A2.in:=2 Aaprint(A.in)按深度优先遍历时，要打印第二个产生式里的继承属性按深度

48、优先遍历时，要打印第二个产生式里的继承属性A.in时，时，该属性还没有被定义。该属性还没有被定义。L-L-属性文法举例属性文法举例产生式产生式语义规则语义规则SBB.ps:=10S.ht:=B.htBB1B2B1.ps:=B.psB2.ps:=B.psB.ht:=max(B1.ht,B2.ht)B B1 sub B2B1.ps:=B.psB2.ps:=shrink(B.ps)B.ht:=disp(B1.ht,B2.ht)BtextB.ht:=text.h B.psSB.ps:=10 B S.ht:=B.htBB1.ps:=B.ps B1 B2.ps:=B.ps B2 B.ht:=max(B1.

49、ht,B2.ht)B B1.ps:=B.ps B1 sub B2.ps:=shrink(B.ps)B2 B.ht:=disp(B1.ht,B2.ht)Btext B.ht:=text.h B.psL-L-属性文法的自顶向下翻译属性文法的自顶向下翻译 在预测分析的过程中实现在预测分析的过程中实现L-属性文法属性文法 为了明显的看出动作和属性计算发生的属性，我们使为了明显的看出动作和属性计算发生的属性，我们使用翻译模式而不是属性文法。用翻译模式而不是属性文法。为了构造不带回溯的自顶向下语法分析，必须消除文为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。法中的左递归。将前面讲过的方法扩充

50、，从翻译模式中消除左递归将前面讲过的方法扩充，从翻译模式中消除左递归（LL(1)文法构造的步骤），这种方法也适用于带有文法构造的步骤），这种方法也适用于带有综合属性的翻译模式。综合属性的翻译模式。举例举例EE1+T E.val:=E1.val+T.valEE1-T E.val:=E1.val-T.valET E.val:=T.valT(E)T.val:=E.valTnum T.val:=num.valETR.i:=T.val RE.val:=R.sR+T R1.i:=R.i+T.val R1 R.s:=R1.sR-T R1.i:=R.i-T.val R1 R.s:=R1.sR R.s:=R.i

51、T(E )T.val:=E.valTnum T.val:=num.val9-5+2R-TnumRETnumR+Tnumval=9val=9i=9val=5val=5i=4val=2val=2i=6s=6val=6一个符号继承属性必须由出现这个符号一个符号继承属性必须由出现这个符号之前的动作来计算，产生式左边非终结之前的动作来计算，产生式左边非终结符的综合属性必须在它所依赖的所有属符的综合属性必须在它所依赖的所有属性都计算出来之后才能计算性都计算出来之后才能计算消除左递归的一般方法消除左递归的一般方法 假设有如下的翻译模式假设有如下的翻译模式 AA1Y A.a:=g(A1.a,Y.y)AX A.

52、a:=f(X.x)每个文法符号都有综合属性，每个文法符号都有综合属性，g和和f是任意函数。是任意函数。文法可以转换为：文法可以转换为：AXR RYR|考虑语义动作，变为：考虑语义动作，变为：AXR.i:=f(X.x)RA.a:=R.s RYR1.i:=g(R.i,Y.y)R1R.s:=R1.s R R.s:=R.i递归下降翻译器的设计递归下降翻译器的设计 为每个非终结符为每个非终结符A构造一个函数构造一个函数 A的每个继承属性均对应该函数的一个形式参数，其返回值为的每个继承属性均对应该函数的一个形式参数，其返回值为A的综合属性的值（可能是一个记录、一个指针或者使用传地址参的综合属性的值（可能是

53、一个记录、一个指针或者使用传地址参数的传递机制）数的传递机制）非终结符非终结符A的代码会根据当前的输入决定使用哪个产生式的代码会根据当前的输入决定使用哪个产生式 与每个产生式有关的代码执行如下动作：从左到右考虑产生式右与每个产生式有关的代码执行如下动作：从左到右考虑产生式右部的记号、非终结符及语义动作部的记号、非终结符及语义动作 对于带有综合属性对于带有综合属性x的终结符的终结符X，把，把x的值保持在的值保持在X.x中，然后产生一中，然后产生一个匹配个匹配X的调用，并继续输入的调用，并继续输入 对于非终结符对于非终结符B，产生一个右部带有函数调用的赋值语句，产生一个右部带有函数调用的赋值语句c

54、=B(b1,b2,.bk)，其中，其中b1,b2,.bk是代表是代表B的继承属性变量，的继承属性变量，c是代表是代表B的综合的综合属性的变量属性的变量 对于每个动作，将其代码复制到语法分析器，并把对属性的引用改对于每个动作，将其代码复制到语法分析器，并把对属性的引用改为对相应变量的引用为对相应变量的引用自底向上计算继承属性自底向上计算继承属性 删除嵌入在翻译模式中的动作删除嵌入在翻译模式中的动作 在自顶向下分析中我们可以在产生式右部的任何地方嵌入动作在自顶向下分析中我们可以在产生式右部的任何地方嵌入动作 在自底向上翻译方法中，需要把所有的翻译动作都放在产生式右在自底向上翻译方法中，需要把所有的

55、翻译动作都放在产生式右部的末尾部的末尾 在基础文法中加入新的形如在基础文法中加入新的形如M的产生式，其中的产生式，其中M M为标记非终为标记非终结符。将每个嵌入动作用不同的标记非终结符结符。将每个嵌入动作用不同的标记非终结符M M来代替，并把该来代替，并把该动作放在此空产生式的末端动作放在此空产生式的末端 例如例如 ETR R+T print(+)R|-T print(-)R|T num print(num.val)转化为转化为 ETR R+TMR|-TNR|M print(+)N print(-)自底向上计算继承属性自底向上计算继承属性 转换后的转换后的语法制导翻译语法制导翻译和原和原语法制

56、导翻译语法制导翻译比较比较用额外的节点表示动作，但动作的执行顺序是一样的用额外的节点表示动作，但动作的执行顺序是一样的转换后的翻译模式中，动作都在产生式的末尾，可以转换后的翻译模式中，动作都在产生式的末尾，可以在自底向上的分析过程中刚好在产生式右部被归约之在自底向上的分析过程中刚好在产生式右部被归约之前执行前执行分析栈中的继承属性分析栈中的继承属性 对于继承属性是由复制规则定义的产生式对于继承属性是由复制规则定义的产生式 自底向上语法分析器对产生式自底向上语法分析器对产生式AXY的归约就是从分的归约就是从分析栈顶移走析栈顶移走X和和Y并用并用A来代替它们。假设来代替它们。假设X有一个综有一个综

57、合属性合属性X.s。X的综合属性在分析中放入属性栈，和状态栈符号栈的综合属性在分析中放入属性栈，和状态栈符号栈是一一对应的。是一一对应的。X.s在在Y以下的子树的任何归约之前已经放在栈中，这以下的子树的任何归约之前已经放在栈中，这个值可以被个值可以被Y继承，也就是说，如果继承属性继承，也就是说，如果继承属性Y.i是由是由复写规则复写规则Y.i:=X.s定义，那么在需要定义，那么在需要Y.i的地方可以使的地方可以使用用X.s的值。的值。举例举例DTL.in:=T.type LTint T.type:=integerTrealT.type:=realL L1.in:=L.in L1,id addt

58、ype(id.entry,L.in)Lidaddtype(id.entry,L.in)int p,q,rrL,intLDTqL,pintypeinin所用产生式所用产生式栈栈输入串输入串-int p,q,rint p,q,rT p,q,rTintTp ,q,rTL ,q,rTintTL,q,rTL,q ,rTL ,rLL,idTL,rTL,rTLLL,idDDTL产生式产生式代码段代码段DTLTintvalnotp:=integerTrealvalnotp:=realLL,idaddtype(valtop,valtop-3)Lidaddtype(valtop,valtop-1)模拟继承属性的计

59、算模拟继承属性的计算 使用自底向上的方法计算继使用自底向上的方法计算继承属性，必须要可以预测属承属性，必须要可以预测属性值在栈中的位置。性值在栈中的位置。产生式产生式语义规则语义规则SaACC.i:=A.sSbABCC.i:=A.sCcC.s:=g(C.i)产生式产生式语义规则语义规则SaACC.i:=A.sSaABMCM.i:=A.s;C.i:=M.s CcC.s:=g(C.i)MM.s:=M.i模拟继承属性的计算模拟继承属性的计算 模拟由复制规则计算的继承属性模拟由复制规则计算的继承属性 引入一个新的标记非终结符引入一个新的标记非终结符M，用，用M的继承属性和综的继承属性和综合属性来传递后

60、面非终结符需要复制的继承属性。合属性来传递后面非终结符需要复制的继承属性。模拟不是复制规则的语义规则（计算函数）模拟不是复制规则的语义规则（计算函数）也可以加入新的标记非终结符，用复制规则继承前面也可以加入新的标记非终结符，用复制规则继承前面非终结符的属性值，其综合属性被置为用计算函数进非终结符的属性值，其综合属性被置为用计算函数进行计算行计算产生式产生式语义规则语义规则SLBB.ps:=L.psS.ht:=B.htLL.ps:=10BB1MB2B1.ps:=B.psM.i:=B.psB2.ps:=M.sB.ht:=max(B1.ht,B2.ht)B B1 subN B2B1.ps:=B.ps

61、N.i:=B.psB2.ps:=N.sB.ht:=disp(B1.ht,B2.ht)BtextB.ht:=text.h B.psMM.s:=M.iNN.s:=shrink(N.i)产生式产生式语义规则语义规则SLBvalntop:=val topLvalntop:=10BB1MB2valntop:=max(val top-2,val top)B B1 subN B2valntop:=disp(val top-2,val top)Btextvalntop:=val topval top-1Mvalntop:=val top-1Nvalntop:=shrink(val top-2)带有继承属性的自

62、底向上语法分析和翻译带有继承属性的自底向上语法分析和翻译 假设条件假设条件 每个非终结符每个非终结符A都有一个继承属性都有一个继承属性A.i，每个文法符号，每个文法符号X都有一个综合属性都有一个综合属性X.s。对于终结符，其综合属性是。对于终结符，其综合属性是词法分析器返回的词法值。词法分析器返回的词法值。对于每个产生式对于每个产生式AX1X2Xn，引入，引入n个新的标记非个新的标记非终结符终结符M1,Mn并用并用A M1X1 MnXn代替该产生式代替该产生式 如果继承属性如果继承属性A.i存在，则其值可以在存在，则其值可以在val数组紧贴数组紧贴M1下面的地方找到。下面的地方找到。继承属性将

63、和标记非终结符继承属性将和标记非终结符Mj联系在一起，属性值联系在一起，属性值Xj.i在在Mj处完成计算，而且该计算是在归约处完成计算，而且该计算是在归约Xj之前进行的之前进行的带有继承属性的自底向上语法分析和翻译带有继承属性的自底向上语法分析和翻译 计算方法计算方法 当归约标记非终结符当归约标记非终结符Mj时，可以从栈顶依次找到需要使用的属时，可以从栈顶依次找到需要使用的属性值，性值，A.i 在在valtop 2j+2的位置上，的位置上，X1.i在在valtop 2j+3的位置上，的位置上，X1.s在在valtop 2j+4的位置上的位置上 得到的得到的Mj.s的值实际上是的值实际上是Xj.

64、i的值，放在的值，放在valtop+1的位置上的位置上 归约非标记符号，只需要计算综合属性归约非标记符号，只需要计算综合属性A.s，因为，因为A.i已经计算出已经计算出来了，放在来了，放在A要插入的那个位置之下。要插入的那个位置之下。算法简化（减少标记符号数目，避免左递归）算法简化（减少标记符号数目，避免左递归）如果如果Xj没有继承属性，就不需要没有继承属性，就不需要Mj了。了。如果如果X1.i存在，但是它是由复制规则存在，但是它是由复制规则X1.i=A.i计算的，那么可以省计算的，那么可以省略略M1作业作业 下列文法由开始符号下列文法由开始符号S产生一个二进制数，令综合属产生一个二进制数，令综合属性性val给出该数的值：给出该数的值：SL.L|L LLB|B B0|1 试设计求试设计求S.val的属性文法，其中，已知的属性文法，其中，已知B的综合属性的综合属性c，给出由，给出由B产生的二进位的结果值。产生的二进位的结果值。作业作业 设下列文法生成变量的类型说明设下列文法生成变量的类型说明 Lid L L,id L|:T Tinteger|real 构造一个翻译模式，把每个标识符的类型存入符号表构造一个翻译模式，把每个标识符的类型存入符号表 从上面得到的翻译模式，构造一个预测翻译器从上面得到的翻译模式，构造一个预测翻译器