哈工大编译原理5-11.ppt

第五章语法制导翻译 2 程序设计语言中更重要的一个方面 是附着在语言结构上的语义 语法表述的是语言的形式 或者说是语言的样子和结构 语义揭示了程序本身的涵义 施加于语言结构上的限制或者要执行的动作 老鼠吃猫 问题 语法正确的句子 它的语义可能存在问题 3 语义分析的任务 检查语言结构的语义是否正确 执行所规定的语义动作 如表达式的求值 符号表的填写 中间代码的生成 4 语法制导翻译的基本思想 对于文法 E E1 TE TT FF digit digit lexval为digit的属性 F val T val E val为文法符号F T E对应的属性值 将语言结构的语义以属性 attribute 的形式赋予代表此结构的文法符号 5 当digit为常数时 digit lexval为digit在常数表中的入口 当digit为标识符时 digit lexval为digit在符号表中的入口 F val T val E val可以看作是中间变量 6 E E1 T E val E1 val T val F digit F val digit lexval T F T val F val E T E val T val 而属性的计算以语义规则 semanticrules 的形式赋予由文法符号组成的产生式 在语法分析推导或归约的每一步骤中 通过语义规则实现对属性的计算 以达到对语义的处理 7 换句话说是 为每一个产生式配上语义规则并且在适当的时候执行这些规则 即当归约 或推导 到某个产生式时 除了按照产生式进行相应的代换之外 语法分析 还要按照产生式所对应的语义规则执行相应的语义动作 如计算表达式 查填符号表 产生中间代码 语义分析 8 语法制导翻译是目前最常用的语义分析技术 语法分析 建立语法分析树 语义分析 遍历语法分析树 语法制导翻译 建立与遍历同时完成 9 例1台式计算器程序的语法制导定义 产生式语义规则 L Enprint E val E E1 TE val E1 val T valE TE val T valT T1 FT val T1 val F valT FT val F valF E F val E valF digitF val digit lexval 3 5 4的分析过程 12 10 3 F 5 T F E T F 4 E T 3 5 4的语法分析过程 11 digit lexval 3 F val 3 T val 3 digit lexval 5 F val 5 T val 15 E val 15 digit lexval 4 F val 4 T val 4 E val 19 L n 3 5 4的语义分析过程 12 5 1语法制导定义 Syntax directeddefinitions 语法制导定义也叫属性文法 通过每一个产生式和一个语义规则集合相关联 它是在上下文无关文法的基础上 通过每个文法符号和一个属性集合相关联 语义规则用来计算与产生式中出现的符号相关联的属性的值 9 13 属性 属性可以代表任何对象 字符串 数字 类型 内存单元或其它对象 综合属性 继承属性 14 5 1 1属性 1 b是A属性 在一个语法制导定义中 规则可表示为 b f c1 c2 ck 其中 f是一个函数 且满足下面两种情况之一 c1 c2 ck是 中的文法符号的属性 或者A的其它属性 则称b是A的综合属性 A P都有与之相关联的一套语义规则 15 在两种情况下 都说属性b依赖于属性c1 c2 ck 2 c1 c2 ck是A或 中的任何文法符号的属性 则称b是 中的符号的一个继承属性 16 5 1 2综合属性 综合属性从下到上包括自身 其属性可从后代和自身的其它属性计算得到 S 属性定义 只使用综合属性的语法制导定义 利用S 属性定义进行语义分析时 结点属性值的计算正好和自底向上分析建立分析树结点同步进行 17 例1台式计算器程序的S 属性定义 产生式语义规则 L Enprint E val E E1 TE val E1 val T valE TE val T valT T1 FT val T1 val F valT FT val F valF E F val E valF digitF val digit lexval 3 5 4的分析过程 18 3 F 5 T F E T F 4 E T 3 5 4的语法分析过程 digit lexval 3 F val 3 T val 3 digit lexval 5 F val 5 T val 15 E val 15 digit lexval 4 F val 4 T val 4 E val 19 n L 19 19 digit lexval 3 F val 3 T val 3 digit lexval 5 F val 5 T val 15 E val 15 digit lexval 4 F val 4 T val 4 E val 19 L n 20 在分析树中为每个文法符号上加上它们的属性 则称为带注释的分析树 简称注释分析树 综合属性值的计算方法 在建立每一个结点处使用语义规则来计算综合属性值 即在用哪个产生式进行归约后 就执行那个产生式的s 属性定义计算属性的值 从叶结点到根结点进行计算 对于s 属性定义 通常使用自底向上的分析方法 21 5 1 3继承属性继承属性值是由此结点的父结点和 或兄弟结点的某些属性值来决定的 继承属性从上到下包括兄弟 也即继承属性从前辈和兄弟的属性计算得到 22 表2带有继承属性L in的语法制导定义 产生式语义规则D TLL in T typeT intT type integerT realT type realL L1 idL1 in L inaddtype id entry L in L idaddtype id entry L in 23 练习 设AS为文法的综合属性集 AI为继承属性集 则下列语法制导定义中 P xQRQ b R dR c 1R e Q a Q uQ a 3 产生式语义规则 24 P yQRQ b R fR c Q aR e 2 R vR d R cR f R e 试求AS和AI 25 解 由1知 Q b R e AI 整理 AS Q a R d R f AI Q b R c R e 由3知 R c AI 由4知 R d R f AS 由2知 Q a 3 AS 26 5 2语义规则 语义规则通常有两种表现形式 语义规则也叫语义子程序或语义动作 语法制导定义和翻译模式 27 5 2 1语法制导定义 语法制导定义是关于语言翻译高层次规格说明 例 下面是将中缀表达式转化为后缀表达式的文法和相应的语法制导定义 它隐藏了具体实现细节 使用户不用显式地说明翻译发生的顺序 28 产生式语法制导定义L Eprint E val E E1 E2E val E1 val E2 val E digitE val Digit lexval 语法制导定义只考虑 做什么 用抽象的属性表示文法符号所代表的语义 29 翻译模式也叫翻译方案 5 2 2翻译模式 一个翻译模式是一个上下文无关文法 其中被称为语义动作的程序段被嵌入到产生式的右部 一个翻译模式类似于语法制导定义 只是语义规则的计算顺序是显式给出的 30 这是一种语法分析和语义动作交错的表示法 翻译模式给出了使用语义规则进行计算的顺序 可看成是分析过程中翻译的注释 他表达在按深度优先遍历分析树的过程中何时执行语义动作 31 例2 一个简单的翻译模式 中缀变后缀 E TRR addopT print addop lexeme R1 T num print num val 32 3 5的语义翻译过程 E R T Pr 3 3 T Pr 5 R Pr 5 结果 35 33 翻译方案不仅要考虑 做什么 还要考虑 怎么做 某种意义上说 语法制导定义类似于算法 而翻译方案更象程序 34 带有继承属性L in的翻译方案 D T L in T type LT 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 例5 3变量说明的类型定义inta b c 35 D L in t type L real L1 in L in id3 L1 in L in id2 id1 句子realid1 id2 id3的带继承属性的分析树 T T type real L L Add L in Add L in Add L in 36 例 文法G的产生式如下 S L S aL L SL S1 试写出一个语法制导定义 输出配对括号个数2 写一个翻译方案 打印每个a的嵌套深度 37 解 1 为S L引入属性h产生式语法制导定义S L S h L h 1S aS h 0L L1 SL h L1 h S hL SL h s hS Sprint S h 38 a S S h 0 L a L h 0 S S h 0 L L h 0 S S h 1 L L h 1 S S h 2 a a 的分析过程 39 2 为S L引入属性d 翻译方案如下S S d 0 SS L d S d 1 L S a print s d L L1 d L d L1 S d L d SL S d L d S 40 S S h 0 S L d 1 L L d 1 L S d 1 S S d 1 S Print 1 a L d 2 L S d 2 S Print 2 a a a 的分析过程 41 5 3S 属性定义及其自底向上的计算 state val top 在分析栈中使用一个附加的域来存放综合属性值 下图为一个带有综合属性值域的分析栈 ZYZ Z valY valZ val 42 A b f c1 c2 ck A b X xY yZ z 例 A XYZA b f X x Y y Z z ci 1 i k 是 中符号的属性 其中 b是A的综合属性 综合属性的值在自底向上的分析过程中 每步归约时 计算相应的属性值 XYZ A 43 state val A A b top 定义式A b f X x Y y Z z 抽象 变成val ntop f val top 2 val top 1 val top 具体可执行代码 归约后 分析栈为 在执行代码段之前执行 ntop top r 1 执行代码段后执行 top ntop 其中 r是句柄的长度 ntop为归约后栈顶 44 例5 10用LR分析器实现台式计算器产生式代码段 和表5 1对比 L Enprintf val ntop E E Tval ntop val top 2 val top E TT T Fval ntop val top 2 val top T FF E val ntop val top 1 F digit 45 表5 5翻译输入3 5 4n所做的移动 输入stateval使用的产生式 3 5 4n 5 4n33 5 4nF3F digit 5 4nT3T F 5 4nT 3 4nT 53 5 4nT F3 5F digit 46 4nT15T T F 4nE15E T 4nE 15 nE 415 4 nE F15 4F digit nE T15 4T F nE19E E T En19 L19L En 输入stateval使用的产生式 47 总结 采用自底向上分析 例如LR分析 首先给出S 属性定义 然后 把S 属性定义变成可执行的代码段 这就构成了翻译程序 象一座建筑 语法分析是构架 归约处有一个 挂钩 语义分析和翻译的代码段 语义子程序 就挂在这个钩子上 这样 随着语法分析的进行 归约前调用相应的语义子程序 48 在这种分析模式中 语法分析是主动的 语义分析是从动的 语法分析制导着语义分析 49 5 4L 属性定义 一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序 在语法分析过程中进行语义分析和翻译 属性的计算顺序受到语法分析建立分析树结点顺序的限制 它适应多种自底向上和自顶向下的翻译方法 50 深度优先顺序计算属性PROCEDUREdfvisit n node BEGINFORn的每个子结点m 从左至右DOBEGIN计算m的继承属性 dfvisit m END 计算n的综合属性END 51 一个语法制导定义是L 属性定义 5 4 1L 属性定义 每一个S 属性定义都是L 属性定义 如果 A X1X2 Xn P 或是Xj 1 j n 的一个继承属性 1 产生式中Xj的左边符号X1 X2 Xj 1的属性 2 A的继承属性 其每一个语义规则中的每一个属性都是一个综合属性 这个继承属性仅依赖于 52 例 一个简单的翻译模式E TRR addopT print addop lexeme R1 T num print num val 95 2 它是输入表达式9 5 2的后缀式 把语义动作看成终结符号 输入9 5 2 其分析树如图 当按深度优先遍历它 执行遍历中访问的语义动作 将输出 53 E T 9 T Pt 9 R Pt Pt R 5 Pt 5 T 2 Pt 2 R 9 5 2的带语义动作的分析树 54 设计翻译模式 根据语法制导定义 T T1 FT val T1 val F valT T1 F T val T1 val F val 1 只需要综合属性的情况 为每一个语义规则建立一个包含赋值的动作 并把这个动作放在相应的产生式右边的末尾 例如 条件 语法制导定义是L 属性定义 保证语义动作不会引用还没有计算的属性值 55 产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算 一个动作不能引用这个动作右边符号的综合属性 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来 2 既有综合属性又有继承属性 计算这种属性的动作通常可放在产生式右端的未尾 56 下面的翻译模式不满足要求 S A1A2 A1 in 1 A2 in 2 A a print A in S A2 A1 a Pr A in A1 in 1 A2 in 2 end 57 5 5自顶向下的翻译 用翻译模式构造自顶向下翻译 5 5 1从翻译模式中消除左递归 对于一个翻译模式 若采用自顶向下分析 必须消除左递归和提取左公因子 在改写基本文法时考虑属性值的计算 58 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 图5 13带左递归的文法的翻译模式 59 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 经过转换的带有右递归文法的翻译模式 67 69 60 E T R i T val R E val R s 9 t val 9 T R1 i R i T val R1 R s R1 s 5 T val 5 T R1 i R i T val R1 R s R1 s 2 T val 2 R s R i 61 关于左递归翻译模式更一般化的讨论 左递归翻译模式A A1Y A a g A1 a Y y A X A a f X x 5 2 每一个文法符号都有一个综合属性 用相应的小写字母表示 g和f是任意函数 消除左递归 文法转换成A XRR YR 62 再考虑语义动作 翻译模式变为 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 5 4 为什么 经过转换的翻译模式与图5 14中一样 使用R的继承属性i和综合属性s 5 2 和 5 4 的结果是一样的 63 A a g g f X x Y1 y Y2 y A a g f X x Y1 y A a f X x Y2 Y1 X a 输入 XY1Y2 64 A R i f X x R i g f X x Y1 y R i g g f X x Y1 y Y2 y Y2 Y1 X