Giáo trình Nguyên lý ngôn ngữ lập trình - Chương 8: Sinh mã trung gian

CHƯƠNG VIII 
SINH MÃ TRUNG GIAN 
Nội dung chính: 
Thay vì một chương trình nguồn được dịch trực tiếp sang mã đích, nó nên được dịch sang 
dạng mã trung gian bởi kỳ trước trước khi được tiếp tục dịch sang mã đích bởi kỳ sau vì một 
số tiện ích: Thuận tiện khi muốn thay đổi cách biểu diễn chương trình đích; Giảm thời gian 
thực thi chương trình đích vì mã trung gian có thể được tối ưu. Chương này giới thiệu các 
dạng biểu diễn trung gian đặc biệt là dạng mã ba địa chỉ. Phần lớn nội dung của chương tập 
trung vào trình bày cách tạo ra một bộ sinh mã trung gian đơn giản dạng mã 3 đại chỉ. Bộ 
sinh mã này dùng phương thức trực tiếp cú pháp để dịch các khai báo, câu lệnh gán, các lệnh 
điều khiển sang mã ba địa chỉ. 
Mục tiêu cần đạt: 
Sau khi học xong chương này, sinh viên phải nắm được cách tạo ra một bộ sinh mã trung gian 
cho một ngôn ngữ lập trình đơn giản (chỉ chứa một số loại khai báo, lệnh điều khiển và câu 
lệnh gán) từ đó có thể mở rộng để cài đặt bộ sinh mã cho những ngôn ngữ phức tạp hơn. 
Tài liệu tham khảo: 
[1] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - 
Addison - Wesley Publishing Company, 1986. 
I. NGÔN NGỮ TRUNG GIAN 
 Cây cú pháp, ký pháp hậu tố và mã 3 địa chỉ là các loại biểu diễn trung gian. 
1. Biểu diễn đồ thị 
 Cây cú pháp mô tả cấu trúc phân cấp tự nhiên của chương trình nguồn. DAG cho ta cùng 
lượng thông tin nhưng bằng cách biểu diễn ngắn gọn hơn trong đó các biểu thức con không 
được biểu diễn lặp lại. 
 Ví dụ 8.1: Với lệnh gán a := b * - c + b * - c, ta có cây cú pháp và DAG: 
 Cây cú pháp DAG 
:= 
a + 
* * 
b 
c 
- b - 
c 
:= 
a + 
* 
b - 
c 
Hình 8.1- Biểu diễn đồ thị của a :=b * - c + b * - c 
 168
 Ký pháp hậu tố là một biểu diễn tuyến tính của cây cú pháp. Nó là một danh sách các nút 
của cây, trong đó một nút xuất hiện ngay sau con của nó. 
a b c - * b c - * + := là biểu diễn hậu tố của cây cú pháp hình trên. 
 Cây cú pháp có thể được cài đặt bằng một trong 2 phương pháp: 
- Mỗi nút được biểu diễn bởi một mẫu tin, với một trường cho toán tử và các trường 
khác trỏ đến con của nó. 
- Một mảng các mẩu tin, trong đó chỉ số của phần tử mảng đóng vai trò như là con trỏ 
của một nút. 
 Tất cả các nút trên cây cú pháp có thể tuân theo con trỏ, bắt đầu từ nút gốc tại 10 
Hình 8.2 - Hai biểu diễn của cây cú pháp trong hình 8.1 
:= 
id a 
+ 
* 
id b 
- 
id c 
:=
id b
-
0 id b 
2 - 1 
1 id c 
3 * 0 2 
4 id b 
5 id c 
6 - 5 
7 * 4 6 
8 + 3 7 
9 id a 
10 := 9 8 
11 .... .... ..... 
d ci
2. Mã 3 địa chỉ 
 Mã lệnh 3 địa chỉ là một chuỗi các lệnh có dạng tổng quát là x :=y op z. Trong đó x,y,z là 
