编译原理第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