Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
PHÂN TÍCH CÚ PHÁP TỪ DƯỚI LÊN Phần này sẽ giới thiệu một kiểu phân tích cú pháp từ dưới lên tổng quát gọi là phân tích cú pháp Shift -Reduce. Một dạng dễ cài đặt của nó gọi là phân tích cú pháp thứ bậc toán tử (Operator - Precedence parsing) cũng sẽ được trình bày và cuối cùng, một phương pháp tổng quát hơn của kỹ thuật Shift - Reduce là phân tích cú pháp LR (LR parsing) sẽ được thảo luận. 1. Bộ phân tích cú pháp Shift - Reduce Phân tích cú pháp Shift -. | IV. PHÂN TÍCH CÚ PHÁP TỪ DƯỚI LÊN Phần này sẽ giới thiệu một kiểu phân tích cú pháp từ dưới lên tổng quát gọi là phân tích cú pháp Shift -Reduce. Một dạng dễ cài đặt của nó gọi là phân tích cú pháp thứ bậc toán tử Operator - Precedence parsing cũng sẽ được trình bày và cuối cùng một phương pháp tổng quát hơn của kỹ thuật Shift - Reduce là phân tích cú pháp LR LR parsing sẽ được thảo luận. 1. Bộ phân tích cú pháp Shift - Reduce Phân tích cú pháp Shift - Reduce cố gắng xây dựng một cây phân tích cú pháp cho chuỗi nhập bắt đầu từ nút lá và đi lên hướng về nút gốc. Đây có thể xem là quá trình thu gọn reduce một chuỗi w thành một ký hiệu bắt đầu của văn phạm. Tại mỗi bước thu gọn một chuỗi con cụ thể đối sánh được với vế phải của một luật sinh nào đó thì chuỗi con này sẽ được thay thế bởi ký hiệu vế trái của luật sinh đó. Và nếu chuỗi con được chọn đúng tại mỗi bước một dẫn xuất phải đảo ngược sẽ được xây dựng. Ví dụ 4.12 Cho văn phạm S a A B e A A b c b B d Câu abbcde có thể thu gọn thành S theo các bước sau a b b c d e a A b c d e a A d e 83 a A B e S Thực chất đây là một dẫn xuất phải nhất đảo ngược như sau S rm aABe rm aAde rm aAbcde rm abbcde Dần xuất phải nhất là chuỗi các thay thế ký hiệu chưa kết thúc phải nhất 2. Handle Handle của một chuỗi là một chuỗi con hợp với vế phải của luật sinh và nếu chúng ta thu gọn nó thành vế trái của luật sinh đó thì có thể dẫn đến ký hiệu chưa kết thúc bắt đầu. Ví dụ 4.13 Xét văn phạm sau E E E E E E E E E id Chuỗi dẫn xuất phải E rm E E các handle được gạch dưới rm E E E rm E E id rm E id2 id rm id1 id_2 id3 3. Cắt tỉa handle Handle Pruning Handle pruning là kỹ thuật dùng để tạo ra dẫn xuất phải nhất đảo ngược từ chuỗi ký hiệu kết thúc w mà chúng ta muốn phân tích. Nếu w là một câu của văn phạm thì w Yn. Trong đó Yn là dạng câu phải thứ n của dẫn xuất phải nhất mà chúng ta chưa biết. S Yo Am Y1 Am Y2 . . rmYn-1 rm Yn w Để xây dựng dẫn xuất này theo thứ tự ngược lại chúng ta tìm handle ßn trong Yn và thay thế ßn bởi An An là vế .