tên, hằng hoặc dữ liệu tạm sinh ra trong khi dịch, op là một toán tử số học hoặc logic. 
 Chú ý rằng không được có quá một toán tử ở vế phải của mỗi lệnh. Do đó biểu thức x + y 
* z phải được dịch thành chuỗi : 
t1 := y * z 
t2 := x + t1 
 Trong đó t1, t2 là những tên tạm sinh ra trong khi dịch. 
 Mã lệnh 3 địa chỉ là một biểu diễn tuyến tính của cây cú pháp hoặc DAG, trong đó các tên 
tường minh biểu diễn cho các nút trong trên đồ thị. 
t1 := - c t1 := -c 
t2 := b * t1 t2 := b * t1 
t3 := - c t3 := t2 + t2 
t4 := b * t3 a := t3 
 169
t5 := t2 + t4 
a := t5 
 Mã lệnh 3 địa chỉ của cây cú pháp Mã lệnh 3 địa chỉ của DAG 
Hình 8.3 - Mã lệnh 3 địa chỉ tương ứng với cây cú pháp và DAG trong hình 8.1 
3. Các mã lệnh 3 địa chỉ phổ biến 
1. Lệnh gán dạng x := y op z, trong đó op là toán tử 2 ngôi số học hoặc logic. 
2. Lệnh gán dạng x := op y, trong đó op là toán tử một ngôi. Chẳng hạn, phép lấy số đối, 
toán tử NOT, các toán tử SHIFT, các toán tử chuyển đổi. 
3. Lệnh COPY dạng x :=y, trong đó giá trị của y được gán cho x. 
4. Lệnh nhảy không điều kiện goto L. Lệnh 3 địa chỉ có nhãn L là lệnh tiếp theo thực 
hiện. 
5. Các lệnh nhảy có điều kiện như if x relop y goto L. Lệnh này áp dụng toán tử quan hệ 
relop (=, .. .. ) vào x và y. Nếu x và y thỏa quan hệ relop thì lệnh nhảy với nhãn 
L sẽ được thực hiện, ngược lại lệnh đứng sau IF x relop y goto L sẽ được thực hiện. 
6. param x và call p, n cho lời gọi chương trình con và return y. Trong đó, y biểu diễn 
giá trị trả về có thể lựa chọn. Cách sử dụng phổ biến là một chuỗi lệnh 3 địa chỉ. 
param x1 
param x2 
.. .. .. 
param xn 
call p, n 
được sinh ra như là một phần của lời gọi chương trình con p (x1,x2,.. .., xn). 
7. Lệnh gán dạng x := y[i] và x[i] := y. Lệnh đầu lấy giá trị của vị trí nhớ của y được xác 
định bởi giá trị ô nhớ i gán cho x. Lệnh thứ 2 lấy giá trị của y gán cho ô nhớ x được 
xác định bởi i. 
8. Lệnh gán địa chỉ và con trỏ dạng x :=&y , x := *y và *x := y. Trong đó, x := &y đặt 
giá trị của x bởi vị trí của y. Câu lệnh x := *y với y là một con trỏ mà r_value của nó 
là một vị trí, r_value của x đặt bằng nội dung của vị trí này. Cuối cùng *x := y đặt 
r_value của đối tượng được trỏ bởi x bằng r_value của y. 
4. Dịch trực tiếp cú pháp thành mã lệnh 3 địa chỉ 
 Ví dụ 8.2: Ðịnh nghĩa S _ thuộc tính sinh mã lệnh địa chỉ cho lệnh gán: 
Luật sinh Luật ngữ nghĩa 
S→ id := E 
E→ E1 + E2
E→ E1 * E2
S.code := E.code || gen (id.place ':=' E.place) 
E.place := newtemp; 
E.code := E1.code || E2.code || 
 gen (E.place ':=' E1.place '+' E2.place) 
E.place := newtemp; 
E.code := E1.code || E2.code || 
 170
