属性文法和语法制导翻译 授课:胡静.

Slides:



Advertisements
Similar presentations
第一章 棉花初加工与纺纱原料选配 第一节 轧棉与脱糖 第二节 配棉 第三节 化纤原料的选配 第四节 配料方法与配料计算.
Advertisements

成功八步 成功一定有方法 失败一定有原因 银河系统.
医用超声耦合剂 南京朗众药业公司总代理.
实 验 设 计 基 础.
第六课 遗传与变异 第六课时 性别决定和伴性遗传.
草虫的村落 执教者:罗小妍 升华        交往1        交往2        演奏        劳动        分工        回应        拓展       
荷塘月色.
5.冷遇是曹雪芹、施耐庵等伟大作家都曾受到过的因社会反对作品所欲传达的理念、不了解意义、不喜欢作品所叙述的事实等原因造成的小则禁书焚书、大则作者遭殃的社会对伟大作家的报偿。(以2为主干的2分,按照例子、原因、结果限定次序切句子通顺的4分,次序混乱扣1分) 6.花香一刻,让您的生活更鲜艳芳菲 塑造健美身体,创造美好生活。
示范流程培训课件.
点此播放教学视频 河中石兽 纪昀 本资源来自初中学科网(
普 通 话.
编 译 原 理 指导教师:杨建国 二零一零年三月.
中学生社会适应问题及其调适.
订单合并拆分功能详解 荷叶.
第五章 语法制导的翻译 赵建华 南京大学计算机系 2010年3月.
小学语文毕业总复习 ( 基础知识部分) 牡丹区实验小学侯宪梅.
教学的内容和方法.
26个英语字母 let's go!.
小学语文教学论 湖南第一师范文史系.
义务教育课程标准实验教科书(人教版)语文七年级下册
第二章 控制系统的数学模型 2-0 引言 2-1 微分方程的建立及线性化 2-2 传递函数 2-3 结构图 2-4 信号流图.
汽车在( )上行驶.
大 堰 河,我 的 保 姆 ◇艾青.
习题与试题 认真复习,重点是掌握基本概念。基本概念掌握了,相当一部分试题的解就有了
桥梁工程 —精品课程 第2篇 梁桥 土木与建筑工程学院 道桥教研室.
销售部工作总结 二O一六年五月.
语文版九年级(下) 多媒体课件.
跳楼价 亏本大甩卖 清仓处理 买一送一 5折酬宾. 跳楼价 亏本大甩卖 清仓处理 买一送一 5折酬宾.
第三单元 散文(2) 9 议论散文两篇.
组织与点评 模拟招聘会.
袁宏道.

雷电颂 郭沫若.
雷电颂 郭沫若. 雷电颂 郭沫若 屈 原 的 故 事 战国时代,称雄的秦、楚、齐、燕、赵、韩、魏七国,争城夺地,互相杀伐,连年混战。
项目九 应收、应付款管理.
枣核 第六课.
XX信托 ·天鑫 9号集合资金信托计划 扬州广陵
機車第六篇 事故預防 單元二 行駛中注意事項.
Part5语法分析 授课:胡静.
CH6.属性文法语法制导翻译 《程序设计语言编译原理》 陈火旺等编著 2000年第3版
编译原理与技术 第7章 中间代码生成 3学时.
邶风·谷风 xí xí gǔ fēng ,yǐ yīn yǐ yǔ 。mǐn miǎn tóng xīn ,bù yí yǒu nù 。
第六章 属性文法和语法制导翻译 网上教学系统: : 编译原理
第四章 语法制导的翻译 本章内容 1、介绍语义描述的一种形式方法:语法制导的翻译,它包括两种具体形式 语法制导的定义 翻译方案
建國國小英語教學線上課程 字母拼讀篇(一) 製作者:秦翠虹老師、林玉川老師.
一元二次方程的解法复习.
19、“精彩极了”和“糟糕透了” 生字学习 阅读理解 拓展练习.
Part5语法分析 授课:胡静.
静默草原 鲍尔吉·原野 引 言 敕勒歌    敕勒川,阴山下,   天似穹庐,笼盖四野。   天苍苍,野茫茫,   风吹草低见牛羊。
运 筹 学 第八章 整 数 规 划.
语义分析简介 编译程序的目标:将源程序翻译成为语义等价的目标程序。 语义分析的主流技术:
容斥原理 若干应用 王瑶 张梦微 张雯露 2019/1/11.
编译原理与技术 语法制导翻译 2019/1/17 《编译原理与技术》讲义.
Kàn yī kàn yī 看 一 看(一) 单击页面即可演示.
孔繁森.
第一模块 向量代数与空间解析几何 第四节 平面及其方程 一、平面的点法式方程 二、平面的一般方程 三、两平面的夹角.
语法制导的翻译 (Syntax-Directed Translation)
雪,甲骨文(羽,白色轻盈的绒毛) (雨点),比喻天空中纷纷扬扬的 羽状飘落物。 造字本义:零度以下的低温状态,空气中的部分
2015长沙事业单位 政策解读 中公教育:邓颖莉 主讲:XX.
关爱华夏学子 服务民族教育 金星教育小学课件 1 桂林山水 金星教育集团 人教版小学语文四年级下册.
编译原理与技术 第4章 语法制导的翻译 6学时.
第五章 自底向上分析方法 LR(0)分析法 1 LR(K)分析法 第一个L表示:相应的语法分析将按自左至右的顺序扫描输入符号串;
第六章 语法制导的翻译 本章内容 介绍一种语义描述方法:语法制导的翻译,介绍语法制导的翻译的实现方法。
语音 行唐县上方职中 乔志峰.
猜谜语 像 云 不 是 云, 像 烟 不 是 烟, 风 吹 轻 轻 飘, 日 出 慢 慢 散。 (打一自然现象)
多收了三五斗 叶圣陶.
第四章 语法分析 南京大学计算机系 戴新宇
毒災聯合防救 無預警測試.
鏈球的力學分析 日本奧運鏈球冠軍(82米91) 室伏廣治因小腿肌肉受傷,退出杜哈亞運。 俄羅斯「鐵娘子」泰亞娜.李森科 九十五年八月八日在
第8章 语法制导翻译与中间代码生成.
Presentation transcript:

属性文法和语法制导翻译 授课:胡静

属性文法

目录 虽然形式语义学的研究已经取得了许多重大进展,但目前在实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译。 本章研究内容: 上下文无关文法所产生的语言的翻译。 把属性附加到代表语法结构的文法符号上,可以将语义信息和程序设计语言的结构联系起来。 属性的值是用与文法产生式相关联的“语义规则”来计算的。 涉及的概念 属性文法:关于语言翻译的高层次规格说明,隐蔽了具体实现细节,不显式的说明翻译发生的顺序(属性文法) 语法制导翻译:指明了语义规则的计算顺序,说明实现细节。

语义规则计算可完成的工作 生成代码 在符号表中保存信息 发出错误信息 对输入符号串翻译的过程就是对语义规则求值的过程

属性文法 是在上下文无关文法的基础上,为每个文法符号(终结符或非终结符)配备若干相关的“值”。 语法制导定义=文法+符号的相关属性集 属性代表与文法符号相关的信息,如类型、值、代码序列、符号表内容 属性可以代表任何对象:字符串,数组,类型,内存单元或其他对象 语法制导定义=文法+符号的相关属性集 属性分为两个子集:综合属性、继承属性 如果把文法符号的结点看成记录,包含若干存储信息的域,那么属性就相当于域的名字

属性文法 分析树节点上属性值由产生式的语义规则来定义 依赖图 注释分析数 综合属性值:通过分析树中其子节点的属性值计算出来的 继承属性值:由该节点的兄弟节点及父节点的属性值计算出来的 依赖图 语义规则建立了属性间的依赖关系,这种关系用图来表示就是依赖图 依赖图表示了语义规则的计算顺序 注释分析数 每个节点都有属性值的分析树叫做注释分析树 计算节点属性的过程称为注释或者装饰分析树

属性文法 在语法制导定义中,每个产生式A→α都有一个形如b=f(c1,c2,...,ck)的语义规则集合与之相关联,其中f是函数,并且满足下面条件之一 b是A的一个综合属性,且c1,c2,...,ck是该产生式文法符号的属性 b是产生式右部某个文法符号的一个继承属性,且c1,c2,...,ck是A或者产生式右边任何文法符号的属性 在这两种情况下,我们说属性b依赖于c1,c2,...,ck 。 特别要强调的是: 终结符只有综合属性,它们由词法分析器提供; 非终结符既可有综合属性也可有继承属性,文法开始符号的所有继承属性作为属性计算前的初始值。

关于属性文法的说明 通常,这种函数的被写为表达式。 其他的语义规则被写为过程调用或者程序段——定义产生式左部非终结符的虚综合属性值 一般说来,对于出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。 属性计算规则中只能使用相应产生式中的文法符号的属性,这有助于在产生式范围内“封装”属性的依赖性。 出现在产生式左边的继承属性和出现在产生式右部的综合属性不由所给产生式的属性计算规则进行计算,它们由其他产生式的属性规则计算或由属性计算器的参数提供。

继承属性和综合属性的计算举例 对于产生式A→BC来讲 直观上来讲,这个产生式可以计算A的综合属性、B和C的继承属性。 那么对于A的继承属性,可能需要根据某个类似于X→…A…的产生式求的。 同样的B和C的综合属性可能需要根据某个类似于B→β,以及C →γ的产生式求的。

属性文法举例 产生式 语义规则 L→En print(E.val) E→E1 + T E.val := E1.val + T.val E→T 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

S-属性文法 S-属性文法 在语法树中,一个结点的综合属性的值由其子结点的属性值决定。 仅使用综合属性的属性文法称为S-属性定义

综合属性举例 L n E .val=19 E .val=15 + T .val=4 T .val=15 F .val=4 3*5+4 T 产生式 语义规则 L→En 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 L n E .val=19 E .val=15 + T .val=4 T .val=15 F .val=4 3*5+4 T .val=3 * F .val=5 digit .val=4 F .val=3 digit .val=5 digit .lexval=3

继承属性 在语法树中,一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。 继承属性在程序设计语言中的作用 表示程序设计语言上下文结构的依赖性 对于赋值号,其左边和右边的标识符在操作的时候需要提供的属性不同,这时候就要跟踪标识符的继承属性。如果在赋值号左边,则需要地址,右边则需要值。 虽然我们总是可以只用综合属性来改写语法制导定义,但是使用带有继承属性的属性文法有时更为自然。

继承属性的例子 D L .in=real T .type=real , real L .in=real id3 , L .in=real 产生式 语义规则 D→TL L.in := T.type T→int T.type := integer T→real T.type := real L→L1 , id L1.in := L.in addtype(id.entry, L.in) L→id D L .in=real T .type=real , real L .in=real id3 , L .in=real id2 real id1,id2,id3 id1

语法制导翻译 基于属性文法的处理过程通常是: 这种由源程序的语法结构驱动的处理办法就是语法制导翻译法。 对符号串进行语法分析, 构造语法分析树 根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。 这种由源程序的语法结构驱动的处理办法就是语法制导翻译法。 在某些情况下,在进行语法分析的同时完成语义规则的计算而无须明显地构造语法树或构造属性之间的依赖图。(一遍处理,L-属性文法) 语义规格的 计算顺序 输入符号串 分析树 依赖图

依赖图 依赖图是有向图 依赖图的构造方法 表示了分析树中各节点属性间的依赖关系。其中属性包括继承属性和综合属性 表示了节点属性的计算先后顺序。如果分析树中某个节点的属性b依赖于属性c,那么在该节点处b的语义规则必须在c的语义规则之后计算。 依赖图的构造方法 为每个包括过程调用的语义规则引入一个虚综合属性b,把每条语义规则都变成b=f(c1,c2,...,ck)的形式 依赖图的每个结点表示一个属性 边表示属性间的依赖关系。如果属性b依赖于属性c,那么从c到b就有一条有向边

依赖图举例 D L T real id3 , .in=real .type=real id2 id1 D y 5 in L 6 T type 产生式 语义规则 D→TL L.in := T.type T→int T.type := integer T→real T.type := real L→L1 , id L1.in := L.in addtype(id.entry, L.in) L→id D L T real id3 , .in=real .type=real id2 id1 D y 5 in L 6 T type 4 real y 7 in L 8 , id3 entry 3 如果一属性文法不存在属性之间的循环依赖关系,那么称该文法为良定义的 y id2 entry 2 9 in L 10 , id1 entry 1

属性的计算顺序 无环有向图的拓扑排序 无环有向图中节点m1,m2,…,mk的拓扑排序是:若mi→mj是从mi到mj的边,那么在此排序中mi先于mj 依赖图的任何拓扑排序都给出了一个分析树中各节点语义规则计算的正确顺序,即在计算f之前,语义规则b=f(c1,c2,...,ck)中的依赖属性c1,c2,...,ck都是已知的 属性文法所说明的翻译可以按照下面的步骤进行 最基本的文法用于构造输入串的分析树 用前面的方法构造依赖图 从依赖图的拓扑排序可以得到语义规则的计算顺序 按该顺序计算语义规则即可得到输入串的翻译

属性文法计算顺序举例 a4 := real a5 := a4 addtype(id3.entry, a5) a7 := a5 in y entry 1 2 3 4 5 6 7 8 9 10

计算语义规则的方法 分析树法: 基于规则的方法 忽略规则的方法 后两种方法在编译时都不必显式的构造依赖图 在编译时,这种方法从分析树所构成的依赖图的拓扑排序中得到语义规则的计算顺序。 如果分析树的依赖图中有环路,这种方法将失败 基于规则的方法 对于每一个产生式,计算该产生式所关联的属性的顺序在编译器构造时已经预先确定好了 忽略规则的方法 选择计算顺序时不考虑语义规则。如果翻译是在语法分析过程中进行的,那么计算顺序的选择就由语法分析方法来确定。 后两种方法在编译时都不必显式的构造依赖图

树遍历的属性计算方法 通过树遍历计算属性值的方法都假设语法树已经建立,并且数中已带有开始符号的继承属性和终结符的综合属性。 最常用的遍历方法是深度优先,从左到右的遍历方法 只要文法的属性是非循环定义的,则每次扫描至少有一个属性值被计算出来。 如果语法树有n个结点(因此最多有O(n)个属性),最坏的情况整个遍历需要O(n2)时间。

树遍历的举例 S Z Y X x y z a=0 h=0 g=1 S Z Y X x y z a=0 S Z Y X x y z a=0 产生式 语义规则 S→XYZ Z.h := S.a X.c := Z.g S.b := X.d – 2 Y.e := S.b X→x X.d := 2*X.c Y→y Y.f := Y.e * 3 Z→z Z.g := Z.h + 1 S Z Y X x y z a=0 第一遍扫描 h=0 g=1 S Z Y X x y z a=0 初始状态 S Z Y X x y z a=0 第二遍扫描 h=0 g=1 c=1 d=2 S Z Y X x y z a=0 第三遍扫描 h=0 g=1 b=0 e=0 f=0 c=1 d=2 S有继承属性a,综合属性b X有继承属性c,综合属性d Y有继承属性e,综合属性f Z有继承属性h,综合属性g 假设S.a的初始值为0

一遍扫描的处理方法 在语法分析的同时计算属性值,而不是语法分析构造语法树之后进行属性的计算,而且无需构造实际的语法树。 一遍扫描的处理方法与语法分析器密切相关的因素: 所采用的语法分析方法 属性的计算顺序 L-属性文法可用于一遍扫描的自顶向下分析,而S-属性文法适合于一遍扫描的自底向上分析。 此时的语法制导翻译可理解为:直观上说为文法中每个产生式配上一组语义规则,并且在语法分析的同时执行这些语义规则 在自顶向下语法分析中,若一个产生式匹配输入串成功 在自底向上语法分析中,当一个产生式被用于进行归约时

抽象语法树的构造 用抽象语法树作为中间表示,可以把翻译从语法分析中分离出来 表达式的抽象语法树的构造 语法树是分析树的压缩形式,去掉了那些对翻译不必要的信息,对表示语言的结构很有用。 表达式的抽象语法树的构造 为每个运算符和运算对象建立节点来为子表达式构造子树。 运算符节点的字节点分别是表示该运算符各运算对象的子表达式组成的子树的根

表达式语法树的构造方法 运算符节点(用记录实现,也可以用对象实现) 构造的过程(方法) 一个域标识运算符,其余域包含指向运算对象的指针 将运算符称为该节点的标记 构造的过程(方法) mknode(op, left, right):建立一个标记为op的运算符节点,其中两个域left和right是指向其左右运算对象的指针 mkleaf(id,entry):建立标记为id的标识符节点,entry是指向该标识符在标识符表中的相应表项的指针 mkleaf(num,value):建立标记为num的数节点,域val保存该数的值。

抽象语法树的例子 产生式 语义规则 E→E1 + T E.nptr := mknode(‘+’ , E1.nptr, T.nptr) T.nptr := E.nptr T→id T.nptr := mkleaf(id , id.entry) T→num T.nptr := mkleaf(num , num.val)

表达式的无环有向图 表达式的无环有向图(dag)可以识别表达式中的公共子表达式 无环有向图的组成 和抽象语法树的区别: 叶子节点:表达式中的操作数(操作符的运算对象) 内部节点:表达式中的操作符(运算符) 子树:表达式中的每一个子表达式 和抽象语法树的区别: 代表公共子表达式的节点具有多个“父结点” 在省城抽象语法树时,mknode和mkleaf之前先查看是否已经存在需要创建的节点,如果存在,则返回以创建的节点而不是新创建一个节点

S属性文法的自底向上计算

S-属性文法的特点 S-属性文法,只有综合属性 也就是说产生式左边的文法的综合属性要根据产生式右边符号的综合属性来进行计算。 适用于那些需要类似于表达式,需要计算结果的文法。 综合属性可以在分数输入符号串的同时由自底向上的分析器来计算。 分析器保存与栈中文法符号有关的综合属性 每当归约时,新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。

S-属性文法翻译器的实现 S-属性文法的翻译器通常可借助于LR分析器实现。 在自底向上的分析方法中,我们使用栈来存放已经分析过了的子树,现在我们可以在分析栈中使用一个附加域来存放综合属性值。 假设综合属性是刚好在每次归约前计算的 S3 Z Z.z S2 Y Y.y S1 X X.x … top A→XYZ 状态栈 符号栈 val

S-属性文法计算举例 我们要控制两个变量top和ntop。 产生式 语义规则 L→En print(val[top]) E→E1 + T val[top] := val[top-2] + val[top] E→T T→T1 * F val[top] := val[top-2] * val[top] T→F F→(E) val[top] := val[top-1] F→digit 代码段刚刚好在归约前执行。 这是利用归约提供一个“挂钩”,使得用户把一个语义动作与一个产生式联系起来。 翻译模式可以提供一种与分析器相互穿插动作的描述方法。 我们要控制两个变量top和ntop。 当右边带有r个符号的产生式被归约时,执行相应的代码段之前,先将top-r+1赋给ntop,在代码段被执行之后将ntop的值赋给top

L-属性文法和自顶向下翻译

L属性文法定义 在语法分析过程中进行翻译时,属性的计算顺序将与分析方法建立分析树节点的顺序相关。有一种能够描述许多自顶向下和自底向上翻译方法的自然顺序——深度优先顺序。 L属性定义 一个属性文法是L-属性文法,如果对于每一个产生式A→X1X2…Xn,其右部符号Xj(1≤j≤n)的每个属性值仅依赖于下列属性 产生式中Xj左边的符号X1X2…Xj-1的属性 A的继承属性 L属性的计算 可以使用深度优先顺序来计算 LL(1)的分析过程,从概念上说可以看成是深度优先建立语法树的过程

L属性文法的反例 产生式 语义规则 A→LM L.i := l(A.i)) M.i := m(l.s) A→QR R.i := r(A.i) Q.i := q(R.s) A.s := f(Q.s)

