Microsoft PowerPoint - L9-v3.pptx

Lecture 9: 语法制导的翻译 -I Xiaoyuan Xie 谢晓园 xxie@whu.edu.cn 计算机学院 E301

Introduction 9.1 概述

语义分析在编译程序中的作用词法分析目标代码生成语法分析中间代码优化语义分析分析中间代码生成合成

语法和语义的区别语法是描述一个合法定义的程序结构的规则例如 <函数调用语句> id( <实参表达式>) 语义说明一个合法定义的程序的含义 int x; float* f(); x(); x = f(); 符合变量声明的语法语义符合函数声明的语法语义符合函数调用的语法不符合语义符合赋值语句的语法不符合语义

语义分析的必要性一个语法正确的程序不能保证它是有意义的! 程序中容易出现各种语义错误 : 标识符未声明 y = x+3; 操作数的类型与操作符的类型不匹配 y = x*3; 数组下标变量的类型出错 A[x]; 语义分析不能检查程序在计算逻辑上的错误!!!!

程序设计语言语义的分类静态语义(static semantics) 编译时(compile-time)可以检查的语义例如标识符未声明标识符重复声明动态语义(dynamics semantics) 目标程序运行时 run-time 才能检查的语义例如除零溢出错误 x/(y-i); 当 y = i时数组下标越界 int a[5]; a[5] =0; 无效指针 int*p; p =NULL; *p = 3;

如何描述程序设计语言的语义? 程序设计语言的形式语义属性文法 ( 用于描述静态语义 ) 操作语义 (Operational Semantics) 指称语义 (Denotational Semantics) 代数语义 (Algebra Semantics) 公理语义 (Axiomatic Semantics) 形式语义技术没有形式语法技术成熟硕士研究生的课程 -- 形式语义学

Basic concepts 9.2 基本概念

什么是语法制导翻译语法制导翻译在语法分析基础上边分析边翻译翻译的依据语义规则或语义子程序翻译的结果相应的中间代码翻译的做法为每个产生式配置相应的语义子程序每当使用某个产生式进行规约或推导时就调用语义子程序完成一部分翻译工作语法分析完成时翻译工作也告结束

语义规则产生式与语义规则每个文法产生式A 有一组形式为b=f(c1, c2,, ck )的语义规则其中b和c1, c2,, ck 是该产生式文法符号的属性 f 是函数描述一个产生式所对应的翻译工作如改变某些变量的值填/查各种符号表发现并报告源程序错误产生中间代码决定于要产生什么样的中间代码

文法属性文法属性每个文法符号有一组属性 X是一个文法符号 a是x的一个属性用X.a表示a在某个标号为X 的分析树结点上的属性值属性可以有多种类型如num, type, table_entry, text等两种类型综合属性如果b是A的属性 c1, c2,, ck 是产生式右部文法符号的属性或A的其它属性继承属性如果b是右部某文法符号X的属性

基本概念(skip, 将在后面讨论) 综合属性在分析树结点N上的非终结符号A的属性值由N对应的产生式所关联的语义规则来定义通过N的子结点或N本身的属性值来定义继承属性结点N的属性值由N的父结点所关联的语义规则来定义依赖于N 的父结点 N本身和N的兄弟结点上的属性值不允许N的继承属性通过N的子结点上的属性来定义, 但是允许N的综合属性依赖于N本身的继承属性, 终结符号有综合属性(由词法分析获得) 但是没有继承属性

语法制导定义语法制导(的文法)定义是一个CFG和属性及规则的结合 Syntax-Directed Definition, SDD 属性和文法符号相关联规则与产生式相关联只含有综合属性的例子

语法分析树上的SDD求值实践中很少先构造语法分析树再进行SDD求值但在分析树上求值有助于翻译方案的可视化便于理解注释语法分析树包含了各个结点的各属性值的语法分析树步骤对于任意的输入串首先构造出相应的分析树给各个结点根据其文法符号加上相应的属性值按照语义规则计算这些属性值即可

