Bài giảng Trình biên dịch - Chương 8: Tổ chức bảng danh biểu

CHƯƠNG 8
TỔ CHỨC BẢNG DANH BIỂU
8.1. Giới thiệu
Có bốn phương pháp truy xuất trên bảng danh biểu:
1. Tìm kiếm tuyến tính (linear search)
2. Tìm kiếm nhị phân (binary search)
3. Tìm kiếm trên cây (tree search)
4. Mã hóa băm (hash coding)
8.2. Các tác vụ trên bảng danh biểu
Bảng 8.1. Các tác vụ trên bảng danh biểu
Tên chương trình
con Cách gọi Hành vi thực thi
Enter Enter (id) Khi gặp một danh biểu mới được khai
báo, thủ tục này sẽ kiểm tra xem danh
biểu mới đó có trùng với tên nào trong
cùng một tầm vực? Nếu không, thủ tục
enter sẽ đưa danh biểu mới vào bảng
danh biểu. Ngược lại enter sẽ thông báo
lỗi về việc khai báo một danh biểu nhiều
lần trong cùng một tầm vực.
loc (hàm) n := loc (id) Khi cần truy xuất một danh biểu, loc sẽ
tìm trên bảng danh biểu từ phân tử mới
nhất của tầm vực mới nhất đến phân tử
cũ nhất của tầm vực cũ nhất để tìm vị trí
của id và trả về thông qua tên loc của
hàm.
Scopeentry Scopeentry Khi trình biên dịch đi vào một tầm vực
mới, scopeentry sẽ đánh dấu trên Stack 
(bảng danh biểu) một tầm vực mới.
Scopeexit Scopeexit Khi trình biên dịch đi hết một tầm vực
scopeenxit sẽ thải hồi những tên biến
không còn có ý nghĩa và tái lập một tầm
vực ngoài cùng gần nhất.
8.3. Bảng danh biểu tuyến tính (linear symbol table)
Thí dụ 8.1. Cho đoạn chương trình trong ngôn ngữ Algol.
begin real A, B;
begin real C, A;
. . . . . . .
end;
end;
5
4 A
3 C
2 B
1 A
I = 5
Hình 8.1. Bảng danh biểu tuyến tính của thí dụ 8.1
Các tác vụ trên bảng danh biểu tuyến tính được trình bày như sau:
Giải thuật:
const tab lim = ..;
btablim = ..;
3
2 3
1 1
B = 3
TAB BTAB
type tabinden = 1 .. tablim;
item = record
key: alfa; /* alfa là kiểu chuỗi các ký tự */
end;
var btab: array [1 .. btablim] of integer;
tab: array [1 .. Tablim] of item;
b: 1 • • tablim;
t: tabindex;
procedure enter (id: alfa)
var sb: tabindex;
begin sb := btab [b –1];
Tìm kiếm trên bảng TAB từ vị trí sb đến vị trí t – 1, xem có phần tử
nào mang key bằng id không? Nếu có, thủ tục error sẽ thông báo lỗi 1 
là lỗi có hai danh biểu cùng tên trong cùng tầm vực. Ngược lại, if t = 
tablim then error (12)
else begin tab [t] key := id;
t := t + 1
end;
end;
function loc (id: alfa): tabindex;
begin
Tìm kiếm từ vị trí đầu TAB đến vị trí t –1, xem có phần tử nào có key 
là id? Nếu không có thì error sẽ thông báo lỗi 13. Ngược lại nếu tìm
thấy danh biểu có khóa id tại vị trí index thì thực thi lệnh loc := index;
end;
Procedure scopeentry;
begin if b = btablim then error (14)
else begin btab [b] := t; b := b + 1
end;
end;
Procedure Scope exit;
begin b := b – 1; t := btab [b]
end;
8.4. Bảng danh biểu băm (hash symbol table)
Một danh biểu chỉ số kH
Chúng ta lấy lại thí dụ 8.1 để minh họa việc xây dựng bảng danh biểu
theo phương pháp băm ở (H.8.2). Giả sử A biến đổi H có k = 3, B có k 
= 6 và C có k = 5.
8 0
7 0
6 2 5
5 3 4 A 1
4 0 3 C 0 3
3 4 2 B 0 2 3
2 0 1 A 0 1 1
1 0 TAB BTAB
HASH
B = 3
T = 5
A k = 3
H
A k = 6
H
H
A k = 5 Hình 8.2. Bảng danh biểu băm
Các tác vụ làm việc trên bảng danh biểu băm được trình bày bằng các
chương trình con sau:
const hashsize = ;
tabsize = ;
btabsize = ;
type tabindex = 1 .. tabsize;
hashindex = 1 .. hashsize;
iterm = record
key: id;
ptr: tabindex;
end;
var tab: array [1 .. tablim] of item
hash: array [hashindex] of tabindex;
btab: array [i .. btabsize] of tabindex;
t: tabindex; b: 1 .. Btabsize;
function H (id: alfa): hashindex;
begin
end;
procedure enter (id: alfa);
var sb: tabindex; k: hashindex; ind: tabindex;
begin
k := H(id);
ind := HASH [k];
sb := btab [b – 1];
if HASH [k] 0 then
while ind > = sb do
if id = tab [ind]. key then error (11) 
/* trùng tên danh biểu trong cùng tầm vực */
else ind := tab [ind]. Ptr; {không trùng tên}
if t = tabsize then error (12)
else begin
tab [t]. Key := id;
tab [t]. Ptr := HASH [k];
HASH [k] := t;
t := t + 1;
end;
end;
function loc (id: alfa): tabindex;
var q: boolean; ind: tabindex;
begin ind := HASH [H(id)]; 
q := false;
while (ind 0) and (not (q)) do
begin q := id = tab [ind]. Key;
if not (q) then ind := tab [ind]. Ptr
end;
if q then loc := ind else error (13);
/* chưa có danh biểu trong bảng danh biểu */
end;
procedure Scopeentry;
begin if b = tabsize then error (14)
else begin btab [b] := t;
b := b + 1;
end;
procedure Scopeexit;
var ind: tabindex;
k: hashindex;
begin
ind := t; t := btab [b – 1];
b := b – 1;
while ind > t do
begin ind := ind – 1;
k := H (tab [ind]. Key);
HASH [k] := tab [HASH [k]]. Ptr;
end;
end;
8.5. Hàm băm (hashing function)
8.6. Lưu giữ thông tin của tầm vực ý nghĩa
nil header sort
a
x
readarray bảng readarray
exchange bảng exchange
header
quicksort
exchange
header k
v
header readarray partition
i
partition header
i
Muốn thực hiện việc tạo bảng danh biểu cho chương trình con bị gọi, 
ta phải tạo các hàm như sau:
1. mktable (x)
2. enter (table, name, type, offset)
3. addwidth (table, width)
4. enterproc (table, name, newtable)