语法制导翻译 语法制导翻译给出了使用语义规则进行计算的次序,这样就可以把某些细节表示出来。 在语法制导翻译中,和文法符号相关的属性和语义规则(这里也称语义动作),用“{}”括起来,插入到产生式右部合适的位置上。 语法制导翻译给出了使用语义规则进行计算的顺序。

语法制导翻译举例 E→TR R→addop T {print(addop.lexeme)} R1 | ε T→num {print(num.val)} 9-5+2 按深度优先遍历之后 95-2+ E R T - 9 {print(‘9’)} T {print(‘-’)} R 5 {print(‘5’)} + T {print(‘+’)} R 2 {print(‘2’)} ε

L-属性定义的语法制导翻译 设计L属性定义的语法制导翻译需要注意以下几点: 基本设计原则:当某个动作引用一个属性时,这个属性是可用的。也就是说,一个动作不会引起一个没有计算出来的属性。 只有综合属性时 为每一个语义规则建立一个赋值动作,并把该动作放在产生式右部的末尾 T→T1*F T.val := T1.val ×F.val T→T1*F {T.val := T1.val ×F.val}

L-属性定义的语法制导翻译 同时存在综合属性和继承属性时: 下面的翻译模式不符合上面的定义: 产生式右部符号的继承属性必须在这个符号以前的动作中计算出来 一个动作不能引用该动作右部符号的综合属性 产生式左部非终结符的综合属性只有在其引用的所有属性值都计算出来以后才能计算。计算该属性的动作通常放在产生式右部的末尾。 下面的翻译模式不符合上面的定义: S→A1A2 {A1.in := 1; A2.in := 2} A→a {print(A.in)} 按深度优先遍历时,要打印第二个产生式里的继承属性A.in时,该属性还没有被定义。

