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

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 A A1 Y X { := g(, ) } { := f() } Ðâ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. | 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 Al Y g A A X f Đâ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 s Bổ sung hành vi ngữ nghĩa cho văn phạm ta được lược đồ dịch A X f R R Y g R1 R s Ví dụ Xét lược đồ dịch của văn phạm đệ quy trái cho biểu thức. E E1 T E E1 - T - E T 130 T E T num Hình - 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 R T R1 R -Ạ - T R - R1 R s T E T num Hình - Lược đồ dịch đã được chuyển đổi có văn phạm đệ quy phải Chẳng hạn đánh giE biểu thức 9 - 5 2 9 í b 9 9 - 4 . 5 f TÍvOl 2 ---- 6 2 s Hình - Xác định giá trị của biểu thức 9-5 2 Ví du Xét lược đồ dịch xây dựng cây cú pháp cho biểu thức E E1 T E E1 - T E T mknode mknode - T E T id mkleaf id 131 T num mkleaf num Á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 R T mknode Ri R -Ạ - T mknode - Ri R s T E T id mkleaf id T num mkleaf num Hình - 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