《天津大学编译原理讲义 - part6属性文法和语法制导翻译》由会员分享，可在线阅读，更多相关《天津大学编译原理讲义 - part6属性文法和语法制导翻译（55页珍藏版）》请在金锄头文库上搜索。
1、属性文法和语法制导翻译,授课：胡静,语义分析面向语法的定义,所处位置,分析技术,LL分析方法 计算最左推导 自顶向下的构造推导 LL的分析表指出要对最左边的非终结符进行扩展时，所选的产生式。 LR分析方法 计算最右推导 自底向上的构造推导 使用LR的状态集合和符号栈 LR分析表指出针对每一个状态，采用何种动作（移进/归约），并且下一个转入的状态是什么。 我们可以使用这些技术来构造 AST,AST 复习,推导：使用的产生式的序列 S E + S 1 + S 1 + E 1 + 2 分析树：描述推导的图 并不能表示产生式使用的顺序 抽象语法树 (AST)：从分析树中去掉了那些不必要的信息。,AST
2、的数据结构,潜在的AST构造,LL/LR分析技术都潜在的构造出了AST 分析树在推导过程中可以得到 LL parsing: 应用产生式的序列潜在的描述了AST LR parsing：应用归约的序列潜在的描述了AST 我们希望从分析过程中明确的创建AST： 在分析器中添加一定的代码来明确的创建AST,AST 的构造,LL分析: 对非终结符进行扩展 Example:,AST的构造,LR分析 我们也需要添加一些代码使得AST可以明确的被构造出来。 LR分析中AST的构造方法： 将树的一部分存放在堆栈里 对每个在堆栈中的非终结符B，将以B作为根节点的自树也存放在堆栈里 当分析器使用产生式B 实施一个归
3、约操作时，为B构造一个AST的结点,LR分析中AST的构造,问题,代码的结构混乱：进行语法分析的代码和构造AST的代码混在一起 语法分析器的生成器： 产生的语法分析器需要包含AST的构造代码 如何使用语法分析器的自动生成器构造不同的AST数据结构？ 我们需要在分析阶段同时的进行其他的动作。 比如，语义检查,Syntax-Directed Definition,解决方法: syntax-directed definition 扩展每个文法的产生式，使得每个产生式都和语义动作（代码）相关联： S E+S action 语法分析器的生成器将这些代码加入到生成的语法分析器中。 当使用产生式进行归约时，
4、对应的动作就会被执行。,语义动作,动作：用程序设计语言编写的代码 和语法分析器的生成器的程序设计语言相同 例如： Yacc = actions written in C CUP = actions written in Java 动作需要访问语法分析栈！ 语法分析器的生成器将状态栈进行扩展，用那些用户定义的结构（分析树）去替换原先的符号 动作代码应该可以引用状态 需要一套命名机制,命名机制,我们需要对那些在语义动作代码中可能用到的文法的符号进行命名。 需要分别引用出现在不同地方的同一个非终结符号 E E1 + E2 需要对左边/右边的符号进行区别 E0 E + E,命名机制：Yacc,Yacc
5、: 使用关键字: $1引用右边的第一个符号，$2引用右边的第二个符号，以此类推 关键字$引用左边的非终结符 Yacc的例子 expr := expr PLUS expr $ = $1 + $3; ,构造 AST,使用语义动作构造AST AST在分析过程中自底向上的构造,例子,分析栈保存了每个非终结符的值,AST的设计,保证AST的抽象性 并不是对每个分析树中的结点都要引入一个AST的结点。,AST 的设计,不要使用一个单一的类AST_node 例如对于像if, while, +, *, ID, NUM： class AST_node int node_type; AST_node childr
6、en; String name; int value; etc 问题：必须要为每个不同的结点保留不同fields来保存其特性。 不可扩展，对Java的类型检查没有帮助,使用类的继承,使用子类解决问题 对每一个“感兴趣的”文法中非终结符的集合使用一个抽象类， (例如，产生式) E E+E | E*E | -E | (E),另一个例子,可以使用syntax-directed定义在语法分析的时候进行语义检查 例如，类型检查 好处：有效率 一个简单的编译过程可以完成多个任务 坏处：代码结构混乱 将语法分析和语义检查过程混在一起 当AST结构改变的时候进行检查 只能是自底向上的过程中,类型声明的例子,值
7、的传递,当创建AST的时候，也要把值属性进行传递。,另一个例子,值的传递,值要两个方向传递：自顶向下和自底向上,构造方法,从语义检查阶段可以单独的构造AST 反复检查AST并且进行语义检查 (或其他动作)只有当树被建立起来并且他的结构是稳定的时候才能做。 这个过程有更多的灵活性，不容易出现错误,属性文法,目录,虽然形式语义学的研究已经取得了许多重大进展，但目前在实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译。 本章研究内容： 上下文无关文法所产生的语言的翻译。 把属性附加到代表语法结构的文法符号上，可以将语义信息和程序设计语言的结构联系起来。 属性的值是用与文法产生
8、式相关联的“语义规则”来计算的。 涉及的概念 属性文法：关于语言翻译的高层次规格说明，隐蔽了具体实现细节，不显式的说明翻译发生的顺序(属性文法) 语法制导翻译：指明了语义规则的计算顺序，说明实现细节。,语义规则计算可完成的工作,生成代码 在符号表中保存信息 发出错误信息 对输入符号串翻译的过程就是对语义规则求值的过程,属性文法,是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”。 属性代表与文法符号相关的信息，如类型、值、代码序列、符号表内容 属性可以代表任何对象：字符串，数组，类型，内存单元或其他对象 语法制导定义=文法+符号的相关属性集 属性分为两个子集：综
9、合属性、继承属性 如果把文法符号的结点看成记录，包含若干存储信息的域，那么属性就相当于域的名字,属性文法,分析树节点上属性值由产生式的语义规则来定义 综合属性值：通过分析树中其子节点的属性值计算出来的 继承属性值：由该节点的兄弟节点及父节点的属性值计算出来的 依赖图 语义规则建立了属性间的依赖关系，这种关系用图来表示就是依赖图 依赖图表示了语义规则的计算顺序 注释分析数 每个节点都有属性值的分析树叫做注释分析树 计算节点属性的过程称为注释或者装饰分析树,属性文法,在语法制导定义中，每个产生式A都有一个形如b=f(c1,c2,.,ck)的语义规则集合与之相关联，其中f是函数，并且满足下面条件之一
10、 b是A的一个综合属性，且c1,c2,.,ck是该产生式文法符号的属性 b是产生式右部某个文法符号的一个继承属性，且c1,c2,.,ck是A或者产生式右边任何文法符号的属性 在这两种情况下，我们说属性b依赖于c1,c2,.,ck 。 特别要强调的是： 终结符只有综合属性，它们由词法分析器提供； 非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。,关于属性文法的说明,通常，这种函数的被写为表达式。 其他的语义规则被写为过程调用或者程序段定义产生式左部非终结符的虚综合属性值 一般说来，对于出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算
11、规则。 属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内“封装”属性的依赖性。 出现在产生式左边的继承属性和出现在产生式右部的综合属性不由所给产生式的属性计算规则进行计算，它们由其他产生式的属性规则计算或由属性计算器的参数提供。,继承属性和综合属性的计算举例,对于产生式ABC来讲 直观上来讲，这个产生式可以计算A的综合属性、B和C的继承属性。 那么对于A的继承属性，可能需要根据某个类似于XA的产生式求的。 同样的B和C的综合属性可能需要根据某个类似于B，以及C 的产生式求的。,属性文法举例,S-属性文法,S-属性文法 在语法树中，一个结点的综合属性的值由其子结点的属性
12、值决定。 仅使用综合属性的属性文法称为S-属性定义 S属性定义的分析树的分析方法自底向上的在每个节点用语义规则来计算综合属性值。,综合属性举例,L,n,E,3*5+4,E,T,+,T,F,*,T,F,F,digit,digit,digit,.lexval=3,.val=5,.val=4,.val=3,.val=3,.val=15,.val=4,.val=4,.val=15,.val=19,.val=5,继承属性,在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。 继承属性在程序设计语言中的作用 表示程序设计语言上下文结构的依赖性 对于赋值号，其左边和右边的标识符在操作
13、的时候需要提供的属性不同，这时候就要跟踪标识符的继承属性。如果在赋值号左边，则需要地址，右边则需要值。 虽然我们总是可以只用综合属性来改写语法制导定义，但是使用带有继承属性的属性文法有时更为自然。,继承属性的例子,D,L,T,real id1,id2,id3,real,id3,L,.in=real,.in=real,.type=real,id2,L,.in=real,id1,语法制导翻译,基于属性文法的处理过程通常是： 对符号串进行语法分析， 构造语法分析树 根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。 这种由源程序的语法结构驱动的处理办法就是语法制导翻译法。 在某些情况下，在进
14、行语法分析的同时完成语义规则的计算而无须明显地构造语法树或构造属性之间的依赖图。（一遍处理，L-属性文法）,输入符号串,分析树,依赖图,语义规格的 计算顺序,依赖图,依赖图是有向图 表示了分析树中各节点属性间的依赖关系。其中属性包括继承属性和综合属性 表示了节点属性的计算先后顺序。如果分析树中某个节点的属性b依赖于属性c，那么在该节点处b的语义规则必须在c的语义规则之后计算。 依赖图的构造方法 为每个包括过程调用的语义规则引入一个虚综合属性b，把每条语义规则都变成b=f(c1,c2,.,ck)的形式 依赖图的每个结点表示一个属性 边表示属性间的依赖关系。如果属性b依赖于属性c，那么从c到b就有
15、一条有向边,依赖图举例,D,L,T,real,id3,L,id2,L,id1,type,in,y,in,y,in,y,entry,entry,entry,1,2,3,4,5,6,7,8,9,10,如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的,属性的计算顺序,无环有向图的拓扑排序 无环有向图中节点m1,m2,mk的拓扑排序是：若mimj是从mi到mj的边，那么在此排序中mi先于mj 依赖图的任何拓扑排序都给出了一个分析树中各节点语义规则计算的正确顺序，即在计算f之前，语义规则b=f(c1,c2,.,ck)中的依赖属性c1,c2,.,ck都是已知的 属性文法所说明的翻译可以按
16、照下面的步骤进行 最基本的文法用于构造输入串的分析树 用前面的方法构造依赖图 从依赖图的拓扑排序可以得到语义规则的计算顺序 按该顺序计算语义规则即可得到输入串的翻译,属性文法计算顺序举例,a4 := real a5 := a4 addtype(id3.entry, a5) a7 := a5 addtype(id2.entry, a7) a9 := a7 addtype(id1.entry, a9),计算语义规则的方法,分析树法： 在编译时，这种方法从分析树所构成的依赖图的拓扑排序中得到语义规则的计算顺序。 如果分析树的依赖图中有环路，这种方法将失败 基于规则的方法 对于每一个产生式，计算该产生式所关联的属性的顺序在编译器构造时已经预先确定好了 忽略规则的方法 选择计算顺序时不考虑语义规则。如果翻译是在语法分析过程中进行的，那么计算顺序的选择就由语法分析方