L-属性文法举例 S→{B.ps := 10} B {S.ht := B.ht} B→{B1.ps := B.ps} B1 {B.ht := max(B1.ht, B2.ht)} B→ {B1.ps := B.ps} sub {B2.ps := shrink(B.ps)} {B.ht := disp(B1.ht, B2.ht)} B→text {B.ht := text.h ×B.ps} 产生式 语义规则 S→B B.ps := 10 S.ht := B.ht B→B1B2 B1.ps := B.ps B2.ps := B.ps B.ht := max(B1.ht, B2.ht) B→ B1 sub B2 B2.ps := shrink(B.ps) B.ht := disp(B1.ht, B2.ht) B→text B.ht := text.h ×B.ps

L-属性文法的自顶向下翻译 在预测分析的过程中实现L-属性文法 为了明显的看出动作和属性计算发生的属性,我们使用翻译模式而不是属性文法。 为了构造不带回溯的自顶向下语法分析,必须消除文法中的左递归。 将前面讲过的方法扩充,从翻译模式中消除左递归(LL(1)文法构造的步骤),这种方法也适用于带有综合属性的翻译模式。

举例 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} 9-5+2 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} R→ε {R.s := R.i} T→( E ) {T.val := E.val} T→num {T.val := num.val} E val=6 R i=9 T val=9 - val=5 R i=4 num val=9 T num val=5 + val=2 R i=6 s=6 T num val=2 ε 一个符号继承属性必须由出现这个符号之前的动作来计算,产生式左边非终结符的综合属性必须在它所依赖的所有属性都计算出来之后才能计算

