ch05--语法制导翻译技术解析.ppt

第5章 语法制导翻译技术 知识点：语法制导定义、翻译方案 S-属性定义、L-属性定义 S-属性定义的翻译 L-属性定义的翻译 语法制导翻译技术 语义分析涉及到语言的语义 形式语义学的研究开始于20世纪60年代初 形式语义学可以分为三类 操作语义学：通过说明程序在一个机器中是如何执行的来定义程序的语义，着重模拟数据加工过程中计算机系统的操作 指称语义学：使用数学函数来描述程序和程序的构成，函数通过把语义值联系到正确的语法结构来描述程序的语义，主要描述数据加工的结果 公理语义学：把数理逻辑应用于语言的语义，语言结构与谓词转换器联系在一起，语言结构的行为以命题刻画，通过描述程序执行对程序断言的影响来定义程序、语句或语言结构的语义，主要用于程序正确性证明 语法制导翻译技术 多数编译程序普遍采用的一种技术 比较接近形式化 语法制导翻译技术 根据翻译目标的要求确定每个产生式所包含的语义； 根据产生式包含的语义，分析文法中每个符号的语义； 把这些语义以属性的形式附加到相应的文法符号上； 根据产生式的语义，给出符号属性的求值规则(即语义规则)，从而形成语法制导定义。 在语法分析过程中，当使用该产生式时，根据语义规则对相应的属性进行求值，从而完成翻译。 例如：考虑算术表达式文法 总目标：计算表达式的值 产生式 E?E1+T 的语义：表达式的值由两个子表达式的值相加得到 分析每个符号的语义，并以属性的形式记录：E.val、E1.val、T.val 求值规则：E.val=E1.val+T.val 语法制导定义：产生式 语义规则 语法制导翻译技术（续） 例如：考虑算术表达式文法 总目标：检查表达式的类型 产生式 E?E1+T 的语义：表达式的类型由两个子表达式的类型综合得到 分析每个符号的语义，并以属性的形式记录：E.type、 E1.type、 T.type 求值规则： if (E1.type==integer)(T.type==integer) E.type=integer; else … 翻译结果—取决于翻译目标 生成代码 可以为源程序产生中间代码 可以直接生成目标机指令 对输入符号串进行解释执行 向符号表中存放信息 给出错误信息 翻译的结果依赖于语义规则 使用语义规则进行计算所得到的结果就是对输入符号串进行翻译的结果。 如：E?E+T 的翻译结果可以是：计算表达式的值、检查表达式的类型是否合法、为表达式创建语法树、生成代码等等。 语法制导翻译技术（续） 进一步： 用一个或多个子程序（称为语义动作）所要完成的功能描述产生式的语义； 把语义动作插入到产生式中相应位置，从而形成翻译方案。 在语法分析过程中使用该产生式时，在适当的时机调用这些动作，完成所需要的翻译。 语法制导定义是对翻译的高层次的说明，它隐蔽了一些实现细节，无须指明翻译时语义规则的计算次序。 翻译方案指明了语义规则的计算次序，规定了语义动作的执行时机。 语法制导翻译的一般步骤 语法制导翻译技术 5.1 语法制导定义及翻译方案 5.2 S-属性定义的自底向上翻译 5.3 L-属性定义的自顶向下翻译 5.4 L-属性定义的自底向上翻译 小 结 5.1 语法制导定义及翻译方案 对上下文无关文法的推广 每个文法符号都可以有一个属性集，其中可以包括两类属性：综合属性和继承属性。 左部符号的综合属性是从该产生式右部文法符号的属性值计算出来的；在分析树中，一个内部结点的综合属性是从其子结点的属性值计算出来的。 出现在产生式右部的某文法符号的继承属性是从其所在产生式的左部非终结符号和/或右部文法符号的属性值计算出来的；在分析树中，一个结点的继承属性是从其兄弟结点和/或父结点的属性值计算出来的。 分析树中某个结点的属性值是由与在这个结点上所用产生式相应的语义规则决定的。 和产生式相联系的语义规则建立了属性之间的关系，这些关系可用有向图（即：依赖图）来表示。 本节内容安排 一、语法制导定义 二、依赖图 三、计算次序 四、S属性定义和L属性定义 五、翻译方案 一、语法制导定义 在一个语法制导定义中，对应于每一个文法产生式A??，都有与之相联系的一组语义规则，其形式为：b=?(c1,c2,…,ck) 这里，?是一个函数，而且或者 (1) b是A的一个综合属性，且c1、c2、…、ck是产生式右部文法符号的属性，或者 (2) b是产生式右部某个文法符号的一个继承属性，且c1、c2、…、ck是A或产生式右部任何文法符号的属性。 属性b依赖于属性c1、c2、…、ck。 语义规则函数都不具有副作用的语法制导定义称 为属性文法 语义规则 一般情况： 语义规则函数可写成表达式的形式。