资源预览内容
第1页 / 共81页
第2页 / 共81页
第3页 / 共81页
第4页 / 共81页
第5页 / 共81页
第6页 / 共81页
第7页 / 共81页
第8页 / 共81页
第9页 / 共81页
第10页 / 共81页
亲,该文档总共81页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
语义分析和中间代码生成第五章 本章要求 主要内容:语义分析和中间代码的功能 ,中间代码的形式,属性文法及语法制 导的翻译程序,各种语句的语法制导的 翻译过程 重点掌握:属性文法,语义分析与处理 的方法,中间代码的表示形式,各种语句 的代码结构,各种语句的翻译方法语义分析 和中间代 码生成所 处的位置 :5.1 概述. 语义分析和中间代码生成在编译器中的位置: 静态语义检查:如:类型、运算、数组维数、越界等的检查 语义处理:如:变量的存储分配、表达式的求值、语句的翻 译(中间代码的生成) 总目标:生成等价的中间代码语法分析语义分析和中 间代码生成编译的后续阶段语法树中间代码. 功能及任务:P166 输入 -语法分析单位 输出- 用中间代码形式表示的文本- 出错处理: 定位、继续编译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中间代码的几种形式+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后缀式的推广 (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是目前最常用的中间代码形式: (运算符,第一运算数,第二运算数,结果)例: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)到目前为止,已知 输入的语法单位, 又知道 要翻译的结果的形式, 翻译的方法是什么? 语义分析和翻译的方法:语义表示较流行 的方法仍然是属性文法,翻译方法是语法 制导的翻译。属性文法 属性文法:是在上下文无关文法的基础上,为 每个文法符号(含终结符和非终结符)配备若干 个属性值,对文法的每个产生式都配备了一组 属性计算规则(称为语义规则)。在语法分析过 程中,完成语义规则所描述的动作,从而实现 语义处理。 属性:代表与文法符号相关的信息,如类型、 值、代码序列、符号表的内容等。与变量一样 ,可以进行计算和传递,属性的加工过程就是 语义的处理过程。 属性分两类: 综合属性:用于自下而上传递信 息 继承属性:用于自上而下传递信 息 注意: 终结符只有综合属性,它由词法 分析器提供; 非终结符可有综合属性,也可有 继承属性,它由词法分析器提供 ; 文法的开始符号的所有继承属性 作为属性计算前的初始值综合属性继承属性 产生式右边的文法符号的继承属性可以继承左边 的文法符号的继承属性 产生式左边的文法符号可以通过综合右边的文法 符号的综合属性而得到 但必须提供一个计算规则:计算规则中只能使用 相应产生式中的文法符号的属性。 实际应用中,一个结点的综合属性的值由其子结 点的综合属性值决定(产生式右边)。一个结点的 继承属性由此结点的父结点和/或兄结点的某些属 性决定(产生式左边)。 但产生式左边的继承属性和右边的综合属性不由 所给的产生式的属性计算规则进行计算,它们由 其它产生式的属性计算规则提供。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例: 综合属性的计算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)语法制导的翻译方法基于属性文法的处理过程通常是:对单词符号串进行语法分析 ;构造语法树;根据需要遍历语法树 ;在语法树的各结点处按语义规则进行计算 。 语义规则描述的工作:属性计算、静态语义检查、符号表的 操作、代码生成等,通常写成过程和 函数调用,称为语义子程序。 语法制导翻译的基本思想:在语法分析过程中,根据语言的语义 定义,随时翻译已识别的那部分语法 成分的全部含义。语法制导的翻译方法:如果遍历语法树的操作和建立语法树 的操作同时进行,称为语法制导的翻 译方法。语法制导翻译的两种方法(1) 在自下而上的语法分析中,使用 和语法分析栈同步操作的语义栈进行 语法制导翻译;(2)在自上而下的语法分析中(如递 归下降分析),利用隐含的堆栈存储 各递归子程序中的局部变量所表示的 语义信息。自下而上分析的语法制导翻译语法分析是自下而上的情况时,语义计 算的时机是:在用某一产生式进行规约的同时, 执行相应的语义动作。在分析完一个 句子时,这个句子的“值”也就同时产 生了。例:属性文法如下,输入串为: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。把语法树 中每个结点得语义 值写在结点后的括 号中,则第一步完 成规约后的情形如 右图所示:E1+TTT*FF(3 )5F4E第一步规约继续进行分析,逐步向上规约,得到下图所示的情 形,最后用E E1+T规约到E时,它的值19就 计算出来了。E1(15 )+T(4 )E 在自下而上的LR语法分析过程中,首先把它的分析 栈进行扩充,使得每个文法符号都带有语义值。修 改后栈的结构如下图所示:状态栈S0S1Sm符号栈X0(#)X1Xm语义栈X1.valXm.val栈顶 同时把LR分析器的能力扩大,使它不仅执行语法分 析任务,且能在用某个产生式进行规约的同时进行相 应的语义处理,完成属性文法中定义的语义动作。每 步工作后的语义值保存在扩充的语义栈中。例:在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#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.lexval0LEn 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) 说明语句的处理:把说明语句中定义的名字和属性登记 在符号表中,用以检查名字的引用和说明是否一致,以便在 翻译可执行语句时使用。一般说明语句的语义处理不生成目 标代码,过程说明和动态数组的说明有相应
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号