Giáo trình Xây dựng chương trình dịch - Chương VIII: Sinh mã trung gian

Nội dung text: Giáo trình Xây dựng chương trình dịch - Chương VIII: Sinh mã trung gian

1. CHƯƠNG VIII SINH MÃ TRUNG GIAN Nội dung chính: Thay vì một chương trình nguồn được dịch trực tiếp sang mã đích, nó nên được dịch sang dạng mã trung gian bởi kỳ trước trước khi được tiếp tục dịch sang mã đích bởi kỳ sau vì một số tiện ích: Thuận tiện khi muốn thay đổi cách biểu diễn chương trình đích; Giảm thời gian thực thi chương trình đích vì mã trung gian có thể được tối ưu. Chương này giới thiệu các dạng biểu diễn trung gian đặc biệt là dạng mã ba địa chỉ. Phần lớn nội dung của chương tập trung vào trình bày cách tạo ra một bộ sinh mã trung gian đơn giản dạng mã 3 đại chỉ. Bộ sinh mã này dùng phương thức trực tiếp cú pháp để dịch các khai báo, câu lệnh gán, các lệnh điều khiển sang mã ba địa chỉ. Mục tiêu cần đạt: Sau khi học xong chương này, sinh viên phải nắm được cách tạo ra một bộ sinh mã trung gian cho một ngôn ngữ lập trình đơn giản (chỉ chứa một số loại khai báo, lệnh điều khiển và câu lệnh gán) từ đó có thể mở rộng để cài đặt bộ sinh mã cho những ngôn ngữ phức tạp hơn. Tài liệu tham khảo: [1] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986. I. NGÔN NGỮ TRUNG GIAN Cây cú pháp, ký pháp hậu tố và mã 3 địa chỉ là các loại biểu diễn trung gian. 1. Biểu diễn đồ thị Cây cú pháp mô tả cấu trúc phân cấp tự nhiên của chương trình nguồn. DAG cho ta cùng lượng thông tin nhưng bằng cách biểu diễn ngắn gọn hơn trong đó các biểu thức con không được biểu diễn lặp lại. Ví dụ 8.1: Với lệnh gán a := b * - c + b * - c, ta có cây cú pháp và DAG: := := a + a + * * * b - b - b - c c c Cây cú pháp DAG Hình 8.1- Biểu diễn đồ thị của a :=b * - c + b * - c 168
2. t5 := t2 + t4 a := t5 Mã lệnh 3 địa chỉ của cây cú pháp Mã lệnh 3 địa chỉ của DAG Hình 8.3 - Mã lệnh 3 địa chỉ tương ứng với cây cú pháp và DAG trong hình 8.1 3. Các mã lệnh 3 địa chỉ phổ biến 1. Lệnh gán dạng x := y op z, trong đó op là toán tử 2 ngôi số học hoặc logic. 2. Lệnh gán dạng x := op y, trong đó op là toán tử một ngôi. Chẳng hạn, phép lấy số đối, toán tử NOT, các toán tử SHIFT, các toán tử chuyển đổi. 3. Lệnh COPY dạng x :=y, trong đó giá trị của y được gán cho x. 4. Lệnh nhảy không điều kiện goto L. Lệnh 3 địa chỉ có nhãn L là lệnh tiếp theo thực hiện. 5. Các lệnh nhảy có điều kiện như if x relop y goto L. Lệnh này áp dụng toán tử quan hệ relop ( =, ) vào x và y. Nếu x và y thỏa quan hệ relop thì lệnh nhảy với nhãn L sẽ được thực hiện, ngược lại lệnh đứng sau IF x relop y goto L sẽ được thực hiện. 6. param x và call p, n cho lời gọi chương trình con và return y. Trong đó, y biểu diễn giá trị trả về có thể lựa chọn. Cách sử dụng phổ biến là một chuỗi lệnh 3 địa chỉ. param x1 param x2 param xn call p, n được sinh ra như là một phần của lời gọi chương trình con p (x1,x2, , xn). 7. Lệnh gán dạng x := y[i] và x[i] := y. Lệnh đầu lấy giá trị của vị trí nhớ của y được xác định bởi giá trị ô nhớ i gán cho x. Lệnh thứ 2 lấy giá trị của y gán cho ô nhớ x được xác định bởi i. 8. Lệnh gán địa chỉ và con trỏ dạng x :=&y , x := *y và *x := y. Trong đó, x := &y đặt giá trị của x bởi vị trí của y. Câu lệnh x := *y với y là một con trỏ mà r_value của nó là một vị trí, r_value của x đặt bằng nội dung của vị trí này. Cuối cùng *x := y đặt r_value của đối tượng được trỏ bởi x bằng r_value của y. 4. Dịch trực tiếp cú pháp thành mã lệnh 3 địa chỉ Ví dụ 8.2: Ðịnh nghĩa S _ thuộc tính sinh mã lệnh địa chỉ cho lệnh gán: Luật ngữ nghĩa Luật sinh S→ id := E S.code := E.code || gen (id.place ':=' E.place) E→ E1 + E2 E.place := newtemp; E.code := E1.code || E2.code || gen (E.place ':=' E1.place '+' E2.place) E→ E1 * E2 E.place := newtemp; E.code := E1.code || E2.code || 170
3. Hình 8.5 - Ðịnh nghĩa trực tiếp cú pháp sinh mã lệnh ba địa chỉ cho câu lệnh while Lệnh S → while E do S1 được sinh ra bằng cách dùng các thuộc tính S.begin và S.after để đánh dấu lệnh đầu tiên trong đoạn mã lệnh của E và lệnh sau đoạn mã lệnh của S. Hàm newlabel trả về một nhãn mới tại mỗi lần được gọi 5. Cài đặt lệnh 3 địa chỉ Lệnh 3 địa chỉ là một dạng trừu tượng của mã lệnh trung gian. Trong chương trình dịch, các mã lệnh này có thể cài đặt bằng một mẩu tin với các trường cho toán tử và toán hạng. Có 3 cách biểu diễn là bộ tứ, bộ tam và bộ tam gián tiếp. ƒ Bộ tứ Bộ tứ (quadruples) là một cấu trúc mẩu tin có 4 trường ta gọi là op, arg1, arg2 và result. Trường op chứa toán tử. Lệnh 3 địa chỉ x := y op z được biểu diễn bằng cách thay thế y bởi arg1, z bởi arg2 và x bởi result. Các lệnh với toán tử một ngôi như x := -y hay x := y thì không sử dụng arg2. Các toán tử như param không sử dụng cả arg2 lẫn result. Các lệnh nhảy có điều kiện và không điều kiện đặt nhãn đích trong result. Nội dung các trường arg1, arg2 và result trỏ tới ô trong bảng ký hiệu đối với các tên biểu diễn bởi các trường này. Nếu vậy thì các tên tạm phải được đưa vào bảng ký hiệu khi chúng được tạo ra. Ví dụ 8.3: Bộ tứ cho lệnh a := b * -c + b * -c op arg1 arg2 result (0) uminus c t1 (1) * b t1 t2 (2) uminus c t3 (3) * b t3 t4 (4) + t2 t4 t5 (5) := t5 a Hình 8.6 - Biểu diễn bộ tứ cho các lệnh ba địa chỉ ƒ Bộ tam Ðể tránh phải lưu tên tạm trong bảng ký hiệu; chúng ta có thể tham khảo tới giá trị tạm bằng vị trí của lệnh tính ra nó. Ðể làm điểu đó ta sử dụng bộ tam (triples) là một mẩu tin có 3 trường op, arg1 và arg2. Trong đó, arg1 và arg2 trỏ tới bảng ký hiệu (đối với tên hoặc hằng do người lập trình định nghĩa) hoặc trỏ tới một phần tử trong bộ tam (đối với giá trị tạm) op arg1 arg2 (0) uminus c (1) * b (0) (2) uminus c Hình 8.7 - Biểu diễn bộ tam cho các (3) * b (2) lệnh ba địa chỉ (4) + (1) (3) (5) := a (4) Các lệnh như x[i]:=y và x:=y[i] sử dụng 2 ô trong cấu trúc bộ tam. 172
4. P → M D M → ε {offset := 0 } Tất cả các hành vi đều nằm cuối vế phải. 2. Lưu trữ thông tin về tầm Trong một ngôn ngữ mà chương trình con được phép khai báo lồng nhau. Khi một chương trình con được tìm thấy thì quá trình khai báo của chương trình con bao bị tạm dừng. Văn phạm cho sự khai báo đó là; P → D D → D ; D | id: T | proc id ; D; S Ðể đơn giản chúng ta tạo ra một bảng ký hiệu riêng cho mỗi chương trình con. Khi một khai báo chương trình con D → proc id D1 ; S được tạo ra và các khai báo trong D1 được lưu trữ trong bảng ký hiệu mới. Ví dụ 8.5: Chương trình Sort có bốn chương trình con lồng nhau readarray, exchange, quicksort và partition. Ta có năm bảng ký hiệu tương ứng. sort quicksort nil header header a readarray k x header v readarray id partition exchange quicksort partition exchange header header i j Hình 8.11 - Những bảng ký hiệu của các chương trình con lồng nhau Luật ngữ nghĩa được xác định bởi các thao tác sau 1. mktable (previous): Tạo một bảng ký hiệu mới và con trỏ tới bảng đó. Tham số previous là một con trỏ trỏ tới bảng ký hiệu của chương trình con bao. Con trỏ previous được lưu trong header của bảng ký hiệu mới. Trong header còn có thể có các thông tin khác như độ sâu lồng của chương trình con. 2. enter (table, name, type, offset): Tạo một ô mới trong bảng ký hiệu được trỏ bởi table. 3. addwidth (table, width): Ghi kích thước tích lũy của tất cả các ô trong bảng vào trong header kết hợp với bảng đó. 174
5. Sau khi từ khóa record được tìm thấy thì hành vi kết hợp với L tạo một bảng ký hiệu mới cho các tên trường. Các hành vi của D → id : T đưa thông tin về tên trường id vào trong bảng ký hiệu cho mẩu tin. III. LỆNH GÁN 1. Tên trong bảng ký hiệu Xét lược đồ dịch để sinh ra mã lệnh 3 địa chỉ cho lệnh gán: S→ id := E {p:=lookup( id.name); if p nil then E.place := p else error } Hình 8.14 - Lược đồ dịch sinh mã lệnh ba địa chỉ cho lệnh gán Hàm lookup tìm trong bảng ký hiệu xem có hay không một tên được cho bởi id.name. Nếu có thì trả về con trỏ của ô, nếu không trả về nil. Xét luật sinh D → proc id ; ND1 ; S Như trên đã nói, hành vi kết hợp với ký hiệu chưa kết thúc N cho phép con trỏ của bảng ký hiệu cho chương trình con đang nằm trên đỉnh Stack tblptr. Các tên trong lệnh gán sinh ra bởi ký hiệu chưa kết thúc S sẽ được khai báo trong chương trình con này hoặc trong bao của nó. Khi tham khảo tới một tên thì trước hết hàm lookkup sẽ tìm xem có tên đó trong bảng ký hiệu hiện hành hay không. (Bảng danh biểu hiện hành được trỏ bởi top(tblptr)). Nếu không thì dùng con trỏ ở trong header của bảng để tìm bảng ký hiệu bao nó và tìm tên trong đó. Nếu tên không được tìm thấy trong tất cả các mức thì lookup trả về nil. 2. Ðịa chỉ hóa các phần tử của mảng Các phần tử của mảng có thể truy xuất nhanh nếu chúng được liền trong một khối các ô nhớ kết tiếp nhau. Trong mảng một chiều nếu kích thước của một phần tử là w thì địa chỉ tương đối phần tử thứ i của mảng A được tính theo công thức Ðịa chỉ tương đối của A[i] = base + (i-low) * w Trong đó low: là cận dưới tập chỉ số base: là địa chỉ tương đối của ô nhớ cấp phát cho mảng tức là địa chỉ tương đối của A[low] 176
6. if E1.type= integer and E2.type = integer then begin emit(E.place ':=' E1.place 'int + ' E2.place); E.type:= integer; end else if E1.type=real and E2.type =real then begin emit(E.place ':=' E1.place 'real + ' E2.place); E.type:= real; end else if E1.type=integer and E2.type =real then begin u:=newtemp; emit(u ':=' ‘intoreal' E1.place); emit(E.place ':=' u 'real +' E2.place); E.type:= real; end else if E1.type=real and E2.type =integer then begin u:=newtemp; emit(u ':=' 'intoreal' E2.place); emit(E.place ':= ' E1.place 'real +' u); E.type:= real; end else E.type := type_error; end Hình 8.16 - Hành vi ngữ nghĩa của E → E1 +E2 Ví dụ 8.5: Với lệnh gán x := y + i * j trong đó x,y được khai báo là real; i , j được khai báo là integer. Mã lệnh 3 địa chỉ xuất ra là: t1 := i int * j t3 := intoreal t1 t2 := y real + t3 x := t2 IV. BIỂU THỨC LOGIC Biểu thức logic được sinh ra bởi văn phạm sau: E→ E or E | E and E | not E | (E) | id relop id | true | false Trong đó or và and kết hợp trái; or có độ ưu tiên thấp nhất, kế tiếp là and và sau cùng là not Thông thường có 2 phương pháp chính để biểu diễn giá trị logic. Phương pháp 1: Mã hóa true và false bằng các số và việc đánh giá biểu thức được thực hiện tương tự như đối với biểu thức số học, có thể biểu diễn true bởi 1 , false bởi 0; hoặc các số khác không biểu diễn true, số không biểu diễn false 178
7. 108 : if e<f goto 111 109 : t3 := 0 110 : goto 112 111 : t3 := 1 112 : t4 := t2 and t3 113 : t5 := t1 or t4 Hình 8.18 - Sự biên dịch sang mã lệnh ba địa chỉ cho a<b or c<d and e<f 1. Mã nhảy Ðánh giá biểu thức logic mà không sinh ra mã lệnh cho các toán tử or, and và not. Chúng ta chỉ biểu diễn giá trị môt biểu thức bởi vị trí trong chuỗi mã. Ví dụ, trong chuỗi mã lệnh trên, giá trị t1 sẽ phụ thuộc vào việc chúng ta chọn lệnh 101 hay lệnh 103. Do đó giá trị của t1 là thừa. 2. Các lệnh điều khiển S→ if E then S1 | if E then S1 else S2 | while E do S1 Với mỗi biểu thức logic E, chúng ta kết hợp với 2 nhãn E.true : Nhãn của dòng điều khiển nếu E là true. E.false : Nhãn của dòng điều khiển nếu E là false. S.code : Mã lệnh 3 địa chỉ được sinh ra bởi S. S.next : Là nhãn mà lệnh 3 địa chỉ đầu tiên sẽ thực hiện sau mã lệnh của S. S.begin : Nhãn chỉ định lệnh đầu tiên được sinh ra cho S. E.code to E.true E.true: to E.false S1.code E.false: (a) if -then to E.true S.begin: E.code E.code to E.true to E.false E.true: E.true: to E.false S .code S1.code 1 goto S.next goto S.begin E.false: E.false: S .code 2 S.next: (b) if -then-else (c) while-do Hình 8.19 - Mã lệnh của các lệnh if-then, if-then-else, và while-do 180
8. E2.false := E.false; E.code := E1.code || gen(E.false ':') || E2.code E→ E1 and E2 E1.true := newlabel; E1.false := E.false; E2.true := E.true; E2.false := E.false; E.code := E1.code || gen(E.true ':') || E2.code E→ not E1 E1.true := E.false; E1.false := E.true; E.code := E1.code E → (E1) E1.true := E.true; E1.false := E.false; E.code := E1.code E.code := gen('if' id .place relop.op id .place E → id1 relop id2 1 2 'goto' E.true) || gen('goto' E.false) E → true E.code:= gen('goto' E.true) E → false E.code:= gen('goto' E.false) Hình 8.21 - Ðịnh nghĩa trực tiếp cú pháp sinh mã lệnh ba địa chỉ cho biểu thức logic 4. Biểu thức logic và biểu thức số học Trong thực tế biểu thức logic thường chứa những biểu thức số học như (a+b) b. Phương pháp biểu diễn biểu thức logic bằng mã lệnh nhảy có thể vẫn còn được sử dụng. Xét văn phạm E → E+ E | E and E | E relop E | id Trong đó, E and E đòi hỏi hai đối số phải là logic. Trong khi + và relop có các đối số là biểu thức logic hoặc/và số học. Ðể sinh mã lệnh trong trường hợp này, chúng ta dùng thuộc tính tổng hợp E.type có thể là arith hoặc bool. E sẽ có các thuộc tính kế thừa E.true và E.false đối với biểu thức số học. Ta có luật ngữ nghĩa kết hợp với E → E1 + E2 như sau E.type := arith; if E1.type = arith and E2.type = arith then begin /* phép cộng số học bình thường */ E.place := newtemp; E.code := E1.code || E2.code || gen(E.place ':=' E1.place '+' E2.place) end else if E1.type = arith and E2.type = bool then begin 182
9. goto next Ln-1 : mã lệnh của Sn-1 goto next Ln : mã lệnh của Sn goto next test : if t=V1 goto L1 if t=V2 goto L2 if t=Vn-1 goto Ln-1 else goto Ln next: Hình 8.24 - Dịch câu lệnh case Một phương pháp khác để cài đặt lệnh SWITCH là mã lệnh để đánh giá biểu thức E vào t if t V2 goto L2 mã lệnh của S2 goto next L2: Ln-2 : if t <> Vn-1 goto Ln-1 mã lệnh của Sn-1 goto next Ln-1 : mã lệnh của Sn next: Hình 8.24 - Một cách dịch khác của câu lệnh case 184