Bài giảng Trình biên dịch - Chương 6: Xử lý ngữ nghĩa

CHƯƠNG 6
XỬ LÝ NGỮ NGHĨA
Xử lý ngữ nghĩa có hai cách: kiểm tra tĩnh (static check) và kiểm tra
động (dynamic check).
Trong chương này chúng ta chỉ bàn đến kiểm tra ngữ nghĩa tĩnh. 
Xử lý ngữ nghĩa tĩnh bao gồm:
1. Truyền thuộc tính
2. Kiểm tra kiểu
3. Kiểm tra trình tự điều khiển
4. Kiểm tra tính duy nhất
5. Kiểm tra mối liên hệ của tên
6. Xử lý các phát biểu goto tham khảo trước.
Bộ phân
tích cú pháp
Bộ xử lý
ngữ nghĩa
Sinh mã
trung
gian
chuỗi
token
cây
cú pháp
cây
cú pháp
mã
trung gian
Hình 6.1. Vị trí của bộ xử lý ngữ nghĩa.
6.1. Truyền thuộc tính
1. Mã trung gian
Mã trung gian có nhiều loại: mã cambridge, mã Balan ngược, mã bộ
tam (triple code), mã bộ tứ (quadruple code).
Bộ tứ cho biểu thức số học
Dạng tổng quát: (, , )
Một cách biểu thị biến tạm ở bảng danh biểu:
Tên:rỗng
Loại: 4
Kiểu dữ liệu: tùy theo kiểu của các toán hạng tham gia phép
toán.
Địa chỉ : địa chỉ tương đối. Địa chỉ này được gán khi sinh mã.
Một số mã bộ tứ cho các phép toán học
JMP (i, 0, 0) nhảy đến bộ tứ có chỉ số i
JPG (i, p1, p2) nhảy đến bộ tứ i nếu toán hạng thứ nhất
lớn hơn toán hạng hai
as1 (p1, p2, 0) gán trị p1 cho p2. p2 là biến đơn
FLT (p1, p2, 0) Đổi trị của p1 thành số thực, gán sang p2
FIX (p1, p2, 0) Đổi trị của p1 thành số nguyên, gán sang p2
6.2. Xử lý ngữ nghĩa với phân tích cú pháp từ dưới lên
1. Vấn đề truyền thuộc tính
Thí dụ 6.1. Chúng ta có văn phạm G.
→ id := 
 → + | 
 → * | 
 → id | ()
