《川师编译原理》PPT课件.pptVIP

第八章 语法制导翻译 和中间代码生成 教学目的教学目的：让学生了解语法制导翻译：让学生了解语法制导翻译 的基本思想，掌握中间代码的几种常用的基本思想，掌握中间代码的几种常用 形式及表达式与基本语句的翻译方法。形式及表达式与基本语句的翻译方法。 教学重点教学重点：中间代码形式、布尔表达：中间代码形式、布尔表达 式与赋值、控制语句的翻译。式与赋值、控制语句的翻译。 课时分配课时分配：4 4 学时。学时。 教学过程教学过程： Date1 8.1 语法制导翻译概述 1、语法制导翻译的概念 在语法分析过程中根据各个规则所相 联的语义动作或所对应的语义子程序进行翻 译的办法。 2、要求 语法结构具有规定的语义。 3、本质 在进行语法分析的同时，完成相应的 语义处理，关键是如何根据被识别出的语法 成分进行语义处理。 Date2 4、语义分析的任务 1）静态语义检查 例：类型、运算、维数、越界 a+b-1*true 2）动态语义处理（真正的翻译） 例：变量的存储分配 例：表达式的求值 例：语句的翻译（中间代码的生成） 总目标：生成等价的中间代码/目标代码 Date3 5、处理方法 1）对应每一个文法规则编制一个语义子 程序，当一个规则获得匹配时，调用相应 的语义子程序实现语义检查与翻译。 2）在文法规则的右部适当位置，插入相 应的语义动作，按照分析的进程，执行遇 到的语义动作。 注意：语义可以看成是相应文法符号 的属性。 Date4 6、语法制导翻译的具体实现途径 使用LR分析器实现：通过对符号栈 加上语义，扩充LR分析器的分析能力，使 它在用某个文法规则进行归约的同时，调 用相应的语义子程序或产生某种中间代码形 式。 Date5 8.2 属性文法 1、现代编译系统多采用语法制导翻译方法， 该方法使用属性文法为工具来说明程序设计语 言的语义。 2、属性文法是Knuth在1968年提出的。 3、属性文法的特点 1）是一种接近形式化的语义描述方法； 2）每个语法符号有相应的属性符号； 3）每个文法规则都有相应的计算属性的规 则：属性变量=属性表达式 Date6 一、属性文法举例 规则 属性(计算)规则/语义规则 E E1 + E2 E.val := E1.val + E2.val E E1 * E2 E.val := E1.val * E2.val E (E1) E.val := E1.val E id E.val := id .val Date7 二、属性文法的定义 1、定义为三元组（，）。 其中：是上下文无关文法；是属性的有 穷集；是关于属性的谓词/断言，充当计算规则 。说明：任何布尔表达式都是谓词。 2、属性(语义信息)与终结符或非终结符相 联；谓词与文法规则相联。 3、静态语义审查即验证关于所编译源程序 的谓词是否全为真。可用带语义信息结点的 语法树来表示与输入串对应语法树的静态语 义审查。 Date8 三、用法 1、根据文法符号的语义，为文法符号设 置属性。 2、为每个文法规则设置语义规则（用于 描述各属性的关系计算规则） 3、两种使用形式： 用于语法制导定义：语义的抽象说明 。 用于翻译模式的定义：规定实现方法( 计算次序)。 Date9 例1：计算器的设计 对下列文法： L E E E1 + T | T T T1 * F | F F ( E ) | digit 用属性文法描述语法制导的翻译过 程如下： Date10 L E 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 其中：lexval 是单词 digit 的属性 Date11 例2：说明语句的设计 说明语句的文法 D T L T int T real L L1,id L id 1 1、要解决的问题：、要解决的问题： 1 1）记录标识符的类型；）记录标识符的类型； 2 2）类型信息的传递。）类型信息的传递。 Date12 2、说明语句类型信息传递的实现 1）方法 编写说明语句的文法，将类型信息 作为类型描述 T 的属性 type 和变量表 L 的属性 in。 2）目的 分析说明语句 D，为变量指定类型。 Date13 3、属性文法的实现 D T L 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 addtype( id.entry, L.in ) 其中：entry 为单词 id 的属性；addtype 表示在符号表中为变量填加类型信息； Date14 四、属性分类 1、综合属性 设 AX1X2Xn 为一个文法规则，则 A.s=f(c1,c2,ck)中，c1,c2,ck表示X1 ，X2，Xn的属性。而A.s是从其右部符 号的属性值计算出来的，如：例中的 E.val 、T.type。即左部非终结符的属性值的计算 来自其规则右部非终结符。 这种属性叫做综合属性。 适应范围：归约分析。 Date15 2、继承属性 设AX1X2Xn为一个文法规则，则 B.in=f(c1,c2,ck)中，B即Xi，而 c1,c2,ck是A, X1，X2，Xi-1的属性 。如：例中 L.in 这种属性叫做继承(Inherited)属性。 Date16 3、固有属性 语言中的单词，如标识符、常数 （数值的、符号的）、常量，它们的属 性是用户给定的、不变的。 这种属性称为固有(Inherent)属 性（单词属性）。 Date17 五、属性的计算 1、综合属性 自底向上按照语义规则来计算各结 点的综合属性值。 2、继承属性 根据依赖关系决定计算顺序（可以 是依赖图的任意一个拓扑排序）。 3、固有属性 在词法分析时计算，此处不考虑。 Date18 例：3*5+4 的分析 树与属性计算。 Date19 1、即S-attributed Definition （ S-attributed Grammar ）。 2、只包含综合属性的语法制导定 义。 3、例如：算术表达式求值的属性 文法。 六、-属性定义(S-属性文法) Date20 1、即L-attributed Definition （L-attributed Grammar）。 2、包含综合属性和继承属性的语 法制导定义。 3、例如：算术表达式求值的属性 文法、说明语句的属性文法。 七、L-属性定义(L-属性文法) Date21 4、其属性可用深度优先的顺序从左至 右计算。 5、对于所有 1 2 n，其 中i 属性计算仅使用1、2、 i-1 的属性和的继承属性。 6、S-属性文法属于L-属性文法。 Date22 八、翻译模式(Translation Scheme) 1、特征 1）规定在语法分析中使用语义规则进行 计算的次序； 2）保证当动作使用某属性时，该属性必 须是可用的； 2、实现方法 将语义动作插入到文法规则的某个位置。 Date23 例：建立说明语句的翻译方案 语法制导定义： D T LL.in := T.type T intT.type := integer T realT.type := real L L1 ,idL1.in := L.in addtype(id.entry, L.in) L idaddtype(id.entry, L.in) 上述动作的执行时，按照自顶向下分析法 进行推导。 Date24 九、翻译模式的设计 方法：将语义动作中继承属性的计算前移， 使它出现在其相应文法符号之前。 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) Date25 8.3 中间代码 1、源程序经过语义分析被译成中间代码 序列（中间语言的语句）； 2、用中间语言过渡的好处： 便于编译系统的实现、移植、代码优化。 Date26 3、常用的中间代码(语言) 1）三地址代码 四元式(编译系统中普遍采用) 用四元组（算符，操作数1 ，操作数2，结果）或用 简单赋值形式表示。对中间结果通过给定的名字显式 引用。 2）语法(结构)树 三元式 用三元组（算符，操作数1 ，操作数2）表示，对 中间结果可通过三元式编号显式引用。 3） 后缀式逆波兰表示(用栈实现) 注意：操作数2缺省时用下划线表示。 Date27 4、特点：形式简单、语义明确、便于翻译 ，独立于目标语言。 例例 ：表达式：表达式 (A - 12) * B + 6 (A - 12) * B + 6 的语法结构树。的语法结构树。 Date28 例：将赋值语句变换为语法结构树 1）属性设置： E.p 是语法结构树指针； id.entry 是名字的表项入口； num.val 是数值； 2）基本函数结点构造 mknode 建中间结点； mkleaf 建叶结点； Date29 3）其语法制导定义(属性文法) Date30 例：a := b * (- c) + b * (- 34) 的语法结构树 :=*-0 +*-0 idbnum 34 idbidcida root Date31 例：表达式例：表达式 a:=b*(-c)+b/(-d) a:=b*(-c)+b/(-d) 的中间代码的中间代码表表 示。示。 2 2）三元式：）三元式： (- , c , _ )(- , c , _ ) (* , b , ) (* , b , ) (- , d , _ ) (- , d , _ ) (/ , b , ) (/ , b , ) (+ , , ) (+ , , ) (:= , ,a ) (:= , ,a ) 3 3）四元式）四元式: : (- , c , _ ,t1) (- , c , _ ,t1) (* , b ,t1 ,t2) (* , b ,t1 ,t2) (- , d , _ ,t3) (- , d , _ ,t3) (/ , b ,t3 ,t4) (/ , b ,t3 ,t4) (+ ,t2 ,t4 ,t5) (+ ,t2 ,t4 ,t5) (:= ,t5 ,_ , a) (:= ,t5 ,_ , a) 1 1） 逆波兰式：逆波兰式： abcabc-*-*bdbd-/+:=-/+:= Date32 5 5、生成后缀式的属性文法、生成后缀式的属性文法 注释：注释： | | 表示代码序列的连接表示代码序列的连接 Date33 6、三地址代码 1）形式：一般/直观形式 x := y op z 四元式形式（op, y, z, x） 其中 x, y, z 为变量名、常数或编译 产生的临时变量。 2 2）种类：）种类：x := y op z x := y op z 双目运算双目运算 x := op y x := op y 单目运算单目运算 x := yx := y 复制语句复制语句 if x if x reloprelop y y gotogoto l l 条件转移语句条件转移语句 Date34 3）其它语句的三地址代码 goto l 无条件转移 param x 实在参数 call p, n 过程调用 return x 过程返回 x := yi 数组 运算 xi := y x := E.code := E1.code | E2.code | gen(E.place:=E1.place+E2.place) E E1 * E2 E.place := newtemp; E.code := E1.code | E2.code | gen(E.place:=E1.place*E2.place) E - E1 E.place := newtemp; E.code := E1.code | gen(E.place:=0-E1.place) Date38 注释： 1）| 表示代码序列的连接； 2）语义过程newtemp表示生成一个临时变量； 3）E.place表示存放E值的变量名在符号表中的登录项 或一个整数码； 4）语义过程gen表示生成四元式序列到输出文件（中 间代码）。 E ( E1 ) E.place:= E1.place; E.code:= E1.code E id E.place:= id.place; E.code:= E num E.place:= num.val；E.code:= Date39 例： 翻译 a:= -c+b*34 Date40 a:= -c+b*34的中间代码 t2:=0 c t3:=b*34 t1:=t2+t3 a:=t1 Date41 四、表达式翻译中的其它问题 1、运算合法性检查 利用符号表保存的名字类型进行。 2、类型自动转换 添加专用指令；通过加入if语句进行 类型的判别和转换。参见教材p163的类型转 换语义处理例子。 3、临时变量空间的统计 了解空间需求、及时释放。 Date42 8.5 控制语句的翻译 一、高级语言的控制结构 顺序 begin 语句; 语句； end 条件 if_then_else； if_then； switch case 循环 while_do； do_while； for；repeat_until。 二、三地址代码的控制结构 goto label; if x relop(关系符） y goto label; Date43 S while C do S1 的翻译 属性设置（继承） 布尔式 C（入口） 代码段真出口 true 代码段假出口 false 语句 S 、 S 1 代码段的入口 begin 后续段入口 next S.begin= S1.next Date44 三、循环语句的属性文法 Swhile C do S1 C.false := S.next; S.begin := S1.next := newlabel; C.true := S1.begin := newlabel; S.code := gen( S.begin: ) | C.code | gen( C.true: ) | S1.code | gen( gotoS.begin ) 语义过程：新标号的产生 newlabel Date45 S if C then S1 else S2 的翻译 代码序列 C S1 S2 属性关系 S1.begin = C.true S2.begin = C.false S1.next = S2.next = S.next Date46 四、条件语句的属性文法 S if C then S1 C.true := newlabel; else S2 C.false := newlabel; S1.next := S2.next := S.next; S.code := C.code | gen( C.true: ) | S1.code | gen( goto S.next ) | gen( C.false: ) | S2.code Date47 五、简单布尔表达式的翻译 C E1 relop E2 C.code := E1.code | E2.code | gen( if E1.place relop.op E2.place gotoC.true ) | gen( gotoC.false ) Date48 例1：翻译下列ifthenelse语句 if af then s1 else s2 上例生成的三地址代码上例生成的三地址代码/ /四元式序列如下：四元式序列如下： (1) if a f goto (7) (6) goto (p+1) (7) s1对应的四元式序列 (p) goto (q) (p+1) s2对应的四元式序列 (q) 四元式标号采用回填技术四元式标号采用回填技术 Date50 例2：翻译下列while语句 while a y do z := x + 1; else S12 x := y S1 Date51 上例生成的三地址代码/四元式序列 (1) if a y goto (4) goto (1) (4) t1 := x + 1 z := t1 goto (3) (5) x := y goto (1) Lnext: C.code C1.code S11.code S12.code S1.code 标号采用回填技术标号采用回填技术 Date52 六、开关语句、for语句、出口语句过 程调用语句的翻译 其核心是控制转移的翻译， 结合循环和布尔表达式的翻译的 考虑，具体实现略。参见教材 P171-178。 Date53 七、控制结构翻译中的其他问题 1、分