消除左递归的一般方法 假设有如下的翻译模式 每个文法符号都有综合属性,g和f是任意函数。 文法可以转换为: 考虑语义动作,变为: A→A1Y {A.a := g(A1.a, Y.y)} A→X {A.a := f(X.x)} 每个文法符号都有综合属性,g和f是任意函数。 文法可以转换为: A→XR R→YR | ε 考虑语义动作,变为: 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}

递归下降翻译器的设计 为每个非终结符A构造一个函数 A的每个继承属性均对应该函数的一个形式参数,其返回值为A的综合属性的值(可能是一个记录、一个指针或者使用传地址参数的传递机制) 非终结符A的代码会根据当前的输入决定使用哪个产生式 与每个产生式有关的代码执行如下动作:从左到右考虑产生式右部的记号、非终结符及语义动作 对于带有综合属性x的终结符X,把x的值保持在X.x中,然后产生一个匹配X的调用,并继续输入 对于非终结符B,产生一个右部带有函数调用的赋值语句c=B(b1,b2,...bk),其中b1,b2,...bk是代表B的继承属性变量,c是代表B的综合属性的变量 对于每个动作,将其代码复制到语法分析器,并把对属性的引用改为对相应变量的引用

自底向上计算继承属性 删除嵌入在翻译模式中的动作 例如 在自顶向下分析中我们可以在产生式右部的任何地方嵌入动作 在自底向上翻译方法中,需要把所有的翻译动作都放在产生式右部的末尾 在基础文法中加入新的形如M→ε的产生式,其中M为标记非终结符。将每个嵌入动作用不同的标记非终结符M来代替,并把该动作放在此空产生式的末端 例如 E→TR R→+T {print(‘+’)} R | -T {print(‘-’)} R | ε T →num {print(num.val)} 转化为 R→+TMR | -TNR | ε M→ ε {print(‘+’)} N→ ε {print(‘-’)}

