编译原理第5章语法制导翻译及中间代码生成.ppt

《编译原理第5章语法制导翻译及中间代码生成.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章语法制导翻译及中间代码生成§5.1语法制导翻译概述§5.2中间语言§5.3自底向上语法制导翻译§5.4自顶向下语法制导翻译§5.5属性文法与属性翻译1§5.1语法制导翻译概述一、语法制导翻译定义二、语法制导翻译原理三、语法制导翻译实现2一、语法制导翻译定义语法制导翻译就是以语法分析为主导的语义处理。在语法分析过程中嵌入语义动作，即调用对应的语义子程序。例如在前面语法分析时分析a+b*c表达式，其分析语法树如下：E+EE*EEabc在语法分析同时进行语义分析3二、语法制导翻译原理语法制导翻译的原理就是先为每个文法规确定相应的语义，即编写

2、出相应语义处理子程序，整个分析是以语法分析为主导。语义动作：给每个文法符号X赋以各种不同的语义值4例如，假定有如下规则和语义动作：E∷=E(1)+E(2){E·VAL:=E(1)·VAL+E(2)·VAL}5例5.1设有文法E∷=E+EE∷=digit这里digit代表0和9之间任一数字，如果我们的目的仅是为了求值，则语义动作如下(1)E∷=E(1)+E(２){E·VAL:=E(1)·VAL+E(2)·VAL}(2)E∷=digit{E·VAL:=digit}假定语义动作中的“+”代表是整型加算术运算。6例如，假定有输入串1+2+3，我们通

3、过语法树的分析来看如何进行语法制导翻译，来求出该句子最后值。输入串1+2+3的语法树如下图所示.E+EE+EE1237(1)X∷=…{动作1}(2)Y∷=…{动作2}(3)A∷=XY{动作3}现在对LR分析器的分析栈加以扩充，为了在语法分析过程中平行地进行语义处理，使得每个文法符号之后都跟着它的语义值，因此，设置一个语义信息栈，为了清晰起见，我们把这个分析栈每一项分三部分组成：状态STATE、文法符号SYM和语义值VAL。三、语法制导翻译实现8SmY•VALYSm-1X•VALXS0－#………TOPSTATEVALSYM分析栈如下图所示:9

4、我们假定先归约后执行语义子程序，所以当X，Y归约为A,Sm和Sm-1归约为新状态S后，执行语义子程序X和Y的值也归约为A的值。10SmSm-1Y•VALX•VALYXTOP归约前SiX•VALATOP归约后Y•VALSiA•VALATOP求值后A•VAL:=Y•VAL+X•VAL11例5.2考虑下面文法及其语义描述：规则语义动作(0)S’∷=E{printE·VAL}(1)E∷=E(1)+E(2){E·VAL:=E(1)·VAL+E(2)·VAL}(2)E∷=E(1)*E(2){E·VAL:=E(1)·VAL*E(2)·VAL}(3)E∷=

5、(E(1)){E·VAL=E(1)·VAL}(4)E∷=i{E·VAL:=LEXVAL}12规则程序段(0)S’∷=E{printVAL［TOP］}(1)E∷=E(1)+E(2){VAL[TOP]：=VAL[TOP]+VAL[TOP+2]}(2)E∷=E(1)*E(2){VAL[TOP]：=VAL[TOP]*VAL[TOP+2]}(3)E∷=(E(1)){VAL［TOP］:=VAL［TOP+1］}(4)E∷=i{VAL［TOP］:=LEXVAL}13根据上述程序段，若输入2*3+2，就有如下图所示的语法制导翻译的分析树。S’EEEEE+*2

6、23E•VAL=8E•VAL=6E•VAL=4E•VAL=2E•VAL=3LEXVAL=2LEXVAL=3LEXVAL=214对2*3+2进行分析和翻译(实为计算值)该输入串过程如下表所示。当状态1面临#时对应的分析动作为acc(接受)，此时，相应的语义动作为printVAL[TOP]，即输出语义程序的计值结果：8。步骤状态栈语义值栈符号栈输入串归约规则及动作10－＃2*3+2＃S3203－－＃2*3+2＃r4301－2＃E*3+2＃GOTO[0,E]=1,S54015－2－＃E*3+2＃S350153－2－－＃E*3+2＃r460158－

7、2－3＃E*E+2＃GOTO[5,E]=8,r2701－6＃E+2＃GOTO[0,E]=1,S48014－6－＃E+2＃S390143－6－－＃E+2＃r4100147－6－2＃E+E＃GOTO[4,E]=7,r11101－8＃E＃acc15§5.2中间语言一、引言二、逆波兰表示三、三元式四、树形表示五、四元式16一、引言1.什么是中间语言2.为什么要引入中间语言17一、引言1.什么是中间语言就是和源程序等价的一种编码形式，其复杂性介于源程序和机器语言中间。源程序前端中间代码代码优化器中间代码代码生成器目标程序符号表182.为什么要引入中间

8、语言（1）为了使编译程序结构上逻辑简单明确（2）为了便于目标代码优化工作（3）便于目标代码生成19二、逆波兰表示1.表达式逆波兰表示（1）逆波兰表示的概念对于一个算术表达式A+B