语法分析树上的SDD求值产生式 L En 注释分析树:结点的属性值都标注出来的分析树 8+5*2 n的注释分析树 L E.val = 18 E.val = 8 + T.val = 8 T.val = 5 F.val = 8 F.val = 5 digit.lexval = 8 n T.val = 10 digit.lexval = 5 语义规则 print (E.val) E E1 + T E.val = E1.val + T.val E T E.val = T.val T T1 F T.val = T1.val F.val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval F.val = 2 digit.lexval = 2

语法分析树上的SDD求值产生式 S属性SDD的分析树各结点属性的计算可以自下而上地完成 L En 8+5*2 n的注释分析树 L E.val = 18 E.val = 8 + T.val = 8 T.val = 5 F.val = 8 F.val = 5 digit.lexval = 8 n T.val = 10 digit.lexval = 5 语义规则 print (E.val) E E1 + T E.val = E1.val + T.val E T E.val = T.val T T1 F T.val = T1.val F.val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval F.val = 2 digit.lexval = 2

语法分析树上的SDD求值产生式分析树各结点属性的计算可以自下而上地完成L E n 8+5*2 n的注释分析树 L E.val = 18 E.val = 8 + T.val = 8 T.val = 5 F.val = 8 F.val = 5 digit.lexval = 8 n T.val = 10 digit.lexval = 5 语义规则 print (E.val) E E1 + T E.val = E1.val + T.val E T E.val = T.val T T1 F T.val = T1.val F.val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval F.val = 2 digit.lexval = 2

语法分析树上的SDD求值按照分析树中的分支对应的文法产生式应用相应的语义规则计算属性值计算顺序问题如果我们可以给各个属性值排出计算顺序那么这个注释分析树就可以计算得到如果某个结点N的属性a为f(N1.b1,N2.b2,,Nk.bk) 那么我们需要先算出 N1.b1,N2.b2,,Nk.bk的值 S属性的SDD一定可以按照自底向上的方式求值下面的SDD不能计算 A B A.s=B.i B.i=A.s+1

回顾一下两种属性的定义综合属性在分析树结点N上的非终结符号A的属性值由N对应的产生式所关联的语义规则来定义通过N的子结点或N本身的属性值来定义继承属性结点N的属性值由N的父结点所关联的语义规则来定义依赖于N 的父结点 N本身和N的兄弟结点上的属性值不允许N的继承属性通过N的子结点上的属性来定义, 但是允许N的综合属性依赖于N本身的继承属性, 终结符号有综合属性(由词法分析获得) 但是没有继承属性

SDD (含有继承属性的例子1) 左递归文法使用自顶向下分析时要消除左递归出现了继承属性

SDD (含有继承属性的例子1) 3*5注释分析树及属性依赖图注意观察inh属性是如何传递的

SDD (含有继承属性的例子2) SDD int id1, id2, id3 产生式 D TL T int 语义规则 L.in = T.type T.type = integer T real T.type = real L L1, id L id L1.in = L.in; addtype(id.entry, L1.in) addtype(id.entry, L.in) 对于一个属性不允许出现即是综合又是继承的现象

SDD (含有继承属性的例子2) int id1, id2, id3 注释分析树不可能像像综合属性那样自下而上标注属性 D L.in = integer T.type = integer, L.in = integer int L.in = integer id1, id2 id3

SDD (含有继承属性的例子2) int id1, id2, id3的分析树虚线的依赖图实线 D TL L.in = T.type 10个结点每个属性一个结点 D T 4 type int in 9 in 5 L 8 in 7 L 10, id1 1 entry L 6, id2 2 entry id3 3 entry

SDD (含有继承属性的例子2) int id1, id2, id3的分析树虚线的依赖图实线 L L1, id L1.in = L.in; addtype (id.entry, L.in) D T 4 type int in 9 in 5 L 8 in 7 L 10, id1 1 entry L 6, id2 2 entry id3 3 entry

拓扑顺序使用依赖图来表示计算顺序 ---拓扑顺序显然这些值的计算顺序应该形成一个偏序关系如果依赖图中出现了环表示属性值无法计算给定一个SDD 很难判定是否存在一棵分析树其对应的依赖图包含环

