Trình biên dịch - Chương 8: Sinh mã trung gian

else if E1.type=real and E2.type =real then begin 
emit(E.place ':=' E1.place 'real + ' E2.place); 
E.type:= real; 
end 
else if E1.type=integer and E2.type =real then begin 
u:=newtemp; emit(u ':=' ‘intoreal' E1.place); 
emit(E.place ':=' u 'real +' E2.place); 
E.type:= real; 
end 
else if E1.type=real and E2.type =integer then begin 
u:=newtemp; emit(u ':=' 'intoreal' E2.place); 
emit(E.place ':= ' E1.place 'real +' u); 
E.type:= real; 
 end 
 else E.type := type_error; 
end 
Hình 8.16 - Hành vi ngữ nghĩa của E → E1 +E2 
 Ví dụ 8.5: Với lệnh gán x := y + i * j trong đó x,y được khai báo là real; i , j được khai 
báo là integer. Mã lệnh 3 địa chỉ xuất ra là: 
t1 := i int * j 
t3 := intoreal t1 
t2 := y real + t3 
x := t2 
IV. BIỂU THỨC LOGIC 
 Biểu thức logic được sinh ra bởi văn phạm sau: 
 E→ E or E | E and E | not E | (E) | id relop id | true | false 
 Trong đó or và and kết hợp trái; or có độ ưu tiên thấp nhất, kế tiếp là and và sau cùng là not 
 Thông thường có 2 phương pháp chính để biểu diễn giá trị logic. 
 Phương pháp 1: Mã hóa true và false bằng các số và việc đánh giá biểu thức được thực 
hiện tương tự như đối với biểu thức số học, có thể biểu diễn true bởi 1 , false bởi 0; hoặc các 
số khác không biểu diễn true, số không biểu diễn false... 
 178
 Phương pháp 2: Biểu diễn giá trị của biểu thức logic bởi một vị trí đến trong chương 
trình. Phương pháp này rất thuận lợi để cài đặt biểu thức logic trong các điều khiển. 
1. Biểu diễn số 
 Sử dụng 1 để biểu diễn true và 0 để biểu diễn false. Biểu thức được đánh giá từ trái 
sang phải theo cách tương tự biểu thức số học. 
 Ví dụ 8.6: Với biểu thức a or b and not c, ta có dãy lệnh 3 địa chỉ: 
t1 := not c 
t2 := b and t1 
t3 := a or t2 
 Biểu thức quan hệ a<b tương đương lệnh điều kiện if a<b then 1 else 0. dãy lênh 3 địa chỉ 
tương ứng là 
100 : if a<b goto 103 
101 : t := 0 
102 : goto 104 
103 : t :=1 
104 : 
 Ta có, lược đồ dịch để sinh ra mã lệnh 3 địa chỉ đối với biểu thức logic: 
 E → E1 or E2 {E.place:= newtemp; emit(E.place ':=' E1.place 'or' E2.place) } 
 E → E1 and E2 { E.place:= newtemp; emit(E.place ':=' E1.place 'and' E2.place)} 
 E → not E1 {E.place:= newtemp; emit(E.place ':=' 'not' E1.place ) } 
 E → id1 relop id2 { E.place:= newtemp; 
 emit('if' id1.place relop.op id2.place 'goto' nextstat +3); 
 emit(E.place ':=' '0'); emit('goto' nextstat +2); 
 emit(E.place ':=' '1') } 
 E → true { E.place:= newtemp; emit(E.place ':=' '1') } 
 E → false { E.place:= newtemp; emit(E.place ':=' '0') } 
Hình 8.17 - Lược đồ dịch sử dụng biểu diễn số để sinh mã lệnh ba địa chỉ cho các biểu thức 
logic 
 Ví dụ 8.7: Với biểu thức a < b or c< d and e < f, nó sẽ sinh ra lệnh địa chỉ như sau: 
100 : if a<b goto 103 
101 : t1 := 0 
102 : goto 104 
103 : t1 := 1 
104 : if c<d goto 107 
105 : t2 := 0 
106 : goto 108 
107 : t2 := 1 
 179
108 : if e<f goto 111 
109 : t3 := 0 
110 : goto 112 
111 : t3 := 1 
112 : t4 := t2 and t3 
113 : t5 := t1 or t4 
Hình 8.18 - Sự biên dịch sang mã lệnh ba địa chỉ cho a<b or c<d and e<f 
1. Mã nhảy 
 Ðánh giá biểu thức logic mà không sinh ra mã lệnh cho các toán tử or, and và not. Chúng 
ta chỉ biểu diễn giá trị môt biểu thức bởi vị trí trong chuỗi mã. Ví dụ, trong chuỗi mã lệnh 
trên, giá trị t1 sẽ phụ thuộc vào việc chúng ta chọn lệnh 101 hay lệnh 103. Do đó giá trị của t1 
là thừa. 
2. Các lệnh điều khiển 
S→ if E then S1
| if E then S1 else S2
| while E do S1
 Với mỗi biểu thức logic E, chúng ta kết hợp với 2 nhãn 
E.true : Nhãn của dòng điều khiển nếu E là true. 
E.false : Nhãn của dòng điều khiển nếu E là false. 
S.code : Mã lệnh 3 địa chỉ được sinh ra bởi S. 
S.next : Là nhãn mà lệnh 3 địa chỉ đầu tiên sẽ thực hiện sau mã lệnh của S. 
S.begin : Nhãn chỉ định lệnh đầu tiên được sinh ra cho S. 
 E.code to E.true
E.false: 
S1.code 
E.true: to E.false
... 
(a) if -then 
E.code to E.true 
E.false: 
S1.code 
E.true: to E.false 
goto S.begin 
(c) while-do 
... 
S.begin: 
E.code to E.true 
E.false: 
S1.code 
E.true: to E.false 
goto S.next 
(b) if -then-else 
S2.code 
S.next: 
... ... ... 
Hình 8.19 - Mã lệnh của các lệnh if-then, if-then-else, và while-do 
 180
 Ta có định nghĩa trực tiếp cú pháp cho các lệnh điều khiển 
Luật sinh Luật ngữ nghĩa 
S→ if E then S1
S→ if E then S1 else S2
S→ while E do S1
E.true := newlabel; 
E.false := S.next; 
S1.next := S.next; 
S.code := E.code || gen(E.true ':') || S1.code 
E.true := newlabel; 
E.false := newlabel; 
S1.next := S.next; 
S2.next := S.next; 
S.code := E.code || gen(E.true ':') || S1.code || 
 gen('goto' S.next) || 
 gen(E.false ':') || S2.code 
S.begin := newlabel; 
E.true := newlabel; 
E.fasle := S.next; 
S1.next := S.begin; 
S.code:= gen(S.begin':') || E.code || gen(E.true ':') || 
S1.code || gen('goto' S.begin) 
Hình 8.20 - Ðịnh nghĩa trực tiếp cú pháp của dòng điều khiển 
3. Dịch biểu thức logic trong các lệnh điều khiển 
• Nếu E có dạng a<b thì mã lệnh sinh ra có dạng 
if a<b goto E.true 
goto E.false 
• Nếu E có dạng E1 or E2. Nếu E1 là true thì E là true. Nếu E1 là flase thì phải đánh giá 
E2. Do đó E1.false là nhãn của lệnh đầu tiên của E2. E sẽ true hay false phụ thuộc vào 
E2 là true hay false. 
• Tương tự cho E1 and E2. 
• Nếu E có dạng not E1 thì E1 là true thì E là false và ngược lại. 
 Ta có định nghĩa trực tiếp cú pháp cho việc dịch các biểu thức logic thành mã lệnh 3 
địa chỉ. Chú ý true và false là các thuộc tính kế thừa. 
Luật sinh Luật ngữ nghĩa 
E→ E1 or E2
E1.true := E.true; 
E1.false := newlabel; 
E2.true := E.true; 
 181
E→ E1 and E2
E→ not E1
E → (E1) 
E → id1 relop id2
E → true 
E → false 
E2.false := E.false; 
E.code := E1.code || gen(E.false ':') || E2.code 
E1.true := newlabel; 
E1.false := E.false; 
E2.true := E.true; 
E2.false := E.false; 
E.code := E1.code || gen(E.true ':') || E2.code 
E1.true := E.false; 
E1.false := E.true; 
E.code := E1.code 
E1.true := E.true; 
E1.false := E.false; 
E.code := E1.code 
E.code := gen('if' id1.place relop.op id2.place 
 'goto' E.true) || gen('goto' E.false) 
E.code:= gen('goto' E.true) 
E.code:= gen('goto' E.false) 
Hình 8.21 - Ðịnh nghĩa trực tiếp cú pháp sinh mã lệnh ba địa chỉ cho biểu thức logic 
4. Biểu thức logic và biểu thức số học 
 Trong thực tế biểu thức logic thường chứa những biểu thức số học như (a+b) < c. Trong 
các ngôn ngữ mà false có giá trị số là 0 và true có giá trị số là 1 thì (a<b) + (b<a) có thể được 
xem như là một biểu thức số học có giá trị 0 nếu a = b và có giá trị 1 nếu a b. 
 Phương pháp biểu diễn biểu thức logic bằng mã lệnh nhảy có thể vẫn còn được sử dụng. 
 Xét văn phạm E → E+ E | E and E | E relop E | id 
 Trong đó, E and E đòi hỏi hai đối số phải là logic. Trong khi + và relop có các đối số là 
biểu thức logic hoặc/và số học. 
Ðể sinh mã lệnh trong trường hợp này, chúng ta dùng thuộc tính tổng hợp E.type có thể là 
arith hoặc bool. E sẽ có các thuộc tính kế thừa E.true và E.false đối với biểu thức số học. 
 Ta có luật ngữ nghĩa kết hợp với E → E1 + E2 như sau 
E.type := arith; 
if E1.type = arith and E2.type = arith then begin 
/* phép cộng số học bình thường */ 
E.place := newtemp; 
E.code := E1.code || E2.code || gen(E.place ':=' E1.place '+' E2.place) 
end 
else if E1.type = arith and E2.type = bool then begin 
 182
E.place := newtemp; 
E2.true := newlabel; 
E2.false := newlabel; 
E.code := E1.code || E2.code || gen(E2.true ':' E.place ':= ' E1.place +1) || 
gen('goto' nextstat +1) || gen(E2.false ':' E.place ':= ' E1.place) 
else if ... 
Hình 8.22 - Luật ngữ nghĩa cho luật sinh E → E1 +E2 
 Trong trường hợp nếu có biểu thức logic nào có biểu thức số học, chúng ta sinh mã lệnh 
cho E1, E2 bởi các lệnh 
E2.true : E.place := E1.place +1 
 goto nextstat +1 
E2.false : E.place := E1.place 
V. LỆNH CASE 
 Lệnh CASE hoặc SWITCH thường được sử dụng trong các ngôn ngữ lập trình. 
1. Cú pháp của lệnh SWITCH/ CASE 
SWITCH E 
begin 
case V1 : S1
case V2 : S2
.... 
case Vn-1 : Sn-1
default: Sn
end 
Hình 8.23 - Cú pháp của câu lệnh switch 
2. Dịch trực tiếp cú pháp lệnh Case 
1. Ðánh giá biểu thức. 
2. Tùy một giá trị trong danh sách các case bằng giá trị của biểu thức. Nếu không tìm 
thấy thì giá trị default của biểu thức được xác định. 
3. Thực hiện các lệnh kết hợp với giá trị tìm được để cài đặt. 
 Ta có phương pháp cài đặt như sau 
mã lệnh để đánh giá biểu thức E vào t 
goto test 
L1 : mã lệnh của S1 
goto next 
L2: mã lệnh của S2 
 183
goto next 
............... .. 
Ln-1 : mã lệnh của Sn-1 
goto next 
Ln : mã lệnh của Sn 
goto next 
test : if t=V1 goto L1
if t=V2 goto L2 
.. .. .. .. 
if t=Vn-1 goto Ln-1 
else goto Ln
next: 
Hình 8.24 - Dịch câu lệnh case 
 Một phương pháp khác để cài đặt lệnh SWITCH là 
mã lệnh để đánh giá biểu thức E vào t 
if t V1 goto L1 
mã lệnh của S1 
goto next 
L1 : if t V2 goto L2 
mã lệnh của S2 
goto next 
L2: ............. .. 
Ln-2 : if t Vn-1 goto Ln-1
mã lệnh của Sn-1 
goto next 
Ln-1 : mã lệnh của Sn 
next: 
Hình 8.24 - Một cách dịch khác của câu lệnh case 
 184
BÀI TẬP CHƯƠNG VIII 
8.1. Dịch biểu thức : a * - ( b + c) thành các dạng: 
 a) Cây cú pháp. 
 b) Ký pháp hậu tố. 
 c) Mã lệnh máy 3 - địa chỉ. 
8.2. Trình bày cấu trúc lưu trữ biểu thức - ( a + b) * ( c + d ) + ( a + b + c) ở các 
dạng: 
 a) Bộ tứ . 
 b) Bộ tam. 
 c) Bộ tam gián tiếp. 
8.3. Sinh mã trung gian ( dạng mã máy 3 - địa chỉ) cho các biểu thức C đơn giản sau: 
 a) x = 1 
 b) x = y 
 c) x = x + 1 
 d) x = a + b * c 
 e) x = a / ( b + c) - d * ( e + f ) 
8.4. Sinh mã trung gian ( dạng mã máy 3 - địa chỉ) cho các biểu thức C sau: 
 a) x = a [i] + 11 
 b) a [i] = b [ c[j] ] 
 c) a [i][j] = b [i][k] * c [k][j] 
 d) a[i] = a[i] + b[j] 
 e) a[i] + = b[j] 
8.5. Dịch lệnh gán sau thành mã máy 3 - địa chỉ: 
 A [ i,j ] := B [ i,j ] + C [A[ k,l]] + D [ i + j ] 
 185