语义分析-4-5-6节.pptVIP

6.4 布尔术表达式到四元式的翻译,用于逻辑赋值语句中布尔表达式演算； A:=BCDE 用作控制语句中的条件表达式 if ABC then S1 else S2 或 while i10 do S,1.布尔表达式的作用,E EE | EE | E | (E) | i | i R i R | | | | | i：布尔变量或数值变量（关系运算）； R：关系运算符 说明： 1). 此文法为二义文法 2). 布尔算符的优先顺序为： ，； 且，服从左结合律； 关系运算优先级别高于布尔运算。,2.布尔表达式的文法,与算术表达式类似，对每一步运算，生成一个四元式，结果存于一个临时变量中。 每个产生式的语义规则与算术表达式类似。,A:=BCDE （优先级别为：、）,四元式:,3. 翻译方法之一,1).翻译思想 对AB，若A=.T.，则不需考察B，就可得：AB.T.,根据A、B、C的取值，可能只需察看1个/2个/3个变量即可得出结论。而在方法(1)中，必须将3个变量的值取出并计算后，方可得出结果。 所以，也称此方法为优化方法。,A,真 E=.T. (一步),假,真,假 E=.F. (二步),真 E=.T. (三步),假 E=.F. (三步),例: A(BC),四个出口,4. 翻译方法之二（优化方法）, B, C,2). 结果四元式的形式（三类） (jnz , A , _ , P ) If A then goto P (jR, A1 , A2 , P ) If A1 R A2 then goto P (j , _ , _ , P ) Goto P 注：这些四元式都是转移四元式，其中P为四元式序号。,例: A(BC),四元式序列,P：为真时的出口 ； Q：为假时的出口,3).属性及语义子程序 E.truelist （或 E.TC, true chain）： 指针， 指向E为 “真” 的四元式构成的链的链首。 一般是E为 “真” 的最新一个四元式。,E.truelist=r，r qp，链尾四元式的第四区段=0；,例：若E有三个四元式是E的真出口，编号为：p、q、r 形成的链如下：, E.falselist (或 E.FC, false chain)：指针， 指向E为“假”的四元式构成的链的链首。 含义与 E.truelist 类似。 Nextquad (或 NXQ)：指针， 指向下一个要生成(但尚未生成）的四元式 编号。初值=1，执行 Gen， Nextquad+1。 M.quad ：指针，指向某个四元式。 makelist(i)：函数， 创建一个仅含i的新链表，i：四元式编号, 返回指向这个链的指针。, merge(P1,P2)：函数 将以P1、P2为链首的两条链合并，返回合并后 的链的链首。(一般为P2 ,若P2为空,则为P1) P1: P2: ,merge(P1,P2),P2: ,例：P1=101, P2=103， Merge(P1,P2),返回103,(100). ( jnz , A , , 102 ) (101). ( j , , , 0 ) (102). ( jnz , B , , 0 ) (103). ( j , , , 101 ),(100). ( jnz , A , , 102 ) (101). ( j , , , 0 ) (102). ( jnz , B , , 0 ) (103). ( j , , , 0 ), backpatch(P,t)：过程， 将P所指链中的每个四元式的第四区段均改为t。,做 backpatch 时，需要先暂存当前四元式的第四区段的值，便于处理链后面的元素。,P1=104 (100), P2=105 (103 )，backpatch(P1,200),(100). ( jnz , A , , 200 ) (101). ( j , , ,102 ) (102). ( jnz , B , , 104 ) (103). ( j , , , 0 ) (104). ( jnz , C , , 200 ) (105). ( j , , , 103 ),(100). ( jnz , A , , 0 ) (101). ( j , , ,102 ) (102). ( jnz , B , , 104) (103). ( j , , , 0 ) (104). ( jnz , C , , 100) (105). ( j , , , 103),4). 改造文法（便于语义分析） E E1 M E2 | E1 M E2 |E1|(E1)| i | i1 R i2 R | | | | | M ( 新引入的非终结符M ) 5).语义规则,归约顺序：,四元式：,E2的四元式,归约M时，记录此处的四元式号,归约 E1M E2 =E3 时， E3 =.T. E1=.T. 且 E2=.T. E1.Truelist 转至 E2 的开始位置，即M记录的位置； E3 =.F. E1 =.F. 或 E2 =.F. ，故两条链合并。,例：(AB)C 设：语法分析采用规范归约，（做规范推导找句柄） E7=E4M2E6 = E4M2 E5 = E4M2 i3 = E4 i3 = (E3 ) i3 = (E1 M1E2) i3 = (E1 M1 i2) i3 = (E1 i2) i3 = (i1 i2) i3 （其中红色标注的是句柄）,四元式:,(100). ( jnz ，A ， ， 0 ) (101). ( j ， ， ， 0 ) (102). ( jnz ，B ， ， 0 ) (103). ( j ， ， ， 0 ),(100). ( jnz , A, , 102 ) (101). ( j , , , 0 ) (102). ( jnz , B, , 0 ) (103). ( j , , ,101 ),(104). ( jnz , C , , 0 ) (105). ( j , , , 0 ) E7.truelist=105 (102 ) E7.falselist=104, 104, 104,102,(100). ( jnz ，A ， ，102 ) (101). ( j ， ， ，104 ) (102). ( jnz ，B ， ， 0 ) (103). ( j ， ， ，104 ) (104). ( jnz ，C ， ， 0 ) (105). ( j ， ， ，102 ),(AB)C E1.truelist=105 (102 ) E1.falselist=104 经验证，四元式符合逻辑要求， E真、假两条链待以后填入。,作业： P217 第 1，3 题 按讲课方式，写出布尔表达式的语义分析过程： A(B(CD),附：布尔术表达式到四元式的翻译 方法2介绍,1. 布尔表达式的文法 E EE | EE | E | (E) | i | i R i R | | | | | ,2. 改造文法，引入新的非终结符：EA，EO E EA E2 | EO E2 |E1|(E1)| i | i1 R i2 R | | | | | EA E EO E,3.语义规则,四元式：,E2的四元式,归约EA时，E1为真的转移目标已定,归约 EA E2 =E3 时， E3 =.T. E1=.T. 且 E2=.T. E1.TC已转至E2 的开始位置， E2.TC就是E.TC； E3 =.F. E1 =.F. 或 E2 =.F. ，故两条链合并。,例：(AB)C E7=EOE6 = EO E5 = EO i3 = E4 i3 = (E3 ) i3 = (EA E2) i3 = (EA i2) i3 = (E1 i2) i3 = (i1 i2) i3,四元式:,(100). ( jnz ，A ， ， 0 ) (101). ( j ， ， ， 0 ) (102). ( jnz ，B ， ， 0 ) (103). ( j ， ， ， 0 ),(100). ( jnz, A , , 102 ) (101). ( j , , , 0 ) (102). ( jnz , B , , 0 ) (103). ( j , , , 101 ),(104). ( jnz , C , , 0 ) (105). ( j , , , 0 ) E7.TC=105 (102 ) E7.FC=104, 104, 104,102,(100). ( jnz ，A ， ，102 ) (101). ( j ， ， ，104 ) (102). ( jnz ，B ， ， 0 ) (103). ( j ， ， ，104 ) (104). ( jnz ，C ， ， 0 ) (105). ( j ， ， ，102 ),(AB)C E1.TC=105 (102 ) E1.FC=104 经验证，四元式符合逻辑要求， E真、假两条链待以后填入。,1. 文 法,S if E then S1 分支语句 | if E then S1 else S2 分支语句 | while E do S1 循环语句 | A 赋值语句 | begin L end 复合语句 L L1；S | S,6.5 控制语句到四元式的翻译,2. 翻译结果的结构,if E then S1,if E then S1 else S2,while E do S1, S.nextlist 、 L.nextlist ：指针，某链的链首。链中 的四元式将控制流转移至S(L)之后要执行的代码处。 E.truelist 、E.falselist ：布尔表达式为“真”(“假”) 的链的链首。 M.quad ：指针，指向某个四元式。,S if E then M S1 | if E then M1 S1 N else M2 S2 | while M1 E do M2 S1 | A | begin L end,LL1； M S | S M N ,3. 属性,4. 改造文法,引入新的非终结符：M,N,5.语义规则,其中：L1的nextlist全部转至M。即：while,if等语句 遇到“;”号，则语句不再嵌套在其他语句中。,记录S1的第一条四元式的位置,if E then M1 S1 N else M2 S2,E,E.truelist,E.falselist,(j,_,_,_),M1.quad,M2.quad,生成四元式，跳过S2,记录S2的第一条四元式的位置,S 的出口，由三部分构成：,S1. nextlist N. Nextlist S2. nextlist,N.Nextlist,图中：加下划线的是句柄；句柄下的非终结符为归约后的符号。,语句待返填的出口链 S3.nextlist =106,结果四元式序列 100 ( jnz ,A, , 102) 101 ( j, , 107 ) 102 ( jnz, B, ,104 ) 103 ( j , , , 107) 104 ( * ,10, y, T1) 105 (:= , T1 , , X) 106 ( j , , , 0) 107 ( + ,20, y, T2) 108 (:= , T2 , , X) 语句待返填的出口链 S3.nextlist =106,If AB then x:=10*y else x:=20+y,四元式序列符合原高级语言的语义定义。,While AB do if CD then x:=y+z,结果四元式序列 100 ( j , A, B, 102 ) 101 ( j , , , 0 ) 102 ( j, C, D, 104 ),四元式序列符合原高级语言的语义定义。,语句待返填 的出口链 S3.nextlist =101,103 ( j , , , 100 ) 104 ( , y , z , T1 ) 105 (:= , T1 , , X ) 106 ( j , , , 100 ),作业： 按讲课方式，写出下面语句的语义分析过程： while AC BD do if A=1 then C:=C+1 else while A=D do A:=A+2 ;,6.6 标号和转移语句到四元式的翻译,1. 定义 调用方式,) 向后转移 (先定义，后使用) L: S; goto L,) 向前转移 (先使用，后定义) goto L L: S ;,对标号，符号表中记录：