SDD (含有继承属性的例子2) Int id1,id2, id3计算顺序 1.先构造输入的分析树 D T 4 type int in 9 in 5 L 8 in 7 L 10, id1 1 entry 4.按拓扑排序的次序计算属性 L 6, 2.构造属性依赖图 id3 3 entry id2 2 entry 3.对结点进行拓扑排序结点的一种排序使得边只会从该次序中先出现的结点到后出现的结点例 1 2 3 4 5 6 7 8 9 10 --- 不一定唯一

SDD (只含综合属性的例子) 8+5*2 n的计算顺序 L E.val = 18 E.val = 8 + T.val = 8 T.val = 5 F.val = 8 F.val = 5 digit.lexval = 8 n T.val = 10 digit.lexval = 5 F.val = 2 digit.lexval = 2

语义规则的计算方法---理论做法

语义规则的计算方法 --- 实际操作 tips 基于规则的方法 :( 编译器实现者 ) 静态确定 ( 编译器设计者提供的 ) 语义规则的计算次序 --- 用于手工构造的方法忽略规则的方法 :( 编译器实现者 ) 事先确定属性的计算策略 ( 如边分析边计算 ),( 编译器设计者提供的 ) 语义规则必须符合所选分析方法的限制 --- 适用于自动生成的方法

实现边分析边翻译怎样的SDD可以和以前所介绍的语法分析结合在一起属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制在对SDD的求值过程中如果结点N的属性a依赖于结点M1的属性a1 M2的属性a2 那么我们必须先计算出Mi的属性才能计算N的属性a 分析树的结点是自左向右生成如果属性信息是自左向右流动那么就有可能在分析的同时完成属性计算

实现边分析边翻译特定类型的SDD一定不包含环且有固定排序模式 S属性的SDD L属性的SDD 对于这些类型的SDD 我们可以确定属性的计算顺序且可以把不需要的属性及分析树结点抛弃以提高效率这两类SDD可以很好地和我们已经研究过的语法分析相结合

S属性的SDD及其相容分析方法只包含综合属性的SDD称为S属性的SDD 自底向上和LR语法分析器一起实现每个语义规则都根据产生式体中的属性值来计算头部非终结符号的属性值在依赖图中总是通过子结点的属性值来计算父结点的属性值可以和自顶向下自底向上的语法分析过程一起计算在构造分析树的结点的同时计算相关的属性此时其子结点的属性必然已经计算完毕栈中的状态可以附加相应的属性值在进行归约时按照语义规则计算归约得到的符号的属性值自顶向下递归下降分析中可以在过程A()的最后计算A的属性---此时A调用的其他过程对应于子结构已经调用完毕

S属性的SDD及其相容分析方法例如和LR分析相容

