编译原理语法制导翻译

第五章语法制导翻译学习重点语法制导定义概念利用语法制导定义构造语法树S-属性定义、L-属性定义自顶向下计算属性自底向上计算属性递归方法计算属性内存分配概述语法制导定义翻译模式“编程语言的翻译根据语法进行”“属性”，attribute每个语法符号与若干属性相关联翻译——指定属性的相互依赖关系语义规则，semanticrule语言规则的执行反映属性的相互关系5.1语法制导定义扩充CFG语法符号属性——语法树节点，记录域产生式语义规则——语法树节点，用于计算属性属性类型综合，synthesized，根据孩子节点属性计算继承，inherited，由父、兄弟节点属性计算依赖图，dependencygraph注释语法树：节点属性值计算完毕annotatedparsetree,annotating,decorating5.1.1语法制导定义的形式每个产生式A与一组语义规则相关联，每个语义规则具有如下形式：b=f(c1,c2,…,ck)，两种可能情况b为A的综合属性，c1,c2,…,ck为A、中语法符号的属性b为中某个符号的继承属性，c1,c2,…,ck为A、中语法符号的属性b依赖c1,c2,…,ck属性文法：扩充了语法制导定义，无副作用例5.1digit.lexval：终结符只有综合属性，由词法分析器提供开始符号通常没有继承属性LEnprint(E.val)EE1+TE.val=E1.val+T.valETE.val=T.valTT1*FT.val=T1.val*F.valTFT.val=F.valF(E)F.val=E.valFdigitF.val=digit.lexval产生式语义规则5.1.2综合属性只有综合属性：S-属性定义语法树自底向上计算属性例55.1.3继承属性表达程序语言结构在上下文中的相互依赖关系更加自然、方便例5.3变量定义realid1,id2,id3;DTLL.in=T.typeTintT.type=integerTrealT.type=realLL1,idL1.in=L.inaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in)产生式语义规则例5.3（续）自顶向下计算5.1.4依赖图属性b依赖属性c，则b应在c之后计算有向图表示这种依赖关系——依赖图构造方法：for语法树中每个节点ndoforn的每个语法符号的属性ado在依赖图中为a构造一个节点for语法树中每个节点ndoforn使用的产生式的每个语义规则b=f(c1,c2,…,ck)dofori=1tokdo构造从ci到b的一条边例5.4EE1+E2,E.val=E1.val+E2.val例5.55.1.5计算顺序拓扑排序，计算顺序满足依赖关系m1,m2,…,mk，存在边mimjij计算b=(c1,c2,…,ck)时，属性值c1,c2,…,ck已经计算出来文法语法树依赖图拓扑排序语义规则计算顺序输入串翻译例5.6例5.5依赖图的边：小数字大数字按编号排列满足要求的拓扑排序a4=real;a5=real;addtype(id3.entry,a5);a7=a5;addtype(id2.entry,a7);a9=a7;addtype(id1.entry,a9);5.2构造语法树作为中间表示形式——分离分析与翻译在进行语法分析的同时进行翻译存在缺陷：适合分析的文法可能未反映自然的语言结构分析顺序可能与翻译顺序不一致利用语法制导翻译方法来构造语法树5.2.1语法树（抽象）语法树，压缩形式关键字和运算符均在内部节点链式结构会被压缩语法树压缩例5.2.2表达式语法树的构造与表达式翻译为后缀形式类似数据结构：语法树每个节点用一个记录表示运算符节点记录格式：{运算符指向运算对象节点1的指针执行运算对象节点2的指针…}辅助函数mknode(op,left,right)：为运算符op创建语法树中节点，标记（运算符）为op，运算对象节点指针left和rightmkleaf(id,entry)：为标识符创建语法树节点，标记为id，另一个域为符号表项指针entrymkleaf(num,val)：为运算数创建节点，标记为num，另一个域为数值例5.7a-4+c的语法树(1)p1=mkleaf(id,entry_a);(4)p4=mkleaf(id,entry_c);(2)p2=mkleaf(num,4);(5)p5=mknode(‘+’,p3,p4);(3)p3=mknode(‘-’,p1,p2);p1p2p3p4p55.2.3构造语法树的语法制导定义例5.8EE1+TE.nptr=mknode(“+”,E1.nptr,T.nptr)EE1-TE.nptr=mknode(“-”,E1.nptr,T.nptr)ETE.nptr=T.nptrT(E)T.nptr=E.nptrTidT.nptr=mkleaf(id,id.lexval)TnumT.nptr=mkleaf(num,num.val)产生式语义规则例5.8（续）5.2.4用有向无环图表示表达式公共子表达式用公共节点表示可能出现一个节点有多个“父节点”的情况构造方法类似语法树构造构造节点前检查是否已构造相同节点图5.9a+a*(b-c)+(b-c)*d(1)p1=mkleaf(id,a);(8)p8=mkleaf(id,b)(=p3);(2)p2=mkleaf(id,a)(=p1);(9)p9=mkleaf(id,c)(=p4);(3)p3=mkleaf(id,b);(10)p10=mknode(‘-’,p8,p9)(=p5);(4)p4=mkleaf(id,c);(11)p11=mkleaf(id,d);(5)p5=mknode(‘-’,p3,p4);(12)p12=mknode(‘*’,p10,p11);(6)p6=mknode(‘*’,p2,p5);(13)p13=mknode(‘+’,p7,p12);(6)p7=mknode(‘+’,p1,p6);例5.9（续）p1,p2p3,p8p4,p9p5,p10p6p7p11p12p13DAG的实现i=i+10算法5.1构造DAG节点输入：标记（操作符）op，节点l，节点r输出：具有op,l,r形式的节点方法：在创建节点前，搜索节点数组寻找标记为op，左孩子l，右孩子r的节点m若找到，直接返回m否则，创建新节点，标记为op，左孩子为l，右孩子为r，将该节点返回搜索方法：hash技术…TinyC中的语法树typedefenum{StmtK,ExpK}NodeKind;typedefenum{IfK,RepeatK,AssignK,ReadK,WriteK}StmtKind;typedefenum{OpK,ConstK,IdK}ExpKind;typedefenum{Void,Integer,Boolean}ExpType;#defineMAXCHILDREN3typedefstructtreeNode{structtreeNode*child[MAXCHILDREN];structtreeNode*sibling;intlineno;NodeKindnodekind;union{StmtKindstmt;ExpKindexp;}kind;union{TokenTypeop;intval;char*name;}attr;ExpTypetype;/*fortypecheckingofexps*/}TreeNode;TinyC中的语法树——表达式TreeNode*simple_exp(void){TreeNode*t=term();while((token==PLUS)||(token==MINUS)){TreeNode*p=newExpNode(OpK);if(p!=NULL){p-child[0]=t;p-attr.op=token;t=p;match(token);t-child[1]=term();}}returnt;}TinyC中的语法树——IFTreeNode*if_stmt(void){TreeNode*t=newStmtNode(IfK);match(IF);if(t!=NULL)t-child[0]=exp();match(THEN);if(t!=NULL)t-child[1]=stmt_sequence();if(token==ELSE){match(ELSE);if(t!=NULL)t-child[2]=stmt_sequence();}match(END);returnt;}TinyC中的语法树——Yacc…#defineYYSTYPETreeNode*…simple_exp:simple_expPLUSterm{$$=newExpNode(OpK);$$-child[0]=$1;$$-child[1]=$3;$$-attr.op=PLUS;}|simple_expMINUSterm{$$=newExpNode(OpK);$$-child[0]=$1;$$-child[1]=$3;$$-attr.op=MINUS;}|term{$$=$1;};TinyC中的语法树——Yaccif_stmt:IFexpTHENstmt_seqEND{$$=newStmtNode(IfK);$$-child[0]=$2;$$-child[1]=$4;}|IFexpTHENstmt_seqELSEstmt_seqEND{$$=newStmtNode(IfK);$$-child[0]=$2;$$-child[1]=$4;$$-child[2]=$6;}5.3自底向上计算S-属性定义与LR(1)分析器结合在栈中保存语法符号的属性值归约时，利用栈中语法符号（产生式右部）属性值计算新的（左部符号的）综合属性值自底向上计算S-属性定义示例AXYZA.a=f(X.x,Y.y,Z.z)val[ntop]=f(val[top-2],val[top-1],val[top])例5.10LEnprint(val[top])EE1+Tval[ntop]=val[top-2]+val[top]ETTT1*Fval[ntop]=val[top-2]*val[top]TFF(E)val[ntop]=val[top-1]Fdigit产生式代码片断例5.10（续）5.4L-属性定义语法分析同时进行翻译，深度优先顺序proceduredfsvisit(n:node){forn的每个孩子，由左至右do{计算m的继承属性;（利用n的继承属性和m的左兄弟的属性）dfsvisit(m);}计算n的综合属性;}L-属性定义可由深度优先计算包括所有基于LL(1)文法的语法制导定义5.4.1L-属性定义一个语法制导定义，若满足如下条件，则称之为L-属性定义：对产生式AX1…Xn，Xj(1≤j≤n)的每个继承属性应仅仅依赖于1.Xj左边符号X1、X2、…、Xj-1的属性（继承属性和综合属性）2.A的继承属性所有S-属性定义都是L-属性定义例5.11不是L-属性定义ALML.i=f1(A.i)M.i=f2(L.s)A.s=f3(M.s)AQRR.i=f4(A.i)Q.i=f5(R.s)A.s=f6(Q.s)产生式语义规则5.4.2翻译模式语义动作嵌入产生式指明计算顺序例5.12ETRRaddopT{print(addop.lexeme)}R1|eTnum{print(num.val)}例5.12（续）设计翻译模式以语法制导定义为基础注意L-属性定义所带来的限制，确保不会违反属性计算的依赖关系最简单情况：只有综合属性既有综合属性，又有继承属性1.右部符号的继承属性必须在符号之前的语义动作中