自底向上计算继承属性 转换后的语法制导翻译和原语法制导翻译比较 用额外的节点表示动作,但动作的执行顺序是一样的 转换后的翻译模式中,动作都在产生式的末尾,可以在自底向上的分析过程中刚好在产生式右部被归约之前执行

分析栈中的继承属性 对于继承属性是由复制规则定义的产生式 自底向上语法分析器对产生式A→XY的归约就是从分析栈顶移走X和Y并用A来代替它们。假设X有一个综合属性X.s。 X的综合属性在分析中放入属性栈,和状态栈符号栈是一一对应的。 X.s在Y以下的子树的任何归约之前已经放在栈中,这个值可以被Y继承,也就是说,如果继承属性Y.i是由复写规则Y.i := X.s定义,那么在需要Y.i的地方可以使用X.s的值。

addtype(val[top], val[top-3] ) addtype(val[top], val[top-1] ) 举例 D→T {L.in := T.type} L T→int {T.type := integer} T→real {T.type := real} L→ {L1.in := L.in} L1,id {addtype(id.entry, L.in)} L→id {addtype(id.entry, L.in)} int p,q,r D L T type in 输入串 栈 所用产生式 int p,q,r - , r in L int p,q,r int p,q,r T T→int in , L q ,q,r Tp p ,q,r TL T→int q,r TL, 产生式 代码段 D→TL T→int val[notp]:=integer T→real val[notp]:=real L→L,id addtype(val[top], val[top-3] ) L→id addtype(val[top], val[top-1] ) ,r TL,q ,r TL L→L,id r TL, TL,r TL L→L,id D D→TL

