编译原理语法制导翻译ppt课件.ppt

《编译原理语法制导翻译ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章语法制导翻译学习重点语法制导定义概念利用语法制导定义构造语法树S-属性定义、L-属性定义自顶向下计算属性自底向上计算属性递归方法计算属性内存分配概述语法制导定义翻译模式“编程语言的翻译根据语法进行”“属性”，attribute每个语法符号与若干属性相关联翻译——指定属性的相互依赖关系语义规则，semanticrule语言规则的执行反映属性的相互关系5.1语法制导定义扩充CFG语法符号属性——语法树节点，记录域产生式语义规则——语法树节点，用于计算属性属性类型综合，synthesized，根据孩子节点属性计算继承，inherited，由父、兄弟节点属性计算依赖图，depen

2、dencygraph注释语法树：节点属性值计算完毕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.1digit.lexval：终结符只有综合属性，由词法分析器提供开始符号通常没有继承属性LEnprint(E.val)E

3、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

4、.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.4EE1+E2,E.val=E1.val+E2.val例5.55.1.5计算顺序拓扑排序，计算顺序满足依赖关系m1,m2,…,mk，存在边mi

5、mji

6、树5.2.1语法树（抽象）语法树，压缩形式关键字和运算符均在内部节点链式结构会被压缩语法树压缩例5.2.2表达式语法树的构造与表达式翻译为后缀形式类似数据结构：语法树每个节点用一个记录表示运算符节点记录格式：{运算符指向运算对象节点1的指针执行运算对象节点2的指针…}辅助函数mknode(op,left,right)：为运算符op创建语法树中节点，标记（运算符）为op，运算对象节点指针left和rightmkleaf(id,entry)：为标识符创建语法树节点，标记为id，另一个域为符号表项指针entrymkleaf(num,val)：为运算数创建节点，标记为num，另一个域

7、为数值例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(