编译原理语法制导翻译市公开课一等奖省赛课微课金奖PPT课件.pptx

？？为何进行词法和语法分析？？用A→α进行归约表示是什么意思看：operand+termE→E1+TE1值+T值结果作为E值——即：取来E1值和T值做加法运算，结果作为E值E.val=E1.val+T.val第五章语法制导翻译5.1语法制导翻译概述1.语义分析任务2.代码结构3.经典处理方法3.经典处理方法语义翻译流程◆语法制导定义是对上下文无关文法推广每个文法符号都有一个相关属性集。综合属性:经过分析树中其子节点属性值计算出来；继承属性:由该节点弟兄节点及父节点属性值计算出来；◆依赖图语义规则建立了属性之间依赖关系，这些关系能够用图来表示，这么图称为依赖图。在一个语法制导定义中，A→P都有与之相关联一套语义规则，规则形式为b：=f（c1，c2，…，ck），f是一个函数，而且或者1．b是A一个综合属性而且c1，c2，…，ck是中符号属性，或者2．b是中符号一个继承属性而且c1，c2，…，ck是A或中任何文法符号属性。在两种情况下，都说属性b依赖于属性c1，c2，…，ck。例5.1台式计算器程序语法制导定义（图5－2)S-属性定义仅仅使用综合属性语法制导定义。结点属性值计算恰好和自底向上分析建立分析树结点同时进行。例5.2输入：3*5+4ndigitlexval:=3◆综合属性值计算方法对于s-属性定义，通常使用自底向上分析方法，在建立每一个结点处使用语义规则来计算综合属性值，即在用哪个产生式进行归约后，就执行那个产生式s-属性定义计算属性值，从叶结点到根结点进行计算。5.1.3继承属性继承属性值是由此结点父结点和／或弟兄结点一些属性值来决定。例5.3变量说明属性定义inta,b,c表5.2带有继承属性L.in语法制导定义T依赖图结构方法for分析树中每个结点ndofor与结点n对应文法符号每个属性ado在依赖图中为a结构一个结点；for分析树每个结点ndofor结点n所用产生式对应每条语义规则b:＝f（c1，c2，…，ck)dofori:=1tokdo从结点ci到结点b结构一条有向边；例5-5图5－5分析树依赖图◆拓扑排序一个无环有向图拓扑排序是图中结点任何次序m1，m2，…，mk，使得边必须是从序列中前面结点指向后面结点，也就是说，假如mi→mj是mi到mj一条边,那么在序列中mi必须出现在mj前面。若依赖图中无环，则存在一个拓扑排序，它就是属性值计算次序。1，2，3，4，5，6，7，8，9，10a4:=real;a5:=a4;addtype(id3entry,a5);a7:=a5;addtype(id2entry,a7);a9:=a7;addtype(id1entry,a9);分析树法:输入串→分析树→依赖图→计算次序基于规则方法：在结构编译器时，用手工或专门工具来分析语义规则,确定属性值计算次序。忽略语义规则方法：在分析过程中翻译，那么计算次序由分析方法来确定而表面上与语义规则无关。这种方法限制了能被实现语法制导定义种类。后两种方法无须显式结构依赖图，所以时空效率更高。◆抽象语法（abstractsyntax）从详细语法中抽象出语言结构本质性东西，而不考虑语言详细符号表示，从而可简化语义形式描述。在不一样语言中赋值语句有不一样写法：x=y;x:=y;y→x等等，能够用抽象形式assignment(variable,expression)把前面各种详细形式统一起来。表示程序层次结构树，它把分析树中对语义无关紧要成份去掉，是分析树抽象形式，也称作语法结构树，或结构树。语法树是惯用一个中间表示形式。把语法分析和翻译分开。语法分析过程中完成翻译有许多优点，但也有一些不足：1.适于语法分析文法可能不完全反应语言成份自然层次结构；2.因为语法分析方法限制，对分析树结点访问次序和翻译需要访问次序不一致。产生式s→ifBthenS1elseS2语法树if-then-else／|＼BS1S2赋值语句语法树assignmentvariableexpression在语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。结构表示式语法树使用函数1.mknode(op,left,right)建立一个标识为op运算符结点，两个域left和right是指向左右运算对象指针。2．mkleaf(id,entry)建立一个标识为id标识符结点,其域entry是指向该标识符在符号表中对应表项指针。3.mkleaf(num,val)建立一个标识为num数结点，域val用于保留该数值。返回指向新建立结点指针。id5.2.3结构语法树语法制导定义图5-10a-4+c语法树结构◆无环有向图（DirectedAcyclicGraph，简称dag)用途：提取表示式中公共子表示式，以取得目标程序局部优化。方法：执行mknode和mkleaf时，