Phần mềm biên dịch

Phần mềm biên dịch (tiếng Anh: compiler) hay trình biên dịch là một chương trình máy tính thực hiện việc dịch một chuỗi lệnh viết bằng một ngôn ngữ lập trình (gọi là ngôn ngữ nguồn hay mã nguồn), biến chúng thành một chương trình tương đương nhưng ở dạng ngôn ngữ máy mới (gọi là ngôn ngữ đích) thường là ngôn ngữ ở cấp độ thấp hơn, như ngôn ngữ máy. Chương trình mới dịch này được gọi là mã đối tượng.

Giới thiệu

Hầu hết các phần mềm biên dịch sẽ chuyển đổi mã nguồn viết bằng một ngôn ngữ cấp cao thành mã đối tượng hoặc ngôn ngữ máy có thể được thực thi trực tiếp bởi một máy tính hoặc một máy ảo. Tuy nhiên, quá trình chuyển đổi từ ngôn ngữ cấp thấp sang ngôn ngữ cấp cao cũng có thể xảy ra; quá trình này thường được hiểu như là một bộ biên dịch ngược nếu nó có thể tái tạo lại một chương trình trong ngôn ngữ cấp cao. Cũng có các phần mềm biên dịch chuyển đổi từ ngôn ngữ cao này sang ngôn ngữ cao khác, hoặc là chuyển đổi sang một ngôn ngữ khác cần thiết cho việc xử lý tiếp theo; những phần mềm biên dịch như vậy được gọi là bộ biên dịch đa tầng.

Các loại phần mềm biên dịch khi biên dịch ra mã đối tượng cơ bản bao gồm cả mã máy mở rộng thêm thông tin về vị trí của các điểm vào và các cuộc gọi bên ngoài (những hàm không có sẵn trong nội bộ của chúng). Một bộ sưu tập các tập tin đối tượng, dù không phải từ cùng một phần mềm biên dịch, vẫn có thể được liên kết với nhau để tạo thành các chương trình hoàn chỉnh cho người dùng. Tất nhiên, để làm điều này các tập tin đối tượng phải tuân thủ một định dạng chung. Ví dụ về loại tập tin này là các tập tin có đuôi .obj có thể dùng chung giữa ASM, C/C++, Fortran,... hoặc các tập tin .DLL trong các nền tảng Windows có thể dùng chung cho nhiều ngôn ngữ khác nhau.

Lịch sử

Nhiều phần mềm biên dịch thử nghiệm đã được phát triển từ những năm 1950. Tuy nhiên, chỉ có nhóm làm việc với FORTRAN dưới sự dẫn dắt của John Backus tại IBM thành công trong việc giới thiệu trình biên dịch hoàn chỉnh đầu tiên vào năm 1957. COBOL, một ngôn ngữ sớm, cũng đã có trình biên dịch cho nhiều kiến trúc khác nhau vào những năm 1960.

Ý kiến về quá trình biên dịch đã thu hút sự quan tâm của nhiều người và hầu hết các nguyên lý thiết kế của trình biên dịch đã được phát triển từ những năm 1960.

Một phần mềm biên dịch tự nó là một chương trình máy tính được viết bằng một vài ngôn ngữ thực thi. Ban đầu, các phần mềm biên dịch thường được viết bằng ngôn ngữ ASM (Assembler).

Trình biên dịch tự phát là một loại trình biên dịch có khả năng tự biên dịch và sinh ra từ mã nguồn trong ngôn ngữ cấp cao bằng chính nó. Trình biên dịch tự phát đầu tiên đã được áp dụng cho Lisp bởi Hart và Levin tại MIT vào năm 1962.

Việc sử dụng ngôn ngữ cấp cao để phát triển các trình biên dịch bắt đầu từ đầu những năm 1970 khi các trình biên dịch Pascal và C được tạo ra từ ngôn ngữ của chúng. Xây dựng một trình biên dịch tự phát là vấn đề về quy trình khởi động. Điều này có nghĩa là phiên bản đầu tiên của trình biên dịch cho một ngôn ngữ phải được biên dịch từ một trình biên dịch viết bằng một ngôn ngữ khác hoặc, theo cách mà Hart và Levin làm với Lisp, biên dịch bằng cách thực thi trình biên dịch này trong một phần mềm thông dịch.

