第六章语法制导翻译与属性文法

第六章语法制导翻译与属性文法内容摘要：

的 语法树 T ⒀ n o d e F ⑵ n o d e n u m ⑴ v a l * i n h ⑶ T 39。 ⑿ s y n F ⑸ n o d e i d ⑺ e n t r y i d ⑷ e n t r yi n h ⑹ T 39。 ⑾ s y n /F ⑻ n o d e i n h ⑼ T 39。 ⑽ s y n ε2020/11/29 41  定义 翻译模式 是语法制导定义的一种便于实现的书写形式。 其中属性与文法符号相关联，语义规则或语义动作用花括号｛ ｝括起来，并可被插入到产生式右部的任何合适的位置上。 这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过程中何时执行语义动作。 翻译模式给出了使用语义规则进行计算的顺序。 可看成是分析过程中翻译的注释。 翻译模式 2020/11/29 42 将中缀表达式翻译成后缀表达式： E→TR R→addop T {print()}R1|ε T→num{print()} 把语义动作看成终结符号，输入 3+45,其分析树如图 ，当按深度优先遍历它，执行遍历中访问的语义动作，将输出 3 4 + 5 它是输入表达式 3+45的后缀式。 例 一个简单的翻译模式 2020/11/29 43 图 3+45的带语义动作的分析树 RTRRεET4{ p r i n t ( ‘ 4 39。 ) }{ p r i n t ( ‘ 3 39。 ) }T { p r i n t ( 39。 39。 ) }5{ p r i n t ( ‘ 5 39。 ) }{ p r i n t ( 39。 + 39。 ) }3+2020/11/29 44  前提 —— 语法制导定义是 L属性定义 保证语义动作不会引用还没计算出来的属性值 1. 只需要综合属性的情况 为每一个语义规则建立一个包含赋值的动作，并把该动作放在相应的产生式右部的末尾。 例如： TT1*F Tval:=T1val*Fval 转换成： TT1*F{Tval:=T1val*Fval} 翻译模式的设计 —— 根据语法制导定义 2020/11/29 45 2. 既有综合属性又有继承属性  产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。  一个动作不能引用这个动作右边符号的综合属性。  产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。 计算这种属性的动作通常可放在产生式右端的末尾。 翻译模式的设计 —— 根据语法制导定义 2020/11/29 46 下面的翻译模式不满足要求： SA1A2 {A1in:=1。 A2in:=2} A a { print(Ain) } /* */ 例 从 L属性制导定义建立一个满足上面 要求的 翻译模式。 使用文法产生的语言是数学排版语言 EQN E sub 1val 编排结果 E1. v a lh e i g h td e p t h2020/11/29 47 B表示盒子 ⑴ B→B1B2代表两个相邻盒子的并列，且 B1位于 B2的左边。 ⑵ B→B1 sub B2代表盒子 B1后随下标盒子 B2，下标盒子 B2以较小的字体和较低的位置出现。 ⑶ B→(B1)代表一个由括号括起来的盒子 B1，主要是为了对多个盒子或下标进行分组。 在 EQN中，使用花括号进行分组，此处使用圆括号是为了避免跟语义动作外面的花括号产生冲突。 ⑷ B→text代表文本字符串，即任意字符组成的串。 该文法是二义性的文法，将“并列”和“下标”看成是左结合的，并令“下标”的优先级高于“并列”的话，则可以对该文法所描述的语言进行自底向上的语法分析。 2020/11/29 48 属性设置 ⑴ point size用于表示盒子中文本的尺寸 (以点来计算，也就是字号 )。 如果标准盒子的尺寸为 p，则下标盒子的尺寸为 p。 属性 B的尺寸，该属性是继承属性。 ⑵ 每个盒子都有一个基线 (baseline)，用来表示每个文本底部的垂直位置。 ⑶ height用来表示从盒子的顶部到基线的距离。 属性 B的高度 height，该属性是综合属性。 ⑷ depth用来表示从基线到盒子底部的距离。 用属性 B的深度 depth，该属性也是综合属性。 2020/11/29 49 表 对盒子进行排版的语法制导定义 产生式 语义规则 ⑴ S →B :=10 := := ⑵ B → B1B2 := := := max(, ) := max(, ) ⑶ B→B1 sub B2 := := :=max(, ) :=max(, + ) ⑷ B →(B1) := := := ⑸ B →text :=getheight(,) :=getdepth(,) 2020/11/29 50 S→{:=10}B { :=。 := } B→{:=}B1{B2 .ps:=} B2{:=max(,)} B→{:=}B1sub{:= } B2{:=max(, )。 :=max(,+ )。 } B→({:=}B1){:=。 :=。 } B→text{:=getheight(,)。 :=getdepth(,)} 从表 2020/11/29 51 T → F {T 39。 .inh := }T 39。 { := T 39。 .syn} T 39。 → *F {T139。 .inh := mknode(39。 *39。 , T 39。 .inh,)} T139。 {T 39。 .syn := T139。 .syn} T 39。 → /F {T139。 .inh := mknode(39。 /39。 , T 39。 .inh,)} T139。 {T 39。 .syn := T139。 .syn} T 39。 →ε {T 39。 .syn := T 39。 .inh} F → (E ){ := } F→ id { := mkleaf(id, )} F→ num { := mkleaf(num, )} 从表 2020/11/29 52 在分析栈中使用一个附加的域来存放综合属性值。 下图为一个带有综合属性值域的分析栈： stack val ... X Y ... ... ... Z top S属性定义的自底向上计算 2020/11/29 53 A b:=f(c1,c2,…, ck) b是 A的综合属性， ci (1 ik)是 中符号的属性。 综合属性的值是在自底向上的分析过程中，每次归约之前进行计算的。 AXYZ Aa:=f(Xx,Yy,Zz) Aa Xx Yy Zz 2020/11/29 54 top stack val ... ... X Y Z stack val ... ... A top 实现时，将定义式 :=f(, , ) (抽象 )变成 stack[ntop].val:=f(stack[top2].val, stack[top1].val, stack[top].val) (具体可执行代码 )。 在执行代码段之前执行： ntop:=topr+1 —— r是句柄的长度 执行代码段后执行： top:=ntop。 2020/11/29 55 例 用 LR分析器实现 台式计算器 —— 与表 L→En{print(stack[top1].val)。 top:=top1。 } E→E1+T{stack[top2].val:= stack[top2].val + stack[top].val。 top:=top2。 } E→T T→T1*F{stack[top2].val:= stack[top2].val stack[top].val。 top:=top2。 } T→F F→(E){ stack[top2].val:= stack[top1].val。 top:=top2。 } F→digit 2020/11/29 56 表 翻译输入 6+7*8n上的移动序列 输入 state val 使用的产生式 6+7*8n +7*8n 6 6 +7*8n F 6 Fdigit +7*8n T 6 TF +7*8n E 6 ET 7*8n E+ 6+ *8n E+7 6+7 2020/11/29 57 *8n E+F 6+7 F digit *8n E+T 6+7 T F。