Thiết kế trình biên dịch - Bảng ký hiệu
Bảng ký hiệu là một cấu trúc dữ liệu quan trọng được tạo và duy trì bởi trình biên dịch để lưu trữ thông tin về sự xuất hiện của các thực thể khác nhau như tên biến, tên hàm, đối tượng, lớp, giao diện, v.v. Bảng ký hiệu được sử dụng cho cả phân tích và tổng hợp các bộ phận của trình biên dịch.
Một bảng ký hiệu có thể phục vụ các mục đích sau tùy thuộc vào ngôn ngữ có trong tay:
Để lưu trữ tên của tất cả các thực thể trong một biểu mẫu có cấu trúc tại một nơi.
Để xác minh xem một biến đã được khai báo hay chưa.
Để thực hiện kiểm tra kiểu, bằng cách xác minh các phép gán và biểu thức trong mã nguồn là đúng về mặt ngữ nghĩa.
Để xác định phạm vi của một tên (độ phân giải phạm vi).
Bảng ký hiệu đơn giản là một bảng có thể là bảng tuyến tính hoặc bảng băm. Nó duy trì một mục nhập cho mỗi tên ở định dạng sau:
<symbol name, type, attribute>Ví dụ, nếu một bảng ký hiệu phải lưu trữ thông tin về khai báo biến sau:
static int interest;thì nó sẽ lưu trữ mục nhập như:
<interest, int, static>Mệnh đề thuộc tính chứa các mục liên quan đến tên.
Thực hiện
Nếu một trình biên dịch phải xử lý một lượng nhỏ dữ liệu, thì bảng ký hiệu có thể được triển khai dưới dạng danh sách không có thứ tự, rất dễ viết mã, nhưng nó chỉ phù hợp với các bảng nhỏ. Một bảng ký hiệu có thể được triển khai theo một trong những cách sau:
- Danh sách tuyến tính (được sắp xếp hoặc không được sắp xếp)
- Cây tìm kiếm nhị phân
- Bảng băm
Trong số tất cả, các bảng biểu tượng chủ yếu được triển khai dưới dạng bảng băm, trong đó bản thân biểu tượng mã nguồn được coi như một khóa cho hàm băm và giá trị trả về là thông tin về biểu tượng.
Hoạt động
Một bảng ký hiệu, tuyến tính hoặc băm, phải cung cấp các phép toán sau.
chèn()
Thao tác này được sử dụng thường xuyên hơn trong giai đoạn phân tích, tức là nửa đầu của trình biên dịch nơi mã thông báo được xác định và tên được lưu trữ trong bảng. Thao tác này được sử dụng để thêm thông tin trong bảng ký hiệu về các tên duy nhất xuất hiện trong mã nguồn. Định dạng hoặc cấu trúc mà các tên được lưu trữ phụ thuộc vào trình biên dịch trong tay.
Thuộc tính cho một ký hiệu trong mã nguồn là thông tin được liên kết với ký hiệu đó. Thông tin này chứa giá trị, trạng thái, phạm vi và loại về biểu tượng. Hàm insert () lấy biểu tượng và các thuộc tính của nó làm đối số và lưu trữ thông tin trong bảng biểu tượng.
Ví dụ:
int a;nên được xử lý bởi trình biên dịch như:
insert(a, int);tra cứu()
Thao tác lookup () được sử dụng để tìm kiếm tên trong bảng ký hiệu nhằm xác định:
- nếu ký hiệu tồn tại trong bảng.
- nếu nó được khai báo trước khi nó được sử dụng.
- nếu tên được sử dụng trong phạm vi.
- nếu ký hiệu được khởi tạo.
- nếu ký hiệu được khai báo nhiều lần.
Định dạng của hàm lookup () thay đổi tùy theo ngôn ngữ lập trình. Định dạng cơ bản phải phù hợp với những điều sau:
lookup(symbol)Phương thức này trả về 0 (không) nếu ký hiệu không tồn tại trong bảng ký hiệu. Nếu biểu tượng tồn tại trong bảng biểu tượng, nó sẽ trả về các thuộc tính của nó được lưu trữ trong bảng.
Phạm vi quản lí
Một trình biên dịch duy trì hai loại bảng ký hiệu: a global symbol table có thể được truy cập bằng tất cả các thủ tục và scope symbol tables được tạo cho từng phạm vi trong chương trình.
Để xác định phạm vi của tên, các bảng ký hiệu được sắp xếp theo cấu trúc phân cấp như trong ví dụ dưới đây:
. . .
int value=10;
void pro_one()
{
int one_1;
int one_2;
{ \
int one_3; |_ inner scope 1
int one_4; |
} /
int one_5;
{ \
int one_6; |_ inner scope 2
int one_7; |
} /
}
void pro_two()
{
int two_1;
int two_2;
{ \
int two_3; |_ inner scope 3
int two_4; |
} /
int two_5;
}
. . .Chương trình trên có thể được biểu diễn theo cấu trúc phân cấp của các bảng ký hiệu:
Bảng ký hiệu toàn cục chứa tên cho một biến toàn cục (giá trị int) và hai tên thủ tục, những tên này sẽ có sẵn cho tất cả các nút con được hiển thị ở trên. Các tên được đề cập trong bảng biểu tượng pro_one (và tất cả các bảng con của nó) không có sẵn cho biểu tượng pro_two và các bảng con của nó.
Phân cấp cấu trúc dữ liệu bảng ký hiệu này được lưu trữ trong trình phân tích ngữ nghĩa và bất cứ khi nào tên cần được tìm kiếm trong bảng ký hiệu, nó sẽ được tìm kiếm bằng thuật toán sau:
đầu tiên một biểu tượng sẽ được tìm kiếm trong phạm vi hiện tại, tức là bảng biểu tượng hiện tại.
nếu một tên được tìm thấy, thì quá trình tìm kiếm sẽ hoàn tất, nếu không nó sẽ được tìm kiếm trong bảng ký hiệu mẹ cho đến khi,
tên được tìm thấy hoặc bảng ký hiệu chung đã được tìm kiếm tên.