《《编译原理课程教案》第5章中间代码生成_图文》由会员分享，可在线阅读，更多相关《《编译原理课程教案》第5章中间代码生成_图文（81页珍藏版）》请在金锄头文库上搜索。
1、语义分析和中间代码生成第五章 本章要求 主要内容：语义分析和中间代码的功能 ，中间代码的形式，属性文法及语法制 导的翻译程序，各种语句的语法制导的 翻译过程 重点掌握：属性文法，语义分析与处理 的方法,中间代码的表示形式，各种语句 的代码结构，各种语句的翻译方法语义分析 和中间代 码生成所 处的位置 ：5.1 概述. 语义分析和中间代码生成在编译器中的位置： 静态语义检查：如：类型、运算、数组维数、越界等的检查 语义处理：如：变量的存储分配、表达式的求值、语句的翻 译(中间代码的生成) 总目标：生成等价的中间代码语法分析语义分析和中 间代码生成编译的后续阶段语法树中间代码. 功能及任务：P16
2、6 输入 -语法分析单位 输出- 用中间代码形式表示的文本- 出错处理: 定位、继续编译3. 为什么要此阶段? 逻辑结构清楚；利于不同目标机上实现同一种语言； 利于进行与机器无关的优化，这些内部形式也能用于 解释。 4. 什么是中间代码(Intermediate code) 源程序的一种内部表示，不依赖目标机的结构，易于 机械生成目标代码的中间表示。 5. 中间代码的几种形式 逆波兰、三元式、间接三元式、四元式、树 1、逆波兰式： 运算对象写在前，运算符写在后(后缀表示形式) 例：a+b ab+ (a+b)*c ab+c*a+b*c abc*+a:=b*c+b*d abc*bd*+:=5.2中
3、间代码的几种形式+a b优点：易于计算机处理利用栈，将扫描到的运算对象入栈，碰到运算符：若是双目运算符，则对栈顶的两个运算对象实施该运算 并将运算结果代替这两个运算对象进栈；若是单目运算符，对栈顶元素，执行该运算，将运算结 果代替该元素进栈，最后结果即栈顶元素。练习写出下列算式的逆波兰表示 a+b*(c+d/e)a:=b*(-c)+b *(-34) not A or not (C or not D)abcde/+*+a b c - * b 34 - * + :=a b c - * b 34 - * + :=A not C D not or not or+a *b +c /d e后缀式的推广 (
4、1)赋值语句A:=E，后缀式为：AE:= (2)转向语句GOTO L的后缀式为：Ljmp (3)条件语句if xy then m:=x else m:=y12345678910 11 12 13 14xy11 jezmx:=14jmy:= 2、三元式 编号（运算符，第一运算数，第二运算数） 如：a：= b*c+b*d (1)（*，b，c） (2)（*，b，d） (3)（+，(1)，(2)） (4)（：=，(3)，a） 对于单目运算符，只有一个运算对象，另一个为空 注意：在三元式中的编号既代表了序号，又代表了结 果的存放位置。 3、四元式P172是目前最常用的中间代码形式: (运算符，第一运算数
5、，第二运算数，结果)例：a:=b*c+b*d(1)(*,b,c,t1) (2)(*,b,d,t2)(3)(+,t1,t2,t3) (4)(:=,t3, ,a)也可以写成赋值语句形式：(1)t1:=b*c (2)t2:=b*d(3)t3:=t1+t2 (4)a:=t3练习 求 -B+C*D 的逆波兰表示形式、三元式和 四元式逆波兰：B C D * +三元式：(1) (-,B,) (2) (*,C,D)(3) (+,(1),(2)四元式：(1) (-,B, , t1) (2) (*,C,D,t2)(3) (+,t1,t2,t3)到目前为止，已知 输入的语法单位， 又知道 要翻译的结果的形式， 翻译
6、的方法是什么？ 语义分析和翻译的方法：语义表示较流行 的方法仍然是属性文法，翻译方法是语法 制导的翻译。属性文法 属性文法:是在上下文无关文法的基础上，为 每个文法符号(含终结符和非终结符)配备若干 个属性值，对文法的每个产生式都配备了一组 属性计算规则(称为语义规则)。在语法分析过 程中，完成语义规则所描述的动作，从而实现 语义处理。 属性：代表与文法符号相关的信息，如类型、 值、代码序列、符号表的内容等。与变量一样 ，可以进行计算和传递，属性的加工过程就是 语义的处理过程。 属性分两类： 综合属性：用于自下而上传递信 息 继承属性：用于自上而下传递信 息 注意： 终结符只有综合属性，它由词
7、法 分析器提供； 非终结符可有综合属性，也可有 继承属性，它由词法分析器提供 ； 文法的开始符号的所有继承属性 作为属性计算前的初始值综合属性继承属性 产生式右边的文法符号的继承属性可以继承左边 的文法符号的继承属性 产生式左边的文法符号可以通过综合右边的文法 符号的综合属性而得到 但必须提供一个计算规则：计算规则中只能使用 相应产生式中的文法符号的属性。 实际应用中，一个结点的综合属性的值由其子结 点的综合属性值决定(产生式右边)。一个结点的 继承属性由此结点的父结点和/或兄结点的某些属 性决定(产生式左边)。 但产生式左边的继承属性和右边的综合属性不由 所给的产生式的属性计算规则进行计算，
8、它们由 其它产生式的属性计算规则提供。digitlexval:=3Fval:=3Tval:=3Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19L n0LEn 1EE1+T 2ET 3TT1*F 4TF 5F(E) 6Fdigitprint(E.val) E.val:=E1.val+t.val E.val:=T.val T.val:=T1.val * F.val T.val:=F.val F.val:=E.val F.val:=digit.lexvaldigitlexval:=5若输入符号串为：3*5+4n例： 综合属性的
9、计算C语言中变量定义： int id1,id2,id3综合属性 的传递继承属性 的传递例： 继承属性的计算产生式语 义 规 则 D TL T int T real L L1,idL idL.in:=T.type T.type=integer T.type:=real addtype(id.entry,L.in) L1.in:=L.in addtype(id.entry,L.in)语法制导的翻译方法基于属性文法的处理过程通常是：对单词符号串进行语法分析 ；构造语法树；根据需要遍历语法树 ；在语法树的各结点处按语义规则进行计算 。 语义规则描述的工作：属性计算、静态语义检查、符号表的 操作、代码生
10、成等，通常写成过程和 函数调用，称为语义子程序。 语法制导翻译的基本思想：在语法分析过程中，根据语言的语义 定义，随时翻译已识别的那部分语法 成分的全部含义。语法制导的翻译方法：如果遍历语法树的操作和建立语法树 的操作同时进行，称为语法制导的翻 译方法。语法制导翻译的两种方法（1） 在自下而上的语法分析中，使用 和语法分析栈同步操作的语义栈进行 语法制导翻译；（2）在自上而下的语法分析中（如递 归下降分析），利用隐含的堆栈存储 各递归子程序中的局部变量所表示的 语义信息。自下而上分析的语法制导翻译语法分析是自下而上的情况时，语义计 算的时机是：在用某一产生式进行规约的同时， 执行相应的语义动作
11、。在分析完一个 句子时，这个句子的“值”也就同时产 生了。例：属性文法如下，输入串为：3*5+4，其语法树如下图 ：0LEn 1EE1+T 2ET 3TT1*F 4TF 5F(E) 6Fdigitprint(E.val) E.val:=E1.val+t.val E.val:=T.val T.val:=T1.val * F.val T.val:=F.val F.val:=E.val F.val:=digit.lexval产生式 语义规则EE1+TTT*FF35F4在第一步规约时使用 产生式6，执行的 语义动作是将F.val 的值置为单词digit 的值3。把语法树 中每个结点得语义 值写在结点后
12、的括 号中，则第一步完 成规约后的情形如 右图所示：E1+TTT*FF（3 ）5F4E第一步规约继续进行分析，逐步向上规约，得到下图所示的情 形，最后用E E1+T规约到E时，它的值19就 计算出来了。E1（15 ）+T（4 ）E 在自下而上的LR语法分析过程中，首先把它的分析 栈进行扩充，使得每个文法符号都带有语义值。修 改后栈的结构如下图所示：状态栈S0S1Sm符号栈X0(#)X1Xm语义栈X1.valXm.val栈顶 同时把LR分析器的能力扩大，使它不仅执行语法分 析任务，且能在用某个产生式进行规约的同时进行相 应的语义处理，完成属性文法中定义的语义动作。每 步工作后的语义值保存在扩充的
13、语义栈中。例：在3*5+4的LR分析过程中增加了语义栈后的语 法制导的实现过程。LR分析表文法 0LEn 1EE1+T 2ET 3TT1*F 4TF 5F(E) 6Fdigitprint(E.val) E.val:=E1.val+t.val E.val:=T.val T.val:=T1.val * F.val T.val:=F.val F.val:=E.val F.val:=digit.lexval序号 状态栈符号栈语义语义 栈栈归约产 生式输入串10#-3*5+4# 205#3-*5+4# 303#F-3Fi*5+4# 402#T-3TF*5+4# 5027#T*-3-5+4# 60275#
14、T*5-3-+4# 702710#T*F-3-5Fi+4# 802#T-15TT*F+4# 901#E-15ET+4# 10016#E+-15-4# 110165#E+4-15-# 120163#E+F-15-4Fi# 130169#E+T-15-4TF# 1401#E-19EE+T# 15接受0LEn 1EE1+T 2ET 3TT1*F 4TF 5F(E) 6Fdigitprint(E.val) E.val:=E1.val+t.val E.val:=T.val T.val:=T1.val * F.val T.val:=F.val F.val:=E.val F.val:=digit.lexva
15、l0LEn 1EE1+T 2ET 3TT1*F 4TF 5F(E) 6Fdigitprint(E.val) E.val:=E1.val+t.val E.val:=T.val T.val:=T1.val * F.val T.val:=F.val F.val:=E.val F.val:=digit.lexval启示： 在刚才的翻译过程中有如下特点： 句柄归约在先，语义动作在后。 归约时，栈内句柄各符号的语义信息与该句柄 同时出栈，整个句柄所表示的语义信息则赋给 相应产生式左部非终结符的语义变量，并让该 非终结符及其语义变量同时入栈。 为了在某处调用语义动作，就必须先归约，因 此，有时需要改写文法。常见语句的语法制导翻译 高级语言的两大类语句： 说明语句：用于定义各种形式的有名实体及其 属性，如常 量、变量、数组、记录（结构）、过程、子程序等。 可执行语句：用于完成程序指定的功能。语义处理也按两大类处理： （1） 说明语句的处理：把说明语句中定义的名字和属性登记 在符号表中，用以检查名字的引用和说明是否一致，以便在 翻译可执行语句时使用。一般说明语句的语义处理不生成目 标代码，过程说明和动态数组的说明有相应
