编译原理第六章属性文法和语法制导翻译

知识点：语法制导定义，知识点：语法制导定义，S-属性定义及其自底向上计算属性，L-属性定义，自顶向下的翻译，自底向上计算继承属性。深刻理解：属性，综合属性，继承属性，依赖图，计算顺序，语法树，语法制导定义，S-属性文法定义，L-属性文法定义，翻译模式。熟练掌握：对于已知文法G和翻译任务，构造其L-属性定义，将其改造成适于自顶向下分析或自底向上分析的翻译模式。属性文法（属性翻译文法SL4语法制导翻译：通过给语法树上各个符号赋予一定的含义并且将各个符号进行有结构的连接，可以形成语言的具体语句的含义。这给予我们以启示：可以通过扩充文法，在文法符号上附着某些语义信息，并在这些语义信息间建立相互计算关系，从而在语法分析的同时进行语义分析。由于这种分析是在语法分析的控制下进行的，故称为语法制导翻译。（1）1例61例618文规则规则相关的属性等式/相关的属性等式/

E.val1.21.2综合属性：用于自下而上传递信息；在语法树中，一个结点的综合属性由其子结点的属性值确定，因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S-属性文法。文文例6.29例63属性文法为例61中的属性文法，输入 (n是换行符L ELEnE+nE+TTTTFdigit*Fdigit*FdigitdigitdigitTTTL1Addtype(idAddtype(idD

real

属性的计算规则：设有产生式定义b=属性的计算规则：设有产生式定义b=f（c1，c2，……，ck）fb是A的一个综合属性，并且c1，c2，……，ck是产生式右边文法符号的属性。或者：c1，c2，……，ck是A或产生式右边任何文法符号的属性2语法树中，语法树中，属性文法（属性翻译文法⼀抽象语法树 Syntax属性计算规则中仅能使用相应产生式中文法符号的属性（封装性）基于属性文法的处理过程通常是：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。输入 分析 依赖 语义规则的计图61在具体实现时，一般都是随语法分析的进展，识别出一个语法结构，就对它的语义进行分析和翻译。也就是语义分析是伴随语法分析的过程进行。2.2 ）。for语法树中每一结点nfor结点n的文法符号的每一个属性a为afor语法树中每一个结点nfor结点nb＝f（c1，c2，，ck)dofori＝1tokdo从结点ci到结点b注意：如果属性文法不存在属性之间循环的依赖关系，那么称该文法为良定义bCL.in=TL1Addtype(idAddtype(idc一个有向非循环图的拓扑排序是图中结点的任何顺序m1,m2,…,mk，果mi→mj是mi到mj的一条边，那么在序列中mi必须出现在mj若依赖图中无环（属性之间没有循环依赖关系），则存在一个拓扑排序，它就是属性值的计算顺序。分析树法：输入串→分析树→依赖图→则，确定属性值的计算顺序 ）确定，表面上与语义规则无关。实际上，要求限制语法制导定义，使属性值的计算顺序能和语法分析过程同步进行。例65例65EEval=E1val+E2E1E2例64中带继承属性文法对于realDTL4in63,in78,2in9id112）且树中已带有开始符号的继承属性和终结符的综合属性；方法：深度优先，从左到右进行（也是一种分析树的方法）while还有未被计算的属性doVisitNode(S)//S是开始符号procedureVisitNode(N：Node)；ifN∈VNthen假设它的产生式N→X1fori=1tomdoifXi∈VNthen例子：6.6行这些语义规则。在自上而下的分析中就是在产生式匹配输入串成2.5抽象语法树产生式S→if产生式S→ifBthenS1elseif-then- BS1

Syntaxs-属性文法：只含有综合属性s-属性文法通常借助于LR "A→ b=f（c1，c2，b是的综合属性，(≤ ik)是a值自向的分析过程中，每步归约时，计算相应的属性值。AST 语法树的抽象形式，也称作语法结构树，或结构树。抽象语法树是常用的一种中间表示形式。AST 语法树的抽象形式，也称作语法结构树，或结构树。抽象语法树是常用的一种中间表示形式。在抽象语法树中，运算符号和关键字都不在叶结点产生 语义规 Efi Enptr:=mknode('+',E1nptr,T 算符号结点，标号是op，left和rightEfiE1- Enptr:=mknode('-',E1nptr,T 2）mkleaf(id，entry)Efi Enptr:=T 由标号id标识，entryTfi Tnptr:=E 3）mkleaf（num，val）Tfi Tnptr:=mkleaf(id,id 标号为num，域valTfi Tnptr:=mkleaf(num,num + num4 toentryctoentryaa-4+c属性文法（属性翻译文法SLZZYYXX Lfi EfiE+Tval[ntop] Lfi EfiE+Tval[ntop]=val[top-2]+val[top]EfiTTfi Tfi输入3*5+4n*5+4n*5+4n*5+4n T* T*val-3 3-3-5FFfi 15Ffi 15- 15-4 15-4T→ 19 Aa╱∣XxYyZZZYYXXAZZYYXXAA定义式A.a=f（Xx，Yy，Zz）（抽象）val[ntop]＝f（val[top-2]，val[top-1]，val[top]）（具体可执行代码）。在执行代码段之前执行：ntop＝top-r+1（r是句柄的长度）总结：采用自底向上分析，例如LR，首先给出S-属性定义，然后，把S-属性定归约处有一个“挂钩”，语义分析和翻译的代码段（语义子程序）就挂在这个钩子上。随着语法分析的进行，归约前调用相应的语义子程序,完成翻译的任务。属性文法（属性翻译文法属性文法（属性翻译文法SLL在语法分析过程中进行语义分析和翻译，属性的计算顺序受到语法分析建立分析树结点顺序的限制。一种自然的计算属性的顺序是按深度优先分析结点的顺序，它适应多种自底向上和自顶向下的翻译方法。L-属性文法可用按深度优先顺序计算属性值。如果"A→X1X2…Xn˛P，其每一个语义规则中的每一个属性都是一个综合属性，或是Xj(1j£n)的一个继承属性a．产生式中Xj的左边符号X1，X2，…Xj-1的属性；．A每⼀个S-属性文法都是L-一个非L-L.i4.21号相对应，语义规则或语义动作用花括号｛｝括起来，可以入到产生式右部的任何合适的位置上。这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过程中何时执行语义动作。翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。例一个简单的翻译模式R→addopT{print(addoplexeme)}R1| {print(numER print(‘-5 +T 9-5+2翻译成后缀式95- 2 52）条件：属性文法是L-保证语义动作不 还没有计算的属性值为每一个语义规则建立一个包含赋值的动作，并把这个动作式右边的末尾。例如：T→T1*F Tval=T1val*Fval2）条件：属性文法是L-保证语义动作不 还没有计算的属性值为每一个语义规则建立一个包含赋值的动作，并把这个动作式右边的末尾。例如：T→T1*F Tval=T1val*FvalT→T1*F{Tval=T1val*Fval}既有综合属性又有继承属性 产生式左边非终结符的综合属性只有在它 的所有属性都计算出来以EfiE1+T｛Eval:=E1val+Tval}EfiE1-T｛Eval:=E1val-Tval｝EfiT {E.val:=Tval}Tfi(E) ｛Tval:=Eval｝Tfinum｛Tval:=numval}图 带左递归的文法的翻译模才能计算。计算这种属性的动作通常才能计算。计算这种属性的动作通常可放在产生式右端的末尾E→TE→T{R.i=T.val}R｛R.s=R.s}R｛R.s=R.s}R→ε｛R.sT→num{T.val R R + 计算表达式9- R.s=R1εA→A1Y｛Aa:=g(A1A→X （6每一个文法符号都有一个综合属性，用相应的小写字母表示，g和fA→XR→Y A→X｛R.i:=f(X.x)}R｛A.a:=R→Y｛R1.i:=g（R.i，Y.y）}R1｛Rs:=R1.s}R→ε｛R.s:=R 经过转换的翻译模式与图6.14中一样,使用R的继承属性i和综合属性s。（6.2）（6.4） XR.i=f(X.x) Y1 A→X A→X｛Ri:=f(X R｛A.a:=R.R→Y｛R1i:=g（Ri，Yy）}R1｛Rs:=R1s}R→ε｛Rs:=Ri}EfiE1+T{Enptr=mknode(´+´,E1nptr,Tnptr)}EfiE1-T{Enptr=mknode(´-´,E1nptr,Tnptr)}EfiT{Enptr=Tnptr}E→T{Ri=Tnptr}R｛Enptr=RT｛R1i=mknode('+',Ri,Tnptr)}R1｛Rs=R1s}T｛R1i=mknode('-',Ri,Tnptr)}R1{Rs=R1s}R→ε｛Rs=Ri}T→(E){Tnptr=Enptr}T→id{Tnptr=mkleaf(id,identry)}6算法6.1算法6.1输入：一个带有适合递归下降分析的基础文法的语法制导翻译模式。输出：一个语法制导翻译器的代码。"˛N,建立⼀个可递归调⽤的函数过程。为设置⼀个形式参数，函数的返回值是函数过程A的代码（指⽤符号形式表⽰的数据和程序）要根据当前的输入符号来决定使⽤哪⼀个产⽣式。与每⼀个产⽣式有关的代码，从左到右根椐产⽣式右部是终结符、非终结符号还是语义动作，分别：对于带有综合属性x的终结符X，x存放在代表X.x的变量中，匹配X，并继续读入⼀个输入符号。对于B˛VN，编写⼀个赋值语句c=B（b1,b2, 其中，b1，b2， 对于每个动作，动作的代码抄进翻译器中，⽤代表属性的变量来代替对属性的每⼀次引⽤。ET

T

+ T +num

--toentryfortoentryfor

属性文法（属性翻译文法属性文法（属性翻译文法SL例:例: ｛R1．i:=mkn