编译原理(第二版)第八章语法制导翻译和中间代码生成.ppt

第八章 语法制导翻译和中间代码生成 教学要求：本章介绍编译程序的第三个 阶段语义分析及中间代码生成的设计原 理和实现方法，要求理解语法制导翻译 、语义动作的基本概念；掌握属性文法 和中间代码。 教学重点：语法制导翻译基本思想，语 法制导翻译概述，基于属性文法的处理 方法，中间代码的表示形式。 语义处理功能： 1、静态语义审查：验证语法结构合理 的程序是否真正有意义。 2、解释执行动态语义、生成代码：执 行真正的翻译（生成中间代码或目标代 码）。 1、属性文法（说明语言语义的工具）定义 属性文法是一个三元组:A=(G,V,F),其中： G:是一个上下文无关文法。 V:有穷的属性集,每个属性与文法的一个终结符或非 终结符相连。如它的类型、值、代码序列、符号 表内容等等。 F:关于属性的属性断言或一组属性的计算规则(称为 语义规则) . 断言或语义规则与一个产生式相联, 只引用该产生式左端或右端的终结符或非终结符 相联的属性. 8.1 属性文法 例1：定义表达式的文法如下： EE+E E(E) En 给出定义表达式值的属性文法。 为文法符号E引进属性符号val,用E.val表示E的值，属性 计算规则以赋值语句的形式给出，附在每个产生式后，并用大 括号括起来。为了明确E的不同出现位置，用上角标区别。终 结符n的值是词法分析程序提供的，这里用n.lex表示。下面给 出属性文法： EE1+E2 E.val := E1.val +E2.val E(E1) E.val := E1.val En E.val := n.lex 属性文法的主要思想有两点： 首先对于每个文法符号引进相关的属性符号； 其次对于每个产生式写出属性值计算的规则。 2、属性分类 综合属性：一个结点的属性值是从其子结点的属性值计算 出来的。 继承属性：一个结点的属性值是由该结点兄弟结点和父结 点的属性值计算出来的。 3、属性的计算 综合属性计算 自底向上按照语义规则来计算各结点的综合属性值 继承属性计算 根据依赖关系决定计算顺序 例1 台式计算器程序的语法制导定义 产生式 语义规则 print(Eval) Eval:=E1val+Tval Eval:=Tval Tval:=T1val*Fval Tval:=Fval Fval:=Eval Fval:=digitlexval 1、与LE相连的语义规则是一个过程，打印E的值，理 解为L的属性是虚的或空的。 2、E,T,F的属性val都为综合属性。 3、lexval 是单词 digit 的属性（由词法程序提供）。 LE EE1+T ET TT1*F TF F(E) Fdigit digitlexval:=3 Fval:=3 Tval:=3 digitlexval:=5 Fval:=5 Tval:=15 * Eval:=15+ digitlexval:=4 Fval:=4 Tval:=4 Eval:=19L 例 5 .2 输入：3*5+4 例2：说明语句语法制导定义(属性文法) L.in:=T.type T.type:=integer T.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in) entry 单词id的属性 addtype 在符号表中为变量填加标识符的类型信息 DTL Tint Treal LL1,id Lid 例2：real id1,id2,id3 的分析树和属 性计算 real T.type=real id1 L.in=real,id2 L.in=real,id3 L.in=real D addtype addtype addtype 1、语法制导翻译基本思想：根据翻译的需要设置文 法符号的属性，以描述语法结构的语义。随着语法分 析的进行，执行属性值的计算，完成语义分析和翻译 的任务。 注：1)语法制导翻译的依据是语义子程序。 2)每个产生式均配置一个语义子程序，当语法分 析进行归约和推导时，就调用相应语义子程序，完成 一部分翻译任务，翻译的结果是生成相应中间代码。 3)语法分析完成，翻译工作也告结束。 8.2 语法制导翻译 2、语义子程序：描述一个产生式所对应的翻译动作 。 注：1)语义子程序中的翻译工作在很大程序上决定 要产生什么形式的中间代码。一般说来，这些工作 包括改变某些变量的值、查填各种符号表、发现并 报告源程序错误、产生中间代码等。 2)若使用LR语法分析，则下推栈包含三个部分：状 态栈、符号栈和语义栈，且语义栈与状态栈和符号 栈同步变化（如P174）。 3)当产生式进行归约时，需对产生式右部符号的语 义值进行综合，其结果作为左部符号的语义值保存 到语义栈中。 例4.3 在下面的语法制导定义中，属性.val用于表达式值 的计算。在与之等价的翻译方案中，设计一个与分析栈并列的 语义栈val，用于存放文法符号对应的值，top指针在任何时刻 与分析栈栈顶指针所指对象相同。 产生式语法制导定义翻译方案 L E print(E.val)print(valtop); E E1 + E2E.val := E1.val + E2.val;valtop := valtop+valtop+2; E E1 * E2E.val := E1.val * E2.val;valtop := valtop*valtop+2; E (E1)E.val := E1.val;valtop := valtop+1; E numE.val := num.lexval;valtop := lexval; 中间代码：源程序的一种内部表示，不依赖目标 机的结构，易于机械生成目标代码的中间表示。 8.3 中间代码的形式 常用的中间代码： 逆波兰式、四元式、三元式、树形表示。 约定符号： LJ:表示转向某标号处 TJ:表示按真转 FJ:表示按假转RJ:表示无条件转 意义：逻辑结构清楚；利于不同目标机上实现同一种语 言；利于进行与机器无关的优化。 一、逆波兰表示 1、 表达式的表示： 例：a+b 2、 赋值语句的逆波兰表示： 左部 := := 例: x := 5X 5 := ab+ 例：-a+b*c 例： (a+b)*c abc*+ ab+c* 典型特征是操作数在前，操作符紧跟其后。 特点:由于操作符紧跟操作数之后，因此只要知道操作 符有几个操作数，每一步的运算就可以确定。 例 :A+B*(C-D)+E/(C-D)N 逆波兰:ABCD-*+ECD-N/+ 后缀式并不局限于二元运算的表达式，可以推广到任何 语句，只要遵守操作数在前，操作符紧跟其后的原则即可 。典型的例子如if-then-else语句： if e then x else y 将if-then-else看作一个完整的操作符，则e、x和 y分 别是三个操作数，这显然是一个三元运算。根据后缀式的 特点，它的后缀式可以写为： exy if-then-else(记为: exy￥) 但是，这样的表示有个弱点。按照算法的计算次序，e 、x和y均需计算，而实际上，根据条件e的取值，计算x则 不计算y，计算y则不计算x。 3、转向语句的逆波兰表示: 4、条件语句的逆波兰表示: v 无条件转: 格式: RJ v 按真转: 格式: TJ v 按假转: 格式: FJ goto 5、循环语句的逆波兰表示: for i :=1 to 100 do s := s + i ; 例: goto 10 10 LJ LJ i := 1; 10: if i , , , ) 2. 表达式和赋值四元式: 例:a * b ( *, a, b, T ) 3. 转向语句和条件语句的四元式: v 无条件转移: goto L(RJ,-,-,L) i := 1 ; 10: if i , , ) 例: b * c( *, b, c ) 三元式的编号具有双重含义，既代表此三元式， 又代表三元式存放的结果。三元式一般被按顺序存放 在数组结构的三元式组中，三元式组中的每个元素是 一个记录，其中的三个域分别存放三元式中的各项。 它的最大弱点是三元式一旦在三元式表中确定了 位置，则不能再被改变，给优化工作带来困难。 2. 表达式和赋值语句的三元式: m:=a * ( b- c ) / d + e(1) ( -, b, c ) (2) ( *, a, (1) ) (3) ( /, (2), d ) (4) ( +, (3), e ) (5) (:=, (4), m) 3. 转向语句和条件语句的三元式: if a b then x := a + b else x := a b ; (1) ( , a, b ) (2) (FJ, (6), (1) ) (3) ( +, a, b ) (4) ( :=, (3), x ) (5) ( RJ, (8), / ) (6) ( -, a, b ) (7) ( :=, (6), x ) (8) ( ) for i :=1 to 100 do s := s + i ; i := 1 ; 10: if i = 100 then begin s := s + i ; i := i + 1 ; goto 10 ; end ; (1) ( :=, 1, i ) (2) ( =, i, 100 ) (3) ( FJ, (9), (2) ) (4) ( +, s, i ) (5) ( :=, (4), s ) (6) ( +, i, 1 ) (7) ( :=, (6), i ) (8) ( RJ, (2),-) (9) ( ) 4. 循环语句的三元式: 例:A+B*(C-D)+E/(C-D)N 三元式:(1)(-,C,D) (2)(*,B