Trình biên dịch - Chương 5: Dịch trực tiếp cú pháp

 ( num.val) } 
Với biểu thức 9 - 5 + 2 ta có cây phân tích cú pháp (hình 5.16) 
 Ðể xây dựng một lược đồ dịch, chúng ta xét hai trường hợp sau đây: 
 Trường hợp 1: Chỉ chứa thuộc tính tổng hợp: 
 127
 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 
9
{ print(‘9’) } R 
R 
R 
ε 
T 
T - { print(‘-’) } 
5 { print(‘5’) } 
+ T { print(‘+’) } 
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 } 2ia
 128
 Ðể xác định chiều rộng và chiều cao của các hộp ta có định nghĩa L_thuộc tính như 
sau: 
Luật sinh Luật ngữ nghĩa 
S Æ B 
B Æ B1B2 
B Æ B1 sub B2
B Æ text 
B.ps := 10 
S.ht := B.ht 
BB1.ps := B.ps 
BB2.ps := B.ps 
B.ht := max(B1.ht, B2.ht) 
BB1.ps := B.ps 
BB2.ps := shrink(B.ps) 
B.ht := disp(B1.ht, B2.ht) 
B.ht := text.h * B.ps 
Hình 5.18 - Ðịnh nghĩa trực tiếp cú pháp xác định kích thước và chiều cao của các 
hộp 
 Trong đó: 
- Ký hiệu chưa kết thúc B biểu diễn một công thức. 
- Luật sinh B → BB biểu diễn sự kề nhau của hai hộp. 
- Luật sinh B → B sub B biểu diễn sự sắp đặt, trong đó hộp chỉ số thứ 2 có kích 
thước nhỏ hơn, nằm thấp hơn hộp thứ nhất. 
- Thuộc tính kế thừa ps (point size - kích thước điểm) phản ánh độ lớn của công 
thức. 
- Luật sinh B → text ứng với luật ngữ nghiã B.ht:= text.h * B.ps lấy chiều cao 
thực của text (h) nhân với kích thước điểm của B để có được chiều cao của 
hộp. 
- Luật sinh B → B1B2 được áp dụng thì B1, B2 kế thừa kích thước điểm của B 
bằng luật copy. Ðộ cao của B bằng giá trị lớn nhất trong độ cao của B1, B2. 
- Khi luật sinh B → B1 sub B2 được áp dụng thì hàm shrink sẽ giảm kích thước 
điểm của B2 còn 30% và hàm disp đẩy hộp B2 xuống. 
Ðây là một định nghĩa L_thuộc tính vì chỉ có duy nhất một thuộc tính kế thừa ps và 
thuộc tính này chỉ phụ thuộc vào vế trái của luật sinh. 
 Dựa vào 3 yêu cầu nói trên, ta xen các hành vi ngữ nghĩa tương ứng với luật ngữ 
nghĩa vào vế phải của mỗi luật sinh để được lược đồ dịch. 
 S Æ {B.ps := 10 } 
 B {S.ht := B.ht } 
 B Æ { B1.ps := B.ps } 
 B1 {BB2.ps := B.ps } 
 B2 {B.ht := max(B1.ht, B2.ht ) } 
 129
 B Æ {B1.ps := B.ps } 
 B1 
 sub {BB2.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
 T Æ (E) {T.val := E.val } 
 T Æ num {T.val := num.val } 
Hình 5.20 - Lược đồ dịch của một văn phạm đệ quy trái 
 Vận dụng ý kiến trên ta khử đệ quy trái để được lược đồ dịch không đệ quy trái 
 E Æ T {R.i := T.val } 
 R {E.val := R.s } 
 R Æ + 
 T {R1.i := R.i + T.val } 
 R1 {R.s := R1.s } 
 R Æ - 
 T {R1.i := R.i - T.val } 
 R1 {R.s := R1.s } 
 R Æ ε {R.s := R.i } 
 T Æ ( 
 E 
 ) {T.val := E.val } 
T Æ num { T.val := num.val } 
Hình 5.21 - Lược đồ dịch đã được chuyển đổi có văn phạm đệ quy phải 
 Chẳng hạn đánh giá biểu thức 9 - 5 + 2 E 
 T.val = 9 
Hình 5.22 - Xác định giá trị của biểu thức 9-5+2 
 Ví du 5.16: Xét lược đồ dịch xây dựng cây cú pháp cho biểu thức 
E Æ E1 + T {E.nptr := mknode(‘+’, E1.nptr, T.nptr) } 
 E Æ E1 - T {E.nptr := mknode(‘-’, E1.nptr, T.nptr) } 
 E Æ T {E.nptr := T.nptr } 
 T Æ (E) {T.nptr := E.nptr } 
 T Æ id {T.nptr := mkleaf(id, id.entry) } 
R.i = 6 
num.val = 9 
R.i = 9 
+ 
T.val = 5 
num.val = 5 
R.i = 4 
T.val = 2 
num.val = 2 
- 
ε 
 131
 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
 ii) Ðối với ký hiệu chưa kết thúc B, phát sinh lệnh gán C := B(b1, b2, ..., bk) với 
lời gọi hàm trong vế phải của lệnh gán, trong đó b1, b2,..., bk là các biến cho các 
thuộc tính kế thừa của B và C là biến cho thuộc tính tổng hợp của B. 
 iii) Ðối với một hành vi, chép mã vào trong bộ phân tích cú pháp, thay thế mỗi 
tham chiếu tới một thuộc tính bởi biến cho thuộc tính đó. 
Ví dụ 5.17: Xét lược đồ dịch cho việc xây dựng cây cú pháp cho biểu thức. Ta thấy 
đó là một văn phạm LL(1) nên phù hợp cho phân tích trên xuống. Với 3 ký hiệu chưa 
kết thúc E, R, T ta xây dựng 3 hàm tương ứng: 
 function E: ↑ syntax - tree - node; /* E không có thuộc tính kế thừa */ 
 function R (i : ↑ syntax - tree - node) : ↑ syntax - tree - node 
 function T : ↑ syntax - tree - node; 
 Dùng token addop biểu diễn cho + và - ta có thể kết hợp hai luật sinh thành một 
luật sinh mới. 
 R Æ addop 
 T {R1.i := mknode(addop.lexeme, R.i, T.nptr) } 
 R1 {R.s := R1.s } 
 R Æ ε {R.s := R.i } 
Ta có hàm R như sau: 
 function R(i : ↑ syntax_ tree_node) : ↑ syntax_tree_node; 
 var nptr, i1, s1, s : ↑ syntax_tree_node; 
 addoplexeme : char; 
 begin 
 if lookahead = addop then 
 begin /* luật sinh R → addop TR */ 
 addoplexeme := lexval; 
 match(addop); 
 nptr := T; 
i1 := mknode(addoplexeme, i, nptr); 
s1 := R(i1); 
s := s1; 
 end 
 else s := i; /* Luật sinh R → ε */ 
 return s; 
 end; 
Hình 5.24 - Xây dựng cây cú pháp đệ quy giảm 
 133
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
5.6. Cho văn phạm sinh ra các dòng text như sau: 
 S → L 
 L → L B | B 
 B → B sub F | F 
 F → { L } | text 
 a) Xây dựng một định nghĩa trực tiếp cú pháp cho văn phạm. 
 b) Chuyển định nghĩa trực tiếp cú pháp trên thành lược đồ dịch. 
 c) Loại bỏ đệ quy trái trong lược đồ dịch vừa xây dựng. 
 135