Trong suốt thập niên 1980 và 1990, nhiều trình biên dịch miễn phí và các công cụ phát triển trình biên dịch đã được tạo ra cho mọi loại ngôn ngữ. Cả hai đều là một phần của dự án GNU và các dự án nguồn mở khác. Một số trong số này được đánh giá cao về chất lượng và là nguồn cảm hứng lớn cho những ai quan tâm đến các nguyên lý của trình biên dịch hiện đại.

Các loại trình biên dịch

Trình biên dịch cùng nền tảng và trình biên dịch chéo nền tảng

Một trình biên dịch có thể tạo ra mã máy được thiết kế để chạy trên cùng một kiểu máy tính và hệ điều hành nhất định được gọi là trình biên dịch cùng nền tảng.

Một loại khác, trình biên dịch có thể tạo ra mã máy dành cho các kiểu máy tính và hệ điều hành khác nhau. Trường hợp này được gọi là trình biên dịch chéo nền tảng. Các trình biên dịch chéo nền tảng rất hữu ích khi phát triển trên các nền tảng phần cứng mới lần đầu tiên. Chúng cũng cần thiết khi phát triển phần mềm cho các hệ điều hành nhúng, nơi không đủ bộ nhớ lưu trữ để cài đặt trình biên dịch.

Số lượng bước biên dịch

Tất cả các trình biên dịch có thể hoạt động theo một bước hoặc nhiều bước

• Trình biên dịch một bước: Với loại này, quá trình biên dịch hoàn tất trong một bước và do đó rất nhanh.

Ví dụ về các trình biên dịch trước đây cho Pascal hoặc Borland C là các trình biên dịch một bước.

• Các trình biên dịch cần nhiều hơn một bước để hoàn tất được gọi là trình biên dịch nhiều bước. Các loại trình biên dịch nhiều bước bao gồm:

• Trình biên dịch từ nguồn sang nguồn là loại trình biên dịch nhận đầu vào là mã nguồn trong một ngôn ngữ cấp cao và biên dịch nó thành một ngôn ngữ cấp cao khác.

Ví dụ: Một trình biên dịch tự động song song thường sử dụng chương trình trong ngôn ngữ cấp cao làm đầu vào và biên dịch nó thành mã nguồn song song cùng với các chỉ thị như OpenMP hay cấu trúc ngôn ngữ như các lệnh DOALL trong Fortran.

• Trình biên dịch phân đoạn biên dịch thành mã ASM của một máy lý thuyết như WAM của Prolog. Loại máy Prolog này còn được gọi là máy trừu tượng Warren.

Ví dụ: Các trình biên dịch bytecode cho Java, Python và nhiều loại trình biên dịch khác là các loại trình biên dịch thuộc kiểu này.

• Trình biên dịch động, còn gọi là trình biên dịch JIT, chuyển đổi các ứng dụng thành bytecode, sau đó bytecode được dịch thành mã máy của ngôn ngữ máy cụ thể trước khi thực thi.

Ví dụ: Trình biên dịch JIT được sử dụng bởi Smalltalk, Java, và cũng là phần của Ngôn ngữ trung gian chung của Microsoft .NET.

Các tính chất khác

Đặc biệt, một trình biên dịch có thể có thêm các chức năng sau đây:

• Trình biên dịch mã liên kết là loại trình biên dịch cho phép thay thế các dòng ký tự trong nguồn bằng các khối mã nhị phân đã có sẵn. Các khối mã này có thể có nhiều cấp độ khác nhau.

Ví dụ: Các trình biên dịch trên hầu hết các kiến trúc của FORTH. Thậm chí, một số trình biên dịch FORTH có thể biên dịch các chương trình mà không cần đến hệ điều hành.

• Trình biên dịch tăng tiến. Trong trình biên dịch tăng tiến, các hàm riêng lẻ có thể được dịch trong thời gian chạy (runtime), nơi các hàm này cũng bao gồm các chức năng thông dịch.

Ví dụ: Kiến trúc dịch tăng tiến đã xuất hiện từ năm 1962 và vẫn được sử dụng trong các hệ thống Lisp ngày nay.

