Mô tả các bước dịch (1) Mã nguồn (dãy các kí tự) If (a == 0) min = a; Phân tích từ vựng Dãy các từ tố (token) If ( Id:a == 0 ) Id:min = Id:a ; Cây cú pháp if Phân tích cú pháp == = ; a 0 min a Cây cú pháp điều khiển Phân tích ngữ nghĩa if boolean== = int ; int int int int a 0 min a goupee.com lvalue fb.com/groups/goupee
Mô tả các bước dịch (2) if boolean int Sinh mã trung gian == = ; int int int int a 0 min a lvalue SEQ(CJUMP(TEMP(a) == 0, L1, L2), Sinh mã assembly LABEL(L1), TEMP(min) = TEMP(a) LABEL(L2)) cmp rb, 0 Tối ưu mã jnz L2 cmp ecx, 0 L1: mov ra, rb cmovz edx,ecx L2: goupee.com fb.com/groups/goupee
Ngôn ngữ trung gian • Là ngôn ngữ cho một loại máy trừu tượng • Cho phép sinh mã không phụ thuộc vào máy đích • Cho phép tối ưu mã trước khi sinh mã máy thật sự Pentium Cây cú pháp Java bytecode + thông tin điều khiển AMD goupee.com fb.com/groups/goupee
Ngôn ngữ trung gian • Dễ sinh ra từ cây cú pháp Cây cú pháp (>40 nút) • Dễ sinh mã máy Mã trung gian (13 nút) • Số lượng lệnh nhỏ, gọn Pentium (>200 lệnh) – Dễ tối ưu mã – Dễ chuyển sang loại mã máy khác goupee.com fb.com/groups/goupee
Ngôn ngữ trung gian • Một dạng thể hiện của chương trình nằm giữa cây cú pháp điều khiển và mã máy • Sử dụng – Lệnh nhảy – Thanh ghi – Vị trí trên bộ nhớ Tối ưu mã Pentium Cây cú pháp Mã trung + Java bytecod gian thông tin điều khiển AMD goupee.com fb.com/groups/goupee
Một ngôn ngữ trung gian • IR (Intermediate Representation) là một cây thể hiện các lệnh của một loại máy trừu tượng • Nút lệnh không trả lại giá trị, được thực hiện theo thứ tự nhất định – Ví dụ: MOVE, SEQ, CJUMP • Nút biểu thức trả lại giá trị, các nút con có thể thực hiện theo thứ tự bất kì – Ví dụ: ADD, SUB – Cho phép tối ưu mã goupee.com fb.com/groups/goupee
Mô tả các nút biểu thức của IR • CONST(i): hằng số nguyên i • TEMP(t): thanh ghi t, máy trừu tượng có vô hạn thanh ghi. • OP(e1, e2): các phép toán – Số học: ADD, SUB, MUL, DIV, MOD – Logic: AND, OR, XOR, LSHIFT, RSHIFT – So sánh: EQ, NEQ, LT, GT, LEQ, GEQ • MEM(e): giá trị bộ nhớ ở vị trí e • CALL(f, a0, a1, …): giá trị của hàm f với các tham số a0, a1, … • NAME(n): địa chỉ của lệnh hoặc dữ liệu có tên là n • ESEQ(s, e): giá trị của e sau khi lệnh s được thực hiện goupee.com fb.com/groups/goupee
CONST • Nút CONSTđại diện cho hằng số CONST(i) • Giá trị của nút là i goupee.com fb.com/groups/goupee
TEMP • Nút TEMP đại diện cho một thanh ghi trong số vô hạn các thanh ghi của máy trừu tượng TEMP(t) • Các biến cục bộ và các biến tạm • Để dễ viết, ký hiệu FP = TEMP(FP) là địa chỉ bắt đầu bộ nhớ của hàm • Giá trị của nút là giá trị của thanh ghi tại thời điểm tính toán goupee.com fb.com/groups/goupee
Toán tử • Máy trừu tượng có nhiều phép toán OP(e1, e2) OP e1 e2 • Tính giá trị của e1 và e2, sau đó áp dụng phép toán với các giá trị này • e1 và e2 phải là hai nút có giá trị • Có thể tính giá trị e1 và e2 theo thứ tự bất kì goupee.com fb.com/groups/goupee
MEM • Nút MEM đại diện cho một vị trí trong bộ nhớ • Giá trị của nút là giá trị tại vị trí e trong bộ nhớ MEM(e) MEM e goupee.com fb.com/groups/goupee
CALL • Nút CALL đại diện cho một lời gọi hàm CALL(e , e , e ,…) CALL f 0 1 … Địa chỉ của hàm Tham số e eee f 0 1 2 • Không định nghĩa cách cài đặt việc truyền tham số, quản lý ngăn xếp • Giá trị của nút là giá trị của hàm goupee.com fb.com/groups/goupee
NAME • Nút NAME đại diện cho địa chỉ của một tên trên bộ nhớ • VD: địa chỉ của một nhãn nhảy NAME(n) goupee.com fb.com/groups/goupee
ESEQ • Nút ESEQ tính toán giá trị của biểu thức e sau khi thực hiện lệnh s ESEQ(s, e) ESEQ s e goupee.com fb.com/groups/goupee
Mô tả các nút lệnh của IR • MOVE(dest, e): chuyển giá trị của e vào dest • EXP(e): tính toán giá trị của e, không cần lưu lại kết quả • SEQ(s1, s2, … sn): thực hiện các lệnh theo thứ tự • JUMP(e): nhảy đến địa chỉ e • CJUMP(e, l1, l2): nhảy đến l1 hoặc l2 tuỳ thuộc vào giá trị của e là true hoặc false • LABEL(n): tạo ra nhãn có tên n goupee.com fb.com/groups/goupee
Ví dụ n = 0; while (n < 10) { SEQ( n = n + 1; MOVE(TEMP(n), CONST(0)), LABEL(HEAD), } CJUMP(LT(TEMP(n), CONST(10)), NAME(BODY), NAME(END)), LABEL(BODY), MOVE(TEMP(n), ADD(TEMP(n), CONST(1))), JUMP(NAME(HEAD)), LABEL(END) ) SEQ MOVE LABEL(HEAD)CJUMP LABEL(BODY)MOVEJUMP LABEL(END) TEMP(n) CONST(0) LT NAME(BODY)NAME(END) NAME(HEAD) TEMP(n) CONST(10) TEMP(n) ADD TEMP(n) CONST(1) goupee.com fb.com/groups/goupee
Cấu trúc của IR • Gốc của cây là một nút lệnh • Các nút biểu thức nằm dưới nút lệnh • Chỉ có nút biểu thức ESEQ có nút lệnh nằm dưới • Có thể duyệt cây IR để chạy chương trình goupee.com fb.com/groups/goupee
Sinh cây IR (mã trung gian) • Kỹ thuật: phương pháp dịch sử dụng cú pháp điều khiển (giống kiểm tra kiểu) • Chuyển cây cú pháp điều khiển thành cây IR • Mỗi cây con của cây cú pháp được chuyển thành một cây con dạng IR có cùng giá trị goupee.com fb.com/groups/goupee
Sinh cây IR • Giống kiểm tra kiểu: thêm một phương thức vào nút tương ứng trong cây cú pháp abstract class ASTNode { IRNode translate(SymTab A) { … } } • Cài đặt kiểu đệ quy • Vấn đề: giống như kiểm tra kiểu, cần mô tả chính xác cách viết hàm translate() goupee.com fb.com/groups/goupee
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!