《第11章 语义分析和中间代码生成.ppt》由会员分享，可在线阅读，更多相关《第11章 语义分析和中间代码生成.ppt（77页珍藏版）》请在三一文库上搜索。
1、第11章 语义分析和中间代码生成,一、语义分析概述 二、中间代码 三、语义变量和语义函数 四、说明语句的翻译 五、赋值语句的翻译 六、控制语句的翻译,一、语义分析概述,1. 语义分析的任务 语义检查：一致性检查（类型是否一致）；越界检查（数组维数是否正确）。 语义处理：对说明语句，将信息登记在符号表中；对执行语句，生成中间代码。,2. 语义分析和语法分析的关系,语法分析只能判断一个句子是否合法，不能给出句子的含义。句子的含义是通过语义分析体现出来的。 例：一个计算程序对表达式“i+i”的分析过程。 表达式文法G(E) ： E E + E | E E | E * E | E / EE i,仅执行
2、语法分析,分析结果：“i+i”是一个合法的表达式,结合了语义分析的语法分析,分析结果：“i+i”是一个合法的表达式，值为3,赋予每个文法符号X以各种不同的值，这些值称为语义值。 语义值的表示形式为：X.XXX 如：S.VALUE、i.VALUE、i.TYPE,3. 语义值,例：结合了语义分析的LR分析过程。 XAB YCD ZXY ,B A ,B.XXX A.XXX ,移进时(A、B)，语义值同步入栈：, ,X ,X.XXX ,归约时(XAB)，语义值保存到新符号(X)中：, ,D C X ,D.XXX C.XXX X.XXX ,移进时(C、D)，语义值同步入栈：, ,Y X ,Y.XXX X
3、.XXX ,归约时(YCD)，语义值保存到新符号(Y)中：, ,Z ,Z.XXX ,可见：在每一次归约时，都必须保存符号的语义值。,归约时(ZXY)，语义值保存到新符号(Z)中：, ,4. 语义动作和语义子程序,每当用一个产生式进行匹配或归约时，需要执行相应的动作对语义值进行操作，这些动作称为语义动作。 每个产生式对应一个语义子程序，负责完成相应的语义动作。 每当用一个产生式进行匹配或归约时，相应的语义子程序被调用，完成相应的语义动作。,语义子程序实例,(1) E E1 + E2 E.VAL := E1.VAL + E2.VAL (2) E i E.VAL := i.VAL 分析输入串“i+i
4、”时，语义分析与语法分析同步进行。由语法分析判断输入串“i+i”是否合法，由语义分析计算“i+i”的值。,yacc中的语义子程序,实例分析： main1.c + lex3.l + yacc5.y,二、中间代码,编译程序的任务是将源程序翻译成目标程序。因此，编译程序的语义分析不仅要操作各符号的语义值，还需要完成源程序中各个语句的翻译，将源代码翻译成目标代码。 通常情况下，由于通用性和优化的考虑，语义分析生成的目标代码并不是最终的与硬件相关的汇编代码或机器代码，而是某种特定形式的中间代码。,中间代码有不同的表现形式（如三地址代码、四元式、后缀式、语法树等），本课程采用三地址代码的形式。 三地址代码
5、常用的语句形式有以下几类： （其中，op为一元或二元运算符，rop为关系运算符，x、y、z为操作数。）,常用的三地址语句形式,(1) x = y op z （二元运算） (2) x = op y（一元运算） (3) x = y（赋值） (4) goto x（无条件转移） (5) if x goto y（条件转移） (6) if x rop y goto z（条件转移）,源语句 a: = - b * c + d 对应的中间代码为 (1)t1 = - b (2)t2 = t1 * c (3)t3 = t2 + d (4)a = t3 注意：语义分析不仅要生成中间代码，还需要生成相关的数据（存放在相
6、应的表格中）。,中间代码实例,语义分析的结果,符号表,中间代码表,代码,数据,语法制导翻译,随着语法分析的进行，语义子程序依次被调用，逐步生成中间代码（和相关数据）。语法分析完成时，也就获得了完整的与源代码等价的中间代码。 在语法分析的过程中，由各个产生式对应的语义子程序对源代码进行翻译（生成中间代码）的方法称为语法制导翻译。,三、语义变量和语义函数,语义子程序中常用到的变量和函数： (1) i.NAME 表示符号 i 对应的变量的名称。 (2) E.PLACE 表示符号E对应的变量在符号表中的位置（普通变量）或整数编码（临时变量）。 (3) enter(NAME, TYPE, OFFSET)
7、 将一个新的符号加入符号表。,(4) newtemp() 生成一个新的临时变量，返回其整数编码。 (5) entry(i) 在符号表中查找符号 i ，如果存在，则返回它在符号表中的位置。 (6) emit (x = y op z) 生成一个新的三地址语句，添加到中间代码表的结尾。（注：指针ip指向中间代码表的结尾，emit将新的三地址语句添加到ip指向的位置，然后ip自动加1，指向新的结尾。）,四、说明语句的翻译,说明语句实例（C语言）： int abc; float f1, f2, f3;,说明语句实例（Pascal语言）： var abc : integer; f1, f2, f3 : r
8、eal;,说明语句的文法表示, （C） :（Pascal） , | int | float | ,简化起见，我们采用下列文法： D D ; D | i : T T real | integer 说明语句的翻译（通过语言子程序实现）主要是将变量相关的说明信息存放在符号表中。,语义子程序,(1) S MD (2) M OFFSET = 0; (3) D D ; D (4) D i : T enter(i.NAME, T.TYPE, OFFSET; OFFSET = OFFSET + T.WIDTH; ,(5) T integerT.TYPE=integer; T.WIDTH=4; (6) T re
9、al T.TYPE=real; T.WIDTH=8; ,五、赋值语句的翻译,赋值语句实例： abc:=1; a:=1+2; b:=a+b*c; 赋值语句的文法表示： A i := E E i E - E1 E (E1) EE1 op E2 ,语义子程序,A i := E P=entry(i.NAME); if(P!=0) emit (P = E.PLACE); else error(); E i P=entry(i.NAME); if(P!=0) E.PLACE=P; else error(); ,E - E1 E.PLACE=newtemp(); emit (E.PLACE = - E1.P
10、LACE); E (E1) E.PLACE = E1. PLACE EE1 op E2 E.PLACE=newtemp(); emit(E.PLACE = E1.PLACE op E2.PLACE); ,例子：a:=-b*(c+d)的语法分析,例子：a:=-b*(c+d)的翻译,4. E1 i E1.PLACE = entry(i.NAME) = b 5. E2 - E1 E2.PLACE = newtemp() = T1 emit ( T1, =, -,b) 9. E3 i E3.PLACE = entry(i.NAME) = c 12. E4 i E4.PLACE = entry(i.NA
11、ME) = d,中间代码表,ip ,T1 = - b,13. E5 E3 + E4 E5.PLACE = newtemp() = T2 emit (T2, =, c , +, d) 15. E6 (E5) E6.PLACE = E5.PLACE = T2 16. E7 E2 * E6 E7.PLACE = newtemp() = T3 emit (T3, =, T1 , * , T2 ,) 17. A i := E7 emit (a, = , T3),a = T3,T2 = c + d,T3 = T1 * T2,ip ,中间代码表,六、控制语句的翻译,语句级控制结构是语言用来构造各种语句执行顺
12、序的机制。 传统语言有3种语句级控制结构： 1. 顺序 2. 选择 3. 重复,顺序是指令指针（硬件）的值自动加1以获取下一条指令的抽象。 选择和重复是显示修改指令指针的值以获取下一条指令的抽象。 大多数语言也提供了无条件转移语句（如goto语句），这是任意修改指令指针的值以获取下一条指令的抽象。,常见的控制语句,goto语句 标号语句 “if B then S”语句 “if B then S1 else S2” while语句 for语句,1. goto语句的翻译,goto语句实例： goto L; goto L1; goto L2; goto语句的文法表示： S goto lable 根据
13、标号lable是否已定义，分为两种情况：,(1) lable已定义, L: / 将L加入符号表，定义否为“已”，地址为其后第一个三地址语句的地址。 goto L; / 查符号表，取出L的地址xxx，生成三地址语句 goto xxx。 goto L; / 同上 ,名字,类型,定义否,地址,L,标号,已,108, (n) goto 108 ,符号表,三地址语句,(2) lable未定义, goto L; / 生成三地址语句 goto 0，将L加入符号表，类型为“标号”，定义否为“未”，地址为本三地址语句的地址。 goto L; / 生成三地址语句 goto ?，与符号表中L的地址组成一个链表（“拉
14、链”），更新L的地址为本三地址语句（链首）的地址。 goto L; / 同上 L: / “回填”三地址语句链表，更新符号表中L的地址，定义否改为“已” 。 ,名字,类型,定义否,地址,L,标号,未,r, (p) goto 0 (q) goto p (r) goto q,符号表,三地址语句,“拉链”和“回填”技术,拉链 将转移目标不确定的三地址语句连接成一个链表的过程。 回填 待转移目标确定下来后，用它回填链表中所有三地址语句的转移目标的过程。,相关语义变量和语义函数,S.CHAIN：语义变量，记录三地址语句链的链头。 例如： (p) goto 0 (q) goto p (r) goto q 链
15、头：S.CHAIN = r,merg(t1,t2)：语义函数，合并t1、t2两个链，返回新链t3。 例如： t1 = r，t2 = w： (p) goto 0 (u) goto 0 (q) goto p (v) goto u (r) goto q (w) goto v 执行merg(t1,t2)后，得到新链t3： (p) goto 0 (u) goto r (q) goto p (v) goto u (r) goto q (w) goto v,backpatch(chain, address)：语义函数，用address回填chain链。 例如：执行backpatch(t3,120)后: (p
16、) goto 120 (u) goto 120 . (q) goto 120(v) goto 120 . (r) goto 120 (w) goto 120,2. 标号语句的翻译,标号语句实例： L: L1: L2: 标号语句的文法表示： label i: 其中，i 是一个标识符，代表一个转移的目标（例如：“L”、“L1”、“L2”）。,翻译标号语句时，不会生成新的三地址语句，但需要更新符号表。分两种情况处理： (1) 若 i（例如：“L”）不在符号表中，则把 i 加入符号表，置“类型”栏为“标号”，“定义否”栏为“已定义”，“地址”栏为 ip 的当前值（即标号 i 后第一个三地址语句的地址）
17、。,(2) 若 i 已在符号表中，“类型” 为“标号”，“定义否” 为“未定义”，则： 把“地址”栏中的链首地址（假定为 r）取出，用 ip 的当前值回填该链表，即执行语义函数backpatch（r, ip）。 将“地址”更新为 ip 的当前值，将定义否更新为“已”。,3. “if B then S”语句的翻译,语句实例： if ab then b:=1; if a then b:=1; if c then if a then b:=1; if d then if c then if a then b:=1; ,文法表示,文法：S if B then S1 由图可知： 布尔表达式B具有真、假两
18、个出口。在翻译B时，不能确定其真假出口转向的目标。 在翻译S1时，能够确定B的真出口，不能确定B的假出口。 在翻译S1时，不能确定S1中的出口语句转向的目标。,B,S1,?,B为假,B为真,?,(1) 布尔表达式B的翻译,布尔表达式B的文法： B i B i1 rop i2 作为控制条件的布尔表达式，它为真或假时，要转移到不同的地方。因此，引入语义变量： B.T：真出口，记录B为真的转移语句地址 B.F：假出口，记录B为假的转移语句地址,语义子程序,B i B.T := ip; emit (if i goto 0); B.F := ip; emit (goto 0) Bi1 rop i2 B.
19、T := ip; emit (if i1 rop i2 goto 0); B.F := ip; emit (goto 0),(2) 文法及改造,文法：S if B then S1 用S1的第一条三地址语句的地址回填B.T链。 改写文法： M if B then S M S1,B,S1,?,B为假,B为真,?,语义子程序,M if B then backpatch(B.T, ip); M.CHAIN := B.F S M S1 S.CHAIN := merg(M.CHAIN , S1.CHAIN) ,例子：if ab then a:=a+b if ab if B B.T=100 100: if
20、a b goto 0 B.F=101 101: goto 0 if B then M backpatch(100,102) M.CHAIN=101 M a:=a+b M A 102: t1=a+b 103: a =t1 M S1 S1.CHAIN=0 S S.CHAIN=merg(M.CHAIN,S1.CHAIN) =101,102,4. “if B then S1 else S2”的翻译,语句实例： if a then b:=1; else b:=2; if a then if b then else b:=2; if a then if b then else else b:=2; if
21、a then if b else if c ;,文法表示,文法： S if B then S1 else S2 用S1的第一条三地址语句的地址回填B.T链。 用S2的第一条三地址语句的地址回填B.F链。,B,S1,S2,?,B为假,B为真,?,?,S if B then S1 else S2 改写文法： M if B then N M S1 else S N S2,B,S1,S2,?,B为假,B为真,?,?,文法的改造,语义子程序 M if B then backpatch(B.T , ip); M.CHAIN := B.F N M S1 else q := ip; emit (goto 0)
22、; backpatch(M.CHAIN , ip); N.CHAIN := merg(S1.CHAIN , q) S N S2 S.CHAIN := merg(N.CHAIN , S2.CHAIN) ,例子：if ab then a:=a+b else a:=a-b if ab if B B.T=100 100: if ab goto 0 B.F=101 101: goto 0 if B then M backpatch(100,102) M.CHAIN=101 M a:=a+b M S1 102: t1=a+b S1.CHAIN=0 103: a=t1 M S1 else N q = 104
23、 104: goto 0 backpatch(M.CHAIN,105) N.CHAIN=merg(S1.CHAIN,q) =104 N a:=a-b N S2 105: t2=a-b S2.CHAIN=0 106: a=t2 S S.CHAIN=merg(N.CHAIN,S2.CHAIN) =104,5. while语句的翻译,文法S while B do S1 B的第一条三地址语句地址需记录。 用S1的第一条三地址语句的地址“回填”B.T链。,B,S1,?,B为假,B为真,?,?,S while B do S1 改写文法： W while D W B do S D S1,B,S1,?,B为假
24、,B为真,?,?,翻译方案 W while W.CODE := ip D W B do backpatch (B.T , ip); D.CHAIN := B.F; D.CODE := W.CODE S D S1 backpatch(S1.CHAIN , D.CODE); emit (goto D.CODE); S.CHAIN := D.CHAIN ,6. for语句的翻译,文法 S for i:=E1 step E2 until E3 do S1 其语义如图所示：,S for i:=E1 step E2 until E3 do S1 改造文法为： F1 for i:=E1 F2 F1 step
25、 E2 F3 F2 until E3 S F3 do S1,翻译方案 (1) F1 for i:=E1 P=entry(i.NAME); emit ( P, =, E1.PLACE ); F1.PLACE := P; F1.CHAIN: = ip; emit ( goto 0 ); F1.AGAIN := ip (2) F2 F1 step E2 F2.AGAIN := F1.AGAIN; F2.PLACE := F1.PLACE; emit (F2.PLACE = F2.PLACE + E2.PLACE ,) backpatch ( F1.CHAIN , ip ) ,(3) F3 F2 un
26、til E3 F3.AGAIN := F2.AGAIN; F3.CHAIN := ip; emit ( if F2.PLACE E3.PLACE goto 0 ) ; (4) S F3 do S1 emit ( goto F3.AGAIN ); backpatch ( S1.CHAIN , F3.AGAIN ); S.CHAIN := F3.CHAIN; ,习题,1. 对文法G(E)： EE+TT TT*FF F(E) i 给出表达式 (5*4+8)*3 的语法树，并注明各结点的语义值VAL。,2. 写出表达式 -(a+b)*(c+d)-(a+b+c) 的翻译过程。 3. 写出赋值语句 A:=
27、B*(-C+D) 的翻译过程。,4. 对下列翻译方案 S PS print 1 S PQ print 2 P a print 3 Q bR print 4 Q dQ print 5 R c print 6 当输入串为 aaadbc 时，翻译结果是什么？,5. 写出语句 if CB do x:=y+2*z 的翻译过程。 6. 写出语句 while AC do if A=1 then C:=C+1 else while AD do A:=A+2 的翻译过程。,7. 试写出 for i:=1 to N do S1 的语义子程序。,77,扩充第10章中完成的语法分析器，修改yacc文件中的语义子程序，实现语法分析的过程中，同步生成中间代码的功能。,课后练习,