1、属性文法和语法制导翻译,授课：胡静,语义分析面向语法的定义,所处位置,分析技术,LL分析方法计算最左推导自顶向下的构造推导LL的分析表指出要对最左边的非终结符进行扩展时，所选的产生式。LR分析方法计算最右推导自底向上的构造推导使用LR的状态集合和符号栈LR分析表指出针对每一个状态，采用何种动作（移进/归约），并且下一个转入的状态是什么。我们可以使用这些技术来构造 AST,AST 复习,推导：使用的产生式的序列S E + S 1 + S 1 + E 1 + 2分析树：描述推导的图并不能表示产生式使用的顺序抽象语法树 (AST)：从分析树中去掉了那些不必要的信息。,潜在的AST构造,LL/LR分析
2、技术都潜在的构造出了AST分析树在推导过程中可以得到LL parsing: 应用产生式的序列潜在的描述了AST LR parsing：应用归约的序列潜在的描述了AST我们希望从分析过程中明确的创建AST：在分析器中添加一定的代码来明确的创建AST,AST 的构造,LL分析: 对非终结符进行扩展 Example:,LR分析中AST的构造,问题,代码的结构混乱：进行语法分析的代码和构造AST的代码混在一起语法分析器的生成器：产生的语法分析器需要包含AST的构造代码如何使用语法分析器的自动生成器构造不同的AST数据结构？我们需要在分析阶段同时的进行其他的动作。比如，语义检查,Syntax-Direc
3、ted Definition,解决方法: syntax-directed definition扩展每个文法的产生式，使得每个产生式都和语义动作（代码）相关联：S E+S action 语法分析器的生成器将这些代码加入到生成的语法分析器中。当使用产生式进行归约时，对应的动作就会被执行。,语义动作,动作：用程序设计语言编写的代码和语法分析器的生成器的程序设计语言相同例如：Yacc = actions written in CCUP = actions written in Java动作需要访问语法分析栈！语法分析器的生成器将状态栈进行扩展，用那些用户定义的结构（分析树）去替换原先的符号动作代码应该
4、可以引用状态需要一套命名机制,命名机制,我们需要对那些在语义动作代码中可能用到的文法的符号进行命名。需要分别引用出现在不同地方的同一个非终结符号E E1 + E2需要对左边/右边的符号进行区别E0 E + E,命名机制：Yacc,Yacc:使用关键字: $1引用右边的第一个符号，$2引用右边的第二个符号，以此类推关键字$引用左边的非终结符Yacc的例子expr := expr PLUS expr $ = $1 + $3; ,构造 AST,使用语义动作构造ASTAST在分析过程中自底向上的构造,例子,分析栈保存了每个非终结符的值,可以使用syntax-directed定义在语法分析的时候进行语义
5、检查例如，类型检查好处：有效率一个简单的编译过程可以完成多个任务坏处：代码结构混乱将语法分析和语义检查过程混在一起当AST结构改变的时候进行检查只能是自底向上的过程中,类型声明的例子,值的传递,当创建AST的时候，也要把值属性进行传递。,另一个例子,值的传递,值要两个方向传递：自顶向下和自底向上,构造方法,从语义检查阶段可以单独的构造AST反复检查AST并且进行语义检查 (或其他动作)只有当树被建立起来并且他的结构是稳定的时候才能做。这个过程有更多的灵活性，不容易出现错误,属性文法,属性文法,虽然形式语义学的研究已经取得了许多重大进展，但目前在实际应用中比较流行的语义描述和语义处理的方法主要还
6、是属性文法和语法制导翻译。本章研究内容：上下文无关文法所产生的语言的翻译。把属性附加到代表语法结构的文法符号上，可以将语义信息和程序设计语言的结构联系起来。属性的值是用与文法产生式相关联的“语义规则”来计算的。涉及的概念语法制导定义：关于语言翻译的高层次规格说明，隐蔽了具体实现细节，不显式的说明翻译发生的顺序(属性文法)翻译模式：指明了语义规则的计算顺序，说明实现细节。,语法制导翻译在编译器中的位置,语义规则的计算完成的工作生成代码在符号表中保存信息发出错误信息对输入符号串翻译的过程就是对语义规则求值的过程L-属性：包含了所有不必显式构造分析树即可完成的翻译,输入符号串,依赖图,语义规格的计算
7、顺序,属性文法,是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”。属性代表与文法符号相关的信息，如类型、值、代码序列、符号表内容属性可以代表任何对象：字符串，数组，类型，内存单元或其他对象语法制导定义=文法+符号的相关属性集属性分为两个子集：综合属性、继承属性如果把文法符号的结点看成记录，包含若干存储信息的域，那么属性就相当于域的名字,属性文法,分析树节点上属性值由产生式的语义规则来定义综合属性值：通过分析树中其子节点的属性值计算出来的继承属性值：由该节点的兄弟节点及父节点的属性值计算出来的依赖图语义规则建立了属性间的依赖关系，这种关系用图来表示就是依赖图依赖
8、图表示了语义规则的计算顺序注释分析数每个节点都有属性值的分析树叫做注释分析树计算节点属性的过程称为注释或者装饰分析树,属性文法,在语法制导定义中，每个产生式A都有一个形如b=f(c1,c2,.,ck)的语义规则集合与之相关联，其中f是函数，并且满足下面条件之一b是A的一个综合属性，且c1,c2,.,ck是该产生式文法符号的属性b是产生式右部某个文法符号的一个继承属性，且c1,c2,.,ck也是该产生式文法符号的属性在这两种情况下，我们说属性b依赖于c1,c2,.,ck 。特别要强调的是：终结符只有综合属性，它们由词法分析器提供；非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作
9、为属性计算前的初始值。,关于属性文法的说明,通常，这种函数的被写为表达式。其他的语义规则被写为过程调用或者程序段定义产生式左部非终结符的虚综合属性值一般说来，对于出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内“封装”属性的依赖性。出现在产生式左边的继承属性和出现在产生式右部的综合属性不由所给产生式的属性计算规则进行计算，它们由其他产生式的属性规则计算或由属性计算器的参数提供。,继承属性和综合属性的计算举例,对于产生式ABC来讲直观上来讲，这个产生式可以计算A的综合属性、B和C的继承属性。那
10、么对于A的继承属性，可能需要根据某个类似于XA的产生式求的。同样的B和C的综合属性可能需要根据某个类似于B，以及C 的产生式求的。,属性文法举例,综合属性,S属性定义在语法树中，一个结点的综合属性的值由其子结点的属性值决定。仅使用综合属性的属性文法称为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=1
11、9,.val=5,继承属性,在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。继承属性在程序设计语言中的作用表示程序设计语言上下文结构的依赖性对于赋值号，其左边和右边的标识符在操作的时候需要提供的属性不同，这时候就要跟踪标识符的继承属性。如果在赋值号左边，则需要地址，右边则需要值。虽然我们总是可以只用综合属性来改写语法制导定义，但是使用带有继承属性的属性文法有时更为自然。,继承属性的例子,D,L,T,real id1,id2,id3,real,id3,L,.in=real,.in=real,.type=real,id2,L,.in=real,id1,语法制导翻译,基于
12、属性文法的处理过程通常是：对符号串进行语法分析，构造语法分析树根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。这种由源程序的语法结构驱动的处理办法就是语法制导翻译法。在某些情况下，在进行语法分析的同时完成语义规则的计算而无须明显地构造语法树或构造属性之间的依赖图。,依赖图,依赖图是有向图表示了分析树中各节点属性间的依赖关系。其中属性包括继承属性和综合属性表示了节点属性的计算先后顺序。如果分析树中某个节点的属性b依赖于属性c，那么在该节点处b的语义规则必须在c的语义规则之后计算。依赖图的构造方法为每个包括过程调用的语义规则引入一个虚综合属性b，把每条语义规则都变成b=f(c1,c2,.
13、,ck)的形式依赖图的每个结点表示一个属性边表示属性间的依赖关系。如果属性b依赖于属性c，那么从c到b就有一条有向边,依赖图举例,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之前，语义规
14、则b=f(c1,c2,.,ck)中的依赖属性c1,c2,.,ck都是已知的属性文法所说明的翻译可以按照下面的步骤进行最基本的文法用于构造输入串的分析树用前面的方法构造依赖图从依赖图的拓扑排序可以得到语义规则的计算顺序按该顺序计算语义规则即可得到输入串的翻译,属性文法计算顺序举例,a4 := reala5 := a4addtype(id3.entry, a5)a7 := a5addtype(id2.entry, a7)a9 := a7addtype(id1.entry, a9),计算语义规则的方法,分析树法：在编译时，这种方法从分析树所构成的依赖图的拓扑排序中得到语义规则的计算顺序。如果分析树的
15、依赖图中有环路，这种方法将失败基于规则的方法对于每一个产生式，计算该产生式所关联的属性的顺序在编译器构造时已经预先确定好了忽略规则的方法选择计算顺序时不考虑语义规则。如果翻译是在语法分析过程中进行的，那么计算顺序的选择就由语法分析方法来确定。后两种方法在编译时都不必显式的构造依赖图,树遍历的属性计算方法,通过树遍历计算属性值的方法都假设语法树已经建立，并且数中已带有开始符号的继承属性和终结符的综合属性。最常用的遍历方法是深度优先，从左到右的遍历方法只要文法的属性是非循环定义的，则每次扫描至少有一个属性值被计算出来。如果语法树有n个结点（因此最多有O(n)个属性），最坏的情况整个遍历需要O(n2
16、)时间。,树遍历的举例,S有继承属性a，综合属性bX有继承属性c，综合属性dY有继承属性e，综合属性fZ有继承属性h，综合属性g假设S.a的初始值为0,一遍扫描的处理方法,在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树。一遍扫描的处理方法与语法分析器密切相关的因素：所采用的语法分析方法属性的计算顺序L-属性文法可用于一遍扫描的自顶向下分析，而S-属性文法适合于一遍扫描的自底向上分析。此时的语法制导翻译可理解为：直观上说为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则在自顶向下语法分析中，若一个产生式匹配输入串成功在自底向
17、上语法分析中，当一个产生式被用于进行归约时,语法树的构造,用语法树作为中间表示，可以把翻译从语法分析中分离出来语法树是分析树的压缩形式，去掉了那些对翻译不必要的信息，对表示语言的结构很有用。表达式的语法树的构造为每个运算符和运算对象建立节点来为子表达式构造子树。运算符节点的字节点分别是表示该运算符各运算对象的子表达式组成的子树的根,表达式语法树的构造方法,运算符节点（用记录实现，也可以用对象实现）一个域标识运算符，其余域包含指向运算对象的指针将运算符称为该节点的标记构造的过程（方法）mknode(op, left, right)：建立一个标记为op的运算符节点，其中两个域left和right是
18、指向其左右运算对象的指针mkleaf(id,entry)：建立标记为id的标识符节点，entry是指向该标识符在标识符表中的相应表项的指针mkleaf(num,value)：建立标记为num的数节点，域val保存该数的值。,抽象语法树的例子,表达式的无环有向图,表达式的无环有向图（dag）可以识别表达式中的公共子表达式无环有向图的组成叶子节点：表达式中的操作数（操作符的运算对象）内部节点：表达式中的操作符（运算符）子树：表达式中的每一个子表达式和语法树的区别：代表公共子表达式的节点具有多个“父结点”,S属性文法的自底向上计算,S-属性文法的特点,S-属性文法，只有综合属性也就是说产生式左边的文
19、法的综合属性要根据产生式右边符号的综合属性来进行计算。适用于那些需要类似于表达式，需要计算结果的文法。综合属性可以在分数输入符号串的同时由自底向上的分析器来计算。分析器保存与栈中文法符号有关的综合属性每当归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。,S-属性文法翻译器的实现,S-属性文法的翻译器通常可借助于LR分析器实现。在自底向上的分析方法中，我们使用栈来存放已经分析过了的子树，现在我们可以在分析栈中使用一个附加域来存放综合属性值。假设综合属性是刚好在每次归约前计算的,状态栈,符号栈,val,top,AXYZ,S-属性文法计算举例,我们要控制两个变量top和ntop。当
20、右边带有r个符号的产生式被归约时，执行相应的代码段之前，先将top-r+1赋给ntop，在代码段被执行之后将ntop的值赋给top,代码段刚刚好在归约前执行。这是利用归约提供一个“挂钩”，使得用户把一个语义动作与一个产生式联系起来。翻译模式可以提供一种与分析器相互穿插动作的描述方法。,L-属性文法和自顶向下翻译,L属性文法定义,在语法分析过程中进行翻译时，属性的计算顺序将与分析方法建立分析树节点的顺序相关。有一种能够描述许多自顶向下和自底向上翻译方法的自然顺序深度优先顺序。L属性定义一个属性文法是L-属性文法，如果对于每一个产生式AX1X2Xn，其右部符号Xj(1jn)的每个属性值仅依赖于下列
21、属性产生式中Xj左边的符号X1X2Xj-1的属性A的继承属性L属性的计算可以使用深度优先顺序来计算LL(1)的分析过程，从概念上说可以看成是深度优先建立语法树的过程,L属性文法的反例,翻译模式,翻译模式给出了使用语义规则进行计算的次序，这样就可以把某些细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里也称语义动作），用“”括起来，插入到产生式右部合适的位置上。翻译模式给出了使用语义规则进行计算的顺序。,翻译模式举例,ETRRaddop T print(addop.lexeme) R1 | Tnum print(num.val),E,R,T,9,print(9),-,T,print
22、(-),R,5,print(5),+,T,print(+),2,print(2),R,9-5+2按深度优先遍历之后95-2+,L-属性定义的翻译模式,设计L属性定义的翻译模式需要注意以下几点：基本设计原则：当某个动作引用一个属性时，这个属性是可用的。也就是说，一个动作不会引起一个没有计算出来的属性。只有综合属性时为每一个语义规则建立一个赋值动作，并把该动作放在产生式右部的末尾TT1*F T.val := T1.val F.valTT1*F T.val := T1.val F.val,L-属性定义的翻译模式,同时存在综合属性和继承属性时：产生式右部符号的继承属性必须在这个符号以前的动作中计算出来
23、一个动作不能引用该动作右部符号的综合属性产生式左部非终结符的综合属性只有在其引用的所有属性值都计算出来以后才能计算。计算该属性的动作通常放在产生式右部的末尾。下面的翻译模式不符合上面的定义：SA1A2 A1.in := 1; A2.in := 2Aaprint(A.in)按深度优先遍历时，要打印第二个产生式里的继承属性A.in时，该属性还没有被定义。,L-属性文法举例,SB.ps := 10 B S.ht := B.htBB1.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
24、 := shrink(B.ps) B2 B.ht := disp(B1.ht, B2.ht)Btext B.ht := text.h B.ps,L-属性文法的自顶向下翻译,在预测分析的过程中实现L-属性文法为了明显的看出动作和属性计算发生的属性，我们使用翻译模式而不是属性文法。为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。将前面讲过的方法扩充，从翻译模式中消除左递归（LL(1)文法构造的步骤），这种方法也适用于带有综合属性的翻译模式。,举例,EE1+T E.val := E1.val + T.valEE1-T E.val := E1.val - T.valET E.val :=
25、T.valT(E) T.val := E.valTnum T.val := num.val,ETR.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.iT( E ) T.val := E.valTnum T.val := num.val,9-5+2,R,-,T,num,R,E,T,num,R,+,T,num,val=9,val=9,i=9,val=5,val=5,i=4,val=2,val=2,i=6,s=6,val=6
26、,一个符号继承属性必须由出现这个符号之前的动作来计算，产生式左边非终结符的综合属性必须在它所依赖的所有属性都计算出来之后才能计算,消除左递归的一般方法,假设有如下的翻译模式AA1Y A.a := g(A1.a, Y.y)AX A.a := f(X.x)每个文法符号都有综合属性，g和f是任意函数。文法可以转换为：AXRRYR | 考虑语义动作，变为：AXR.i := f(X.x) RA.a := R.sRYR1.i := g(R.i, Y.y) R1R.s := R1.sR R.s := R.i,递归下降翻译器的设计,为每个非终结符A构造一个函数A的每个继承属性均对应该函数的一个形式参数，其返回
27、值为A的综合属性的值（可能是一个记录、一个指针或者使用传地址参数的传递机制）非终结符A的代码会根据当前的输入决定使用哪个产生式与每个产生式有关的代码执行如下动作：从左到右考虑产生式右部的记号、非终结符及语义动作对于带有综合属性x的终结符X，把x的值保持在X.x中，然后产生一个匹配X的调用，并继续输入对于非终结符B，产生一个右部带有函数调用的赋值语句c=B(b1,b2,.bk)，其中b1,b2,.bk是代表B的继承属性变量，c是代表B的综合属性的变量对于每个动作，将其代码复制到语法分析器，并把对属性的引用改为对相应变量的引用,自底向上计算继承属性,删除嵌入在翻译模式中的动作在自顶向下分析中我们可
28、以在产生式右部的任何地方嵌入动作在自底向上翻译方法中，需要把所有的翻译动作都放在产生式右部的末尾在基础文法中加入新的形如M的产生式，其中M为标记非终结符。将每个嵌入动作用不同的标记非终结符M来代替，并把该动作放在此空产生式的末端例如ETRR+T print(+) R | -T print(-) R | T num print(num.val) 转化为ETRR+TMR | -TNR | M print(+) N print(-),自底向上计算继承属性,转换后的翻译模式和原翻译模式比较用额外的节点表示动作，但动作的执行顺序是一样的转换后的翻译模式中，动作都在产生式的末尾，可以在自底向上的分析过程中
29、刚好在产生式右部被归约之前执行,分析栈中的继承属性,对于继承属性是由复制规则定义的产生式自底向上语法分析器对产生式AXY的归约就是从分析栈顶移走X和Y并用A来代替它们。假设X有一个综合属性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
30、 addtype(id.entry, L.in)Lidaddtype(id.entry, L.in),int p,q,r,r,L,int,L,D,T,q,L,p,in,type,in,in,所用产生式,栈,输入串,-,int p,q,r,int,p,q,r,T,p,q,r,Tint,Tp,q,r,TL,q,r,Tint,TL,q,r,TL,q,r,TL,r,LL,id,TL,r,TL,r,TL,LL,id,D,DTL,模拟继承属性的计算,使用自底向上的方法计算继承属性，必须要可以预测属性值在栈中的位置。,模拟继承属性的计算,模拟由复制规则计算的继承属性引入一个新的标记非终结符M，用M的继承属性
31、和综合属性来传递后面非终结符需要复制的继承属性。模拟不是复制规则的语义规则（计算函数）也可以加入新的标记非终结符，用复制规则继承前面非终结符的属性值，其综合属性被置为用计算函数进行计算,带有继承属性的自底向上语法分析和翻译,假设条件每个非终结符A都有一个继承属性A.i，每个文法符号X都有一个综合属性X.s。对于终结符，其综合属性是词法分析器返回的词法值。对于每个产生式AX1X2Xn ，引入n个新的标记非终结符M1, ,Mn并用A M1X1 MnXn代替该产生式如果继承属性A.i存在，则其值可以在val数组紧贴M1下面的地方找到。继承属性将和标记非终结符Mj联系在一起，属性值Xj.i在Mj处完成
32、计算，而且该计算是在归约Xj之前进行的,带有继承属性的自底向上语法分析和翻译,计算方法当归约标记非终结符Mj时，可以从栈顶依次找到需要使用的属性值，A.i 在valtop 2j +2的位置上，X1.i在valtop 2j +3的位置上， X1.s在valtop 2j +4的位置上得到的Mj.s的值实际上是Xj.i的值，放在valtop+1的位置上归约非标记符号，只需要计算综合属性A.s，因为A.i已经计算出来了，放在A要插入的那个位置之下。算法简化（减少标记符号数目，避免左递归）如果Xj没有继承属性，就不需要Mj了。如果X1.i存在，但是它是由复制规则X1.i=A.i计算的，那么可以省略M1,作业,下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：SL.L | LLLB | BB0 | 1试设计求S.val的属性文法，其中，已知B的综合属性c，给出由B产生的二进位的结果值。,作业,设下列文法生成变量的类型说明Lid LL,id L | :TTinteger | real构造一个翻译模式，把每个标识符的类型存入符号表从上面得到的翻译模式，构造一个预测翻译器,Thanks for your time!Questions & Answers,
