编译原理—计算三地址码、布尔语句翻译

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()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

画出该函数体的语法树如下：

三地址码：

i=1
F1:
if i>length1 goto Fnext
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 F3
M2:
#计算arr[i][j]
t18 = i * 33
t18 = t18 + j
t19 = arr
t20 = t18 * 4
t33 = t19[t20]
#计算arr[i-1][j]
t21 = i-1
t22 = j
t23 = t21 * 33
t23 = t23 + t22
t24 = arr
t25 = t23 * 4
t26 = t24[t25]
#计算arr[i][j-1]
t27 = i
t28 = j-1
t29 = t27 * 33
t29 = t29 + t28
t30 = arr
t31 = t29 * 4
t32 = t30[t31]
if t26 > t32 goto L1
t33 = t32
goto F3
L1:
t33 = t26
F3:
j = j + 1
goto F2
F4:
i = i + 1
goto F1  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

（2）按要求给出以下C表达式的三地址代码：

i && j && i > j && j < 10 
|| (i>10) 
|| !(i <= 100) && ( j <= 100) && !( i>50 )
|| !(j > 20 && i < -10)
1
2
3
4

（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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

（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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

​ （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
1
2
3
4
5
6
7
8
9
10
11
12
13