编译原理第五章

第5章

语法制导的翻译主讲：闫健恩计算机网络与信息安全中心Email：yanjianen(@)1本章重点语法制导定义S属性定义L属性定义语法制导的翻译方案设计语法制导定义和翻译方案的关系自底向上实现L属性的SDD2语法制导的翻译5.1语法制导定义5.2SDD的求值顺序5.3语法制导的翻译方案3第五章语法制导的翻译翻译的任务首先是语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。基本思想语法结构具有规定的语义根据翻译的需要设置文法符号的属性，以描述语法结构的语义。例如，一个变量的属性有类型，层次，存储地址等。表达式的属性有类型，值等。属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任务。45.1语法制导定义1.语义分析的任务语义检查例：类型、运算、维数、越界语义处理例：变量的存储分配例：表达式的求值例：语句的翻译（中间代码的生成）总目标：生成等价的中间代码52.代码结构计算学科：对信息（数据表示）描述和变换算法的系统研究变换：源、目标以及源与目标的对应关系语句的代码结构语句分类：说明语句——符号表的查填可执行语句——指令代码5.1语法制导定义63.典型处理方法（1）对应每一个产生式编制一个语义子程序，当一个产生式获得匹配时，调用相应的语义子程序实现语义检查与翻译E→E1+T E.val:=E1.val+T.valT→T1*F T.val:=T1.val*F.valF→id F.val:=id.val适宜在完成归约的时候进行5.1语法制导定义73.典型处理方法（2）在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id{…}语义——可以看成是相应文法符号的属性适宜在进行推导时完成5.1语法制导定义8语义翻译的流程输入符号串

分析树依赖图语义规则的计算实际上，编译中语义翻译的实现并不是按图中的流程处理的；而是随语法分析的进展，识别出一个语法结构，就对它的语义进行分析和翻译。94.什么是语法制导定义（SDD）上下文无关文法和属性/规则的结合；属性和文法符号相关联规则和产生式相关联根据需要，将文法符号和某些属性相关联，并通过语义规则来描述如何计算属性的值E→E1+T E.code=E1.code||T.code||‘+’code表示了我们关心的表达式的逆波兰表示，规则说明加法表达式的逆波兰表示由两个分量的逆波兰表示并置，然后加上‘+’得到。5.1语法制导定义105.语法制导的翻译

