Thiết kế trình biên dịch: Bảng ký hiệu
Trong hướng dẫn trước, bạn sẽ tìm hiểu chi tiết các phương pháp để tối ưu mã trong thiết kế trình biên dịch. Nếu bỏ lỡ thì bạn có thể xem ở đây:
Comdy
Bảng ký hiệu (symbol table) 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 thành 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ữ đang sử dụng:
- Để 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 dữ liệ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 (giới hạn 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 phần tử 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ữ phần tử như sau:
<interest, int, static>Mệnh đề attribute chứa các thực thể liên quan đến tên.
Triển khai
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 thực hiện 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 ký hiệu chủ yếu được triển khai dưới dạng bảng băm, trong đó bản thân ký hiệu 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ề ký hiệu.
Các thao tác
Một bảng ký hiệu, tuyến tính hoặc băm, phải cung cấp các thao tác sau.
insert()
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 vào 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 đang được sử dụng.
Attribute 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 ký hiệu và các attribute của nó làm đối số và lưu trữ thông tin trong bảng ký hiệu.
Ví dụ:
int a;sẽ được xử lý bởi trình biên dịch như sau:
insert(a, int);lookup()
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 ký hiệu 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: bảng ký hiệu toàn cục có thể được truy cập bởi tất cả các thủ tục và bảng ký hiệu phạm vi được tạo cho mỗi 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ư thể hiện 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 các 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 ký hiệu là pro_one (và tất cả các bảng con của nó) không có sẵn cho các ký hiệu 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 một 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 ký hiệu sẽ được tìm kiếm trong phạm vi hiện tại, tức là bảng ký hiệu hiện tại.
- nếu 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 cha 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.
Trong hướng dẫn tiếp theo, bạn sẽ tìm hiểu chi tiết về môi trường thực thi, nơi chương trình sau khi biên dịch sẽ được thực thi.
Comdy