Tài liệu trình biên dịch C (ĐH Cần Thơ) part 16

Chia sẻ: Mr Yukogaru | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

83
lượt xem 12
download

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

ÐÁ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ử...

Chủ đề:

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

Lưu

Nội dung Text: Tài liệu trình biên dịch C (ĐH Cần Thơ) part 16

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
= X.x. Sau khi rút gọn, top bị giảm 2 đơn vị, A nằm trong state[top] và thuộc tính tổng hợp nằm trong val[top]. State val ... ... Mỗi ô trong stack là một con trỏ trỏ tới X X.x bảng phân tích LR(1). Nếu phần tử thứ I của stack là ký hiệu A thì val[i] là giá trị Y Y.y thuộc tính kết hợp với A. Z Z.z Stack top Hình 5.12 - Stack phân tích cú pháp vào một trường lưu giữ thuộc tính tổng hợp 2. Ví dụ Ví dụ 5.10: Xét định nghĩa trực tiếp cú pháp: Luật sinh Luật ngữ nghĩa L En print(E.val) E E1 + T E.val := E1.val + T.val E T E.val := T.val T T1 * F T.val := T1.val * F.val T F T.val := F.val F (E) F.val := E.val F digit F.val := digit.lexval Với biểu thức 3 * 5 + 4 n ta có cây chú thích: L E.val = 19 n E.val = 15 + T.val = 4 T.val = 15 F.val = 4 T.val = 3 * F.val = 5 digit.lexval = 4 F.val = 3 digit.lexval = 5 digit.lexval = 3 125
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+4n _ _ *5+4n 3 3 *5+4n F 3 F digit *5 + 4 n T 3 T F 5+4n T* 3- +4n T*5 3-5 +4n T*F 3-5 F digit +4n T 15 T T*F +4n E 15 E T 4n E+ 15 - n E+4 15 - 4 n E+F 15 - 4 F digit n E+T 15 - 4 T F 126
n E 19 E E+T En 19 - L 19 L En Hình 5.15- Các phép chuyển được tạo ra bởi bộ thông dịch trên chuỗi nhập 3* 5+4n IV. ÐỊNH NGHĨA L_THUỘC TÍNH 1. Ðịnh nghĩa L_thuộc tính. Mỗi định nghĩa trực tiếp cú pháp là một định nghĩa L thuộc tính nếu mỗi một thuộc tính kế thừa của Xi (1
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 } ai 2 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.ps := 10 S.ht := B.ht B B1B2 B1.ps := B.ps B B2.ps := B.ps B B.ht := max(B1.ht, B2.ht) B B1 sub B2 B1.ps := B.ps B B2.ps := shrink(B.ps) B B.ht := disp(B1.ht, B2.ht) B text 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 {B2.ps := B.ps } B B2 {B.ht := max(B1.ht, B2.ht ) } 129
B {B1.ps := B.ps } B1 sub {B2.ps := shrink(B.ps) } B 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 } 130