Thiết kế trình biên dịch: Tạo mã trung gian

Trung Nguyen
06/04/2021
7 min read

Nội dung chính của bài viết

Ở hướng dẫn trước, bạn sẽ tìm hiểu chi tiết về phân tích ngữ nghĩa và trình phân tích ngữ nghĩa trong thiết kế trình biên dịch. Nếu bỏ lỡ thì bạn có thể xem ở đây:

Mã nguồn có thể được dịch trực tiếp sang mã máy đích của nó, vậy tại sao chúng ta lại cần dịch mã nguồn thành mã trung gian và sau đó nó được dịch sang mã máy đích của nó? Chúng ta hãy xem lý do tại sao chúng ta cần mã trung gian.

Thiết kế trình biên dịch: Tạo mã trung gian

Nếu một trình biên dịch dịch ngôn ngữ nguồn sang ngôn ngữ máy đích của nó mà không có tùy chọn tạo mã trung gian, thì với mỗi máy mới, cần có một trình biên dịch gốc đầy đủ.
Mã trung gian loại bỏ sự cần thiết của một trình biên dịch đầy đủ mới cho mọi máy duy nhất bằng cách giữ nguyên phần phân tích cho tất cả các trình biên dịch.
Phần thứ hai của trình biên dịch, tổng hợp, được thay đổi theo máy đích.
Việc áp dụng các sửa đổi mã nguồn để cải thiện hiệu suất mã trở nên dễ dàng hơn bằng cách áp dụng các kỹ thuật tối ưu hóa mã trên mã trung gian.

Biểu diễn trung gian

Mã trung gian có thể được biểu diễn theo nhiều cách khác nhau và chúng có những lợi ích riêng.

IR cấp cao - Biểu diễn mã trung gian cấp cao rất gần với chính ngôn ngữ nguồn. Chúng có thể dễ dàng được tạo từ mã nguồn và chúng ta có thể dễ dàng áp dụng các sửa đổi mã để nâng cao hiệu suất. Nhưng để tối ưu hóa máy mục tiêu, nó ít được ưu tiên hơn.
IR cấp thấp - Cái này gần với máy mục tiêu, điều này làm cho nó phù hợp cho việc cấp phát thanh ghi và bộ nhớ, lựa chọn tập lệnh, v.v. Nó tốt cho việc tối ưu hóa phụ thuộc vào máy.

Mã trung gian có thể là ngôn ngữ cụ thể (ví dụ: Byte Code cho Java, MSIL cho .NET) hoặc ngôn ngữ độc lập (mã ba địa chỉ).

Mã ba địa chỉ (Three-Address Code)

Trình tạo mã trung gian nhận đầu vào từ trình phân tích ngữ nghĩa dưới dạng một cây cú pháp có chú thích.

Sau đó, cây cú pháp đó có thể được chuyển đổi thành một biểu diễn tuyến tính, ví dụ: ký hiệu hậu tố.

Mã trung gian có xu hướng là mã độc lập với máy. Do đó, bộ tạo mã giả định có số lượng bộ nhớ lưu trữ (thanh ghi) không giới hạn để tạo mã.

Ví dụ:

a = b + c * d;

Bộ tạo mã trung gian sẽ cố gắng chia biểu thức này thành các biểu thức con và sau đó tạo mã tương ứng.

r1 = c * d;
r2 = b + r1;
a = r2

r được sử dụng như các thanh ghi trong chương trình đích.

Mã ba địa chỉ có nhiều nhất ba vị trí địa chỉ để tính toán biểu thức. Mã ba địa chỉ có thể được biểu diễn dưới hai dạng: quadruples và triples.

Quadruples

Mỗi lệnh trong định dạng quadruples được chia thành bốn trường: toán tử, tham số 1, tham số 2 và kết quả. Ví dụ trên được trình bày dưới đây ở định dạng quadruples:

Toán tử	Tham số 1	Tham số 2	Kết quả
*	c	d	r1
+	b	r1	r2
+	r2	r1	r3
=	r3		a

Triples

Mỗi lệnh trong định dạng triples có ba trường: toán tử, tham số 1 và tham số 2. Kết quả của các biểu thức con tương ứng được biểu thị bằng vị trí của biểu thức. Các triples thể hiện sự tương tự với DAG và cây cú pháp. Chúng tương đương với DAG trong khi biểu diễn các biểu thức.

Toán tử	Tham số 1	Tham số 2
*	c	d
+	b	(0)
+	(1)	(0)
=	(2)

Triples phải đối mặt với vấn đề về tính bất động của mã trong khi tối ưu hóa, vì các kết quả là theo vị trí và việc thay đổi thứ tự hoặc vị trí của một biểu thức có thể gây ra vấn đề.

Triples gián tiếp

Biểu diễn này là một sự cải tiến so với biểu diễn triples. Nó sử dụng con trỏ thay vì vị trí để lưu trữ kết quả. Điều này cho phép các trình tối ưu hóa tự do định vị lại biểu thức con để tạo ra một mã được tối ưu hóa.

Khai báo

Một biến hoặc thủ tục phải được khai báo trước khi nó có thể được sử dụng. Khai báo liên quan đến việc phân bổ không gian trong bộ nhớ và nhập kiểu và tên trong bảng ký hiệu.

Một chương trình có thể được viết code và thiết kế để lưu ý đến cấu trúc máy đích, nhưng không phải lúc nào cũng có thể chuyển đổi chính xác mã nguồn sang ngôn ngữ đích của nó.

Lấy toàn bộ chương trình làm tập hợp các thủ tục và thủ tục con, có thể khai báo tất cả các tên cục bộ cho thủ tục.

Việc cấp phát bộ nhớ được thực hiện liên tiếp và các tên được cấp phát cho bộ nhớ theo trình tự mà chúng được khai báo trong chương trình. Chúng tôi sử dụng biến offset và đặt nó thành 0 {offset = 0} biểu thị địa chỉ cơ sở.

Ngôn ngữ lập trình nguồn và kiến trúc máy đích có thể khác nhau về cách lưu trữ tên, do đó, địa chỉ tương đối được sử dụng.

Trong khi tên đầu tiên được cấp phát bộ nhớ bắt đầu từ vị trí bộ nhớ 0 {offset = 0}, tên tiếp theo được khai báo sau, sẽ được cấp phát bộ nhớ bên cạnh tên đầu tiên.

Ví dụ:

Chúng ta lấy ví dụ về ngôn ngữ lập trình C trong đó một biến kiểu int được gán 2 byte bộ nhớ và một biến kiểu float được gán 4 byte bộ nhớ.

int a;
float b;

Allocation process:
{offset = 0}

   int a;
   id.type = int
   id.width = 2

offset = offset + id.width 
{offset = 2}

   float b;
   id.type = float
   id.width = 4
   
offset = offset + id.width 
{offset = 6}

Để nhập chi tiết này vào bảng ký hiệu, có thể sử dụng một thủ tục enter. Phương thức này có thể có cấu trúc sau:

enter(name, type, offset)

Thủ tục này sẽ tạo một mục nhập trong bảng ký hiệu, đối với tên biến, có kiểu của nó được đặt thành kiểu và offset địa chỉ tương đối trong vùng dữ liệu của nó.

Trong hướng dẫn tiếp theo, bạn sẽ tìm hiểu tạo mã và trình tạo mã trong thiết kế trình biên dịch.