E→ - E1
E→ (E1) 
E→ id 
 gen (E.place ':=' E1.place '*' E2.place) 
E.place := newtemp; 
E.code := E1.code|| gen (E.place ':=' 'uminus' E1.place ) 
E.place := newtemp; 
E.code := E1.code 
E.place := id.place; 
E.code := '' 
Hình 8.4 - Ðịnh nghĩa trực tiếp cú pháp sinh mã lệnh ba địa chỉ cho lệnh gán 
 Với chuỗi nhập a = b * - c + b * - c, nó sinh ra mã lệnh 3 địa chỉ 
t1 := -c 
t2 := b * t1 
t3 := - c 
t4 := b * t3 
t5 := t2 + t4 
thuộc tính tổng hợp S.code biểu diễn mã 3 địa chỉ cho lệnh gán 
S. Ký hiệu chưa kết thúc E có 2 thuộc tính E.place là giá trị của 
E và E.code là chuỗi lệnh 3 địa chỉ để đánh giá E 
a := t5 
 Khi mã lệnh 3 địa chỉ đuợc sinh, tên tạm được tạo ra cho mỗi nút trong trên cây cú 
pháp. 
 Giá trị của ký hiệu chưa kết thúc E trong luật sinh E → E1 + E2 được tính vào trong tên 
tạm t. Nói chung mã lệnh 3 địa chỉ cho lệnh gán id := E bao gồm mã lệnh cho việc đánh giá E 
vào trong biến tạm t, sau đó là một lệnh gán id.place := t. 
 Hàm newtemp trả về một chuỗi các tên t1, t2, .. .. , tn tương ứng các lời gọi liên tiếp. Gen 
(x ':=' y '+' z) để biểu diễn lệnh 3 địa chỉ x :=y+z 
E.code 
if E.place = 0 goto S.after 
S1.code 
goto S.begin 
S.begin: 
S.after: 
Luật sinh Luật ngữ nghĩa 
S→ while E do S1 S.begin := newlabel; 
S.after := newlabel; 
S.code := gen(S.begin ':') || E.code || 
gen('if' E.place '=' 0 'goto' S.after) || 
S1.code || gen('goto' S.begin) || gen(S.after ':') 
 171
Hình 8.5 - Ðịnh nghĩa trực tiếp cú pháp sinh mã lệnh ba địa chỉ cho câu lệnh while 
 Lệnh S → while E do S1 được sinh ra bằng cách dùng các thuộc tính S.begin và S.after để 
đánh dấu lệnh đầu tiên trong đoạn mã lệnh của E và lệnh sau đoạn mã lệnh của S. 
 Hàm newlabel trả về một nhãn mới tại mỗi lần được gọi 
5. Cài đặt lệnh 3 địa chỉ 
 Lệnh 3 địa chỉ là một dạng trừu tượng của mã lệnh trung gian. Trong chương trình dịch, các 
mã lệnh này có thể cài đặt bằng một mẩu tin với các trường cho toán tử và toán hạng. Có 3 
cách biểu diễn là bộ tứ, bộ tam và bộ tam gián tiếp. 
ƒ Bộ tứ 
Bộ tứ (quadruples) là một cấu trúc mẩu tin có 4 trường ta gọi là op, arg1, arg2 và result. 
Trường op chứa toán tử. Lệnh 3 địa chỉ x := y op z được biểu diễn bằng cách thay thế y 
bởi arg1, z bởi arg2 và x bởi result. Các lệnh với toán tử một ngôi như x := -y hay x := y 
thì không sử dụng arg2. Các toán tử như param không sử dụng cả arg2 lẫn result. Các 
lệnh nhảy có điều kiện và không điều kiện đặt nhãn đích trong result. 
Nội dung các trường arg1, arg2 và result trỏ tới ô trong bảng ký hiệu đối với các tên biểu 
diễn bởi các trường này. Nếu vậy thì các tên tạm phải được đưa vào bảng ký hiệu khi 
chúng được tạo ra. 
Ví dụ 8.3: Bộ tứ cho lệnh a := b * -c + b * -c 
 op arg1 arg2 result 
