第6章属性文法和语法制导翻译.ppt

第六章属性文法和语法制导翻译 语义分析 是编译程序最实质性的工作 语义分析程序在整个编译过程中 首次对源程序的语义做出解释 引起源程序发生质的变化 而词法分析和语法分析仅是对源程序形式上的识别和处理 高级程序语言结构的形式化描述已经有比较成熟的技术 由于这种形式化描述的完善 使分析器的构造甚至自动构造是比较容易的 1 编译程序的语义分析涉及到语言的语义 语义形式化是个专门的研究课题 形式语义学 如指称语义学 公理语义学 操作语义学等 的研究从20世纪60年代已经开始 并且在理论研究方面也有了重要的进展 但不论哪种方法 其本身的符号系统比较繁杂 其描述文本不易读 尚不便借助这些形式系统自动完成语义处理任务 并且在工程实现和应用方面还有一定的差距 2 目前实际应用中较流行的语义描述和语义处理方法主要还是属性文法和语法制导翻译方法 但它仍不是一种形式系统 只是比较接近形式化 语法制导翻译方法的实质是在语法分析过程中同时进行语义处理的翻译技术 这种方法使用属性文法为工具来说明程序设计语言的语义 3 第六章属性文法和语法制导翻译 6 1属性文法6 2基于属性文法的处理方法6 3S 属性文法的自下而上计算6 4L 属性文法和自顶向下翻译6 5自下而上计算继承属性 4 6 1属性文法 一 基本概念 1 属性 广义 用以描述事物或人的特征 性质 品质等等 属性文法中 代表与文法符号相关的信息 其信息值即为属性值 例如 其类型 值 代码序列 符号表内容等 5 6 1属性文法 1 属性与变量一样 可以进行计算和传递 2 属性加工的过程即是语义处理的过程 3 属性综合属性 用于 自下而上 传递信息 继承属性 用于 自上而下 传递信息 6 6 1属性文法 2 语义规则 为文法的每一个产生式配备的属性的计算规则 称为语义规则 3 属性文法 上下文无关文法 语义规则 属性文法 7 6 1属性文法 二 基本规则 1 语义规则的形式 产生式A 的语义规则的一般形式为b f c1 c2 ck 其中 1 f是一个函数 2 或者b A的综合属性 且c1 c2 ck是 中文法符号的属性 3 或者b 中某个文法符号的继承属性 且c1 c2 ck是A或 中任何文法符号的属性 属性b依赖于属性c1 c2 ck 8 6 1属性文法 2 VT VN的属性 1 VT 只有综合属性 由词法分析器提供 2 VN 既可有综合属性也可有继承属性 文法开始符号S的所有继承属性作为属性计算前的初始值 9 6 1属性文法 3 属性的计算 获得 1 产生式右边的继承属性产生式左边的综合属性 2 产生式左边的继承属性产生式右边的综合属性 10 6 1属性文法 例6 1 C d B c 1A b A a B c 产生式A BC的规则 C d 右部继承属性A b 左部综合属性A a 左部继承属性B c 右部综合属性 11 6 1属性文法 例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 12 addtype id entry L in T type integer T type real L1 in L in L in T type addtype id entry L in 13 14 6 1属性文法 二 综合属性 1 语法树中 一个结点的综合属性的值由其子结点的属性值确定 2 通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值 S 属性文法 仅使用综合属性的属性文法 15 6 1属性文法 例6 3 例6 2的表中定义的属性文法说明了一个台式计算器 该计算器读入一个可含数字 括号和 运算符的算术表达式 并打印表达式的值 每个输入行以n作为结束 假设表达式为3 5 4 后跟一个换行符n 则程序打印数值19 其带注释的语法树 16 三 继承属性 1 语法树中 一个结点的继承属性由此结点的父结点和 或兄弟结点的某些属性确定 6 1属性文法 用继承属性来表示程序设计语言结构中的上下文依赖关系很方便 17 6 1属性文法 例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 18 输入串 realid1 id2 id3的带注释的语法树 D T type real L in real real L in real L in real id2 id3 id1 19 1 构造依赖图的方法 6 2基于属性文法的处理方法 2 遍历语法树的方法 单词符号串 语法分析树 计算 3 可用一遍扫描实现属性文法的语义规则计算 20 一 依赖图 1 定义 一个表示一棵语法树中结点的继承属性和综合属性之间的相互依赖关系的有向图 6 2基于属性文法的处理方法 21 2 依赖图的构造方法 1 构造依赖图以前 先为每一个包含过程调用的语义规则引入一个虚综合属性b 在每一个语义规则均写成b f c1 c2 ck 的形式 2 在依赖图中为每一个属性设置一个结点 3 若属性b依赖于属性c 则从属性c的结点有一条有向边连到属性b的结点 6 2基于属性文法的处理方法 22 A a X i X x Y y 6 2基于属性文法的处理方法 23 3 例题 例6 6 将下面的产生式应用于语法树中 产生式语义规则E E1 E2E val E1 val E2 val E Val是从E1 val和E2 val综合得出 6 2基于属性文法的处理方法 24 addtype id entry L in T type integer T type real L1 in L in L in T type addtype id entry L in 25 D T L real L L id2 id3 id1 a4 a6 a7 a8 a9 a10 a1 a2 a3 a5 a4 reala5 a4Addtype id3 entry a5 a7 a5 addtype id2 entry a7 a9 a7 Addtype id1 entry a9 拓扑序列a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 26 二 树遍历的属性计算方法 1 方法 A 前提 假设语法树已经建立起来了 且树中已有如下信息 开始符号 继承属性终结符 综合属性 B 遍历 以某种次序遍历语法树 直至计算出所有属性 遍历方法 深度优先 从左到右 6 2基于属性文法的处理方法 27 6 2基于属性文法的处理方法 2 算法 While还有未被计算的属性doVisitNode S S是开始符号 procedureVisitNode N Node beginIfN是一个非终结符then 假设它的产生式为N X1 Xm fori 1tomdoifnotXi VTthen 即Xi是非终结符 begin计算Xi的所有能够计算的继承属性 VisitNode Xi end 计算N的所有能够计算的综合属性end 注 只要文法的属性是非循环定义的 则每次扫描至少有一个属性值被计算出来 28 其中 S有继承属性a 综合属性b X有继承属性c 综合属性d Y有继承属性e 综合属性f Z有继承属性h 综合属性g 3 举例 例6 9 考虑下表所给的属性文法G 6 2基于属性文法的处理方法 29 S a 0 X Y Z x y a z S a 0 X Y Z h 0g 1 x y b z 30 S a 0 b 0 X c 1d 2 Y e 0f 0 Z h 0g 1 x y d z S a 0 b 0 X c 1d 2 Y Z h 0g 1 x y c z 31 6 2基于属性文法的处理方法 三 一遍扫描的处理方法 1 特点 在语法分析的同时计算属性值 而不是语法分析构造语法树之后进行属性的计算 而且无需构造实际的语法树 注 采用该处理方法 当一个属性值不再用于计算其它属性值时 编译程序就不必再保留这个属性值 如果需要 可把语义值存到文件中 32 6 2基于属性文法的处理方法 2 相关因素 1 所使用的语法分析方法 L 属性文法 一遍扫描的自上而下分析S 属性文法 一遍扫描的自下而上分析 2 属性的计算次序 33 上节课的内容 属性文法 属性 综合属性 继承属性 产生式 属性计算规则 语义规则 A X1 XK A a Xi x 属性计算方法 123 S 属性文法 6 3L 属性文法 6 4 34 6 2基于属性文法的处理方法 例2 构造表达式产生抽象语法树 AbstractSyntaxTree 的属性文法 1 定义 在语法树中去掉那些对翻译不必要的信息 从而获得更有效的源程序中间表示 这种经变换后的语法树称之为抽象语法树 注 抽象语法树中 操作符和关键字都不作为叶结点出现 35 抽象语法树 内部结点 外部结点 操作符关键字 标识符常数 如 a 3 b的抽象语法树 a 3 b 36 6 2基于属性文法的处理方法 2 如何建立表达式的抽象语法树 1 方法 通过为每一个运算分量或运算符号都建立一个结点来为子表达式建立子树 运算符号结点的各个子结点分别表示该运算符号的各个运算分量的子表达式组成的子树的根 37 6 2基于属性文法的处理方法 2 抽象语法树中每个结点可由包含几个域的记录来实现 运算符号结点 一个域 运算符号其它域 指向运算符号分量的结点的指针结点 附加的域 存放结点的属性值 指向属性值的指针 38 6 2基于属性文法的处理方法 39 6 2基于属性文法的处理方法 例6 10 下面一系列函数调用建立了表达式a 4 c的抽象语法树 如图 在这个序列中 p1 p2 p5是指向结点的指针 entrya和entryc分别是指向符号表中的标识符a和c的指针 id id num4 toentryfora toentryforc 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 4 如何设计产生表达式抽象语法树的属性文法 E E1 TE E1 TE TT E T idT num 41 为表达式建立抽象语法树的属性文法 T nptr mkleaf num num val T nptr mkleaf id id entry T nptr E nptr E nptr T nptr E nptr mkNode E1 nptr T nptr E nptr mkNode E1 nptr T nptr 42 E nptr T nptr E nptr E T nptr num T nptr id id 带注释的语法分析树 Toentryfora Toentryforc 43 6 3S 属性文法的自下而上计算 1 S 属性文法 只含综合属性的属性文法 2 S 属性文法的翻译借助于LR分析器来实现 LR分析器 44 3 对分析栈改造 状态栈符号栈属性栈 S0 Sm 1xx val Smyy val 45 3 对分析栈改造自底向上分析法中 栈 存放已经分析过的子树的内容附加域 存放综合属性数组State 元素 一个指向LR 1 分析表的指针 索引 指向表中某个状态 文法符号为隐含在State中而不需存在栈中数组Val 符号的属性值 46 6 1属性文法 例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 47 状态栈符号栈属性栈 S0 Sm 2EE val Sm 1 考虑 E E1 TE val E1 val T val SmTT val S EE val 转换为 E E1 Tval ntop val top 2 val top 48 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 把下面文法的语义规则转换为对属性栈的操作 Print val top Val ntop val top 2 val top Val ntop val top 1 Val ntop val top 2 val top 49 6 11举例 L EnE E1 TE TT T1 FT FF E F digit输入串3 5 4n 为表达式建立抽象语法树的属性文法 T nptr mkleaf num num val T nptr mkleaf id id entry T nptr E nptr E nptr mkNode E1 nptr T nptr E nptr mkNode E1 nptr T nptr E nptr T nptr nptr ntop mkNode nptr top 2 nptr top nptr ntop mkNode nptr top 2 nptr top nptr ntop nptr top 1 nptr ntop mkleaf id id entry nptr ntop mkleaf num num val 51 6 4L 属性文法和自顶向下翻译 对语法分析树进行一次深度优先遍历就能计算出所有的属性 即在自上而下建立语法树的过程中完成对属性的计算 L 属性文法 52 A X1 Xj Xk A X1 Xj Xk A a Xj x 53 6 4L 属性文法和自顶向下翻译 L 属性文法 对任意产生式A X1X2 Xn 其每个语义规则中的属性或者是综合属性 或者Xj是一个继承属性 且仅依赖与 1 X1X2 Xj 1 2 A的继承属性 S 属性文法是L 属性文法的一个特例 54 6 4L 属性文法和自顶向下翻译 判定下面属性文法是否是L 属性文法 Q i q R s 55 6 4 1翻译模式 属性文法是语言翻译的高级规范说明 翻译模式 描述文法符号属性的语义规则和计算次序 E TRR addopT pr addop lex R1 T num pr num val 56 翻译模式举例 E TRR addopT pr addop lex R1 T num pr num val 输入 9 5 2 E T R R R 9 Pr 9 T Pr T Pr 5 Pr 5 2 Pr 2 深度优先遍历后输出 95 2 建立翻译模式的方法 1 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来 2 一个动作不能引用这个动作右边符号的综合属性 3 产生式左边非终结符的综合属性只能在它所引用的所有属性都计算出来以后才能计算 通常这类动作可放在产生式右端的末尾 58 例 把下面属性文法修改为翻译模式 59 S B ps 10 B S ht B ht B B1 ps B ps B1 B2 ps B ps B2 B ht max B1 ht B2 ht 60 6 4 2自顶向下翻译 消除左递归 规则P P 1 P P 2 P P 直接左递归 P P 1 P 2 P m 1 2 n i 消除方法 P 1P 2P nP P 1P 2P mP 在自顶向下分析过程中 在消除左递归的同时考虑属性计算 这样许多属性文法可以使用自顶向下来实现 适用综合和继承属性的计算 61 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 s T E T val E val T num T val num val E T R R R 9 T T 2 5 计算表达式9 5 2 val 9 val 5 val 2 63 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 E T val 9 R i 9 R i 4 R i 6 Num val 9 T val 5 T val 2 Num val 2 Num val 5 计算表达式9 5 2 递归过程 综合属性计算 E val R s R s R s 64 转换左递归翻译模式的一般方法 A A1Y A a g A1 a Y y A X A a f X x A XRR YR1R 带注释语法树 A a g g f X x Y1 y Y2 y A a g f X x Y1 y A a f X x X Y2 Y1 A R s R s R s P15