模拟继承属性的计算 使用自底向上的方法计算继承属性,必须要可以预测属性值在栈中的位置。 产生式 语义规则 S→aAC C.i := A.s S→bABC C→c C.s :=g(C.i) 产生式 语义规则 S→aAC C.i := A.s S→aABMC M.i := A.s; C.i := M.s C→c C.s := g(C.i) M→ε M.s := M.i

模拟继承属性的计算 模拟由复制规则计算的继承属性 模拟不是复制规则的语义规则(计算函数) 引入一个新的标记非终结符M,用M的继承属性和综合属性来传递后面非终结符需要复制的继承属性。 模拟不是复制规则的语义规则(计算函数) 也可以加入新的标记非终结符,用复制规则继承前面非终结符的属性值,其综合属性被置为用计算函数进行计算

val[ntop] := max(val [top-2], val [top]) 产生式 语义规则 S→LB B.ps := L.ps S.ht := B.ht L→ε L.ps := 10 B→B1MB2 B1.ps := B.ps M.i := B.ps B2.ps := M.s B.ht := max(B1.ht, B2.ht) B→ B1 subN B2 N.i := B.ps B2.ps := N.s B.ht := disp(B1.ht, B2.ht) B→text B.ht := text.h ×B.ps M→ε M.s := M.i N→ε N.s := shrink(N.i) 产生式 语义规则 S→LB val[ntop] := val [top] L→ε val[ntop] := 10 B→B1MB2 val[ntop] := max(val [top-2], val [top]) B→ B1 subN B2 val[ntop] := disp(val [top-2], val [top]) B→text val[ntop] := val [top]×val [top-1] M→ε val[ntop] := val [top-1] N→ε val[ntop] := shrink(val [top-2])

