[工学]第4章 语法制导的翻译.ppt

第4章 语法制导的翻译 主讲人：范 敏 引入 复习 词法分析的任务和正规式的作用 语法分析的任务和文法的作用 思考 语言结构的属性如何计算？何时计算？属性值如何存放？ 第1章 编译器概述 第2章 词法分析 第3章 语法分析 第4章 语法制导的翻译 第5章 类型检查 第6章 运行时存储空间的组织和管理 第7章 中间代码生成 第8章 代码生成 第9章* 代码优化 第10章* 编译系统和运行系统 第11章* 面向对象语言的编译 第12章* 函数式语言的编译 4.1 语法制导的定义 4.2 S属性定义的自下而上计算 4.3 L属性定义的自上而下计算 4.4 L属性的自下而上计算 4.5 递归计算 本章内容 介绍一种形式化的语义描述方法 语法制导的翻译，包括它的两种具体形式：语法制导的定义和翻译方案 介绍语法制导的翻译的实现方法 本章学习目标 掌握综合属性、继承属性、语法树、翻译方案等概念 掌握语法制导的定义方法 掌握S属性和L属性的计算方法 4.1 语法制导的定义 例：简单台式计算器的语法制导定义 基础文法 基础文法是语法制导定义中的文法。其中，每个文法符号都有一组可以用于计算的属性 每个产生式A ? ?有一组形式为b := f(c1, c2, …, ck )的语义规则。其中f 是函数，b, c1 , c2 , …, ck 是文法符号的属性 语义规则 一组计算表达式 计算相应产生式中文法符号的属性值 文法符号属性分类 继承属性：如果b是产生式右部某个文法符号X的属性，c1 , c2 , …, ck 是产生式左部文法符号A的属性或产生式右部文法符号属性 综合属性：如果b是A的属性，c1 , c2 , …, ck 是产生式右部文法符号属性或A的继承属性 S属性定义：仅使用综合属性的语法制导定义 8+5*2 n的计算：1. 根据基础文法画出推导出句子的分析树 8+5*2 n的计算：2. 标出分析树中每个结点的属性（如果有） 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成 利用分析树对S属性定义中综合属性的计算方法小结 画出句子（词法记号流符号串）的分析树 标出每个结点的属性（如果有） 根据语义规则自下而上、从左到右完成各个结点属性的计算 int id, id, id int id1, id2, id3的注释分析树 分析树 int id1, id2, id3的注释分析树 在注释分析树每个L结点，除传递继承属性in给子结点L1外，addtype过程在符号表中将L右子结点上标识符id的类型记为整型：addtype (id.entry, L.in ) int id1, id2, id3的分析树的依赖图 描述结点属性间依赖关系的有向图称为依赖图 D ? TL { L.in := T.type } int id1, id2, id3的分析树的依赖图 L? L1, id { L1.in := L.in; addtype (id.entry, L.in )} 拓扑排序：属性结点出现顺序的一种排序，使得有向边只从该次序中先出现的结点指向后出现的结点 例：1，2，3，4，5，6，7，8，9，10 属性计算过程 （1）构造输入串的分析树 属性计算过程 （1）构造输入串的分析树；（2）构造属性依赖图 属性计算过程 （1）构造输入串的分析树；（2）构造属性依赖图；（3）对属性结点进行拓扑排序 属性计算过程 （1）构造输入串的分析树；（2）构造属性