编译原理第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+E E=digit 这里digit代表0和9之间任一数字，如果我们的目的仅是为了求值，则语义动作如下(1)E=E(1)+E()EVAL:=E(1)VAL+E(2)VAL(2)E=digit EVAL:=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=E print EVAL(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=i EVAL:=LEXVAL,13,规 则 程序段(0)S=E print VALTOP(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=i VALTOP:=LEXVAL,14,根据上述程序段，若输入2*3+2，就有如下图所示的语法制导翻译的分析树。,S,E,E,E,E,E,+,*,2,2,3,E VAL=8,E VAL=6,E VAL=4,E VAL=2,E VAL=3,LEXVAL=2,LEXVAL=3,LEXVAL=2,15,对2*3+2进行分析和翻译(实为计算值)该输入串过程如下表所示。当状态1面临#时对应的分析动作为acc(接受)，此时，相应的语义动作为print VALTOP，即输出语义程序的计值结果：8。,16,5.2 中间语言 一、引言 二、逆波兰表示 三、三元式 四、树形表示 五、四元式,17,一、引言 1.什么是中间语言 2.为什么要引入中间语言,18,一、引言 1.什么是中间语言 就是和源程序等价的一种编码形式，其复杂性介于源程序和机器语言中间。,源程序,前端,中间代码,代码优化器,中间代码,代码生成器,目标程序,符号表,19,2.为什么要引入中间语言（1）为了使编译程序结构上逻辑简单明确（2）为了便于目标代码优化工作（3）便于目标代码生成,20,二、逆波兰表示 1.表达式逆波兰表示,（1）逆波兰表示的概念 对于一个算术表达式A+B或逻辑表达式AB，根据运算符和运算 对象的位置关系，可分为三种等价表示形式：1)中缀表示法 运算符在运算对象中间，如：A+B，A B，a+b*(c+d*(e-f)等.,21,2)后缀表示法 将运算符放在运算对象后面，通常将后缀表示称为逆波兰表示.如：A+B表示为AB+，A B表示为AB，a+b*c表示为abc*+对于逆波兰表示非常适合机械处理，只要从左到右按运算顺序一个个计算下去3)前缀表示法 即将运算符放在运算对象前面。如:+AB，AB，,22,例如表达式中缀表示和后缀表示如下表所示,23,(2)逆波兰(后缀)表示的优点 1）后缀表示是一种无括号表示法，不但简明，而且又确切规定了计算顺序。2）运算处理极其简单方便，只要从左到右扫描后缀表达式各个符号,就能进行对表达式处理 3)十分方便容易生成目标指令,24,(3)用后缀表示对表达式处理的过程 下面通过求后缀表达式ab+c*的值，来说明用后缀表式对表达式处理的过程 设a，b和c分别为1，3和5，为了求1 3+5*的值，其计算过程如下：1)把1推进栈。2)把3推进栈。3)将栈顶两个元素1和3相加，使它们退出栈，然后把结果4存入栈。4)把5推进栈。5)将栈顶两个元素4和5相乘，使它们退出栈，然后将结果20存入栈。结束时栈顶的值(这里是20)是整个表达式值。,25,（1）赋值语句 左部:=表达式 把赋值号“:=”看成是一个赋值运算符，它的后缀式为 左部表达式的后缀式：=例如：x:=5 x:=a*b-c/d 的后缀式分别为 x5:=xab*cd/-:=,2.逆波兰表示的扩充,26,（2）条件语句 if E then S1 else S,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是运算结果,39,例如：赋值语句 a:=-b*(c+d)用四元式表示，则可写成(1)(-,b,T1)(2)(+,c,d,T2)(3)(*,T1,T2,T3)(4)(:=,T3,a),四元式之间联系是通过临时变量实现的，调整四元式之间相对位置并不意味着一定要改变一系列指示器值。因此，对中间代码进行优化处理时，四元式比三元式方便得多。下面主要讨论如何用四元式表示各种语句，并产生四元式语义子程序。,