带有继承属性的自底向上语法分析和翻译 假设条件 每个非终结符A都有一个继承属性A.i,每个文法符号X都有一个综合属性X.s。对于终结符,其综合属性是词法分析器返回的词法值。 对于每个产生式A→X1X2…Xn ,引入n个新的标记非终结符M1, … ,Mn并用A→ M1X1… MnXn代替该产生式 如果继承属性A.i存在,则其值可以在val数组紧贴M1下面的地方找到。 继承属性将和标记非终结符Mj联系在一起,属性值Xj.i在Mj处完成计算,而且该计算是在归约Xj之前进行的

带有继承属性的自底向上语法分析和翻译 计算方法 算法简化(减少标记符号数目,避免左递归) 当归约标记非终结符Mj时,可以从栈顶依次找到需要使用的属性值, A.i 在val[top – 2j +2]的位置上, X1.i在val[top – 2j +3]的位置上, X1.s在val[top – 2j +4]的位置上…… 得到的Mj.s的值实际上是Xj.i的值,放在val[top+1]的位置上 归约非标记符号,只需要计算综合属性A.s,因为A.i已经计算出来了,放在A要插入的那个位置之下。 算法简化(减少标记符号数目,避免左递归) 如果Xj没有继承属性,就不需要Mj了。 如果X1.i存在,但是它是由复制规则X1.i=A.i计算的,那么可以省略M1

作业 下列文法由开始符号S产生一个二进制数,令综合属性val给出该数的值: S→L.L | L L→LB | B B→0 | 1 试设计求S.val的属性文法,其中,已知B的综合属性c,给出由B产生的二进位的结果值。

作业 设下列文法生成变量的类型说明 构造一个翻译模式,把每个标识符的类型存入符号表 从上面得到的翻译模式,构造一个预测翻译器 L→id L L→,id L | :T T→integer | real 构造一个翻译模式,把每个标识符的类型存入符号表 从上面得到的翻译模式,构造一个预测翻译器

Thanks for your time! Questions & Answers