在产生式体中加入语义动作，并在适当的时候执行这些语义动作E→E1+T {print‘+’;}5.1语法制导定义11综合属性(synthesizedattribute)：分析树结点N上的非终结符号A的属性值由N的产生式所关联的语义规则来定义，又称为S-属性定义。必然通过N的子结点或N本身的属性值来定义继承属性(inheritedattribute)：分析树结点N的属性值由N的父结点所关联的语义规则来定义。又称为L-属性定义。依赖于N的父结点、N本身和N的兄弟结点上的属性值。5.1.1继承属性和综合属性12不允许N的继承属性通过N的子结点上的属性来定义，但是允许N的综合属性依赖于N本身的继承属性。终结符号有综合属性（由词法分析获得），但是没有继承属性。5.1.1继承属性和综合属性13语法制导定义（SDD）的例子目标：计算表达式L的值（属性val）计算L的val值需要E的val值E的val值又依赖于E和T的val值…终结符号digit有综合属性lexval。14注释语法分析树在分析树上求值有助于翻译方案的可视化，便于理解。包含了各个结点的各属性值的语法分析树5.1.2翻译方案的可视化15注释语法分析树构造注释语法分析树步骤：对于任意的输入串，首先构造出相应的分析树。根据结点上的文法符号，每个结点都有相应的属性值按照分析树中的分支对应的文法产生式，应用相应的语义规则计算属性值。如果某个规则N的属性a为f(N1.b1,N2.b2,……,Nk.bk)，那么我们需要先算N1.b1,N2.b2,……,Nk.bk的值。16如果可以给各个属性值排出顺序，那么这个注释分析树就可以计算得到。S属性的SDD一定可以按照自底向上的方式求值。但是下面的SDD不能计算A→B A.s=B.i；B.i=A.s+1；5.1.2翻译方案的可视化17digitlexval=3Fval=3Tval=3digitlexval=5Fval=5Tval=15*Eval=15+digitlexval=4Fval=4Tval=4Eval=19Lval=19n例5.2输入：3*5+4n的注释语法分析树18适用于自顶向下分析的SDD前面的表达式文法存在直接左递归，因此无法直接用自顶向下方法处理。消除左递归之后，无法直接使用属性val进行处理：比如规则：T→FT’T’→*FT’T对应的项中，第一个因子对应于F，而运算符在T’中。19相同表达式的不同文法的比较输入串：3*4*5请观察左边的T对应的部分，和右边的T’对应部分计算方法：把T’之外的部分的值继承给T’。TF*digit:4digit:5TTFdigit:3F*TF*εT’TFF*digit:3digit:4T’T’digit:520适用于自顶向下分析的SDD注意：T’的属性inh实际上是继承了相应的*号的左运算分量。21例5.33*5的注释分析树请观察inh属性是如何传递的。225.2SDD的求值顺序在对SDD的求值过程中，如果结点N的属性a依赖于结点M1的属性a1，M2的属性a2，…。那么必须先计算出Mi的属性，才能计算N的属性a。显然，这些值的计算顺序应该形成一个偏序关系。235.2.1依赖图依赖图描述了某棵特定的分析树上的各个属性实例之间的信息流（计算顺序）从实例a1到实例a2的有向边表示计算a2时需要a1的值。（必须先计算a2，再计算a1）24依赖图的构造方法for分析树中的每个结点ndofor与结点n对应的文法符号的每个属性ado在依赖图中为a构造一个结点；for分析树的每个结点ndofor结点n所用产生式对应的每条语义规则b:＝f（c1，c2，…，ck)dofori:=1tokdo

从结点ci到结点b构造一条有向边；5.2.1依赖图25例5.5依赖图的例子3*2的注释分析树；T→FT’{T.val=T’.syn;

T’.inh=F.val;}边e1、e2。可能的计算顺序：1,2,3,4,5,6,7,8.91,3,5,2,4,6,7,8,926属性值的计算顺序可以按照依赖图的拓扑排序计算各个属性的值。如果图中存在环，那么这个计算过程就无法进行。给定一个SDD，很难判定是否存在一棵分析树，其对应的依赖图包含环。但是特定类型的SDD一定不包含环，且有固定的排序模式。S属性的SDDL属性的SDD275.2.3S属性的SDD每个属性都是综合属性都是根据子构造的属性计算整个构造的属性。在依赖图中，总是通过子结点的属性值来计算父结点的属性值。可以和自顶向下、自底向上的语法分析过程一起计算自底向上：在构造分析树的子结点的同时计算相关的属性自顶向下：递归子程序法中，在过程A()的最后计算A的属性28在分析树上计算SDD按照后序遍历的顺序计算属性值即可postorder(N){ for(从左边开始，对N的每个子结点C)

postorder(c);

对N的各个属性求值；}在LR分析过程中，我们实际上不需要构造分析树的结点。295.2.4L属性的SDD每个属性要么是综合属性，要么是继承属性，且产生式A→X1X2…Xn中计算Xi.a的规则只能使用A的继承属性Xi左边的文法符号Xj的继承属性或综合属性。Xi自身的继承或综合属性。且这些属性的依赖关系不形成环。特点：依赖图的边总是从左到右，从下到上。在扫描过程中，计算一个属性值时相关的依赖属性都已经计算完成了。30带有继承属性L.inh的语法制导定义

产生式语义规则

DTLLinh:=TtypeTintTtype:=integerTfloatTtype:=floatLL1,idL1

inh:=Linh

addtype(id

entry,Linh)Lid

