Máy ảo kiểu Stack
Ta đã biết rằng kết quả của giai đoạn phân tích là một biểu diễn trung gian của chương trình nguồn mà giai đoạn tổng hợp sử dụng nó để phát sinh mã đích. Một dạng phổ biến của biểu diễn trung gian là mã của một máy ảo kiểu Stack (abstact ...
Ta đã biết rằng kết quả của giai đoạn phân tích là một biểu diễn trung gian của chương trình nguồn mà giai đoạn tổng hợp sử dụng nó để phát sinh mã đích. Một dạng phổ biến của biểu diễn trung gian là mã của một máy ảo kiểu Stack (abstact stack machine - ASM).
Trong phần này, chúng ta sẽ trình bày khái quát về một máy ảo kiểu Stack và chỉ ra cách sinh mã chương trình cho nó. Máy ảo này bao gồm 3 thành phần:
1. Vùng nhớ chỉ thị (instructions): là nơi chứa các chỉ thị. Các chỉ thị này rất hạn chế và được chia thành 3 nhóm chính: nhóm chỉ thị số học trên số nguyên, nhóm chỉ thị thao tác trên Stack và nhóm chỉ thị điều khiển trình tự.
2. Vùng Stack: là nơi thực hiện các chỉ thị trên các phép toán số học.
3. Vùng nhớ dữ liệu (data): là nơi lưu trữ riêng các dữ liệu.
Hình sau đây minh họa cho nguyên tắc thực hiện của dạng máy này, con trỏ pc (program counter) chỉ ra chỉ thị đang chờ để thực hiện tiếp theo. Các giá trị dùng trong quá trình tính toán được nạp vào đỉnh Stack. Sau khi tính toán xong, kết quả được lưu tại đỉnh Stack.
Ví dụ 2.15: Biểu thức (5 + b) * c với b = 11, c = 7 sẽ được thực hiện trên Stack dưới dạng biểu thức hậu tố 5 b + c *.
Các chỉ thị số học
Máy ảo phải cài đặt mỗi toán tử bằng một ngôn ngữ trung gian Khi gặp các chỉ thị số học đơn giản, máy sẽ thực hiện phép toán tương ứng với hai giá trị trên đỉnh Stack, kết quả cũng được lưu vào đỉnh STACK. Một phép toán phức tạp hơn có thể cần phải được cài đặt như một loạt chỉ thị của máy.
Mã chương trình máy ảo cho một biểu thức số học sẽ mô phỏng hành động ước lượng dạng hậu tố cho biểu thức đó bằng cách sử dụng Stack. Việc ước lượng được tiến hành bằng cách xử lý chuỗi hậu tố từ trái sang phải, đẩy mỗi toán hạng vào Stack khi gặp nó. Với một toán tử k - ngôi, đối số cận trái của nó nằm ở (k -1) vị trí bên dưới đỉnh Stack và đối số cận phải nằm tại đỉnh. Hành động ước lượng áp dụng toán tử cho k giá trị trên đỉnh của Stack, lấy toán hạng ra và đặt kết quả trở lại vào Stack.
Trong ngôn ngữ trung gian, mọi giá trị đều là số nguyên; số 0 tương ứng với false và các số khác 0 tương ứng với true. Toán tử logic and và or cần phải có cả 2 đối số.
Chỉ thị L- value và R-value
Ta cần phân biệt ý nghĩa của các danh biểu ở vế trái và vế phải của một phép gán. Trong mỗi phép gán sau :
L-value l : Ðẩy nội dung ở vị trí dữ liệu l vào Stack
R-value l : Đẩy địa chỉ của vị trí dữ liệu l vào Stack
Các chỉ thị thao tác trên STACK
Bên cạnh những chỉ thị cho thao tác đẩy một hằng số nguyên vào Stack và lấy một giá trị ra khỏi đỉnh Stack, còn có một số chỉ thị truy xuất vùng nhớ dữ liệu như sau:
push v : Ðẩy giá trị v vào đỉnh Stack (top := top +1)
pop : Lấy giá trị ra khỏi đỉnh Stack (top := top +1)
:= : R-value trên đỉnh Stack được lưu vào L-value ngay bên dưới nó và lấy cả hai ra khỏi Stack (top := top -2)
copy : Sao chép giá trị tại đỉnh Stack (top := top +1)
Dịch các biểu thức
Ðoạn mã chương trình dùng để ước lượng một biểu thức trên một máy ảo kiểu Stack có liên quan mật thiết với ký pháp hậu tố cho biểu thức đó.
Ví dụ 2.16: Dịch phép gán sau thành mã máy ảo kiểu Stack:
day := (1461 * y) div 4 + (153 * m + 2) div 5 + d
Ký pháp hậu tố của biểu thức như sau :
day 1461 y * 4 div 153 m * 2 + 5 div + d + :=
Ðoạn mã máy có dạng :
L-value day push 2
push 1461 +
R-value y push 5
* div
push 4 +
div R-value d
push 153 +
R- value m :=
*
Các chỉ thị điều khiển trình tự
thực hiện các chỉ thị theo đúng thứ tự liệt kê trừ khi được yêu cầu thực hiện khác đi bằng các câu lệnh nhảy có điều kiện hoặc không điều kiện. Có một số các tùy chọn dùng để mô tả các đích nhảy :
1. Toán hạng làm chỉ thị cho biết vị trí đích.
2. Toán hạng làm chỉ thị mô tả khoảng cách tương đối cần nhảy theo chiều tới hoặc lui.
3. Ðích nhảy đến được mô tả bằng các ký hiệu tượng trưng gọi là các nhãn.
Một số chỉ thị điều khiển trình tự cho máy là :
lable l : Gán đích của các lệnh nhảy đến là l, không có tác dụng khác.
goto l : Chỉ thị tiếp theo được lấy từ câu lệnh có lable l .
gofalse l : Lấy giá trị trên đỉnh Stack ra, nếu giá trị là 0 thì nhảy đến l, ngược lại, thực hiện lệnh kế tiếp.
gotrue l : Lấy giá trị trên đỉnh Stack ra, nếu giá trị khác 0 thì nhảy đến l, ngược lại, thực hiện lệnh kế tiếp.
halt : Ngưng thực hiện chương trình.
Dịch các câu lệnh
Sơ đồ phác thảo đoạn mã máy ảo cho một số lệnh cấu trúc được chỉ ra trong hình sau:
IF expr THEN stmt WHILE expr DO stmt
Xét sơ đồ đoạn mã cho câu lệnh If . Giả sử rằng newlable là một thủ tục trả về một nhãn mới cho mỗi lần gọi. Trong hành vi ngữ nghĩa sau đây, nhãn được trả về bởi một lời gọi đến newlabel được ghi lại bằng cách dùng một biến cục bộ out :
stmt → if expr then stmt1 { out := newlable;
stmt.t := expr.t ||
‘ gofalse ’ out ||
stmt1.t ||
‘ lable ’ out }
Thay vì in ra các câu lệnh, ta có thể sử dụng thủ tục emit để che dấu các chi tiết in. Chẳng hạn như emit phải xem xét xem mỗi chỉ thị máy ảo có cần nằm trên một hàng riêng biệt hay không. Sử dụng thủ tục emit, ta có thể viết lại như sau :
stmt → if
expr { out := newlable; emit (‘ gofalse ’, out); }
then
stmt1 { emit (‘ lable ’, out); }
Khi một hành vi ngữ nghĩa xuất hiện bên trong một luật sinh, ta xét các phần tử ở vế phải của luật sinh theo thứ tự từ trái sang phải. Ðoạn mã (ngôn ngữ giả) cho phép dịch phép gán và câu lệnh điều kiện If tương ứng như sau :
procedure stmt;
var test, out: integer; /* dùng cho các nhãn */
begin
if lookahead = id then
begin
emit (‘lvalue’, tokenval); match (id); match (‘:=‘); expr;
end
else if lookahead = ‘if’ then
begin
match (‘if’); expr; out := newlable;
emit (‘gofalse’, out); match(‘then’); stmt;
emit (‘lable’, out);
end
/* đoạn mã cho các lệnh còn lại */
else error;
end;