在分析树上计算SDD 按照后序遍历的顺序计算属性值即可 postorder(n) { for(从左边开始对N的每个子结点C) postorder(c); //递归调用返回时各子结点的属性计算完毕对N的各个属性求值 } 一个自底向上的语法分析过程对应于一次后序遍历后续遍历精确地对应于一个LR分析器将一个产生式规约为它的开始符号的过程在LR分析过程中我们实际上不需要构造分析树的结点

L属性的SDD及其相容分析方法每个属性要么是综合属性(S属性定义属于L属性定义) 要么是继承属性且产生式A X1X2 Xn中计算Xi.a的规则只能使用依赖图的边 A的继承属性 Xi左边的文法符号Xj的继承属性或综合属性 Xi自身的继承或综合属性且这些属性之间的依赖关系不形成环继承属性从左到右从上到下综合属性从下到上在扫描过程中计算一个属性值时和它相关的依赖属性都已经计算完毕

L属性的SDD及其相容分析方法例如教材例5.8所示SDD是L属性的再如教材例5.9 任何包含下列产生式和规则的SDD都不是L属性的

L属性的SDD及其相容分析方法例如变量类型声明的语法制导定义是一个L属性定义产生式语义规则 D L.in = T.type TL T int T. type = integer T T. type = real real L L1, L1.in = L.in; id addtype(id.entry, L.in) L id addtype(id.entry, L.in) 相容分析顺序 D T 4 type int in 9 in 5 L 8 in 7 L 10, id1 1 entry L 6, id2 2 entry id3 3 entry

具有受控副作用的语义规则一个没有副作用的SDD称为属性文法一个属性文法的规则仅通过其他属性值和常量值来顶一个另一个属性值增加了描述的复杂度比如语法分析时如果没有副作用标识符表就必须作为属性传递可以把标识符表作为全局变量然后通过副作用函数来添加新标识符受控的副作用不会对属性求值产生约束即可以按照任何拓扑顺序求值不会影响最终结果或者对求值过程添加简单的约束

受控副作用的例子 L En print(e.val) 通过副作用打印出E的值总是在最后执行而且不会影响其它属性的求值变量声明的SDD中的副作用 addtype将标识符的类型信息加入到标识符表中只要标识符不被重复声明标识符的类型信息总是正确的

9.3 语法制导翻译的应用

语法制导翻译的应用语法制导翻译技术主要应用类型检查处理基本类型和数组类型的L属性定义中间代码生成抽象语法树---一种中间代码表示形式

构造AST 抽象语法树AST 语法树是分析树的浓缩表示算符和关键字是作为内部结点语法制导翻译可以基于分析树也可以基于语法树语法树的例子 if B then S1 else S2 8+5 2 + if-then-else B S1 S2 * 8 5 2

构造AST 抽象语法树每个结点代表一个语法结构对应于一个运算符结点的每个子结点代表其子结构对应于运算分量表示这些子结构按照特定方式组成了较大的结构可以忽略掉一些标点符号等非本质的东西语法树的表示方法每个结点用一个对象表示对象有多个域 Leaf(op, val)创造一个叶子对象返回一个指向叶子结点对应新记录的指针 Node(op, c1, c2,, ck) 其中c1-ck为子结点

构造AST (S属性SDD) 例1 S属性SDD 构造语法树的语法制导定义 p203, 5.11 a-4+c

构造AST (S属性SDD) 例1 S属性SDD 构造语法树的语法制导定义 p203, 5.11 a-4+c, 构造步骤 p1=new Leaf(id, entry_a) p2=new Leaf(num, 4); p3=new Node( -, p1,p2); p4=new Leaf(id, entry_c); p5=new Node( +, p3,p4);

构造AST (S属性SDD) 例2 S属性SDD 构造语法树的语法制导定义产生式 E E1 + T E T T T1 F T F F (E) F id F num 语义规则 E.nptr = mknode( +, E1.nptr, T.nptr) E.nptr = T.nptr T.nptr = mknode(, T1.nptr, F.nptr) T.nptr = F.nptr F.nptr = E.nptr F.nptr = mkleaf (id, id.entry) F.nptr = mkleaf (num, num.val)

构造AST (S属性SDD) a+5 b的语法树的构造 E.nptr T.nptr + E.nptr T.nptr T.nptr + F.nptr F.nptr num id id 指向符号表中a的入口 F.nptr id num 5 id 指向符号表中b的入口

构造AST (L属性SDD) 例3 L属性SDD 构造语法树的语法制导定义 p205, 5.12 消除左递归

构造AST (L属性SDD) 例3 L属性SDD 构造语法树的语法制导定义 p205, 5.12 a-4+c 构造依赖图

构造AST (L属性SDD) 例3 L属性SDD 构造语法树的语法制导定义 p205, 5.12 a-4+c 不同的语法分析树与抽象语法树

基本类型和数组类型的L属性定义例4 简化的类型表达式的语法类型包括两个部分 T B C 基本类型B 分量C 分量形如[3][4] 表示3X4的二维数组 e.g. int [3][4] 数组构造算符array array(3,array(4,int)) 表示抽象的3X4的二维数组

基本类型和数组类型的L属性定义例4 简化的类型表达式的语法 int [2][3]的语法注释树 array(2, array(3, integer))

SDT 9.4 语法制导的翻译方案

语法制导的翻译方案语法制导的翻译方案(syntax-directed translation scheme, SDT) SDD的一种补充在产生式体内嵌入了程序片段的一个CFG 程序片段成为语义动作可以出现在产生式体中任何地方用 {语义动作}表示

可在语法分析过程中实现的SDT 实现SDT时实际上并不会真的构造语法分析树而是在分析过程中执行语义动作即使基础文法可以应用某种分析技术仍可能因为动作的缘故导致此技术不可应用我们主要关注用SDT实现以下两类重要的SDD 基本文法是LR的且SDD是S属性的基本文法是LL的且SDD是L属性的

可在语法分析过程中实现的SDT 判断是否可在分析过程中实现将每个语义动作替换为一个独有的标记非终结符号每个标记非终结符号M的产生式为M ε 如果新的文法可以由某种方法进行分析那么这个SDT就可以在这个分析过程中实现注意这个方法没有考虑变量值的传递等要求

判断SDT可否用特定分析技术实现例子 L E n M1 M1 ε E E+T M2 M2 ε E T M3 M3 ε

面向S属性SDD的后缀翻译方案后缀SDT 所有动作都在产生式最右端的SDT 文法可以自底向上分析且SDD是S属性的必然可以构造出后缀SDT 构造方法将每个语义规则看作是一个赋值语义动作将所有的语义动作放在规则的最右端

面向S属性SDD的后缀翻译方案实现桌上计算器的后缀SDT 注意动作中对属性值的引用我们允许语句引用全局变量局部变量文法符号的属性文法符号的属性只能被赋值一次

面向S属性SDD的后缀翻译方案后缀SDT的语法分析栈实现可以在LR语法分析的过程中实现归约时执行相应的语义动作定义用于记录各文法符号的属性的union结构栈中的每个文法符号或者说状态都附带一个这样的union类型的值在按照产生式A XYZ归约时 Z的属性可以在栈顶找到 Y的属性可以在下一个位置找到 X的属性可以在再下一个位置找到

面向S属性SDD的后缀翻译方案分析栈实现的例子假设语法分析栈存放在一个被称为stack的记录数组中下标top 指向栈顶 stack[top]是这个栈的栈顶 stack[top-1]指向栈顶下一个位置如果不同的文法符号有不同的属性集合我们可以使用union来保存这些属性值归约时能够知道栈顶向下的各个符号分别是什么,因此我们也能够确定各个union中究竟存放了什么样的值

面向S属性SDD的后缀翻译方案分析栈实现的例子注意 stack[top-i]和文法符号的对应

产生式内部带有语义动作的SDT 例把有加和减的中缀表达式翻译成后缀表达式例如如果输入是8+5 2 则输出是8 5 + 2 E TR R addop T {print (addop.lexeme)} R1 T num {print (num.val)} E T R num {print (8)} R num{print (8)}addop T{print (+)}R num{print(8)}addop num{print(5)}{print (+)}R {print(8)}{print(5)}{print(+)}addop T{print( )}R {print(8)}{print(5)}{print(+)}{print(2)}{print( )}

产生式内部带有语义动作的SDT 产生式内部带有语义动作的SDT 动作左边的所有符号(以及动作)处理完成后就立刻执行这个动作 B X{a}Y 自底向上分析时在X出现在栈顶时执行动作a 自顶向下分析时在试图展开Y或者在输入中检测到Y的时刻执行a

产生式内部带有语义动作的SDT 不是所有的SDT都可以在分析过程中实现例如打印前缀表达式后缀SDT以及L属性对应的SDT可以在分析时完成移入/规约冲突 M2 ε M4 ε 移入数字

SDT的基本实现方法 SDT的基本实现方法忽略语义动作对输入进行语法分析产生一个语法分析树检查每个内部结点N 如果产生式为A α 将α中各个动作当做 N的附加子结点加入使得N的子结点从左到右和α中符号及动作完全一致对分析树进行前序遍历在访问虚拟结点时执行相应动作

SDT的基本实现方法例如语句3*4*5的分析树如右 DFS可知动作执行顺序 A71,A5, A72, A41, A73, A42, A2 注意一个动作的不同实例所访问的属性值属于不同的结点 E A 2 T 3 T * F A42 2 T 1 F * A5 digit:3 F A41 digit:4 A71 digit:5 A7 3 A72

SDT的基本实现方法再如语句3*5+4的分析树如右分析后得到+*345

消除左递归时SDT的转换如果动作不涉及属性值可以把动作当作终结符号进行处理然后消左递归原始的产生式 E E1+T {print( + );} E T 转换后得到 E TR R + T {print ( + );} R R ε

消除左递归时SDT的一般转换形式假设只有单个递归产生式且该左递归非终结符只有单个属性引入继承属性R.i 用来累计从A.a的值开始不断应用g所得到的结果 XYY

消除左递归时 SDT 的一般转换形式

面向L属性SDD的翻译方案产生式内部带有语义动作的SDT 将一个L属性的SDD转换为一个SDT的规则如下将每个语义规则看作是一个赋值语义动作将赋值语义动作放到相应产生式的适当位置计算A的继承属性的动作插入到产生式体中对应的A的左边如果A的继承属性之间具有依赖关系则需要对计算动作进行排序计算产生式头的综合属性的动作在产生式的最右边

面向L属性SDD的翻译方案例数学排版语言EQN E sub 1.val S B B B1 B2 B B1 sub B2 B text E 1.val

面向L属性SDD的翻译方案例数学排版语言EQN 语法制导定义 E sub 1.val E.val 1 产生式 S B B B1 B2 B B1 sub B2 B text 语义规则 B.ps = 10; S.ht = B.ht B1.ps = B.ps; B2.ps = B.ps; B.ht = max(b1.ht, B2.ht ) B1.ps =B.ps; B2.ps = shrink(b.ps); B.ht = disp (B1.ht, B2.ht ) B.ht = text.h B.ps

面向L属性SDD的翻译方案例数学排版语言EQN 翻译方案 S {B.ps = 10 } B继承属性的计算 B {S.ht = B.ht } 位于B的左边

面向L属性SDD的翻译方案例数学排版语言EQN 翻译方案 S {B.ps = 10 } B综合属性的计算 B {S.ht = B.ht } 放在右部末端

面向L属性SDD的翻译方案例数学排版语言EQN 翻译方案 S B B1 B2 B B text {B.ps = 10 } B {S.ht = B.ht } {B1.ps = B.ps } {B2.ps = B.ps } {B.ht = max(b1.ht, B2.ht ) } { B1.ps =B.ps } B1 sub { B2.ps = shrink(b.ps) } B2 {B.ht = disp (B1.ht, B2.ht ) } {B.ht = text.h B.ps }

面向L属性SDD的翻译方案例继承属性 next 语句结束后应该跳转到的标号 true false C为真/假时应该跳转到的标号综合属性code表示代码

面向L属性SDD的翻译方案语义动作 (a) (b) (c) (d) L1=new( ) L2=new( ) 计算临时值 C.false = S.next; C.true = L2 计算C的继承属性 S1.next = L1 计算S1的继承属性 S.code= 计算S的综合属型根据放置语义动作的规则得到如下SDT (b)在c之前 (c)在s1之前 (d)在最右端 (a)可以放在最前面

作业图5-4的SDD扩充如右图所示为教材P198练习5.1.1的第二个表达式 P 语法规则画出注释语法树和依赖图教材P203 5.2.4 教材P207 5.3.1 1) L -> En L.val = E.val 2) E -> TE' E'.inh = T.val E.val = E'.syn 3) E' -> +TE1' E_1'.inh = E'.inh + T.val E'.syn = E_1'.syn 4) E' -> ε E'.syn = E'.inh 5) T -> FT' T'.inh = F.val T.val = T'.syn 6) T' -> *FT1' T_1'.inh = T'.inh * F.val T'.syn = T_1'.syn 7) T' -> ε T'.syn = T'.inh 8) F -> (E) F.val = E.val 9) F -> digit F.val = digit.lexval