• Trình biên dịch đa chức năng là loại trình biên dịch có khả năng được điều chỉnh để tạo ra mã cho các kiến trúc CPU khác nhau một cách tương đối dễ dàng. Mã đối tượng được tạo ra bởi các trình biên dịch này thường có chất lượng thấp hơn so với các mã được tạo ra từ các trình biên dịch chỉ chuyên dùng cho một loại CPU cụ thể. Trình biên dịch đa chức năng thường cũng là trình biên dịch chéo bản.

Ví dụ: GCC là một loại trình biên dịch đa chức năng miễn phí rất phổ biến.

• Trình biên dịch đồng thời là loại trình biên dịch có khả năng chuyển đổi một chương trình được viết theo kiểu liên tục sang một dạng thuận tiện hơn trên kiến trúc của máy tính đồng thời.

So sánh với phần mềm thông dịch

Nhiều người vẫn phân loại các ngôn ngữ lập trình cấp cao thành các ngôn ngữ biên dịch và các ngôn ngữ thông dịch. Tuy nhiên, hiếm khi một ngôn ngữ yêu cầu phải là loại biên dịch hay thông dịch. Các trình biên dịch và các phần mềm thông dịch là các thực thể thực hiện ngôn ngữ chứ không phải bản thân ngôn ngữ đó.

Phân loại này chỉ phản ánh thực trạng phổ biến về sự thực hiện của các ngôn ngữ như BASIC được nhiều người cho là ngôn ngữ thông dịch và C lại được xem là ngôn ngữ biên dịch. Tuy nhiên, thực tế vẫn tồn tại các trình biên dịch cho BASIC và các phần mềm thông dịch cho C.

Thiết kế của trình biên dịch

Trong quá khứ, các trình biên dịch thường chia quá trình biên dịch thành nhiều bước để tiết kiệm bộ nhớ. Mỗi bước trong quá trình biên dịch, thông qua mã nguồn của chương trình, là một phần thực thi dẫn đến việc tạo ra một bộ dữ liệu nội tại (ví dụ như bảng ký hiệu và các dữ liệu hướng dẫn cho việc dịch). Sau khi hoàn tất mỗi bước, trình biên dịch có thể loại bỏ các dữ liệu nội tại không cần thiết để tiết kiệm bộ nhớ. Phương pháp chia quá trình biên dịch thành nhiều bước là một kỹ thuật phổ biến vào thời điểm đó, nhằm giải quyết vấn đề về bộ nhớ khi máy tính còn có khối lượng nhỏ so với mã nguồn và dữ liệu.

Nhiều trình biên dịch hiện đại áp dụng một thiết kế hai mặt. Mặt ngoài chuyển đổi ngôn ngữ nguồn thành biểu diễn trung gian. Mặt thứ hai là mặt trong, trong đó chủ yếu là làm việc với các biểu diễn nội tại (ví dụ như bảng ký hiệu và các dữ liệu cần thiết khác) để tạo ra kết quả là mã trong ngôn ngữ đích. Cả mặt ngoài và mặt trong đều có thể thực hiện trong nhiều bước và có trường hợp mặt ngoài gọi mặt trong như là một chương trình con để chuyển các biểu diễn trung gian vào đó.

Phương pháp này giảm bớt sự phức tạp. Mặt ngoài thường xử lý các vấn đề liên quan đến ý nghĩa của ngôn ngữ, trong khi mặt trong tập trung vào việc tạo ra các kết quả hiệu quả và chính xác. Ưu điểm của phương pháp này là cho phép sử dụng một mặt trong chung từ nhiều ngôn ngữ khác nhau (nguồn) và ngược lại, cho phép sử dụng các mặt trong khác nhau để phục vụ cho các mục đích khác nhau.

Thường thì các thành phần tối ưu hóa và các thành phần kiểm tra lỗi có thể chia sẻ một thiết kế chung với mặt ngoài và mặt trong nếu chúng được thiết kế để hoạt động trên ngôn ngữ trung gian được chuyển từ mặt ngoài sang mặt trong. Điều này có thể dẫn đến việc nhiều trình biên dịch (kết hợp của mặt ngoài và mặt trong) có thể tái sử dụng một lượng công việc lớn thường được thực hiện trong các thành phần tối ưu hóa và kiểm tra lỗi.

