[高等教育]第七章语义分析和中间代码生成.doc

编译原理 第七章 语义分析和中间代码生成第七章 语义分析和中间代码生成知识结构： 语义分析语法分析概述 语法制导翻译 逆波兰式表示 三元式表示语义分析和中 中间语言 图型表示间代码生成 四元式表示 三地址语句表示 赋值语句的翻译 布尔表达式的翻译中间代码生成 控制语句的翻译 说明语句的翻译 过程语句的翻译第一节 语法制导翻译概述一、语义分析的任务在词法分析和语法分析的基础上进一步分析其含义，主要的工作是进行静态语义检查和翻译。二、语义分析的功能1、类型检查检查运算的合法性（运算对象的一致性）。2、一致性检查一个对象（标识符等）在一个分程序中只能被定义一次。3、相关名字检查如果一个名字必须出现多次，检查使用的名字是否相同的。4、控制流检查控制流语句必须使控制转移到合法的地方。5、确定类型确定标识符所关联得数据类型。6、识别含义确认程序中各种成分组合到一起的含义，并作相应的语义处理，对可执行的语句生成中间语言或目标语言。三、生成的语言1、直接生成目标语言根据源程序中各语法成分的语义，直接生成机器语言或汇编语言。其特点： 编译时间较短； 存储空间较大； 目标语言的质量较差。2、生成中间语言介于源程序语言和机器语言之间的机内表示形式。其特点： 编译程序的逻辑结构简单； 有利于编译程序的移植； 便于目标语言的优化。四、语义分析方法1、语法制导翻译方法在语法分析过程中，使用语法规则进行归约的同时，根据每个产生式的语义动作进行翻译（在语法规则的制导下，通过对语义规则的计算，完成对输入字符串的翻译）的方法。2、属性翻译方法指明语义规则的计算次序，陈述一些实现细节，以表达语义动作在语法分析过程中的执行时刻。五、语义规则为文法中的每一条产生式配置计算属性的计算规则。六、语法制导翻译为文法中每个产生式配备一组语义规则。1、语义规则语义规则计算包括：产生代码、在符号表中存放信息、在分析工作栈中填写语义值（属性值）,并生成相应的中间代码。2、自上而下分析用一条产生式与输入符号匹配成功时, 执行相应语义子程序生成中间代码。3、自下而上分析用一条产生式进行的归约时, 执行相应语义子程序生成中间代码。七、翻译简例表达式文法和相应的翻译模式：（P179）Sid:=E p:=Lookup(); if p nil then emit (p:=E.place)else error E.place 为属性值(语义变量)，代表存放E值的变量名在符号表的入口地址或指向代表E值的临时变量的整数值。 EE1+E2 E.place:=newtemp; emit( E.place:=E1.place+E2.place) 语法分析工作栈进行扩充,增加相应的语义值，语法分析同时(如归约时)，执行语义规则(语义子程序)。例：x:=y+z的语法制导翻译用EE1+E2归约 执行语义规则E2 E2.place E.place:=T1; + - 归约后 E E.place emit(T1:=y+z) E1 E1.place 符号 语义值 生成一条中间代码符号 语义值 用Sid:=E归约 执行语义规则 E E.place p:=Lookup(x); := - 归约后 s E.place emit (x:= T1) id id.place 符号 语义值 生成一条中间代码。 符号 语义值 这样语法分析结束时也就生成了中间代码： （0） T1:=y+z （1） x:= T1 注意：语义工作栈中的值与状态工作栈中的值一一对应，某些符号可能无相应的语义值，如上例“+”，保留语义栈位是用“”表示。归约时符号和语义值同时退出工作栈，同时进入工作栈。例A XYZ Z Z.z Y Y.y 归约后 A A.a X X.x 符号 语义值 符号 语义值 八、语义值（属性）和语义规则（语义子程序） 1、语义值代表文法符号的类型、值、符号表地址等语义子程序需要的信息。如 E.place（符号表指针）。2、语义规则对语义值（属性）进行计算，或其它加工处理过程。属性文法翻译使用语义规则进行属性值的计算。语法制导翻译给出使用语义规则进行计算的顺序（用 括号起来）。九、理解语法制导翻译的若干关键问题1、语义值（属性）代表的含义2、语义子程序（语义规则）3、语法制导翻译过程 翻译的顺序与语义子程序执行的顺序相关； 子程序执行的顺序与应用产生式进行归约的顺序相关； 归约的顺序与中间代码的顺序相关； 第二节 中间语言一、中间语言的表示形式1、后缀式（逆波兰表示）（P167 定义）2、图表示法（DAG无环路有向图，抽象语法树）3、三地址代码 三地址语句 四元式 三元式 间接三元式二、后缀式（逆波兰表示）1、表达式表示形式 中缀形式二目运算的运算符总是置于两个运算对象之间。例：a*（b+c） 后缀形式把运算符置于运算对象之后，将中缀式中的算符，按优先级或结合律重新排序。 后缀形式表达式E的定义 如果E是一个变量或常量，则E的后缀形式是E自身。 如果E是E1 OP E2形式的表达式，这里的OP是任何二元操作符，则E的后缀形式是E1E2 OP，这里E1和E2分别为E1和 E2的后缀形式。 如果E是（E1 ）形式的表达式，则E1的后缀形式就是E的后缀形式。例：中缀形式：a*（b+c），而后缀形式：abc+*2、中缀形式转换后缀形式的算法建立两个工作栈，存放运算对象和经处理后的运算符（逆波兰区）；另一个存放运算符，首先将“#”压入工作栈顶。 若输入的符号是运算对象，送入波兰区。 若输入的符号是运算符，送入运算符工作栈，操作过程： 工作栈顶运算符的优先级高于当前输入的运算符，将工作栈顶运算符弹出，送入逆波兰区，并把当前输入的运算符压入运算符工作栈； 工作栈顶运算符的优先级低于当前输入的运算符，将当前输入的运算符压入运算符工作栈； 若当前输入的符号是“#”，将运算符工作栈的符号依次弹出，送入逆波兰区。3、转换的语义规则 属性定义（语义变量）Ecode：表示E的后缀式，定义了识别的标识符（指针）。OP表示任意的二元操作符。“”表示后缀形式的连接。 语义规则的描述（P167）对同一产生式重复出现的文法符号用角标进行区分。例 a + b * （c + d * b） + d 4 3 2 1 5 后缀式：abcdb*+*+d+ 产生式 语义动作 Eid E.codeid EE1 OP E2 E.codeE1.codeE2.codeop三、图表示法1、抽象语法树语法树可以作为一种合适的中间语言形式。在语法树中去掉那些对翻译无效的信息，从而获得更有效的源程序中间表示。这种变换后的语法树为抽象语法树。抽象语法树的表示形式： 操作符和关键字作为内部结点。 运算对象作为叶子结点。例：354的抽象语法树 4 3 5 2、DAG图（无环路有向图）与抽象语法树一样，对表达式的每个子表达式，DAG都有一个结点。DAG图的结构： 内部结点为运算符。 子结点为操作对象。3、DAG与抽象语法树的区别（P168） DAG图的公共子表达式的结点具有多个父结点。 抽象语法树的公共子表达式对应重复子树。四、三地址代码1、三地址代码一般形式X := Y op Z 结果 操作数 操作符 操作数例：X+Y*Z中间代码为：T1 :=Y*Z T2 :=X+T1 T1, T2为临时变量（由编译生成）2、三地址语句的种类 (P170)： 二目运算的赋值语句x := y op z。 单目运算的赋值语句x :=op y 。 复制语句x := y。 无条件转移语句goto L（中间代码地址）。 条件转移语句if x relop y goto L或if a goto L。 调用语句param x和call p, n，返回语句return y。 索引赋值x := yi和xi := y（数组元素）。 地址和指针赋值x :=&y，x :=*y和 *x :=y。3、三地址代码的几种表示 四元式 （op，arg1，arg2，result）例：x:=y op z 的四元式(op，y，z，x)例：a:=b * -c + b* -c(，c，_，T1)(*，b，T1，T2)(，c，_，T3)(*，b，T3，T4)(+，T2，T4，T5)(:=，T5，_，a) 三元式 为了避免把临时变量填入符号表，用中间代码地址（指针）代表运算对象。（op，arg1，arg2）例：a:=b * -c + b * -c(0)(，c，_ )(1)(*，b，(0)(2)(，c，_ )(3)(*，b，(2)(4)(+，(1)，(3)(5)(:=，a，(4)例：xi:= y(0)(= ，x，i)(1)(:=，y,（0）)用两条三元式表示索引赋值。例：x:=yi(0)( =，y，i) (1)(:=，x，(0)(3) 间接三元式(P173)为了便于代码优化处理，不直接使用三元式的指针，而是另设一张间接代码表，按先后顺序列出三元式在三元式代码表中的位置。例：x:=(A+B)*cy:=D(A+B) 三元式代码表 间接代码表OP ARG1 ARG2 (1)(1) + A B (2)(2) * (1) C (3)(3) X (2) (1)(4) D (1) (4)(5) Y (1) (5) 比较几种形式的三地址代码a:=b*-c+b*-c三地址码 四元式 三元式间接三元式 T1:= - c (,c,-,T1) (,c,-)(0)(,c,- )(0) T2:=b*T1 ( *,b,T1,T2) (*,b,(0)(1)(*,b,(0) (1) T3:= - c (,c,-,T3 ) (,c,-) (2)(+,)(0) T4:=b*T3 (* ,b,T3,T4 ) (*,b,) (3)(：=，a,)(1) T5:=T2+T4 (+ ,T2,T4,T5) (+,) (4)(2) A:=T5 (:= ,T5 ,-,a) (：=，a,) (5)(3) 第三节 赋值语句的翻译一、简单算术表达式及赋值语句1、语义函数（子程序）P178Lookup()：查找在符号表中的入口地址。emit( )：生成三地址语句（中间代码）发送到输出文件中。例：emit(X:=uminusT) 产生中间代码。 newtemp：产生一个新临时变量名的整数码。如T1，T2，T3。 2、语义变量（属性）E.place：代表存放E值在符号表的入口地址或临时变量。 ：以存在的变量名。赋值语句的翻译模式（P179）Sid:=E p:=Lookup(); if p nil then emit (p:=E.place)else errorEE1+E2 E.place:=newtemp;emit( E.place:=E1.place+E2.place)EE1*E2 E.place:=newtemp;emit(E.place:=E1.place*E2.place)E-E1 E.place:=newtemp;emit(E.place:=uminusE1.place)E(E1) E.place:=E1.placeEid p:= lookup () if pnil then E.place:=pElse error例：X:=-B*(C+D) 的语法制导翻译过程输入 栈 Place 产生式 三地址代码 X:=-B*(C+D) X _ :=-B*(C+D) X:= _ _ -B*(C+D) X:=- _ _ _ B*(C+D) X:=-B _ _ _ _ Eid *(C+D) X:=-E _ _ _ B *(C+D) X:=E _ _ T1 E-E1 T1:=uminus B *(C+D) X:=E* _ _ T1_ (C+D) X:=E*( _ _ T1_ _ C+D) X:=E*(C _ _ T1_ _ _ +D) X:=E*(E _ _ T1 _ _C Eid +D) X:=E*(E+ _ _ T1 _ _C_ D) X:=E*(E+D _ _ T1_ _ C _ _ Eid) X:=E*(E+E _ _T1 _ _ C _ D ) X:=E*(E _ _ T1_ _T2 EE1+E2 T2:=C+D ) X:=E*(E) _ _ T1_ _ T2_ E(E) X:=E*E _ _T1 _T2 EE1*E2 T3:=T1*T2 X:=E _ _ T3 Sid:=E X:=T3 二、不同类型运算的翻译（P184）对不同类型运算，生成代码时首先进行类型转换。例：x:=y + i*j 其中x,y为实型， i,j为整型；产生三地址代码为：T1:= i int* jT2:= int to real T1T3:= y real+ T2X:=T3增加一个语义值（属性）类型属性 E.type语义栈扩充 state place typeEE1 + E2的语义规则（P184）E.place:=newtemp;if E1.type=integer and E2.type=integer then begin emit(E.place:=E1.placeint+E2.place)E.type=integer end else if E1.type =real and E2.type =real then beginemit(E.place:=E1.placereal+E2.place)E.type=realendelse if E1.type=integer and E2.type=realthen beginu:= newtemp; emit(u:= int to realE1.place)emit(E.place:=ureal+E2.place)E.type=real endelse if E1.type=real and E2.type=integer then beginu:= newtemp; emit(u:= inttoreal E2.place)emit(E.place:=E1.placereal+u)E.type=real end else E.type:=type_error 三、数组元素的引用1、编译对变量、数组元素的处理 为某过程的名字（变量、数组元素）分配空间，在中间代码中操作数用相对地址表示。2、符号表（实数域宽8字节, 整数域宽4字节） 某一过程有变量X, Y, i, j 名字 类型 相对地址 内存的分布 0 X Real 0 X8字节 1 Y Real 8 Y8字节 2 I Int 16 i4字节 3 J Int 20 j4字节 3、操作数在中间代码中表示： 如i的E.place为2（符号表的指针2）; 书面表达用名字i（直观）; 存储分配后相对地址16;4、数组元素地址的计算数组元素的存储方式：数组元素存放在一片连续的单元中，地址用相对地址表示。例 Var A：array12，13of integer； a11，a12，a13 a21，a22，a23 行排序 列排序 A1，1 A1，1 A1，2 A2，1 A1，3 A1，2 A2，1 A2，2 A2，2 A1，3 A2，3 A2，3 数组下标：沿着每一维的距离称为一个下标，每一维下标只能在上、下限之内变动。例：一维数组Alowhighlow为下标的下限、high为下标的上限。例：数组说明为A15, low=1, high=5。lowihigh （i取值范围）其中：i为一个下标值。数组下标变量:由数组名连同各维的下标值命名的，表示数组元素的地址。例：Ai数组元素地址的计算： 一维数组元素地址的计算D=base+(ilow)w = iw+(base-loww)其中：D表示数组元素Ai的相对地址；base为A的第一个数据元素A1的相对地址，w为域宽。(base-loww)为相对地址D的常量用CONSTPART表示。iw为相对地址D中的变量用VARPART表示。地址计算公式：D=CONSTPART+VARPART例：求A3的地址A334(10014)=12+96=108A0 96 A1 100 A2 104 A3 108例：一维数组A25, low=2、high=5，base为A的相对地址为100，w为4。相对地址偏移量：(base-loww)=10024=92。例：求A4的地址A4iw (base-loww)4492=108 A0 92 A1 96A2 100A3 104A4 108 二维数元素地址的计算(按行存放)：二维数组Alow1high1, low2high2例：Ai1,i2的地址D base+(i1-low1)n2+ i2-low2)w base+( i1n2 -low1n2+ i2-low2)w（i1n2+i2）w + base-(low1n2+low2)w /* n2为第二维的取值个数， n2=high2-low2+1 */CONSTPART= base-(low1n2+low2)wVARPART=（i1n2+i2）w例：二维数组A12，13, 求数组元素A1,3的地址。其中：low11，low21，high23，n23113。CONSTPART base-(low1n2+low2)w100（131）484 VARPART (i1n2+i2)w(1*3+3)*4=24A1,3 CONSTPART+VARPART84+24 = 108数组元素A1,3是第三个元素（按行存放）。A1，1 100A1，2 104A1，3 108A2，1 112A2，2 116A2，3 118制作人：李明新 共57页第57页 19-1-5 多维数组元素地址的计算D（i1n2+i2）n3+i3）nk+i k )w +base-(（low1n2+low2）n3+low3）)nk+lowk)wDVARPART + CONSTPART 数组内情向量： 下限值 上限值 每维界差 i1 h1 n1 in hn nn n（维数） C（常量） TYPE（类型） A（数组名称）数组元素在中间代码中的表示：用CONSTPART VARPATR两部分表示数组元素。例：A2，3:=E 中间代码为：Tj:= VARPATR; Ti := CONSTPART Ti保存语义值L.place符号表指针；Tj保存语义值L.offset属性变量。TiTj:=E L.placeL.offset:=E例：X:=A2,3的中间代码为：X:=TiTj四、含数组元素的赋值语句的翻译模式（P181）1、语义值和语义子程序L.place： 简单变量：指此名字的符号表入口。 数组元素：指保存CONSTPART的临时变量整数码。L.offset： 简单变量：null。 数组元素：指保存VARPART的临时变量整数码。Elist.array：表示数组名在符号表中的位置。Elist.ndim：下标个数（数组维数）计数器。Elist.place：保存VARPART的中间结果的临时变量整数码。Limit（array,m）：给出数组array第m维的长度。2、语义规则（翻译规则）：（P181-P182）Elistid E Elist.place:= E.place; Elist.ndim:=1; Elist.array := id.place Elist Elist1 ,E t:= newtemp; m:=Elist1.ndim + 1;emit(t:= Elist1.place*limit(Elist1.array,m)emit (t:=t+E.place)Elist.array := Elist1.array;Elist.place := tElist.ndim := m LElist L.place:=newtemp;emit(L.place := Elist.arry - c )L.offset:=newtemp;emit(L.offset := w *Elist.place)EL if L.offset = null then E.place := L.place else begin E.place := newtemp;emit(E.place:=L.placeL.offset) end EL:=E if L.offset=null /* L是简单变量*/Then emit(L.place := E.place)Else emit(L.place L.offset:=E.palce)例71 （P183）A110，120设w=4, A的第一个元素的地址为200。CONSTPARTbase-(low1n2+low2)w200-(1*20+1)*4:=200-84:=116写出X:=AY,Z的语法制导翻译过程Lid L.place:=Elist.placeL.offset:=nullElistid E Elist.place:=Y Elist.ndim:=1, Elist.array:=A ElistElist,E t:=T1 ，m:=1+1=2T1=Y*20T1:=T1+ZElist.array:=AElist.place:=T1Elist.ndim:=2 LElist L.place:=T2 T2:=200-84=116 L.offset:=T3T3:=4*T1EL E.place:=T4 T4:= T2 T3SL:=E ifL.offset=null Then X:=T4 else T2 T3:=X 第四节 布尔表达式的翻译一、布尔表达式的定义和翻译1、布尔表达式的定义布尔表达式是用布尔运算符号（and，or，not）作用到布尔变量或关系运算符上而组成的。 布尔表达式的作用 逻辑值的计算； 作为条件控制的布尔式。 布尔表达式的优先级（P185）算术运算符（一元负），*，/，+，。比较运算符=， , 。逻辑运算符not，and，or。2、布尔表达式的计算方法 按优先关系计算值用1代表true，0代表false 1 or ( not 0 and 0) or 0= 1 or (1 and 0) or 0= 1or 0 or 0= 1 or 0=1 按优化方式计算值A or B： if A then true else B (A为真时无需判断B)；A and B：if A then B else false(A为假时无需判断B)；not A： if A then false else true3、数值表示法的翻译例：ab 等价为if ab then 1 else 0翻译为：100: if ab goto 103101: T1:=0102: goto 104103: T1 :=1104:其中：T1的值表示ab结果例：a or b and not c翻译为：100： T1 := not c101： T2 := b and T1102： T3 := a or T2 数值表示法的翻译模式:EE1 or E2 E.place:= newtemp; emit(E.place := E1.place or E2.place) EE1 and E2 E.place:= newtemp; emit(E.place := E1.place and E2.place) E not E1 E.place:= newtemp; emit(E.place := not E1.place) E ( E1 ) E.place:= E1.place Eid1 relop id2 E.Place:=newtemp; emit(if id1.place relop.op id2.place gotonextstat + 3 ); emit(E.place:=0)； emit(gotonextstat + 2 ); emit(E.place:=1) Eid E.place:= id.place 例：ab or cd and ef的翻译过程 Eid1 r