Giáo trình Xây dựng chương trình dịch - Chương V: Dịch trực tiếp cú pháp

Nội dung text: Giáo trình Xây dựng chương trình dịch - Chương V: Dịch trực tiếp cú pháp

1. CHƯƠNG V DỊCH TRỰC TIẾP CÚ PHÁP Nội dung chính: Khi viết một chương trình bằng một ngôn ngữ lập trình nào đó, ngoài việc quan tâm đến cấu trúc của chương trình (cú pháp – văn phạm), ta còn phải chú ý đến ý nghĩa của chương trình. Như vậy, khi thiết kế một trình biên dịch, ta không những chú ý đến văn phạm mà còn chú ý đến cả ngữ nghĩa. Chương 5 trình bày các cách biểu diễn ngữ nghĩa của một chương trình. Mỗi ký hiệu văn phạm kết hợp với một tập các thuộc tính – các thông tin. Mỗi luật sinh kết hợp với một tập các luật ngữ nghĩa – các quy tắc xác định trị của các thuộc tính. Việc đánh giá các luật ngữ nghĩa được sử dụng để thực hiện một công việc nào đó như tạo ra mã trung gian, lưu thông tin vào bảng ký hiệu, xuất các thông báo lỗi, v.v. Ta sẽ thấy rõ việc đánh giá này ở các chương sau: 6, 8, 9. Hai cách để kết hợp các luật sinh với các luật ngữ nghĩa được trình bày trong chương là: Định nghĩa trực tiếp cú pháp và Lược đồ dịch. Ở mức quan niệm, bằng cách sử dụng định nghĩa trực tiếp cú pháp hoặc lược đồ dịch, ta phân tích dòng thẻ từ, xây dựng cây phân tích cú pháp và duyệt cây khi cần để đánh giá các luật ngữ nghĩa tại các nút của cây. 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ác cách kết hợp các luật sinh với các luật ngữ nghĩa: Định nghĩa trực tiếp cú pháp và Lược đồ dịch. • Biết cách thiết kế chương trình – bộ dịch dự đoán - thực hiện một công việc nào đó từ một lược đồ dịch hay từ một định nghĩa trực tiếp cú pháp xác định. Tài liệu tham khảo: [1] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986. [2] Modern Compiler Implementation in C - Andrew W. Appel - Cambridge University Press, 1997. I. ÐỊNH NGHĨA TRỰC TIẾP CÚ PHÁP Ðịnh nghĩa trực tiếp cú pháp là sự tổng quát hóa một văn phạm phi ngữ cảnh, trong đó mỗi ký hiệu văn phạm kết hợp với một tập các thuộc tính. Cây phân tích cú pháp có trình bày giá trị các thuộc tính tại mỗi nút gọi là cây chú thích . 1. Khái niệm về định nghĩa trực tiếp cú pháp Trong một định nghĩa trực tiếp cú pháp, mỗi luật sinh A → α kết hợp một tập luật ngữ nghĩa có dạng b := f (c1, c2, , ck) trong đó f là một hàm và : 116
2. Hình 5.2- Cây chú thích cho biểu thức 3* 5+4n 2. Thuộc tính kế thừa • Là một thuộc tính mà giá trị của nó được xác định từ giá trị các thuộc tính của các nút cha hoặc anh em của nó. • Nói chung ta có thể viết một định nghĩa trực tiếp cú pháp thành một định nghĩa S_ thuộc tính. Nhưng trong một số trường hợp, việc sử dụng thuộc tính kế thừa lại thuận tiện vì tính tự nhiên của nó. Ví dụ 5.2: Xét định nghĩa trực tiếp cú pháp sau cho sự khai báo kiểu cho biến: Luật sinh Luật ngữ nghĩa D Æ TL L.in := T.type T Æ int T.type := integer T Æ real T.type := real L1.in := L.in; addtype (id.entry, L.in) L Æ L1, id L Æ id addtype (id.entry, L.in) Hình 5.3 - Ðịnh nghĩa trực tiếp cú pháp với thuộc tính kế thừa L.in type là thuộc tính tổng hợp kết hợp với ký hiệu chưa kết thúc T, giá trị của nó được xác định bởi từ khóa trong khai báo. Bằng cách sử dụng thuộc tính kế thừa in kết hợp với ký hiệu chưa kết thúc L chúng ta xác định được kiểu cho các danh biểu và dùng thủ tục addtype đưa kiểu này vào trong bảng ký hiệu tương ứng với danh biểu. Ví dụ 5.3: Xét phép khai báo: real id1, id2, id3. Ta có cây chú thích: D T type = real L.in = real real , id 3 Lin=real , id2 Lin real id1 Hình 5.4- Cây phân tích cú pháp với thuộc tính kế thừa in tại mỗi nút được gán nhãnL 118
3. Chú ý: Với luật ngữ nghĩa dạng b = f( c1, c2, , ck) có chứa lời gọi thủ tục thì chúng ta tạo ra một thuộc tính tổng hợp giả. Trong ví dụ của chúng ta là nút 6, 8, 10. II. XÂY DỰNG CÂY CÚ PHÁP • Cây cú pháp (syntax - tree) là dạng rút gọn của cây phân tích cú pháp dùng để biểu diễn cấu trúc ngôn ngữ. • Trong cây cú pháp các toán tử và từ khóa không phải là nút lá mà là các nút trong. Ví dụ với luật sinh S ( if B then S1 else S2 được biểu diễn bởi cây cú pháp: if - then - else S B 1 S2 • Một kiểu rút gọn khác của cây cú pháp là chuỗi các luật sinh đơn được rút gọn lại. Chẳng hạn ta có: + được rút gọn từ E 4 * E + T 3 5 T F id T F * id id 1. Xây dựng cây cú pháp cho biểu thức Tương tự như việc dịch một biểu thức thành dạng hậu tố. Xây dựng cây con cho biểu thức con bằng cách tạo ra một nút cho toán hạng và toán tử. Con của nút toán tử là gốc của cây con biểu diễn cho biểu thức con toán hạng của toán tử đó. Mỗi một nút có thể cài đặt bằng một mẩu tin có nhiều trường. Trong nút toán tử, có một trường chỉ toán tử như là nhãn của nút, các trường còn lại chứa con trỏ, trỏ tới các nút toán hạng. Ðể xây dựng cây cú pháp cho biểu thức chúng ta sử dụng các hàm sau đây: 1. mknode(op, left, right): Tạo một nút toán tử có nhãn là op và hai trường chứa con trỏ, trỏ tới con trái left và con phải right. 120
4. Với biểu thức a - 4 + c ta có cây phân tích cú pháp (biểu diễn bởi đường chấm) tronh hHình 5.9. 122
5. Ðể xây dựng một DAG, trước khi tạo một nút phải kiểm tra xem nút đó đã tồn tại chưa, nếu đã tồn tại thì hàm tạo nút (mknode, mkleaf) trả về con trỏ của nút đã tồn tại, nếu chưa thì tạo nút mới. Cài đặt DAG: Người ta thường sử dụng một mảng mẩu tin , mỗi mẩu tin là một nút. Ta có thể tham khảo tới nút bằng chỉ số của mảng. Ví dụ 5.9: Lệnh gán DAG Biểu diễn i := i + 10 := 1 id entry i + 2 num 10 i 10 3 + 1 2 4 := 1 3 Hình 5.11- Minh họa cài đặt DAG Nút 1: có nhãn là id, con trỏ trỏ tới entry i. Nút 2: có nhãn là num, giá trị là 10. Nút 3: có nhãn là +, con trái là nút 1, con phải là nút 2. Nút 4: có nhãn là :=, con trái là nút 1, con phải là nút 3. Giải thuật: Phương pháp số giá trị (value – number) để xây dựng một nút trong DAG. Giả sử rằng các nút được lưu trong một mảng và mỗi nút được tham khảo bởi số giá trị của nó. Mỗi một nút toán tử là một bộ ba Input: Nhãn op, nút l và nút r. Output: Một nút với Phương pháp: Tìm trong mảng một nút m có nhãn là op con trái là l, con phải là r. Nếu tìm thấy thì trả về m, ngược lại tạo ra một nút mới n, có nhãn là op, con trái là l, con phải là r và trả về n. III. ÐÁNH GIÁ DƯỚI LÊN ÐỐI VỚI ÐỊNH NGHĨA S_THUỘC TÍNH 1. Sử dụng Stack Như đã biết, định nghĩa S_ thuộc tính chỉ chứa các thuộc tính tổng hợp do đó phương pháp phân tích dưới lên là phù hợp với định nghĩa trực tiếp cú pháp này. Phương pháp phân tích dưới lên sử dụng một STACK để lưu trữ thông tin về cây con đã được phân tích. Chúng ta có thể mở rộng STACK này để lưu trữ giá trị thuộc tính tổng hợp. STACK được cài đặt bởi một cặp mảng state và val. Giả sử luật ngữ nghĩa A.a := f ( X.x, Y.y, Z.z ) kết hợp với luật sinh A → XYZ. Trước khi XYZ được rút gọn thành A thì val[top] = Z.z, val[top - 1] = Y.y, val[top - 2] 124
6. Hình 5.13 – Cây chú thích cho biểu thức 3 * 5 + 4 n Cây chú thích này có thể được đánh giá bằng một bộ phân tích cú pháp LR từ dưới lên trên. Chú ý rằng bộ phân tích đã nhận biết giá trị thuộc tính digit.lexval. Khi digit được đưa vào stack thì token digit được đưa vào state[top] và giá trị thuộc tính của nó được đưa vào val[top]. Chúng ta có thể sử dụng kỹ thuật trong mục VI của chương IV để xây dựng bộ phân tích LR. Ðể đánh giá các thuộc tính chúng ta thay đổi bộ phân tích cú pháp để thực hiện đoạn mã sau: Luật sinh Luật ngữ nghĩa L Æ En print(val[top]) E Æ E1 + T val[ntop] := val[top - 2] + val[top] E Æ T T Æ T1 * F val[ntop] := val[top - 2] * val[top] T Æ F F Æ (E) val[ntop] := val[top - 1] F Æ digit Hình 5.14- Cài đặt một máy tính tay sử dụng bộ phân tích cú pháp LR Khi một luật sinh với r ký hiệu bên vế phải được rút gọn thì ntop = top - r + 1. Sau khi một đoạn mã thực hiện thì đặt top = ntop Bảng sau trình bày quá trình thực hiện của bộ phân tích cú pháp Input State Val Luật sinh được dùng 3 * 5 + 4 n _ _ * 5 + 4 n 3 3 * 5 + 4 n F 3 F Æ digit *5 + 4 n T 3 T Æ F 5 + 4 n T* 3 - + 4 n T * 5 3 - 5 + 4 n T * F 3 - 5 F Æ digit + 4 n T 15 T Æ T * F + 4 n E 15 E Æ T 4 n E + 15 - n E + 4 15 - 4 n E + F 15 - 4 F Æ digit n E + T 15 - 4 T Æ F 126
7. Với mỗi một luật ngữ nghĩa, ta tạo một hành vi ngữ nghĩa và đặt hành vi này vào cuối vế phải luật sinh. Ví dụ 5.13: Luật sinh Luật ngữ nghĩa T Æ T1 * F T.val := T1.val * F.val Ta có lược đồ dịch: T Æ T1 * F { T.val := T1.val * F.val} Trường hợp 2: Có cả thuộc tính tổng hợp và kế thừa phải thỏa mãn 3 yêu cầu sau đây: 1. Thuộc tính kế thừa của một ký hiệu trong vế phải của luật sinh phải được xác định trong hành vi nằm trước ký hiệu đó. 2. Một hành vi không được tham khảo tới thuộc tính tổng hợp của một ký hiệu nằm bên phải hành vi đó. 3. Thuộc tính tổng hợp của ký hiệu chưa kết thúc trong vế trái chỉ có thể được xác định sau khi tất cả các thuộc tính mà nó tham khảo đã được xác định. Hành vi xác định các thuộc tính này luôn đặt cuối vế phải của luật sinh. Với một định nghĩa trực tiếp cú pháp L_thuộc tính ta có thể xây dựng lược đồ dịch thỏa mãn 3 yêu cầu nói trên. E T R - T { print(‘-’) } 9 { print(‘9’) } R 5 { print(‘5’) } + T { print(‘+’) } R 2 { print(‘2’) } ε Hình 5.17 - Cây phân tích cú pháp của các hoạt động biểu diễn 9-5+2 Ví dụ 5.14: Bộ xử lý các công thức toán học – EQN - có thể xây dựng các biểu thức toán học từ các toán tử sub (subscripts) và sup (superscripts). Chẳng hạn: input output BOX sub box BOX box a sub {i sup 2 } ai2 128
8. B Æ {B1.ps := B.ps } B1 sub {B2B .ps := shrink(B.ps) } B2 {B.ht := disp(B1.ht, B2.ht ) } B Æ text {B.ht := text.h * B.ps } Hình 5.19 - Lược đồ dịch được tạo ra từ hình 5.18 Chú ý: Ðể dễ đọc mỗi ký hiệu văn phạm trong luật sinh được viết trên một dòng và hành vi được viết vào bên phải. Chẳng hạn: S Æ {B.ps := 10 } B {S.ht := B.ht } Ðược viết thành S Æ {B.ps := 10 } B {S.ht := B.ht } V. DỊCH TRÊN XUỐNG 1. Loại bỏ đệ qui trái Vấn đề loại bỏ đệ qui trái của một văn phạm đã được trình bày trong mục III của chương IV. Ở đây chúng ta giải quyết vấn đề chuyển một lược đồ dịch của văn phạm đệ quy trái thành một lược đồ dịch mới không còn đệ quy. Giả sử, ta có lược đồ dịch dạng A Æ A1 Y {A.a := g(A1.a, Y.y) } A Æ X {A.a := f(X.x) } Ðây là một văn phạm đệ quy trái, áp dụng giải thuật khử đệ qui trái ta được văn phạm không đệ quy trái A Æ X R R Æ Y R | ε Bổ sung hành vi ngữ nghĩa cho văn phạm ta được lược đồ dịch: A Æ X { R.i := f(X.x) } R {A.a := R.s } R Æ Y {R1.i := g(R.i, Y.y) } R1 {R.s := R1.s } R Æ ε {R.s := R.i } Ví dụ 5.15: Xét lược đồ dịch của văn phạm đệ quy trái cho biểu thức. E Æ E1 + T {E.val := E1.val + T.val } E Æ E1 - T {E.val := E1.val - T.val } E Æ T {E.val := T.val } 130
9. T Æ num {T.nptr := mkleaf(num, num.val) } Áp dụng quy tắc khử đệ quy trái trên với E ≈ A, +T, -T ≈ Y và T ≈ X ta có lược đồ dịch E Æ T {R.i := T.nptr } R {E.nptr := R.s } R Æ + T {R1.i := mknode(‘+’, R.nptr, T.nptr) } R1 {R.s := R1.s } R Æ - T {R1.i := mknode(‘-’, R.nptr, T.nptr) } R1 {R.s := R1.s } R Æ ε {R.s := R.i } T Æ ( E ) {T.nptr := E.nptr } T Æ id {T.nptr := mkleaf(id, id.entry) } T Æ num { T.nptr := mkleaf(num, num.val) } Hình 5.23 - Lược đồ dịch được chuyển đổi để xây dựng cây cú pháp 2. Thiết kế bộ dịch dự đoán Giải thuật: Xây dựng bộ dịch trực tiếp cú pháp dự đoán (Predictive - Syntax - Directed Translation) Input: Một lược đồ dịch cú pháp trực tiếp với văn phạm có thể phân tích dự đoán. Output: Mã cho bộ dịch trực tiếp cú pháp. Phương pháp: 1. Với mỗi ký hiệu chưa kết thúc A, xây dựng một hàm có các tham số hình thức tương ứng với các thuộc tính kế thừa của A và trả về giá trị của thuộc tính tổng hợp của A. 2. Mã cho ký hiệu chưa kết thúc A quyết định luật sinh nào được dùng cho ký hiệu nhập hiện hành. 3. Mã kết hợp với mỗi luật sinh như sau: chúng ta xem xét token, ký hiệu chưa kết thúc và hành vi bên phải của luật sinh từ trái sang phải i) Ðối với token X với thuộc tính tổng hợp x, lưu giá trị của x vào trong biến được khai báo cho X.x. Sau đó phát sinh lời gọi để hợp thức (match) token X và dịch chuyển đầu đọc. 132
10. BÀI TẬP CHƯƠNG V 5.1. Xây dựng một cây phân tích cú pháp chú thích cho biểu thức số học sau: (4 * 7+ 1) * 2 5.2. Xây dựng một cây phân tích cú pháp và cây cú pháp cho biểu thức ((a) + (b)) theo: a) Ðịnh nghĩa trực tiếp cú pháp cho biểu thức số học. b) Lược đồ dịch cho biểu thức số học. 5.3. Xây dựng một DAG cho các biểu thức sau đây: a) a + a + ( a+ a + a + ( a+ a+ a+ a)) b) x *( 3 *x + x * x) 5.4. Văn phạm sau đây sinh ra các biểu thức có được khi áp dụng một toán tử số học + cho các hằng số nguyên và số thực. Khi 2 số nguyên được công lại, kiểu kết quả là kiểu nguyên, ngược lại nó là kiểu số thực. E → E + T | T T → num • num | num a) Ðưa ra một định nghĩa trực tiếp cú pháp xác định kiểu của mỗi biểu thức con. b) Mở rộng định nghĩa trực tiếp cú pháp trên để dịch các biểu thức thành ký pháp hậu tố và xác định các kiểu. Dùng toán tử một ngôn inttoreal để chuyển một giá trị nguyên thành giá trị thực tương đương mà nhờ đó cả hai toán hạng của + ở dạng hậu tố có cùng kiểu. 5.5. Giả sử các khai báo sinh bởi văn phạm sau: D → id L L → , id L | : T T → integer | real a) Xây dựng một lược đồ dịch để nhập kiểu của mỗi định danh vào bảng danh biểu. b) Xây dựng chương trình dịch dự đoán từ lược đồ dịch trên. 134