(0) 
(1) 
(2) 
(3) 
(4) 
(5) 
uminus 
* 
uminus 
* 
+ 
:= 
c 
b 
c 
b 
t2 
t5 
t1 
t3 
t4 
t1 
t2 
t3 
t4 
t5 
a 
Hình 8.6 - Biểu diễn bộ tứ cho các lệnh ba địa chỉ 
ƒ Bộ tam 
 Ðể tránh phải lưu tên tạm trong bảng ký hiệu; chúng ta có thể tham khảo tới giá trị tạm 
bằng vị trí của lệnh tính ra nó. Ðể làm điểu đó ta sử dụng bộ tam (triples) là một mẩu tin 
có 3 trường op, arg1 và arg2. Trong đó, arg1 và arg2 trỏ tới bảng ký hiệu (đối với tên hoặc 
hằng do người lập trình định nghĩa) hoặc trỏ tới một phần tử trong bộ tam (đối với giá trị 
tạm) 
 op arg1 arg2 
(0) 
(1) 
(2) 
(3) 
(4) 
(5) 
uminus 
* 
uminus 
* 
+ 
:= 
c 
b 
c 
b 
(1) 
a 
(0) 
(2) 
(3) 
(4) 
 Các lệnh như x[i]:=y và x:=y[i] sử dụng 2 ô trong cấu trúc bộ tam. 
Hình 8.7 - Biểu diễn bộ tam cho các 
lệnh ba địa chỉ 
 172
 op arg1 arg2 op arg1 arg2 
(0) 
(2) 
[ ] 
:= 
x 
(0) 
i 
y 
 (0) 
(2) 
[ ] y 
x 
i 
(0) := 
Hình 8.8 - Biểu diễn bộ tam cho x[i]:=y và x:=y[i] 
ƒ Bộ tam gián tiếp 
 Một cách biểu diễn khác của bộ tam là thay vì liệt kê các bộ tam trực tiếp ta sử dụng 
một danh sách các con trỏ các bộ tam. 
 statements op arg1 arg2 
 (0) 
(1) 
(2) 
(3) 
(4) 
(5) 
(14) 
(15) 
(16) 
(17) 
(18) 
(19) 
 (14) 
(15) 
(16) 
(17) 
(18) 
(19) 
uminus 
* 
uminus 
* 
+ 
:= 
c 
b 
c 
b 
(15) 
a 
(14) 
(16) 
(17) 
(18) 
Hình 8.9 - Biểu diễn bộ tam gián tiếp cho các lệnh ba địa chỉ 
II. KHAI BÁO 
1. Khai báo trong chương trình con 
 Các tên cục bộ trong chương trình con được truy xuất đến thông qua địa chỉ tương đối của 
nó. Gọi là offset. 
 Ví dụ 8.4: Xét lược đồ dịch cho việc khai báo biến 
P → {offset:= 0 } D 
 D → D ; D 
D → id : T {enter(id.name, T,type, offset); offset := offset + T.width } 
T → integer { T.type:= integer; T.width := 4 } 
T → real { T.type:= real ; T.width := 8 } 
T → array[ num] of T1{ T.type:= array(num.val, T1.type); 
 T.width := num.val * T1.width } 
T→ ↑ T1 { T.type := pointer(T1.type) ; T.width := 4 } 
Hình 8.10 - Xác định kiểu và địa chỉ tương đối của các tên được khai báo 
 Trong ví dụ trên, ký hiệu chưa kết thúc P sinh ra một chuỗi các khai báo dạng id:T. 
 Trước khi khai báo đầu tiên được xét thì offset = 0. Khi mỗi khai báo được tìm thấy tên và 
