程序设计语言 编译原理(第三版)第6章.ppt

1 第六章属性文法和语法制导翻译 6 1属性文法6 2基于属性文法的处理方法6 3S 属性文法的自下而上计算6 4L 属性文法和自顶向下翻译6 5自下而上计算继承属性 2 6 1属性文法 一 基本概念 1 属性 广义 用以描述事物或人的特征 性质 品质等等 狭义 代表与文法符号相关的信息 其信息值即为属性值 例如 其类型 值 代码序列 符号表内容等 3 1 属性与变量一样 可以进行计算和传递 6 1属性文法 2 属性加工的过程即是语义处理的过程 用于 自上而下 传递信息 用于 自下而上 传递信息 注 4 2 语义规则 为文法的每一个产生式配备的计算属性的计算规则 称为语义规则 3 属性文法 在上下文无关文法的基础上 为每个文法符号 终结符或非终结符 引进一组属性 且让该文法中的重写规则附加上语义规则时 称该上下文无关文法为属性文法 注 属性文法往往以语法制导翻译和翻译方案两种形式出现 6 1属性文法 5 补充 语法制导定义 基于上下文无关文法 是关于语言翻译的抽象规格说明 其中除去了一些实现细节 不规定翻译顺序 翻译模式 规定实现途径和细节 指明使用语义规则进行计算的顺序 6 1属性文法 6 二 基本规则 1 语义规则的形式 产生式A 的语义规则的形式为b f c1 c2 ck 其中 1 f是一个函数 属性b依赖于属性c1 c2 ck 2 或者b A的综合属性 且c1 c2 ck是 中文法符号的属性 6 1属性文法 3 或者b 中某个文法符号的继承属性 且c1 c2 ck是A或 中任何文法符号的属性 7 2 VT VN的属性 1 VT 只有综合属性 由词法分析器提供 6 1属性文法 2 VN 既可有综合属性也可有继承属性 开始符号S的所有继承属性作为属性计算前的初始值 8 3 属性的计算 获得 1 产生式右边的继承属性产生式左边的综合属性 2 产生式左边的继承属性产生式右边的综合属性 6 1属性文法 9 例6 1 考虑非终结符 和 其中 有一个继承属性 和一个综合属性 有综合属性 有继承属性 C d B c 1 产生式A BC可能有规则 属性A a和B c在其它地方计算 A a 左部继承属性A b 左部综合属性B c 右部综合属性C d 右部继承属性 6 1属性文法 10 例6 2 一个简单台式计算器的属性文法 Print E val E val E1 val T val E val T val T val T1 val F val T val F val F val E val F val digit lexval 6 1属性文法 11 三 综合属性 1 语法树中 一个结点的综合属性的值由其子结点的属性值确定 2 通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值 S 属性文法 仅使用综合属性的属性文法 6 1属性文法 12 例6 3 例6 2的表中定义的属性文法说明了一个台式计算器 该计算器读入一个可含数字 括号和 运算符的算术表达式 并打印表达式的值 每个输入行以n作为结束 假设表达式为3 5 4 后跟一个换行符n 程序打印数值19 其带注释的语法树 6 1属性文法 13 返回 的带注释的语法树 14 四 继承属性 1 语法树中 一个结点的继承属性由此结点的父结点和 或兄弟结点的某些属性确定 2 用继承属性来表示程序设计语言结构中的上下文依赖关系很方便 6 1属性文法 15 例6 带继承属性L in的属性文法 addtype id entry L in T type integer T type real L1 in L in L in T type addtype id entry L in 6 1属性文法 16 输入串 realid1 id2 id3的带注释的语法树 D T type real L in real real L in real L in real id2 id3 id1 17 基于属性文法的处理过程 单词符号串 语法分析树 计算 例 6 2基于属性文法的处理方法 18 语法制导翻译法 语义规则的计算将有下列作用 产生代码 在符号表中存放信息 给出错误信息或执行其它动作 由源程序的语法结构所驱动的处理方法 6 2基于属性文法的处理方法 19 一 依赖图 1 定义 一个表示一棵语法树中结点的继承属性和综合属性之间的相互依赖关系的有向图 6 2基于属性文法的处理方法 20 2 依赖图的构造方法 1 构造依赖图以前 先为每一个包含过程调用的语义规则引入一个虚综合属性b 在每一个语义规则均写成b f c1 c2 ck 的形式 2 在依赖图中为每一个属性设置一个结点 3 若属性b依赖于属性c 则从属性c的结点有一条有向边连到属性b的结点 6 2基于属性文法的处理方法 21 返回 6 2基于属性文法的处理方法 22 6 2基于属性文法的处理方法 23 3 例题 例6 6 将下面的产生式应用于语法树中 产生式语义规则E E1 E2E val E1 val E2 val E Val是从E1 val和E2 val综合得出 6 2基于属性文法的处理方法 24 例6 7 例6 4中语法分析树的依赖图 in56type3typein78in9102entry1entry 6 2基于属性文法的处理方法 25 属性的计算次序 6 2基于属性文法的处理方法 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序 注 在拓扑排序中 在一个结点上 语义规则b f c1 c2 ck 中的属性c1 c2 ck在计算b以前是可用的 良定义的 若一个属性文法不存在属性之间的循环依赖关系 则称该文法为良定义的 26 基础文法 用于建立输入符号串的语法分析树 从依赖图的拓扑排序中 我们可以得到计算语义规则的顺序 用这个顺序来计算语义规则就得到输入符号串的翻译 6 2基于属性文法的处理方法 a4 reala5 a4addtype id3 entry a5 a7 a5 addtype id2 entry a7 a9 a7 addtype id1 entry a9 例6 8 27 二 树遍历的属性计算方法 1 方法 A 前提 假设语法树已经建立起来了 且树中已有如下信息 开始符号 继承属性终结符 综合属性 B 遍历 以某种次序遍历语法树 直至计算出所有属性 遍历方法 深度优先 从左到右 6 2基于属性文法的处理方法 28 2 算法 While还有未被计算的属性doVisitNode S S是开始符号 procedureVisitNode N Node beginIfN是一个非终结符then 假设它的产生式为N X1 Xm fori 1tomdoifnotXi VTthen 即Xi是终结符 begin计算Xi的所有能够计算的继承属性 VisitNode Xi end 计算N的所有能够计算的综合属性end 29 6 2基于属性文法的处理方法 注 只要文法的属性是非循环定义的 则每次扫描至少有一个属性值被计算出来 30 其中 S有继承属性a 综合属性b X有继承属性c 综合属性d Y有继承属性e 综合属性f Z有继承属性h 综合属性g 3 举例 例6 9 考虑下表所给的属性文法G 6 2基于属性文法的处理方法 31 6 2基于属性文法的处理方法 32 6 2基于属性文法的处理方法 33 三 一遍扫描的处理方法 1 特点 在语法分析的同时计算属性值 而不是语法分析构造语法树之后进行属性的计算 而且无需构造实际的语法树 注 采用该处理方法 当一个属性值不再用于计算其它属性值时 编译程序就不必再保留这个属性值 如果需要 可把语义值存到文件中 6 2基于属性文法的处理方法 34 2 相关因素 1 所使用的语法分析方法 L 属性文法 一遍扫描的自上而下分析S 属性文法 一遍扫描的自下而上分析 6 2基于属性文法的处理方法 2 属性的计算次序 35 3 语法制导翻译 A 在语法规则的制导下 通过计算语义规则 完成对输入符号串的翻译 6 2基于属性文法的处理方法 该产生式相应的语义规则被计算 完成有关的语义分析和代码产生工作 由此可见 在该情况下 语法分析工作和语义规则的计算是穿插进行的 B 为文法中每个产生式配上一组语义规则 并在语法分析的同时执行这些语义规则 36 四 抽象语法树 AbstractSyntaxTree 1 定义 注 抽象语法树中 操作符和关键字都不作为叶结点出现 而是把它们作为内部结点 即这些叶结点的父结点 6 2基于属性文法的处理方法 在语法树中去掉那些对翻译不必要的信息 从而获得更有效的源程序中间表示 这种经变换后的语法树称之为抽象语法树 37 2 如何建立表达式的抽象语法树 1 方法 通过为每一个运算分量或运算符号都建立一个结点来为子表达式建立子树 6 2基于属性文法的处理方法 运算符号结点的各个子结点分别是表示该运算符号的各个运算分量的子表达式组成的子树的根 38 2 抽象语法树中每个结点可由包含几个域的记录来实现 6 2基于属性文法的处理方法 运算符号结点 一个域 运算符号其它域 指向运算符号分量的结点的指针 结点 附加的域 存放结点的属性值 指向属性值的指针 39 6 2基于属性文法的处理方法 40 例6 10 下面一系列函数调用建立了表达式a 4 c的抽象语法树 如图 在这个序列中 p1 p2 p5是指向结点的指针 entrya和entryc分别是指向符号表中的标识符a和c的指针 6 2基于属性文法的处理方法 1 p1 mkleaf id entrya 2 p2 mkleaf num 4 3 p3 mknode p1 p2 4 p4 mkleaf id entryc 5 p5 mknode p3 p4 41 为表达式建立抽象语法树的属性文法 6 2基于属性文法的处理方法 42 E nptr T nptr E nptr E T nptr num T nptr id id 带注释的语法分析树 Toentryfora Toentryforc 43 6 3S 属性文法的自下而上计算 1 S 属性文法定义 1 所有非终结符只具有综合属性 2 在一个产生式中 每个符号的各个综合属性的定义互不依赖 2 综合属性的计算在分析输入符号串的同时由自下而上的分析器来计算 分析器可以保存与栈中文法符号有关的综合属性值 每当进行归约时 新的属性值就由栈中正在归约的产生式右边符号的属性值来计算 44 3 S 属性文法的翻译器通常可借助于LR分析器实现在S 属性文法的基础上 LR分析器可以改造为一个翻译器 在对输入串进行语法分析的同时对属性进行计算 6 3S 属性文法的自下而上计算 45 4 分析栈 6 3S 属性文法的自下而上计算 自底向上分析法中 栈 存放已经分析过的子树的内容附加域 存放综合属性值 数组State 元素 一个指向LR 1 分析表的指针 索引 指向表中某个文法符号 数组Val 存放语法树中与结点对应的属性值 注 1 假定综合属性刚好在每次归约前计算 2 若一个符号无综合属性 则数组val中相应的元素就不定义 46 5 举例 L EnE E1 TE TT T1 FT FF E F digit 输入串3 5 4n 3 5 4n 5 4n33 5 4nF3 5 4nT3 5 4nT 3 4nT 53 5 4nT15 4nE15 4nE 15 4nT F3 5 F digit T F F digit T T F E T 47 L EnE E1 TE TT T1 FT FF E F digit 输入串3 5 4n 4nE 15 nE 415 4 nE F15 4 nE T15 4 nE19 En19 L19 F digit T F E E T L En 5 举例 48 6 4L 属性文法和自顶向下翻译 L 属性文法 1 定义 若属性文法中每个产生式A X1X2 Xn 其相关的每个语义规则中的每个属性 或者是综合属性 或者是Xj的一个继承属性且该继承属性仅依赖于Xj左边符号X1 X2 Xj 1的属性和A的继承属性 则称该属性文法为L 属性文法 49 2 特点 6 4L 属性文法和自顶向下翻译 L 属性文法 A 该类属性文法允许我们通过一次遍历就计算出所有属性值 B 可在自上而下语法分析的同时实现L 属性文法的计算 C S 属性文法一定是L 属性文法 50 6 4L 属性文法和自顶向下翻译 一个非L 属性文法 51 一 翻译模式 1 翻译模式的定义 一种适合语法制导翻译的语义描述形式 给出了使用语义规则进行计算的次序 可把某些实现细节表示出来 形式 在翻译模式中 和文法符号相关的属性和语义规则 用 括起来 插入到产生式右部的合适位置上 例 E TRR addopT pr addop lex R1 T num pr num val 6 4L 属性文法和自顶向下翻译 52 为每一个语义规则建立一个包含赋值的动作 并把这个动作放在相应的产生式右边的末尾 6 4L 属性文法和自顶向下翻译 2 翻译模式的设计 A 只有综合属性时 可以按如下方式建立翻译模式 53 B 若既有综合属性又有继承属性时 则按如下方式建立翻译模式 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来 一个动作不能引用这个动作右边的符号的综合属性 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算 计算这种属性的动作通常可放在产生式右端的末尾 6 4L 属性文法和自顶向下翻译 2 翻译模式的设计 54 举例 E TRR addopT pr addop lex R1 T num pr num val 输入 9 5 2深度优先遍历后输出 95 2 E T R R R 9 Pr 9 T Pr T Pr 5 Pr 5 2 Pr 2 55 二 自顶向下翻译 1 讨论 L 属性文法在自顶向下分析中的实现 6 4L 属性文法和自顶向下翻译 自顶向下语法分析的前提是消除文法中的左递归 56 E E1 T E val E1 val T val E E1 T E val E1 val T val E T E val T val T E T val E val T num T val num val E T R i T val R E val R s R T R1 i R i T val R1 R s R1 s R T R1 i R i T val R1 R s R1 s R R s R i T E T val E val T num T val num val 2 例题 57 计算表达式9 5 2 带注释语法树i 继承属性s 综合属性 6 4L 属性文法和自顶向下翻译 58 计算表达式9 5 2 递归过程 综合属性计算 6 4L 属性文法和自顶向下翻译 59 A A1Y A a g A1 a Y y A X A a f X x A X R i f X x R A a R s R Y R1 i g R i Y y R1 R s R1 s R R s R i 6 4L 属性文法和自顶向下翻译 3 转换左递归翻译模式的一般方法 消除左递归前 消除左递归后 60 6 4L 属性文法和自顶向下翻译 带注释语法树 P155 156 61 递归下降分析器的构造p156举例AST AbstractSyntaxTree 三 递归下降翻译器的设计 6 4L 属性文法和自顶向下翻译 62 L 属性文法的自上而下分析翻译方法 适用于所有基于LL 1 文法和许多基于LR 1 文法的L 属性文法 是S 属性文法自下而上翻译技术的一般化 1 从翻译模式中去掉嵌入在产生式中间的动作 2 分析栈中的继承属性 3 模拟继承属性的计算 4 用综合属性代替继承属性 6 5自下而上的计算继承属性 63 S 属性文法翻译自下而上规约时进行 翻译模式允许翻译动作嵌入产生式 如何保证嵌入的动作在产生式的末尾 标