n11
n10
id1
n2 
n5 
n9
n8
n1
id2:= * (
n4
n3
id3
n7
n12 
n6 
+ id4 )
Hình 6.2. Cây cú pháp A := X * (R + Q).
Bảng danh biểu
- Truyền thuộc tính
- Sinh ra biến tạm khi thu giảm
2. Phương pháp thực hiện sự truyền thuộc tính
Để thực hiện xử lý ngữ nghĩa trong quá trình phân tích cú pháp, chúng
ta sẽ dùng một stack đặc biệt gồm các phần:
A: ký hiệu văn phạm (tượng trưng cho một danh hiệu)
B: có trị 0 hoặc 1 (ký hiệu 1 là biến tạm)
C: con trỏ chỉ đến bảng danh biểu (thực chất là vị trí của danh
biểu ở trong bảng danh biểu
Token Trị từ vựng Kiểu dữ liệu
1
2
3
4
id
id
id
id
A
X
R
Q
thực
thực
thực
thực
Thí dụ 6.2. Cho văn phạm G như ở thí dụ 6.1. 
 → id := 
 → + | 
 → * | 
 → id | ()
3. Nguyên tắc xử lý ngữ nghĩa
Khi có một chuỗi con x = x1x2xn sắp được thu giảm về KHKKT U 
(với luật sinh U Ỉ x1, x2 xn) thì hành vi xử lý ngữ nghĩa tại nút V là
hàm của:
1) Luật sinh U Ỉ x1x2xn
2) Các xử lý ngữ nghĩa của các nút xi, tức là các nút con của V có thể
là:
i) Tra cứu bảng danh biểu
ii) Tạo ra biến tạm
iii) Sinh mã trung gian
iv) Truyền thuộc tính từ x về V
6.3. Kiểm tra kiểu dữ liệu
1. Hệ thống kiểu
Định nghĩa biểu thức kiểu
1. Kiểu dữ liệu cơ bản
2. Khi biểu thức kiểu được đặt tên
3. Bộ kiến thiết kiểu bao gồm:
1) Dãy (array): array (I, T).
2) Tích số (product): tích số cartesian T1 x T2.
3) Bản ghi (record): kiểu của bản ghi là tích số của biểu thức
kiểu các thành phần của nó. 
Thí dụ:
type row = record
address : integer;
lexeme : array [1..15] of char;
end;
var table : array [1..10] of row;
Kiểu row được biểu diễn bằng biểu thức kiểu:
record ((address x integer) x (lexeme x array (1...15, char))).
4) Con trỏ (pointer): pointer (T).
5) Hàm (function): D Ỉ R.
Thí dụ: trong Pascal có khai báo:
function f (a, b : char) : ↑ integer;
Biểu thức kiểu của f là: 
char x char Ỉ pointer (integer)
4. Biểu thức kiểu chứa các biến mà trị của chúng là biểu thức kiểu. 
Để biểu diễn biểu thức kiểu ta dùng đồ thị. (H.6.4) là cây và dag, 
biểu thị cho biểu thức kiểu char x char Ỉ pointer (integer).
Hệ thống kiểu
Hình 6.4. Cây và dag, biểu thị cho biểu thức char x char Ỉ point 
(interger)
char char
pointer
interger
x x
char
pointer
interger
Kiểm tra kiểu tĩnh và kiểm tra kiểu động
Phát hiện lỗi
2. Đặc tả bộ kiểm tra kiểu đơn giản
Ngôn ngữ đơn giản
Chúng ta có ngôn ngữ đơn giản được sinh ra từ văn phạm G
P → D ; E
D → D ; D | id : T
T → char | integer | array [num] of T | ↑ T
E → literal | num | id |E mod E | [E] | E ↑
Mô phỏng 6.1. Sơ đồ biên dịch dùng để lưu giữ kiểu của các danh biểu
P → D ; E
D → D ; D
D → id : T {addtype (id. entry, T. type)}
T → char { T. type := char}
T → integer {T. type := integer}
T → ↑ T1{T. type := pointer (T1. type)}
T → array [num] of T1{T. type = array (num. val, T1 . type)}
Kiểm tra cho biểu thức
1. Kiểu token là literal và num thí có kiểu là char và integer.
E → literal {E. type := char}
E → num {E. type := integer}
2. E → id {E. type := lookup (id. Entry)}
3. E → E1 mod E2 {E. type := if (E1 . type = integer) and
(E2. type := integer) then integer
else type - error}
4. E → E1 {E2} {E. type := if (E1 . type = integer) and
(E1. type E2 = array (s, t)) then t else type – error}
5. E → E1 ↑ {E. type := if E1. type = pointer (t) then t
else type – error}
Kiểm tra kiểu dữ liệu cho các phát biểu
Một chương trình bao gồm các khai báo, sau đó là các phát biểu, điều
này được biểu thị bằng luật sinh P Ỉ D; S.
Mô phỏng 6.2. Sơ đồ biên dịch cho kiểu dữ liệu của các phát biểu
P → D; S
S → id := E {S.type := if id. type = E. type then void
else type - error}
S → if E then S1 {S.type := if E. type = boolean then
S1. type else type - error}
S → while E do S1 {S.type := if E. type = boolean then
S1. type else type - error}
S → S1; S2 {S.type := if (S1. type = void) and
(S2. Type = void) then void
else type - error}
Kiểm tra kiểu của hàm
E Ỉ E (E)
Để diễn tả kiểu cho biểu thức kiểu ta dùng ký hiệu T và thêm luật
sinh
T Ỉ T1’Ỉ ‘ T2 {T. type := T1. type Ỉ T2. type}
Quy tắc kiểm tra kiểu của hàm là
E Ỉ E1 (E2) {E. type := if (E2. type = s) and
(E1. type = s Ỉ t) then t else
{type - error}
T1 x T2 x .. x Tn
Thí dụ: root Ỉ (real Ỉ real) x real Ỉ real
Chúng ta sẽ hiểu là có khai báo:
function root (functionf (real) : real; x : real) : real
3. Sự tương đương của biểu thức kiểu
• Sự tương đương cấu trúc của biểu thức kiểu
• Giải thuật kiểm tra tương đương cấu trúc của các biểu thức kiểu
Mô phỏng 6.3. Kiểm tra tương đương cấu trúc của hai biểu thức
kiểu s và t.
function sequiv (s, t): boolean;
begin 
if s và t cùng một kiểu cơ bản then true
else if s = array (s1, s2) and t = array (t1, t2) then
return sequiv (s1, s2) and sequiv (s2, t2) 
else if s = s1 x s2 and t = t1 x t2 then
return sequiv (s1, t1) and sequiv (s2, t2) 
else if s = pointer (s1) and t = pointer (t1) then
return sequiv (s1, t1) 
else if s = s1→ s2 and t = t1→ t2 then
return sequiv (s1, t1) and sequiv (s2, t2)
else return false;
end; 
Thí dụ 6.3. Chúng ta sẽ giới thiệu cách mã hoá các biểu thức kiểu của
trình biên dịch C do D.M. Ritchie viết.
Mô phỏng 6.4. Các thí dụ về biểu thức kiểu.
char
freturns (char)
pointer (freturns (char))
array (pointer (freturns (char)) 
Các kiểu cơ bản của ngôn ngữ C được John (1979) mã hóa bằng 4 bit
Bộ kiến thức kiểu Mã hóa
pointer
array
freturns
01
10
11 
Kiểu cơ bản Mã hóa
boolean
char
integer
real 
0000
0001
0010
0011 
Mô phỏng 6.5. Mã hóa biểu thức kiểu ở mô phỏng 6.4.
- Tên cho biểu thức kiểu
Sau đây là một đoạn khai báo kiểu trong Pascal:
type link = ↑ cell;
var next : link;
last : link;
p : ↑ cell;
q, r : ↑ cell;
Biểu thức kiểu Mã hóa
char
freturns (char)
pointer (freturns (char))
array (pointer (freturns (char)) 
000000 0001
000011 0001
0111 0001
100111 0001 
Thí dụ 6.4. 
Biến Biểu thức kiểu
next
last
p
q
r
link
link
pointer (cell)
pointer (cell)
pointer (cell)
Hình 6.11. Biến và các biểu thức kiểu tương ứng
6.4. Chuyển đổi kiểu
Thí dụ ký hiệu hậu tố của biểu thức a + i sau khi thực hiện hành vi 
chuyển đổi kiểu: 
a i intereal real +
- Áp đặt toán tử (Coercion)
Thí dụ 6.5. 
Mô phỏng 6.6. Quy tắc kiểm tra kiểu cho việc áp đặt toán tử để đổi trị
toán hạng từ số nguyên sang số thực.
Luật sinh Luật ngữ nghĩa
E → num
E → num. num
E → id
E → E1 op E2
E. type := integer
E. type := real
E. type := lookup (id. entry)
E. type := if (E1. type = integer) and
(E2. type = integer) then integer
else if (E1. type = integer) and (E2. type = real)
then real
else if (E1. type = real) and (E2. type = integer)
then real
else if (E1. type = real) and (E2. type = real)
then real
else type - error 
Lưu ý:
for | := 1 to N do x [i] := 1 (1)
for | := 1 to N do x [i] := 1.0 (2)
6.5. Xử lý ngữ nghĩa cho phát biểu goto tham khảo trước
Thí dụ 6.6. Giả sử chúng ta có đoạn chương trình
goto L (10) JMP (0,0,0)
goto L (50) JMP (10,0,0)
goto L (90) JMP (50,0,0)
L: x := x + 1 (120)
Bảng 6.2. Bảng lưu giữ tên phát biểu và chỉ số đầu danh sách liên kết
Bảng 6.3. Điền chỉ số của tên L vào các lệnh nhảy
Tên p/b Địa chỉ Định nghĩa
L 90 0
Tên p/b Địa chỉ Định nghĩa
L 120 1
(10) JMP (120,0,0)
(50) JMP (120,0,0)
(90) JMP (120,0,0)