giá trị của offset hiện tại được đưa vào trong bảng ký hiệu, sau đó offset được tăng lên một 
khoảng bằng kích thước của đối tượng dữ liệu được cho bởi tên đó. 
 Thủ tục enter(name, type, offset) tạo một ô trong bảng ký hiệu với tên, kiểu và địa chỉ 
tương đối của vùng dữ liệu của nó. Ta sử dụng các thuộc tính tổng hợp type và width để chỉ ra 
kiểu và kích thước (số đơn vị nhớ) của kiểu đó. 
 Chú ý rằng lược đồ dịch P → {offset := 0} D có thể được viết lại bằng cách thay thế hành 
vi {offset := 0} bởi một ký hiệu chưa kết thúc M để được 
 173
P → M D 
M → ε {offset := 0 } 
 Tất cả các hành vi đều nằm cuối vế phải. 
2. Lưu trữ thông tin về tầm 
 Trong một ngôn ngữ mà chương trình con được phép khai báo lồng nhau. Khi một chương 
trình con được tìm thấy thì quá trình khai báo của chương trình con bao bị tạm dừng. 
 Văn phạm cho sự khai báo đó là; 
P → D 
D → D ; D | id: T | proc id ; D; S 
 Ðể đơn giản chúng ta tạo ra một bảng ký hiệu riêng cho mỗi chương trình con. 
 Khi một khai báo chương trình con D → proc id D1 ; S được tạo ra và các khai báo trong 
D1 được lưu trữ trong bảng ký hiệu mới. 
 Ví dụ 8.5: Chương trình Sort có bốn chương trình con lồng nhau readarray, exchange, 
quicksort và partition. Ta có năm bảng ký hiệu tương ứng. 
Hình 8.11 - Những bảng ký hiệu của các chương trình con lồng nhau 
nil header 
a 
x 
readarray 
exchange 
quicksort 
sort 
 header 
k 
v 
partition 
i 
j 
quicksort 
partition 
 header header 
exchange 
 header 
readarray 
id 
Luật ngữ nghĩa được xác định bởi các thao tác sau 
1. mktable (previous): Tạo một bảng ký hiệu mới và con trỏ tới bảng đó. Tham số 
previous là một con trỏ trỏ tới bảng ký hiệu của chương trình con bao. Con trỏ 
previous được lưu trong header của bảng ký hiệu mới. Trong header còn có thể có các 
thông tin khác như độ sâu lồng của chương trình con. 
2. enter (table, name, type, offset): Tạo một ô mới trong bảng ký hiệu được trỏ bởi table. 
3. addwidth (table, width): Ghi kích thước tích lũy của tất cả các ô trong bảng vào trong 
header kết hợp với bảng đó. 
 174
4. enterproc (table, name, newtable): Tạo một ô mới cho tên chương trình con vào trong 
bảng được trỏ bởi table. newtable trỏ tới bảng ký hiệu của chương trình con này. 
Ta có lược đồ dịch 
P → M D { addwidth(top(tblptr), top(offset)); 
 pop(tblptr); pop(offset) } 
