Xem mẫu
- Chương 2
TỔNG QUAN VỀ TRÌNH BIÊN DỊCH
Trường Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính Bài giảng môn Lý thuyết ngôn ngữ lập tr
- Nội dung Chương 2
2.1. Trình biên dịch
2.1.1. Mô hình phân tích - tổng hợp của một trình biên dịch
2.1.2 Môi trường của trình biên dịch
2.2. Các giai đoạn biên dịch
2.2.1. Quản lý bảng ký hiệu
2.2.2. Xử lý lỗi
2.2.3. Các giai đoạn phân tích
2.2.4. Sinh mã trung gian
2.2.5. Tối ưu mã
2.2.6. Sinh mã
2.3. Gộp các giai đoạn
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 2
- 2.1 Trình biên dịch
Trình biên dịch đọc một chương trình được viết bằng
ngôn ngữ nguồn (source language) rồi dịch sang ngôn
ngữ đích (target languague)
Quá trình dịch ghi nhận và thông báo các lỗi có trong
chương trình nguồn
Chương Trình Chương
trình biên dịch trình đích
nguồn
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 3
- 2.1 Trình biên dịch (tt)
Mô hình phân tích - tổng hợp
– Quy trình của chương trình dịch thường bao gồm hai quá
trình: phân tích và tổng hợp
Quá trình phân tích: phân rã chương trình nguồn thành các phần
cấu thành và tạo ra một dạng biểu diễn trung gian
Quá trình tổng hợp: từ dạng biểu diễn trung gian xây dựng thành
ngôn ngữ đích
Chương Phân tích Đặc tả Tổng hợp Chương
trình trung trình
nguồn gian đích
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 4
- 2.1 Trình biên dịch (tt)
Mô hình phân tích - tổng hợp (tt)
– Trong quá trình phân tích: phân rã chương trình nguồn thành
một cấu trúc phân cấp dạng cây cú pháp (syntax tree), mỗi nút
là một toán tử và các nhánh con là các toán hạng
– Ví dụ: Cây cú pháp cho lệnh gán a := b + c * 5
:=
a +
b *
c 5
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 5
- 2.1 Trình biên dịch (tt)
Môi trường của trình biên dịch
– Ngoài trình biên dịch, cần dùng nhiều chương trình
khác để tạo chương trình đích có thể thực thi
(executable)
– Các chương trình đó gồm:
Bộ tiền xử lý
Trình dịch hợp ngữ
Bộ tải và soạn thảo liên kết
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 6
- 2.1 Trình biên dịch (tt)
Bộ tiền xử lý
– Chương trình nguồn có thể được phân thành các
module và được lưu trong các tập tin riêng
– Việc tập hợp các tập tin này lại thường được giao cho
bộ tiền xử lý
– Bộ tiền xử lý có thể "bung" các ký hiệu tắt được gọi là
các macro thành các câu lệnh của ngôn ngữ nguồn
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 7
- 2.1 Trình biên dịch (tt)
Trình dịch hợp ngữ
– Chương trình đích được tạo ra bởi trình biên dịch có
thể cần phải được xử lý thêm trước khi chúng có thể
chạy được
– Thông thường, trình biên dịch chỉ tạo ra mã lệnh hợp
ngữ (assembly code)
– Trình dịch hợp ngữ (assembler) dịch thành dạng mã
máy
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 8
- 2.1 Trình biên dịch (tt)
Chương trình nguồn khung
Bộ tải và soạn thảo liên kết Bộ tiền xử lý
– Dạng mã máy được liên kết
Chương trình nguồn
với một số thủ tục (hàm, lớp,
…) trong thư viện hệ thống Trình biên dịch
thành các mã thực thi được
Chương trình đích hợp ngữ
Một quá trình biên dịch điển Trình dịch hợp ngữ
hình được cho như hình
bên Mã máy khả tái định vị
Thư viện, tập
Trình tải / Liên kết
đối tượng khả
định vị
Mã máy tuyệt đối
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 9
- 2.2 Các giai đoạn biên dịch
Biên dịch được chia thành nhiều giai đoạn
Mỗi giai đoạn chuyển chương trình nguồn từ một dạng
biểu diễn này sang một dạng biểu diễn khác
Việc quản lý bảng ký hiệu và xử lý lỗi được thực hiện
xuyên suốt qua tất cả các giai đoạn
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 10
- 2.2 Các giai đoạn biên dịch (tt)
Một cách phân rã điển hình trình biên dịch như sau:
s
Chương trình nguồn
thể phân từ vựng
thể phân cú pháp
thể phân ngữ nghĩa
thể quản lý bảng ký hiệu thể xử lý lỗi
thể sinh mã trung gian
thể tối ưu hoá mã
thể sinh mã
Chương trình đích
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 11
- 2.2 Các giai đoạn biên dịch (tt)
Quản lý bảng ký hiệu
– Bảng ký hiệu (symbol table) là một cấu trúc dữ liệu mà mỗi
phần tử là một mẩu tin dùng để lưu trữ một định danh, bao
gồm các trường lưu giữ ký hiệu và các thuộc tính của nó
– Những thuộc tính cung cấp thông tin về vị trí lưu trữ của định
danh, kiểu và tầm vực
– Bảng ký hiệu cho phép tìm kiếm, truy xuất định danh một cách
nhanh chóng
– Trong quá trình phân tích từ vựng, định danh được tìm thấy
và nó được đưa vào bảng ký hiệu nhưng nói chung các thuộc
tính của nó có thể chưa xác định được trong giai đoạn này
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 12
- 2.2 Các giai đoạn biên dịch (tt)
Xử lý lỗi
– Mỗi giai đoạn đều có thể gặp lỗi
– Tùy thuộc vào trình biên dịch mà có các cách xử lý khác nhau
Dừng và thông báo lỗi khi gặp lỗi đầu tiên (Pascal)
Ghi nhận lỗi và tiếp tục quá trình dịch (C)
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 13
- 2.2 Các giai đoạn biên dịch (tt)
Xử lý lỗi (tt)
– Giai đoạn phân tích từ vựng: thường gặp lỗi khi các ký tự
không thể ghép thành một thẻ (token)
– Giai đoạn phân tích cú pháp: khi các thẻ (token) không thể kết
hợp với nhau
– Giai đoạn phân tích ngữ nghĩa: khi các toán hạng có kiểu
không đúng yêu cầu của phép toán hay các kết cấu không có
nghĩa đối với thao tác thực hiện
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 14
- 2.2 Các giai đoạn biên dịch (tt)
Các giai đoạn phân tích
– Giai đoạn phân tích từ vựng (phân tích tuyến tính)
Các dòng ký tự tạo ra chương trình nguồn sẽ được đọc từ trái sang phả
và được nhóm lại thành các token (thẻ từ)
Token từ là các chuỗi ký tự được hợp lại để tạo ra một nghĩa chung
chẳng hạn một định danh, từ khóa, một ký hiệu,..
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 15
- 2.2 Các giai đoạn biên dịch (tt)
Các giai đoạn phân tích (tt)
– Giai đoạn phân tích từ vựng (tt)
Ví dụ: Quá trình phân tích từ vựng cho câu lệnh gán a = b + c *5 sẽ tách
thành các token như sau:
– 1. Định danh a (id1)
– 2. Ký hiệu phép gán =
– 3. Định danh b (id12)
– 4. Ký hiệu phép cộng (+)
– 5. Định danh c (id3)
– 6. Ký hiệu phép nhân (*)
– 7. Số 5
Trong quá trình phân tích từ vựng các khoảng trắng (blank) sẽ bị bỏ qua
Sau giai đoạn này câu lệnh a = b + c * 5 sẽ trở thành id1 = id2 + id3*5
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 16
- 2.2 Các giai đoạn biên dịch (tt)
Các giai đoạn phân tích (tt)
– Giai đoạn phân tích cú pháp
Nhóm các thẻ từ của chương trình nguồn thành các ngữ đoạn văn
phạm (grammatical phrase), mà sau đó sẽ được trình biên dịch tổng
hợp ra thành phẩm
Thông thường, các ngữ đoạn văn phạm này được biểu diễn bằng dạng
cây phân tích cú pháp (parse tree) với :
– Ngôn ngữ được đặc tả bởi các luật sinh
– Phân tích cú pháp dựa vào luật sinh để xây dựng cây phân tích cú pháp
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 17
- 2.2 Các giai đoạn biên dịch (tt)
Các giai đoạn phân tích (tt)
– Giai đoạn phân tích cú pháp (tt)
Ví dụ: Sau giai đoạn này câu lệnh a = b + c * 5 có cây phân tích cú
pháp được xây dựng như sau :
assignment
statemeent
expression
identifier =
expression expression
a +
expression expression
identifier *
b identifier number
c 5
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 18
- 2.2 Các giai đoạn biên dịch (tt)
Các giai đoạn phân tích (tt)
– Giai đoạn phân tích ngữ nghĩa
Giai đoạn phân tích ngữ nghĩa sẽ thực hiện việc kiểm tra xem chương
trình nguồn có chứa lỗi về ngữ nghĩa hay không và tập hợp thông tin
về kiểu cho giai đoạn sinh mã về sau
Một phần quan trọng trong giai đoạn phân tích ngữ nghĩa là kiểm tra
kiểu (type checking) và ép chuyển đổi kiểu
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 19
- 2.2 Các giai đoạn biên dịch (tt)
Các giai đoạn phân tích (tt)
– Giai đoạn phân tích ngữ nghĩa (tt)
Ví dụ: Trong câu lệnh a = b + c * 5, giả sử các định danh (biến) a,b,c
được khai báo là số thực (real), còn 5 là số nguyên (int), vì vậy trình
biên dịch sẽ đổi số nguyên 5 thành số thực 5.0
=
=
a +
a +
b *
b *
c inttoreal
c 5
5
ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 20
nguon tai.lieu . vn
