Bài giảng Chương trình dịch: Bài giảng 9 - Nguyễn Phương Thái

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PPT | Số trang:27

Thêm vào BST

Báo xấu

67
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Chương trình dịch - bài giảng 9 trình bày về sinh mã. Các nội dung chính được trình bày trong chương này gồm có: Chương trình đích, máy tính ảo, một bộ sinh mã đơn giản, bản diễn tả thông tin thanh ghi và địa chỉ, thuật toán sinh mã,... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Chương trình dịch: Bài giảng 9 - Nguyễn Phương Thái

Nguyễn Phương Thái Bộ môn Khoa học Máy tính http://www.coltech.vnu.vn/~thainp/
Nội dung Chương trình đích Máy tính ảo Sinh mã
Chương trình đích Ngôn ngữ máy tuyệt đối: Có thể được đặt trong một vị trí cố định của bộ nhớ và thực thi ngay được Ưu điểm: Chương trình nhỏ và chạy nhanh. Ngôn ngữ máy định vị: Cho phép biên dịch riêng rẽ các chương trình con, sau đó được liên kết lại với nhau và được tải vào để thực thi nhờ một công cụ tải và liên kết (linking loader). Ưu điểm: Các môđun chương trình độc lập và có dịch độc lập, sau đó kết hợp với nhau thành một chương trình đối tượng hoàn chỉnh nhờ việc liên kết và nạp.
Chương trình đích (tiếp) Mã thông dịch:  Chuỗi hoạt động của nó được biểu diễn không phải bằng các chỉ thị lệnh máy hoạt động trực tiếp mà bằng các câu lệnh thông dịch trừu tượng ở một dạng mã hoá nào đó.  Chương trình biên dịch trong trường hợp này sẽ chuyển chương trình nguồn thành một chương trình với các lệnh ảo này.  Chương trình đích này sau đó sẽ được hoạt động nhờ vào một chương trình thông dịch.  Ưu điểm: Dễ viết chương trình dịch, có thể chạy trên nhiều nền tảng phần cứng và hệ điều hành.  Nhược điểm: Chậm hơn mã máy tuyệt đối nhiều lần
Máy đích Để thiết kế một bộ sinh mã, chúng ta phải thông hiểu về máy đích và tập chỉ thị của nó. Để đơn giản, chúng ta sẽ dùng một máy ảo làm máy đích. 
Máy tính ảo Tên gọi: VIM Chỉ có hai thanh ghi cùng với bộ nhớ và ngăn xếp Bộ nhớ chương trình và bộ nhớ dữ liệu nằm tách rời nhau Mọi chỉ thị chiếm một ô trong bộ nhớ chương trình chương trình (địa chỉ các ô lệnh này là các số tự nhiên) Một thanh ghi là con trỏ chỉ thị ic có chứa địa chỉ của lệnh sẽ được thực hiện. Đỉnh ngăn xếp được chỉ bằng thanh ghi thứ hai sp.
Máy tính ảo (tiếp) Cấu trúc máy tính VIM bao gồm hai thanh ghi ic, sp và bộ nhớ chia thành ba vùng ngăn xếp (stack), bộ nhớ dữ liệu (data), bộ nhớ chương trình (prog) sp stack data ic prog
Máy tính ảo (tiếp) Các chỉ thị bao gồm một toán tử và nhiều nhất một tham số (có thể là một số hoặc một địa chỉ trong bộ nhớ chương trình hoặc dữ liệu) Các toán tử số học và quan hệ không có tham số. Chúng thực hiện trên một hoặc hai giá trị (toán hạng) đang nằm trên đỉnh ngăn xếp số học (gọi tắt là ngăn xếp). Các toán hạng này sẽ được thay thế bằng kết quả thu được nhờ áp dụng phép toán cho các toán hạng đó.
Máy tính ảo (tiếp) Các chỉ thị nạp (load) và lưu (store), nhẩy (jump) đều có một tham số Lệnh nạp: sao chép dữ liệu của một biến nằm trong bộ nhớ dữ liệu vào đỉnh của ngăn xếp Lệnh lưu: loại bỏ giá trị trên đỉnh của ngăn xếp và đưa nó vào bộ nhớ dữ liệu Các chỉ thị vào ra: không có tham số, lệnh vào đọc một giá trị từ bàn phím và lưu nó vào trong ngăn xếp, lệnh ra loại bỏ giá trị đang ở đỉnh ngăn xếp và ghi nó ra màn hình
Máy tính ảo (tiếp) câu lệnh trong ngôn ngữ nguồn SLANG “a := b + c” , với a, b là biến và c là hằng số sẽ được chuyển sang mã máy VIM như sau: ldvar b ldcon c add stvar a
Giả sử giá trị b và c ban đầu là 37 và 2 thì quá trình thực hiện trên ngăn xếp như sau:
Máy tính ảo (tiếp) Các chỉ thị lệnh của máy đích chia thành các loại: load and store các chỉ thị số học và logic các chỉ thị so sánh chỉ thị không có điều kiện các chỉ thị nhảy có điều kiện các chỉ thị vào ra
Máy tính ảo (tiếp) chỉ thị Nạp và Lưu ldcon intval nạp giá trị số nguyên intval vào ngăn xếp ldvar address sao chép giá trị số nguyên từ địa chỉ bộ nhớ address vào ngăn xếp stvar address loại bỏ giá trị số nguyên ở đỉnh ngăn xếp và ghi nó vào địa chỉ bộ nhớ address chỉ thị Phép toán số học hai ngôi add cộng hai số nguyên sub trừ hai số nguyên mul nhân hai số nguyên
Máy tính ảo (tiếp) dvi lấy thương của hai số nguyên mdl lấy phần dư của hai số nguyên chỉ thị Phép toán số học một ngôi neg lưu giá trị số nguyên dạng –intval vào ngăn xếp abs lưu giá trị tuyệt đối của intval vào ngăn xếp chỉ thị Phép so sánh eq bằng (=) ne khác () lt bé hơn (=)
Máy tính ảo (tiếp) chỉ thị Nhảy jump address nhảy tới địa chỉ address mà không cần điều kiện jift address loại bỏ giá trị chân lý (gọi là truthval) ra khỏi ngăn xếp; nếu giá trị dó là true thì nhảy tới địa chỉ address, còn nếu trái lại thì chỉ thị tiếp theo sẽ được thực hiện jiff address loại bỏ giá trị chân lý (gọi là truthval) ra khỏi ngăn xếp; nếu giá trị dó là false thì nhảy tới địa chỉ address, còn nếu trái lại thì chỉ thị tiếp theo sẽ được thực hiện chỉ thị Vào ra rdint đọc một giá trị số nguyên từ bàn phím và lưu nó vào ngăn xếp wrint loại giá trị nằm trên đỉnh ngăn xếp và ghi nó ra màn hình các chỉ thị khác half dừng việc thực hiện
Một bộ sinh mã đơn giản Giả sử máy đích của chúng ta có các đặc điểm sau: đánh địa chỉ theo byte với bốn byte cho một từ nhớ có n thanh ghi R0, R1, . . ., Rn1 các chỉ thị hai địa chỉ có dạng op source, destination. Trong đó op là mã toán tử, còn source và destination là các trường dữ liệu. Với một số chỉ thị lệnh như sau:  MOV source,destination  ADD source,destination  SUB source,destination
Yêu cầu Thiết kế một bộ sinh mã để sinh ra mã đích cho một dãy câu lệnh ba địa chỉ Để đơn giản, chúng ta giả sử rằng: Mỗi toán tử trong một câu lệnh sẽ có một toán tử tương ứng trong ngôn ngữ đích Kết quả tính được có thể để lại trong thanh ghi càng lâu càng tốt
Ví dụ x := y+z với x, y và z đều được cấp phát tĩnh có thể được dịch thành dãy mã ba địa chỉ sau: MOV y,R0 ADD z,R0 MOV R0,z
Ví dụ (tiếp) a := b + c d := a + e sẽ được dịch thành: MOV b,R0 ADD c,R0 MOV R0,a MOV a,R0 ADD e,R0 MOV R0,d Ở đây câu lệnh thứ tư là thừa, và câu lệnh thứ ba cũng thừa nếu a sau đó không được dùng.
Bản diễn tả thông tin thanh ghi và địa chỉ Bản diễn tả thông tin thanh ghi (register descriptor)  theo dõi xem mỗi thanh ghi hiện đang chứa giá trị nào  được tham vấn mỗi khi cần đến một thanh ghi mới  ban đầu bản diễn tả thông tin thanh ghi cho biết mọi thanh ghi đều rỗng (chưa chứa thông tin). Khi tiến hành sinh mã, mỗi thanh ghi sẽ giữ giá trị của không hoặc nhiều tên tại một thời điểm đã cho. Bản diễn tả địa chỉ (address descriptor)  theo dõi vị trị (hoặc các vị trí) có thể tìm được giá trị hiện tại của tên (vị trí có thể là một thanh ghi, một vị trí ngăn xếp, một địa chỉ bộ nhớ hoặc một tập các vị trí này)  thông tin này có thể được cất trong bảng ký hiệu và được dùng để xác định phương pháp truy xuất cho một tên.