Thiết kế trình biên dịch: Tổng quan
Trình biên dịch dịch mã được viết bằng ngôn ngữ này sang một số ngôn ngữ khác mà không làm thay đổi ý nghĩa của chương trình. Người ta cũng mong đợi rằng một trình biên dịch sẽ làm cho mã đích hiệu quả và được tối ưu hóa về mặt thời gian và không gian.
Các nguyên tắc thiết kế trình biên dịch cung cấp một cái nhìn chuyên sâu về quá trình dịch và tối ưu hóa. Thiết kế trình biên dịch bao gồm cơ chế dịch cơ bản, phát hiện và phục hồi lỗi. Nó bao gồm phân tích từ vựng, cú pháp và ngữ nghĩa như frontend, tạo mã và tối ưu hóa như backend.
Tại sao nên học thiết kế trình biên dịch?
Máy tính là sự kết hợp cân bằng giữa phần mềm và phần cứng. Phần cứng chỉ là một phần của thiết bị vật lý và các chức năng của nó được điều khiển bởi một phần mềm tương thích.
Phần cứng hiểu các hướng dẫn dưới dạng điện tử, là bản sao của ngôn ngữ nhị phân trong lập trình phần mềm. Ngôn ngữ nhị phân chỉ có hai chữ cái là 0 và 1. Mã cho phần cứng phải được viết ở định dạng nhị phân, đơn giản là một dãy số 1 và 0.
Sẽ là một nhiệm vụ khó khăn và cồng kềnh đối với các lập trình viên máy tính khi viết những đoạn mã như vậy, đó là lý do tại sao chúng ta có những trình biên dịch để viết những đoạn mã như vậy.
Đối tượng độc giả
Hướng dẫn này được thiết kế cho sinh viên quan tâm đến việc tìm hiểu các nguyên tắc cơ bản của trình biên dịch.
Những độc giả nhiệt huyết muốn biết thêm về trình biên dịch và những người muốn tự thiết kế trình biên dịch có thể bắt đầu từ đây.
Điều kiện tiên quyết
Hướng dẫn này không yêu cầu kiến thức trước về thiết kế trình biên dịch nhưng yêu cầu hiểu biết cơ bản về ít nhất một ngôn ngữ lập trình như C, Java, v.v. Một lợi thế lớn nếu bạn đã từng tiếp xúc với lập trình hợp ngữ.
Hệ thống xử lý ngôn ngữ
Chúng ta đã biết rằng bất kỳ hệ thống máy tính nào cũng được cấu tạo từ phần cứng và phần mềm. Phần cứng hiểu một ngôn ngữ mà con người không thể hiểu được.
Vì vậy, chúng ta viết các chương trình bằng ngôn ngữ bậc cao, dễ hiểu và dễ nhớ hơn. Các chương trình này sau đó được đưa vào một loạt các công cụ và thành phần hệ điều hành để có được mã mong muốn mà máy có thể sử dụng.
Đây được gọi là Hệ thống xử lý ngôn ngữ.
Ngôn ngữ cấp cao được chuyển đổi thành ngôn ngữ nhị phân trong nhiều giai đoạn khác nhau. Một trình biên dịch là một chương trình chuyển đổi ngôn ngữ cấp cao sang ngôn ngữ hợp ngữ. Tương tự, trình hợp dịch là một chương trình chuyển đổi ngôn ngữ hợp ngữ sang ngôn ngữ máy.
Đầu tiên chúng ta hãy hiểu cách một chương trình, sử dụng trình biên dịch C, được thực thi trên một máy chủ.
- Nhà phát triển viết chương trình bằng ngôn ngữ C (ngôn ngữ bậc cao).
- Trình biên dịch C, biên dịch chương trình và chuyển nó sang chương trình hợp ngữ (ngôn ngữ cấp thấp).
- Sau đó, một trình hợp dịch sẽ dịch chương trình hợp ngữ thành mã máy (đối tượng).
- Một công cụ trình liên kết được sử dụng để liên kết tất cả các phần của chương trình với nhau để thực thi (mã máy thực thi).
- Trình tải nạp tất cả chúng vào bộ nhớ và sau đó chương trình được thực thi.
Trước khi đi sâu vào các khái niệm về trình biên dịch, chúng ta nên hiểu một vài công cụ khác hoạt động chặt chẽ với trình biên dịch.
Bộ tiền xử lý (Preprocessor)
Bộ tiền xử lý thường được coi là một phần của trình biên dịch, là một công cụ tạo ra đầu vào cho trình biên dịch. Nó làm việc với macro-processing, augmentation, file inclusion, mở rộng ngôn ngữ, v.v.
Trình thông dịch (Interpreter)
Trình thông dịch cũng giống như một trình biên dịch, dịch ngôn ngữ cấp cao sang ngôn ngữ máy cấp thấp. Sự khác biệt nằm ở cách chúng đọc mã nguồn hoặc đầu vào.
Một trình biên dịch đọc toàn bộ mã nguồn cùng một lúc, tạo token, kiểm tra ngữ nghĩa, tạo mã trung gian, thực thi toàn bộ chương trình và có thể liên quan đến nhiều lần chuyển.
Ngược lại, một trình thông dịch đọc một câu lệnh từ đầu vào, chuyển đổi nó thành một mã trung gian, thực thi nó, sau đó thực hiện câu lệnh tiếp theo theo trình tự. Nếu xảy ra lỗi, trình thông dịch sẽ ngừng thực thi và báo cáo lỗi đó, trong khi trình biên dịch đọc toàn bộ chương trình ngay cả khi nó gặp một số lỗi.
Trình hợp dịch (Assembler)
Trình hợp dịch dịch các chương trình hợp ngữ thành mã máy. Đầu ra của trình hợp dịch được gọi là tệp đối tượng, tệp này chứa sự kết hợp của các lệnh máy cũng như dữ liệu cần thiết để đặt các lệnh này trong bộ nhớ.
Trình liên kết (Linker)
Trình liên kết là một chương trình máy tính liên kết và hợp nhất các tệp đối tượng khác nhau với nhau để tạo thành một tệp thực thi. Tất cả các tệp này có thể đã được biên dịch bởi các trình lắp ráp riêng biệt.
Nhiệm vụ chính của trình liên kết là tìm kiếm và định vị mô-đun / tiến trình được tham chiếu trong chương trình và xác định vị trí bộ nhớ nơi các mã này sẽ được tải, làm cho lệnh chương trình có tham chiếu tuyệt đối.
Trình tải (Loader)
Trình tải là một phần của hệ điều hành và chịu trách nhiệm tải các tập tin thực thi vào bộ nhớ và thực thi chúng. Nó tính toán kích thước của một chương trình (lệnh và dữ liệu) và tạo không gian bộ nhớ cho nó. Nó khởi tạo các thanh ghi khác nhau để bắt đầu thực thi.
Trình biên dịch chéo (Cross-compiler)
Một trình biên dịch chạy trên nền tảng (A) và có khả năng tạo mã thực thi cho nền tảng (B) được gọi là trình biên dịch chéo.
Trình biên dịch từ nguồn sang nguồn (Source-to-source Compiler)
Một trình biên dịch lấy mã nguồn của một ngôn ngữ lập trình và dịch nó sang mã nguồn của ngôn ngữ lập trình khác được gọi là trình biên dịch nguồn sang nguồn.
Kiến trúc trình biên dịch
Nói chung, một trình biên dịch có thể được chia thành hai giai đoạn dựa trên cách chúng biên dịch.
Giai đoạn phân tích
Được biết đến như là phần trước của trình biên dịch, giai đoạn phân tích của trình biên dịch đọc chương trình nguồn, chia nó thành các phần cốt lõi và sau đó kiểm tra các lỗi từ vựng, ngữ pháp và cú pháp.
Giai đoạn phân tích tạo ra một biểu diễn trung gian của chương trình nguồn và bảng ký hiệu, nó sẽ được cung cấp cho giai đoạn tổng hợp làm đầu vào.
Giai đoạn tổng hợp
Được biết đến như là phần cuối của trình biên dịch, giai đoạn tổng hợp tạo ra chương trình đích với sự trợ giúp của biểu diễn trung gian của mã nguồn và bảng ký hiệu.
Một trình biên dịch có thể có nhiều giai đoạn và băng chuyền.
- Băng chuyền: Băng chuyên đề cập đến việc truyền tải của một trình biên dịch thông qua toàn bộ chương trình.
- Giai đoạn: Giai đoạn của trình biên dịch là giai đoạn có thể phân biệt được, giai đoạn này lấy đầu vào từ giai đoạn trước, xử lý và tạo ra đầu ra có thể được sử dụng làm đầu vào cho giai đoạn tiếp theo. Một băng chuyền có thể có nhiều hơn một giai đoạn.
Các giai đoạn của trình biên dịch
Quá trình biên dịch là một chuỗi các giai đoạn khác nhau. Mỗi giai đoạn lấy đầu vào từ giai đoạn trước của nó, có đại diện riêng của chương trình nguồn và cung cấp đầu ra của nó cho giai đoạn tiếp theo của trình biên dịch.
Chúng ta cùng tìm hiểu các giai đoạn của một trình biên dịch ngay thôi.
Phân tích từ vựng (Lexical Analysis)
Giai đoạn đầu tiên của máy quét hoạt động như một máy quét văn bản. Giai đoạn này quét mã nguồn dưới dạng một luồng ký tự và chuyển đổi nó thành các từ vựng có ý nghĩa.
Trình phân tích từ vựng biểu thị các từ vựng này ở dạng mã thông báo (token) như sau:
<token-name, attribute-value>Phân tích cú pháp (Syntax Analysis hoặc Parsing)
Giai đoạn tiếp theo được gọi là phân tích cú pháp. Nó lấy mã thông báo được tạo ra bằng phân tích từ vựng làm đầu vào và tạo cây phân tích cú pháp (hoặc cây cú pháp).
Trong giai đoạn này, các sắp xếp mã thông báo được kiểm tra dựa trên ngữ pháp mã nguồn, tức là trình phân tích cú pháp sẽ kiểm tra xem biểu thức được tạo bởi các mã thông báo có đúng về mặt cú pháp hay không.
Phân tích ngữ nghĩa (Semantic Analysis)
Phân tích ngữ nghĩa kiểm tra xem cây phân tích cú pháp được xây dựng có tuân theo các quy tắc của ngôn ngữ hay không.
Ví dụ: gán giá trị giữa các kiểu dữ liệu tương thích và cộng chuỗi vào một số nguyên.
Ngoài ra, trình phân tích ngữ nghĩa theo dõi các định danh, các kiểu dữ liệu và biểu thức của chúng; liệu các định danh có được khai báo trước khi sử dụng hay không, v.v …
Bộ phân tích ngữ nghĩa tạo ra một cây cú pháp có chú thích như một đầu ra.
Tạo mã trung gian (Intermediate Code Generation)
Sau khi phân tích ngữ nghĩa, trình biên dịch tạo ra một mã trung gian của mã nguồn cho máy đích.
Nó đại diện cho một chương trình cho một số máy trừu tượng. Nó nằm giữa ngôn ngữ cấp cao và ngôn ngữ máy. Mã trung gian này nên được tạo theo cách giúp nó dễ dàng được dịch sang mã máy đích hơn.
Tối ưu hóa mã (Code Optimization)
Giai đoạn tiếp theo là thực hiện tối ưu hóa mã của mã trung gian.
Tối ưu hóa có thể được coi là việc loại bỏ các dòng mã không cần thiết và sắp xếp chuỗi các câu lệnh để tăng tốc độ thực thi chương trình mà không lãng phí tài nguyên (CPU, bộ nhớ).
Tạo mã (Code Generation)
Trong giai đoạn này, trình tạo mã lấy biểu diễn được tối ưu hóa của mã trung gian và ánh xạ nó sang ngôn ngữ máy đích.
Bộ tạo mã dịch mã trung gian thành một chuỗi mã máy định vị lại (nói chung). Chuỗi lệnh của mã máy thực hiện nhiệm vụ như mã trung gian sẽ làm.
Bảng ký hiệu (Symbol Table)
Nó là một cấu trúc dữ liệu được duy trì trong suốt tất cả các giai đoạn của một trình biên dịch. Tất cả tên của mã định danh cùng với kiểu dữ liệu của chúng được lưu trữ ở đây.
Bảng ký hiệu giúp trình biên dịch dễ dàng tìm kiếm nhanh bản ghi định danh và truy xuất nó. Bảng ký hiệu cũng được sử dụng để quản lý phạm vi.
Những điều cần nhớ về trình biên dịch
- Trình biên dịch dịch mã được viết bằng ngôn ngữ này sang một số ngôn ngữ khác mà không làm thay đổi ý nghĩa của chương trình.
- Bộ tiền xử lý (Preprocessor) là một công cụ tạo ra đầu vào cho trình biên dịch.
- Trình thông dịch (Interpreter) cũng giống như một trình biên dịch, dịch ngôn ngữ cấp cao sang ngôn ngữ máy cấp thấp. Sự khác biệt nằm ở cách chúng đọc mã nguồn hoặc đầu vào.
- Trình hợp dịch (Assembler) dịch các chương trình hợp ngữ thành mã máy.
- Trình liên kết (Linker) là một chương trình máy tính liên kết và hợp nhất các tệp đối tượng khác nhau với nhau để tạo thành một tệp thực thi.
- Trình tải (Loader) là một phần của hệ điều hành và chịu trách nhiệm tải các tập tin thực thi vào bộ nhớ và thực thi chúng.
- Trình biên dịch có thể được chia thành hai giai đoạn dựa trên cách chúng biên dịch: giai đoạn phân tích, giai đoạn tổng hợp.
Ở hướng dẫn tiếp theo, bạn sẽ tìm hiểu về các giai đoạn phân tích từ vựng (Lexical Analysis) của trình biên dịch:
Comdy