M → ε { t:=mktable(nil); push(t, tblptr) ; push(0,offset) } 
D→ D1 ; D2
D→ proc id ; N D1 ; S {t:= top(tblptr); addwidth(t, top(offset)); pop(tblptr; 
pop(offset); enterproc(top(tblptr), id_name,t) } 
D→ id : T {enter(top(tblptr), id_name, T.type, top(offset)); 
 top(offset):= top(offset) + T.width } 
N→ ε {t:=mktable(top(tblptr)); push(t, tblptr); 
 push(0,offset) } 
Hình 8.12 - Xử lý các khai báo trong những chương trình con lồng nhau 
Ta dùng Stack tblptr để giữ các con trỏ bảng ký hiệu. 
 Chẳng hạn, khi các khai báo của partition được khảo sát thì trong tblptr chứa các con trỏ 
của các bảng của sort, quicksoft và partition. Con trỏ của bảng hiện hành nằm trên đỉnh Stack. 
 offset là một Stack khác để lưu trữ offset. Chú ý rằng với lược đồ A→ BC {action A} thì 
tất cả các hành vi của các cây con B và C được thực hiện trước A. 
 Do đó hành vi kết hợp với M được thực hiện trước. Nó không tạo ra bảng ký hiệu cho 
tầng ngoài cùng (chương trình sort) bằng cách dùng mktable(nil), con trỏ tới bảng này được 
đưa vào trong Stack tblptr đồng thời được đưa vào Stack offset. 
 Ký hiệu chưa kết thúc N đóng vai trò tương tự như M khi một khai báo chương trình con 
xuất hiện. Nó dùng mktable(top(tblptr)) để tạo ra một bảng mới. Tham số top(tblptr) cho 
giá trị con trỏ tới bảng lại được push vào đỉnh Stack tblptr và 0 được push vào Stack offset. 
 Với mỗi khai báo biến id:T; một ô mới được tạo ra trong bảng ký hiệu hiện hành. Giá trị 
trong top(offset) được tăng lên bởi T.width. 
 Khi hành vi vế phải P → proc id ; N D1 ; S diễn ra, kích thước của tất cả các đối tượng dữ 
liệu khai báo trong D1 sẽ nằm trên đỉnh Stack offsert. Nó được lưu trữ bằng cách dùng 
addwidth, các Stack tblptr và offset bị pop và chúng ta trở về để thao tác trên các khai báo của 
chương trình con 
3. Xử lý đối với mẩu tin 
 Khai báo một mẩu tin được cho bởi luật sinh 
T→ record D end 
 Luật dịch tương ứng 
T→ record L D end { T.type := record(top(tblptr)); 
 T.width := top(offset); pop(tblptr) ; pop(offset) } 
L→ ε { t:= mktable(nil); push(t,tblptr) ; push(0,offset) } 
Hình 8.13 - Cài đặt bảng ký hiệu cho các tên trường trong mẩu tin 
 175
 Sau khi từ khóa record được tìm thấy thì hành vi kết hợp với L tạo một bảng ký hiệu mới 
cho các tên trường. Các hành vi của D → id : T đưa thông tin về tên trường id vào trong bảng 
ký hiệu cho mẩu tin. 
III. LỆNH GÁN 
1. Tên trong bảng ký hiệu 
 Xét lược đồ dịch để sinh ra mã lệnh 3 địa chỉ cho lệnh gán: 
S→ id := E {p:=lookup( id.name); 
 if p nil then emit( p ':=' E.place) else error } 
E→ E1 + E2 { E.place := newtemp; 
 emit(E.place ':=' E1.place '+’ E2.place) } 
E→ E1 * E2 { E.place := newtemp; 
 emit(E.place ':=' E1.place '*’ E2.place) } 
E→ - E1 { E.place := newtemp; 
 emit(E.place ':=' 'unimus' E1.place) } 
E→ ( E1 ) { E.place:=E1.place) } 
E→ id { p:=lookup( id.name); 
 if p nil then E.place := p else error } 
Hình 8.14 - Lược đồ dịch sinh mã lệnh ba địa chỉ cho lệnh gán 
 Hàm lookup tìm trong bảng ký hiệu xem có hay không một tên được cho bởi id.name. Nếu 
có thì trả về con trỏ của ô, nếu không trả về nil. 
 Xét luật sinh D → proc id ; ND1 ; S 
 Như trên đã nói, hành vi kết hợp với ký hiệu chưa kết thúc N cho phép con trỏ của bảng ký 
hiệu cho chương trình con đang nằm trên đỉnh Stack tblptr. 
 Các tên trong lệnh gán sinh ra bởi ký hiệu chưa kết thúc S sẽ được khai báo trong chương 
trình con này hoặc trong bao của nó. Khi tham khảo tới một tên thì trước hết hàm lookkup sẽ 
tìm xem có tên đó trong bảng ký hiệu hiện hành hay không. (Bảng danh biểu hiện hành được 
trỏ bởi top(tblptr)). Nếu không thì dùng con trỏ ở trong header của bảng để tìm bảng ký hiệu 
bao nó và tìm tên trong đó. Nếu tên không được tìm thấy trong tất cả các mức thì lookup trả 
về nil. 
2. Ðịa chỉ hóa các phần tử của mảng 
 Các phần tử của mảng có thể truy xuất nhanh nếu chúng được liền trong một khối các ô 
nhớ kết tiếp nhau. Trong mảng một chiều nếu kích thước của một phần tử là w thì địa chỉ 
tương đối phần tử thứ i của mảng A được tính theo công thức 
 Ðịa chỉ tương đối của A[i] = base + (i-low) * w 
Trong đó 
low: là cận dưới tập chỉ số 
base: là địa chỉ tương đối của ô nhớ cấp phát cho mảng tức là địa chỉ tương đối của 
A[low] 
 176
 Biến đổi một chút ta được 
Ðịa chỉ tương đối của A[i]= i * w + (base -low * w) 
Trong đó: c=base - low * w có thể tính được tại thời gian dịch và lưu trong bảng ký 
hiệu. Do đó địa chỉ tương đối A[i] = i * w +c. 
 Mảng hai chiều co ïthể xem như là một mảng theo một trong hai dạng: theo dòng 
(row_major) hoặc theo cột (colum_major) 
 a[1,1] a[1,2] a[1,3] 
a[2,1] a[2,2] a[2,3] 
a[1,1] → a[1,2] → a[1,3] 
a[2,1] → a[2,2] → a[2,3] 
 Theo dòng Theo cột 
a[1,1] 
a[1,2] 
a[1,3] 
a[2,1] 
a[2,3] 
a[2,2] 
a[1,1] 
a[2,1] 
a[1,2] 
a[2,2] 
a[2,3] 
a[1,3] Cột 3 
 Cột 2 
Cột 1 
 Dòng 1 
Dòng 2 
Hình 8.15 - Những cách sắp xếp của mảng hai chiều 
 Trong trưòng hợp lưu trữ theo dòng, địa chỉ tương đối của phần tử a[i1, j2] có thể tính 
theo công thức 
 Ðịa chỉ tương đối của A[i1, j2] = base + ((i1- low1) * n2 +j2 -low2) * w 
 Trong đó low1 và low2 là cận dưới của hai tập chỉ số. 
n2 : là số các phần tử trong một dòng. Nếu gọi high2 là cận trên của tập chỉ số thứ 2 thì n2 = 
high2 -low2 +1 
 Trong đó công thức trên chỉ có i1, i2 là chưa biết tại thời gian dịch. Do đó, nếu biến đổi 
công thức để được : 
 Ðịa chỉ tương đối của A[i1, j2]= ((i1 * n2)+j2) * w +(base-((low1* n2)+low2) * w) 
 Trong đó 
C= (base- ((low1 * n2) + low2) * w) được tính tại thời gian dịch và ghi vào trong bảng 
ký hiệu. 
 Tổng quát hóa cho trường hợp k chiều, ta có 
 Ðịa chỉ tương đối của A[i1, i2, .. .. ik] là 
((...((i1n2 + i2) n3 +i3)...) nk+ik) w+base-((...((low1n2 + low2) n3+low3)...)nk+ lowk) w 
3. Biến đổi kiểu trong lệnh gán 
 Giả sử chúng ta có 2 kiểu là integer và real; integer phải đổi thành real khi cần thiết. Ta có, 
các hành vi ngữ nghĩa kết hợp với luật sinh E → E1 + E2 như sau: 
E.place := newtemp 
 177
if E1.type= integer and E2.type = integer then begin 
emit(E.place ':=' E1.place 'int + ' E2.place); 
E.type:= integer; 
end 
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