addtype(id

entry,Linh)315.2.5具有受控副作用的语义规则属性文法没有副作用，但是会增加描述的复杂度比如语法分析时如果没有副作用，符号表就必须作为属性传递。可以把符号表作为全局变量，然后通过副作用函数来添加新标识符；受控的副作用不会对属性求值产生约束，即可以按照任何拓扑属性求值，不会影响最终结果。添加部分简单的约束。32受控副作用的例子L→En

print(E.val)通过副作用打印出E的值总是在最后执行，且不会影响其它属性的求值变量声明的SDD中的副作用addType将标识符的类型信息加入到标识符表中。只要标识符不被重复声明，标识符的类型信息总是正确的。335.3语法制导的翻译方案语法制导的翻译方案（SDT）是在产生式体中嵌入程序片断（语义动作）的上下文无关文法SDT的基本实现方法：建立语法分析树；从左到右、深度优先地执行这些动作用SDT实现两类重要的SDD基本文法是LR的，SDD是S属性的基本文法是LL的，SDD是L属性的34可在语法分析过程中实现的SDT实际实现SDT时，并不会真的构造语法分析树，而是在分析过程中执行语义动作判断是否可在分析过程中实现将每个语义动作替换为一个独有的标记非终结符号；每个标记非终结符号M的产生式为M→ε。如果新的文法可以由某种方法进行分析，那么这个SDT就可以在这个分析过程中实现。注意：这个断言没有考虑变量值的传递等要求。355.3.1后缀翻译方案文法可以自底向上分析且SDD是S属性的可以构造出SDT，且所有的动作都放在产生式最后；分析过程中在按照这个产生式归约时执行这个动作；计算得到的属性值放在栈中；所有动作都在产生式最右端的SDT称为后缀翻译方案361后缀翻译方案的例子实现桌上计算机的后缀SDT372后缀SDT的语法分析栈实现可以在LR语法分析的过程中实现归约时执行相应的语义动作定义可以记录各个文法符号的属性的union结构栈中的每个文法符号（或者状态）的附带一个这样的结构的值；在按照产生式A→XYZ归约时，Z的属性可以在栈顶找到，Y的属性可以在下一个位置找到，X的属性可以在再下一个位置找到。38例5.15分析栈实现的例子假设语法分析栈存放在一个被称为stack的记录数组中，下标top指向栈顶；stack[top]指向这个栈的栈顶；stack[top-1]指向栈顶下一个位置；如果不同的文法符号有不同的属性集合，我们可以使用union来保存这些属性值。（归约时，我们知道栈顶向下的各个符号分别是什么）39这个SDT中没有局部变量，不会产生和局部变量有关的问题403产生式内部带有语义动作的SDT一个动作左部的所有符号（以及动作）处理完成后，就立刻执行这个动作B→X{a}Y自底向上分析时，a在X出现在栈顶时执行自顶向下分析时，在试图展开Y或者在输入中检测到Y时执行a不是所有的SDT都可以在分析过程中实现但是后缀SDT以及实现L属性的SDT可以在分析时完成。对于所有的SDT，都可以先建立分析树（语义动作作为虚拟的结点），然后进行前序遍历并执行动作。414L属性定义的SDTL属性SDD转换为SDT的规则：将计算非终结符号A继承属性的动作放在产生式中紧靠A之前，如果A有多个属性，要注意属性计算的顺序；将计算产生式头的综合属性的动作放在产生式的最右端。42例5.19L属性的SDT的例子继承属性：Next：语句结束后应该跳转到的标号true、false：C为真/假时应该跳转到的标号综合属性code表示代码435L属性的SDD的实现使用递归下降的语法分析器每个非终结符号对应一个函数函数的参数接受继承属性返回值包含了综合属性在函数体中，首先选择适当的产生式使用局部变量来保存属性对于产生式体中的终结符号，读入符号并获取其（经词法分析得到的）综合属性对于非终结符号，使用适当的方式调用相应函数，并记录返回值。446L属性的自底向上实现（1）以LL文法为基础的L属性SDD可以在LR语法分析过程中实现方法：首先构造出L属性SDD的SDT，即在非终结符号前计算其继承属性若有产生式A→α{a