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

1,第五章语法制导翻译及中间代码生成,5.1语法制导翻译概述5.2中间语言5.3自底向上语法制导翻译5.4自顶向下语法制导翻译5.5属性文法与属性翻译,2,5.1语法制导翻译概述一、语法制导翻译定义二、语法制导翻译原理三、语法制导翻译实现,3,一、语法制导翻译定义语法制导翻译就是以语法分析为主导的语义处理。在语法分析过程中嵌入语义动作，即调用对应的语义子程序。例如在前面语法分析时分析a+b*c表达式，其分析语法树如下：,E,+,E,E,*,E,E,a,b,c,在语法分析同时进行语义分析,4,二、语法制导翻译原理语法制导翻译的原理就是先为每个文法规确定相应的语义，即编写出相应语义处理子程序，整个分析是以语法分析为主导。语义动作：给每个文法符号X赋以各种不同的语义值,5,例如，假定有如下规则和语义动作：E=E(1)+E(2)EVAL:=E(1)VAL+E(2)VAL,6,例5.1设有文法E=E+EE=digit这里digit代表0和9之间任一数字，如果我们的目的仅是为了求值，则语义动作如下(1)E=E(1)+E()EVAL:=E(1)VAL+E(2)VAL(2)E=digitEVAL:=digit假定语义动作中的“+”代表是整型加算术运算。,7,例如，假定有输入串1+2+3，我们通过语法树的分析来看如何进行语法制导翻译，来求出该句子最后值。输入串1+2+3的语法树如下图所示.,E,+,E,E,+,E,E,1,2,3,8,(1)X=动作1(2)Y=动作2(3)A=XY动作3现在对LR分析器的分析栈加以扩充，为了在语法分析过程中平行地进行语义处理，使得每个文法符号之后都跟着它的语义值，因此，设置一个语义信息栈，为了清晰起见，我们把这个分析栈每一项分三部分组成：状态STATE、文法符号SYM和语义值VAL。,三、语法制导翻译实现,9,TOP,STATE,VAL,SYM,分析栈如下图所示:,10,我们假定先归约后执行语义子程序，所以当X，Y归约为A,Sm和Sm-1归约为新状态S后，执行语义子程序X和Y的值也归约为A的值。,11,TOP,归约前,TOP,归约后,YVAL,TOP,求值后,AVAL:=YVAL+XVAL,12,例5.2考虑下面文法及其语义描述：规则语义动作(0)S=EprintEVAL(1)E=E(1)+E(2)EVAL:=E(1)VAL+E(2)VAL(2)E=E(1)*E(2)EVAL:=E(1)VAL*E(2)VAL(3)E=(E(1)EVAL=E(1)VAL(4)E=iEVAL:=LEXVAL,13,规则程序段(0)S=EprintVALTOP(1)E=E(1)+E(2)VALTOP：=VALTOP+VALTOP+2(2)E=E(1)*E(2)VALTOP：=VALTOP*VALTOP+2(3)E=(E(1)VALTOP:=VALTOP+1(4)E=iVALTOP:=LEXVAL,14,根据上述程序段，若输入2*3+2，就有如下图所示的语法制导翻译的分析树。,S,E,E,E,E,E,+,*,2,2,3,EVAL=8,EVAL=6,EVAL=4,EVAL=2,EVAL=3,LEXVAL=2,LEXVAL=3,LEXVAL=2,15,对2*3+2进行分析和翻译(实为计算值)该输入串过程如下表所示。当状态1面临#时对应的分析动作为acc(接受)，此时，相应的语义动作为printVALTOP，即输出语义程序的计值结果：8。,16,5.2中间语言一、引言二、逆波兰表示三、三元式四、树形表示五、四元式,17,一、引言1.什么是中间语言2.为什么要引入中间语言,18,一、引言1.什么是中间语言就是和源程序等价的一种编码形式，其复杂性介于源程序和机器语言中间。,源程序,前端,中间代码,代码优化器,中间代码,代码生成器,目标程序,符号表,19,2.为什么要引入中间语言（1）为了使编译程序结构上逻辑简单明确（2）为了便于目标代码优化工作（3）便于目标代码生成,20,二、逆波兰表示1.表达式逆波兰表示,（1）逆波兰表示的概念对于一个算术表达式A+B或逻辑表达式AB，根据运算符和运算对象的位置关系，可分为三种等价表示形式：1)中缀表示法运算符在运算对象中间，如：A+B，AB，a+b*(c+d*(e-f)等.,21,2)后缀表示法将运算符放在运算对象后面，通常将后缀表示称为逆波兰表示.如：A+B表示为AB+，AB表示为AB，a+b*c表示为abc*+对于逆波兰表示非常适合机械处理，只要从左到右按运算顺序一个个计算下去3)前缀表示法即将运算符放在运算对象前面。如:+AB，AB，,22,例如表达式中缀表示和后缀表示如下表所示,23,(2)逆波兰(后缀)表示的优点1）后缀表示是一种无括号表示法，不但简明，而且又确切规定了计算顺序。2）运算处理极其简单方便，只要从左到右扫描后缀表达式各个符号,就能进行对表达式处理3)十分方便容易生成目标指令,24,(3)用后缀表示对表达式处理的过程下面通过求后缀表达式ab+c*的值，来说明用后缀表式对表达式处理的过程设a，b和c分别为1，3和5，为了求13+5*的值，其计算过程如下：1)把1推进栈。2)把3推进栈。3)将栈顶两个元素1和3相加，使它们退出栈，然后把结果4存入栈。4)把5推进栈。5)将栈顶两个元素4和5相乘，使它们退出栈，然后将结果20存入栈。结束时栈顶的值(这里是20)是整个表达式值。,25,（1）赋值语句左部:=表达式把赋值号“:=”看成是一个赋值运算符，它的后缀式为左部表达式的后缀式：=例如：x:=5x:=a*b-c/d的后缀式分别为x5:=xab*cd/-:=,2.逆波兰表示的扩充,26,（2）条件语句ifEthenS1elseS,27,3.语法制导翻译生成后缀式,28,（1）定义三元式的一般形式为(i)(OP,ARG1,ARG2)其中：(i)为三元式的编号，不同三元式不能有相同的编号OP是运算符部分ARG1和ARG2是运算对象部分，它们或者指向符号表登记项指示器(对于运算对象是常数或标识符的情况)，或者是一个指向三元式序列(或三元式表)中某一个三元式位置的指示器(对于运算对象是中间结果的情况)。,三、三元式表示1.三元式,29,如：A+B*C对应的三元式表示为：（1）（*，B，C）（2）（+，A，（1）,30,对于一目运算符OP，ARG1和ARG2只需其一。我们可以随意规定选用一个，例如，规定用ARG1。至于多目运算符可以用若干个相继三元式表示。如：赋值语句x:=-b*(c+d)用三元式来表示，则可写成(1)(-,b,)(2)(+,c,d)(3)(*,(1),(2)(4)(:=,x,(3)其中，三元式(3)就引用三元式(1)和(2)的结果作为它的两个运算对象,31,（2）三元式的生成同样可以用语法制导翻译来产生三元式：,32,2.间接三元式为了便于代码优化，常常采用间接三元式。这由两张表组成：（1）三元式表，用来存放各三元式本身；（2）执行表(间接码表)，它按执行三元式顺序，依次列出相应各三元式在三元式表中位置。,例如，对于如下赋值语句x:=a*b+c+a*b若按三元式表示，可写成(1)(*,a,b)(2)(+,(1),c)(3)(*,a,b)(4)(+,(2),(3)(5)(:=,x,(4)其中，三元式(1)和(3)完全一样，但是不能将(3)省去。,按间接三元式表示，则可写成执行表三元式表(1)(1)(*,a,b)(2)(2)(+,(1),c)(1)(3)(+,(2),(1)(3)(4)(:=,x,(3)(4),33,间接三元式的优点：（1）便于代码优化（2）节省空间,34,四、树形表示1.表示方法我们可以用树形数据结构来表示一个表达式或语句。在树表示中，叶子结点表示运算对象，即常量或变量，其它结点表示运算符，如表达式a+b,a-b,-a的树表示分别定义为：,+,a,b,a,b,a,35,双目运算对应二叉树，多目运算对应多叉树，单目运算对应单叉树。如表达式a*b-(c+d)/(e-f)的二叉树如下图：,后序遍历上述二叉树便得到该表达式的逆波兰表示为ab*cd+ef-/-,*,/,a,b,+,c,d,e,f,36,表达式的三元式可以看作是树的直接表示，图5.7所对应的三元式为(1)(*,a,b)(2)(+,c,d)(3)(-,e,f)(4)(/,(2),(3)(5)(-,(1),(4)显然，每一个三元式对应一棵子树，子树的根便是三元式的运算符，三元式的运算对象是子树两个分枝。,37,2.树表示生成,38,五、四元式表示四元式是一种用得比较多的一种中间语言代码形式，四元式一般形式是(OP，ARG1，ARG2，RESULT)其中：OP是运算符，其含义与三元式中OP类似；ARG1和ARG2是运算对象，RESULT是运算结果,