国防科技大学：《编译原理》课程电子教案（PPT教学课件）第10章 优化

i:=m-1 j:=n T1=4*n v:=aT Br if i>=j goto B Ba i:=i计1 T2=4*i T3:=a[T2] B2 B5 Bo if T3<v goto B2 a [T2l=Ts a [T=T3 a [T2J=v goto B2 a [T l=T3 j=j-1 乃3 T=4*j Ts:=a[Td if Tsv goto B3 L 口强度削弱 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ❑强度削弱 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] B1 i:=i+1 T2 :=4*i T3 :=a[T2 ] if T3<v goto B2 B2 j:=j-1 T4 :=4*j T5 :=a[T4 ] if T5>v goto B3 B3 if i>=j goto B6 B4 a [T2 ]=T5 a [T4 ]= T3 goto B2 B5 a [T2 ]=v a [T1 ]=T3 B6

i:=m-1 j:=n T1=4*n v:=a[Ti Br if i>=j goto BB T2:=4*1 工=4*1 i:=i+1 B2 Bs Bo T2:=T2+4 T:=a[T2] a [TJ=Ts a [T=T3 a [T2]=v if T3<v goto B2 goto B2 a [T J=T3 j=j-1 B: T4=T44 Ts:=alTd ifTs>y goto B3 口强度削弱后 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ❑强度削弱后 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] T2 :=4*i T4 :=4*j B1 i:=i+1 T2 := T2+4 T3 :=a[T2 ] if T3<v goto B2 B2 j:=j-1 T4 := T4 -4 T5 :=a[T4 ] if T5>v goto B3 B3 if i>=j goto B6 B4 a [T2 ]=T5 a [T4 ]= T3 goto B2 B5 a [T2 ]=v a [T1 ]=T3 B6

i:=m-1 j:=n T1=4*n y:=a[Ti Br if i>=j goto B T2=4*1 工4=4*1 i=i计1 B2 Bs Bo T2=T2+4 T:=a[T2] a [T2J-Ts a [T=T3 a [T2]=v ifT3≤y goto B2 goto B2 a [T l=T3 j:=j-1 B3 T4=T44 Ts:=a[T4l ifTs>y goto B3 口删除归纳变量 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ❑删除归纳变量 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] T2 :=4*i T4 :=4*j B1 i:=i+1 T2 := T2+4 T3 :=a[T2 ] if T3<v goto B2 B2 j:=j-1 T4 := T4 -4 T5 :=a[T4 ] if T5>v goto B3 B3 if i>=j goto B6 B4 a [T2 ]=T5 a [T4 ]= T3 goto B2 B5 a [T2 ]=v a [T1 ]=T3 B6

i:=m-1 j:=n T1=4*n v:=a[Ti Br ifT2>=Ta goto B6 B4 T2=4*1 工=4*1 T2:=T2+4 B2 Bs Bo T:=a[T2] a [TJ=Ts ifT3<v goto B2 a [T=T3 a [T2]=v goto B2 a [T l=T3 B3 T4=T44 Ts:=a[Ta ifTs>y goto B3 口删除归纳变量后 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ❑删除归纳变量后 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] T2 :=4*i T4 :=4*j B1 T2 := T2+4 T3 :=a[T2 ] if T3<v goto B2 B2 T4 := T4 -4 T5 :=a[T4 ] if T5>v goto B3 B3 if T2>=T4 goto B6 B4 a [T2 ]=T5 a [T4 ]= T3 goto B2 B5 a [T2 ]=v a [T1 ]=T3 B6

i:=m-1 j:=n T1=4*n v:=a[T] Bi if i>=j goto B B4 i:=i+1 T6=4*i T1=4*1 T2:=4*i x:=a [Tol B2 T7=4*i B5 x:=a [Tul Bo Ta:=a[T2] T12=4*1 if T3<v goto B2 Ts:=4*j T13=4*n To:=a [Tsl Tu:=a [Tial a [T-l=T9 a [Tl-T14 T10=4*j j=j-1 B: T15=4*n a [TIol=x a [Tis]=x T4=4*j goto B2 Ts:=alTa if Ts>y goto B3 ▣中间代码程序段 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ❑中间代码程序段 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] B1 i:=i+1 T2 :=4*i T3 :=a[T2 ] if T3<v goto B2 B2 j:=j-1 T4 :=4*j T5 :=a[T4 ] if T5>v goto B3 B3 if i>=j goto B6 B4 T6 :=4*i x:=a [T6 ] T7 :=4*i T8 :=4*j T9 :=a [T8 ] a [T7 ]=T9 T10:= 4*j a [T10]=x goto B2 B5 T11:=4*i x:=a [T11] T12:=4*i T13:=4*n T14:=a [T13] a [T12]=T14 T15:= 4*n a [T15]=x B6