Lý thuyết ngôn ngữ lập trình - Chương 2: Tổng quan về trình biên dịch

Nội dung text: Lý thuyết ngôn ngữ lập trình - Chương 2: Tổng quan về trình biên dịch

1. Chương 2 TTỔỔNGNG QUANQUAN VVỀỀ TRÌNHTRÌNH BIÊNBIÊN DDỊỊCHCH 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
2. NNộộii dungdung ChươngChương 22 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
3. 2.12.1 TrTrììnhnh biênbiên ddịịchch  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
4. 2.12.1 TrTrììnhnh biênbiên ddịịchch ((tttt))  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
5. 2.12.1 TrTrììnhnh biênbiên ddịịchch ((tttt))  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
6. 2.12.1 TrTrììnhnh biênbiên ddịịchch ((tttt))  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
7. 2.12.1 TrTrììnhnh biênbiên ddịịchch ((tttt))  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
8. 2.12.1 TrTrììnhnh biênbiên ddịịchch ((tttt))  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
9. 2.12.1 TrTrììnhnh biênbiên ddịịchch ((tttt)) 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 với một số thủ tục (hàm, lớp, Chương trình nguồn ) 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
10. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch  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
11. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt)) 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
12. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  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
13. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  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
14. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  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
15. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  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
16. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  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
17. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  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
18. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  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 a + expression 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
19. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  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
20. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  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
21. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  Sinh mã trung gian – Sau khi phân tích ngữ nghĩa, một số trình biên dịch sẽ tạo ra một dạng biểu diễn trung gian của chương trình nguồn – Có thể xem dạng biểu diễn này như một chương trình dành cho một máy trừu tượng – Chúng có hai đặc tính quan trọng: dễ sinh và dễ dịch thành chương trình đích ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 21
22. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  Sinh mã trung gian (tt) – Thường sử dụng dạng mã máy 3 địa chỉ, tương tự hợp ngữ cho một máy, mỗi vị trí nhớ đóng vai trò như một thanh ghi – Mã máy 3 địa chỉ là một dãy các lệnh liên tiếp, mỗi lệnh có thể có tối đa 3 đối số – Ví dụ: t1 := inttoreal (5) t2 := id3 * t1 t3 := id2 + t2 id1 := t3 ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 22
23. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  Các tính chất của mã trung gian – Mỗi lệnh chỉ chứa nhiều nhất một toán tử – Do đó khi tạo ra lệnh này, trình biên dịch phải xác định được thứ tự các phép toán, ví dụ * thực hiện trước + – Trình biên dịch phải tạo ra một biến tạm để lưu trữ giá trị tính toán cho mỗi lệnh. – Một số lệnh có ít hơn 3 toán hạng ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 23
24. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  Tối ưu mã – Cải thiện mã trung gian để có thể có mã máy thực hiện nhanh hơn – Ví dụ: t1 := inttoreal (5) t2 := id3 * t1 t3 := id2 + t2 id1 := t3  Việc đổi số nguyên 5 thành số thực 5.0 có thể thực hiện một lần lúc biên dịch → có thể loại bỏ phép toán inttoreal  t3 chỉ được dùng để chuyển giá trị cho id1 nên có thể bỏ  Có thể tối ưu thành: t1 := id3 * 5.0 id1 := id2 + t1 ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 24
25. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  Tối ưu mã (tt) – Khối lượng tối ưu hoá mã được các trình biên dịch khác nhau thực hiện cũng khác nhau – Trong những "trình biên dịch chuyên tối ưu", một phần thời gian đáng kể được dành cho giai đoạn này – Có những phương pháp tối ưu giúp giảm đáng kể thời gian chạy của chương trình nguồn mà không làm tăng thời gian dịch quá nhiều ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 25
26. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  Sinh mã – Giai đoạn cuối cùng của biên dịch là sinh mã đích. – Thường là mã máy hoặc mã hợp ngữ. – Các vị trí vùng nhớ được chọn lựa cho mỗi biến được chương trình sử dụng. – Các chỉ thị trung gian được dịch lần lượt thành chuỗi các chỉ thị mã máy. – Vấn đề quyết định là việc gán các biến cho các thanh ghi ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 26
27. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  Sinh mã (tt) – Ví dụ: Sử dụng các thanh ghi (chẳng hạn R1, R2) cho việc sinh mã đích như sau: MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 id1 = id2 +id3 * 5.0 ADDF R2, R1 MOVF R1, id1 – Toán hạng thứ nhất và thứ hai của mỗi chỉ thị tương ứng mô tả đối tượng nguồn và đích – Chữ F biểu thị số chấm động – Dấu # để xác định số 5.0 xem như một hằng số ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 27
28. 2.22.2 CCáácc giaigiai đođoạạnn biênbiên ddịịchch ((tttt))  Quá trình dịch một câu lệnh: position:=initial + rate*60 Sinh mã trung gian Phân tích từ vựng Phân tích cú pháp Tối ưu mã Phân tích ngữ nghĩa Sinh mã ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 28
29. 2.32.3 GGộộpp ccáácc giaigiai đođoạạnn  Các giai đoạn đề cập ở trên thực hiện theo trình tự logic của một trình biên dịch  Thực tế, các hoạt động một giai đoạn có thể được nhóm lại với nhau  Thường được nhóm thành hai nhóm cơ bản – Kỳ đầu (Front end) – Kỳ sau (Back end) ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 29
30. 2.32.3 GGộộpp ccáácc giaigiai đođoạạnn ((tttt))  Kỳ đầu (Front end) – Bao gồm các giai đoạn phụ thuộc nhiều vào ngôn ngữ nguồn và độc lập với máy đích, thường chứa các giai đoạn sau:  Phân tích từ vựng  Phân tích cú pháp  Phân tích ngữ nghĩa  Sinh mã trung gian – Một phần của việc tối ưu hóa mã được thực hiện ở kỳ này – Nó cũng bao gồm cả việc xử lý lỗi xuất hiện trong từng giai đoạn ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 30
31. 2.32.3 GGộộpp ccáácc giaigiai đođoạạnn ((tttt))  Kỳ sau (Back End) – Kỳ sau bao gồm một số phần nào đó của trình biên dịch – Phụ thuộc vào máy đích – Nói chung các phần này không phụ thuộc vào ngôn ngữ nguồn mà là ngôn ngữ trung gian – Còn có một số vấn đề tối ưu hoá mã, phát sinh mã đích cùng với việc xử lý lỗi và các thao tác trên bảng ký hiệu ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 31
32. 2.42.4 CâuCâu hhỏỏii ônôn ttậậpp  1. Trình bày các giai đoạn của trình biên dịch và chức năng của từng giai đoạn  2. Trình biên dịch có thể nhóm lại thành các giai đoạn cơ bản nào ? Nêu nhiệm vụ của các giai đoạn đó  3. Trình bày các giai đoạn của quá trình dịch các câu lệnh sau:  a/ m = (n + k )*10, với m,n,k là các số thực  b/ a = (b+c) * (d+e)  c/ y = x*y + z *12 ờng Cao đẳng CNTT HN Việt – Hàn Khoa Khoa học máy tính 32