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

第八章语法制导翻译和中间代码生成,教学要求：本章介绍编译程序的第三个阶段语义分析及中间代码生成的设计原理和实现方法，要求理解语法制导翻译、语义动作的基本概念；掌握属性文法和中间代码。教学重点：语法制导翻译基本思想，语法制导翻译概述，基于属性文法的处理方法，中间代码的表示形式。,语义处理功能：1、静态语义审查：验证语法结构合理的程序是否真正有意义。2、解释执行动态语义、生成代码：执行真正的翻译（生成中间代码或目标代码）。,1、属性文法（说明语言语义的工具）定义,属性文法是一个三元组:A=(G,V,F),其中：G:是一个上下文无关文法。V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连。如它的类型、值、代码序列、符号表内容等等。F:关于属性的属性断言或一组属性的计算规则(称为语义规则).断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性.,8.1属性文法,例1：定义表达式的文法如下：EE+EE(E)En给出定义表达式值的属性文法。,为文法符号E引进属性符号val,用E.val表示E的值，属性计算规则以赋值语句的形式给出，附在每个产生式后，并用大括号括起来。为了明确E的不同出现位置，用上角标区别。终结符n的值是词法分析程序提供的，这里用n.lex表示。下面给出属性文法：EE1+E2E.val:=E1.val+E2.valE(E1)E.val:=E1.valEnE.val:=n.lex属性文法的主要思想有两点：首先对于每个文法符号引进相关的属性符号；其次对于每个产生式写出属性值计算的规则。,2、属性分类,综合属性：一个结点的属性值是从其子结点的属性值计算出来的。继承属性：一个结点的属性值是由该结点兄弟结点和父结点的属性值计算出来的。,3、属性的计算,综合属性计算自底向上按照语义规则来计算各结点的综合属性值继承属性计算根据依赖关系决定计算顺序,例1台式计算器程序的语法制导定义,产生式语义规则,print(Eval)Eval:=E1val+TvalEval:=TvalTval:=T1val*FvalTval:=FvalFval:=EvalFval:=digitlexval,1、与LE相连的语义规则是一个过程，打印E的值，理解为L的属性是虚的或空的。2、E,T,F的属性val都为综合属性。3、lexval是单词digit的属性（由词法程序提供）。,LEEE1+TETTT1*FTFF(E)Fdigit,digitlexval:=3,Fval:=3,Tval:=3,digitlexval:=5,Fval:=5,Tval:=15,*,Eval:=15,+,digitlexval:=4,Fval:=4,Tval:=4,Eval:=19,L,例5.2输入：3*5+4,例2：说明语句语法制导定义(属性文法),L.in:=T.typeT.type:=integerT.type:=realL1.in:=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in),entry单词id的属性addtype在符号表中为变量填加标识符的类型信息,DTLTintTrealLL1,idLid,例2：realid1,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指针在任何时刻与分析栈栈顶指针所指对象相同。,中间代码：源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。,8.3中间代码的形式,常用的中间代码：逆波兰式、四元式、三元式、树形表示。,约定符号：,LJ:表示转向某标号处,TJ:表示按真转,FJ:表示按假转,RJ:表示无条件转,意义：逻辑结构清楚；利于不同目标机上实现同一种语言；利于进行与机器无关的优化。,一、逆波兰表示,1、表达式的表示：,例：a+b,2、赋值语句的逆波兰表示：,左部:=,:=,例:x:=5,X5:=,ab+,例：-a+b*c,例：(a+b)*c,abc*+,ab+c*,典型特征是操作数在前，操作符紧跟其后。,特点:由于操作符紧跟操作数之后，因此只要知道操作符有几个操作数，每一步的运算就可以确定。,例:A+B*(C-D)+E/(C-D)N,逆波兰:ABCD-*+ECD-N/+,后缀式并不局限于二元运算的表达式，可以推广到任何语句，只要遵守操作数在前，操作符紧跟其后的原则即可。典型的例子如if-then-else语句：ifethenxelsey将if-then-else看作一个完整的操作符，则e、x和y分别是三个操作数，这显然是一个三元运算。根据后缀式的特点，它的后缀式可以写为：exyif-then-else(记为:exy￥)但是，这样的表示有个弱点。按照算法的计算次序，e、x和y均需计算，而实际上，根据条件e的取值，计算x则不计算y，计算y则不计算x。,3、转向语句的逆波兰表示:,4、条件语句的逆波兰表示:,无条件转:,格式:RJ,按真转:,格式:TJ,按假转:,格式:FJ,goto,5、循环语句的逆波兰表示:,fori:=1to100dos:=s+i;,例:goto10,10LJ,LJ,i:=1;10:ifi=100thenbegins:=s+i;i:=i+1;goto10;end;,i1:=i100=21FJssi+:=ii1+:=10RJ,例:ifabthenx:=a+belsex:=a-b,ab,13FJ,xab+:=,18RJ,xab-:=,fori:=1to100dos:=s+i;,逆波兰表达式的处理,1、逆波兰表达式的处理算法,从左到右扫描逆波兰表达式:凡是遇到运算分量,则运算分量入栈;凡是遇到运算符,则把运算分量栈栈顶的两个或一个分量取出,生成相应的目标指令,运算结果存入栈中.如上一直处理下去，直到整个逆波兰表达式处理完毕为止.,2、逆波兰表达式的处理具体过程,例如,对于表达式abc*+d*对其具体处理过程如下:,例:m:=a*b+c/d,(*,a,b,T1)(/,c,d,T2)(+,T1,T2,T3)(:=,T3,-,m),二、四元式,1.四元式:,格式:(,),2.表达式和赋值四元式:,例:a*b,(*,a,b,T),3.转向语句和条件语句的四元式:,无条件转移:,gotoL,(RJ,-,-,L),i:=1;10:ifi=100thenbegins:=s+i;i:=i+1;goto10end;20:,(:=,1,-,i)(=,i,100,T1)(FJ,T1,-,20)(+,s,i,s)(+,i,1,i)(RJ,-,-,10)(),ifAthengotoL1elsegotoL2,按真转：(TJ,A,-,L1),按假转:(FJ,A,-,L2),4.循环语句的四元式:,fori:=1to100dos:=s+i;,三、三元式,1.三元式:,格式:(,),例: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.转向语句和条件语句的三元式:,ifabthenx:=a+belsex:=ab;,(1)(,a,b)(2)(FJ,(6),(1)(3)(+,a,b)(4)(:=,(3),x)(5)(RJ,(8),/)(6)(-,a,b)(7)(:=,(6),x)(8)(),fori:=1to100dos:=s+i;,i:=1;10:ifi=100thenbegins:=s+i;i:=i+1;goto10;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,(1)(3)(+,A,(2)(4)(-,C,D)(5)(,(4),N)(6)(/,E,(5)(7)(+,(3),(6),对于表达式：,a+b,a-b,-a,a*b-(c+d)/(ef),四、树形表示,树表示为：,