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
Affichage des 20 premières pages. Téléchargez le document pour le voir en entier.
Aucun commentaire pour le moment. Soyez le premier !
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !