Homework 6
(1)针对以下C函数,给出其函数体三地址码。
#define N 32
int a[N],b[N];
int arr[N+1][N+1];
void lcs()
{
for (i = 1; i <= length1; ++i){for (j = 1; j <= length2; ++j) {if (a[i - 1] == b[j - 1]) { //串中的下标从0开始arr[i][j] = arr[i - 1][j - 1] + 1;}else {arr[i][j] = arr[i - 1][j] > arr[i][j - 1] ? arr[i - 1][j] : arr[i][j - 1];}}
}
} // end of lcs()
画出该函数体的语法树如下:
三地址码:
i=1
F1:
if i>length1 goto F
j = 1
F2:
if j>length2 goto F4
#计算a[i-1]:
t0 = i-1
t1 = a
t2 = t0 * 4
t3 = t1[t2]
#计算b[j-1]:
t4 = j - 1
t5 = b
t6 = t4 * 4
t7 = t5[t6]
if t3 == t7 goto M1
goto M2
M1:
#计算arr[i,j]:
t8 = i * 33
t8 = t8 + j
t9 = arr
t10 = t8 * 4
#计算arr[i-1,j-1]+1
t11 = i-1
t12 = j-1
t13 = t11 * 33
t13 = t13 + t12
t14 = arr
t15 = t13 * 4
t16 = t14[t15]
t17 = 16 + 1
#arr[i][j] = arr[i-1,j-1]+1
t9[t10] = t17
goto F
M2:
#计算arr[i][j]
.......
#计算arr[i-1][j]
.......
#计算arr[i][j-1]
.......
if arr[i-1][j] > arr[i][j-1] goto L1
arr[i][j] = arr[i-1][j]
goto F3
L1:
arr[i][j] = arr[i-1][j]
goto
F3:
j = j + 1
goto F2
F4:
i = i + 1
goto F1
(2)按要求给出以下C表达式的三地址代码:
i && j && i > j && j < 10
|| (i>10)
|| !(i <= 100) && ( j <= 100) && !( i>50 )
|| !(j > 20 && i < -10)
(2.1)数值计算方式
# i
if i goto L0
t0 = 0
goto L1
L0:
t0 = 1
L1:
# j
if j goto L2
t1 = 0
goto L3
L2:
t1 = 1
# i > j
L3:
t2 = t0 and t1
if i > j goto L4
t3 = 0
goto L5
L4:
t3 = 1
# j < 10
L5:
t4 = t2 and t3
if j < 10 goto L6
t5 = 0
goto L7
L6:
t5 = 1
L7:
# i > 10
t6 = t4 and t5
if i >10 goto L8
t7 = 0
goto L9
L8:
t7 = 1
L9:
t8 = t6 or t7
# !(i <= 100)
if i<= 100 goto L10
t9 = 0
goto L11
L10:
t9 = 1
L11:
t10 = not t9
# j<=100
if j <= 100 goto L12
t11 = 0
goto L13
L12:
t11 = 1
L13:
t12 = t10 and t11
# i>50
if i>50 goto L14
t13 = 0
goto L15
L14:
t13 = 1
L15:
t14 = not t13
t15 = t12 and t14
t16 = t8 or t15
# j>20
if j>20 goto L16
t17 = 0
goto L17
L16:
t17 = 1
L17:
# i < -10
if i < -10 goto L18
t18 = 0
goto L19
L18:
t18 = 1
L19:
t19 = t17 and t18
t20 = not t19
t21 = t16 or t20
(2.2)短路计算方式:
(a)翻译方案
if i goto L0
goto L3
L0:
if j goto L1
goto L3
L1:
if i > j goto L2
goto L3
L2:
if j < 10 goto T
goto L3
L3:
if i>10 goto T
goto L4
L4:
if i<=100 goto L7
goto L5
L5:
if j<= 100 goto L6
goto L7
L6:
if i>50 goto L7
goto T
L7:
if j>20 goto L8
goto T
L8:
if i < -10 goto F
goto T
(b)更精简的短路代码翻译方案
if !i goto L0
if !j goto L0
if i<=j goto L0
if j<10 gotoT
L0:
if i>10 goto T
if i<=100 goto L1
if j>100 goto L1
if i<=50 goto T
L1:
if j<=20 goto T
if i>=-10 goto T
goto F