Có nhiều ngôn ngữ, dựa vào thiết kế và các quy tắc để khai báo biến và các đối tượng khác cũng như việc khai báo trước khi sử dụng hay tham chiếu các hàm hay thủ tục, có khả năng được sử dụng trong một bước.

Ví dụ: Pascal là một ngôn ngữ phổ biến với tính năng này. Ngôn ngữ C cũng có thể được sử dụng trong việc biên dịch một bước và đạt được kết quả ngay lập tức.

Mặt ngoài của trình biên dịch

Mặt ngoài của trình biên dịch bao gồm nhiều giai đoạn. Các giai đoạn theo lý thuyết ngôn ngữ là:

1. Phân tích từ vựng - Chia nhỏ các dòng mã nguồn thành các thẻ khóa. Mỗi thẻ khóa đại diện cho một đơn vị không thể chia nhỏ của ngôn ngữ. Ví dụ: một từ khóa, một ký hiệu nhận dạng hay một tên ký hiệu. Các thẻ khoá có thể nhận biết được bằng cách sử dụng máy hữu hạn trạng thái. Pha này còn được gọi là pha đọc từ ngữ hay pha quét.
2. Phân tích cú pháp - Nhận diện cấu trúc cú pháp của mã nguồn. Nó tập trung vào việc nhận diện thứ tự sắp xếp của các thẻ khóa và hiểu cấu trúc phân cấp trong bộ mã.
3. Phân tích ý nghĩa - Sử dụng để nhận biết ý nghĩa của chương trình (mã nguồn) và chuẩn bị cho ra kết quả. Trong pha này, kiểm tra kiểu dữ liệu được hoàn thành và hầu hết các lỗi dịch được phát hiện.
4. Biểu trưng trung gian - Đây là một dạng tương đương của chương trình nguyên thủy đã được chuyển đổi và được gọi là biểu trưng trung gian. Biểu trưng này có thể là một cấu trúc dữ liệu (thường là dạng cây hoặc biểu đồ) hay một ngôn ngữ trung gian khác.

Mặt trong của trình biên dịch

Một trình biên dịch hoàn chỉnh sẽ chuyển giao biểu trưng trung gian được tạo ra bởi mặt ngoài cho mặt trong. Nhiệm vụ của mặt trong là tạo ra chương trình tương đương về chức năng trong ngôn ngữ đích. Việc này bao gồm các giai đoạn:

1. Phân tích biên dịch - Quá trình này thu thập thông tin về chương trình từ biểu trưng trung gian của các tệp nguồn. Phân tích đặc trưng bao gồm việc phân tích việc sử dụng định nghĩa biến, phân tích quan hệ giữa các định nghĩa biến và việc sử dụng chúng trong chuỗi các phép gán giá trị, phân tích sự phụ thuộc dữ liệu, phân tích các nhãn thay thế, và nhiều hơn nữa. Phân tích chính xác là cơ sở cho mọi tối ưu hóa về biên dịch. Đồ thị gọi và đồ thị dòng điều khiển thường được xây dựng trong giai đoạn này.
2. Tối ưu hóa biên dịch - Ngôn ngữ trung gian được chuyển đổi thành các dạng tương đương về chức năng nhưng nhanh hơn hoặc hiệu quả hơn. Những kỹ thuật tối ưu hóa phổ biến bao gồm mở rộng nội tuyến, loại bỏ mã không sử dụng, biến đổi vòng lặp, phân phối thanh ghi và thậm chí tự động hóa song song hóa.
3. Tạo mã - Chuyển đổi ngôn ngữ trung gian sang ngôn ngữ đích, thường là tạo mã cho một hệ thống có cùng ngôn ngữ máy. Việc này bao gồm các quyết định về tài nguyên và lưu trữ như quyết định liệu biến nào nên được đặt vào thanh ghi hay lưu trữ trong bộ nhớ, quyết định việc chọn lựa và đặt lịch thực thi các chỉ thị máy, và quyết định về các chế độ địa chỉ tương ứng (xem thêm thuật toán Sethi-Ullman).