21/1/2010 Bài toán phân tích cú pháp Bài 6 Bài toán đặt ra Cho văn phạm phi ngữ cảnh G và xâu w w ∈ L(G) đúng hay sai? Phân tích cú pháp trên xuống có quay lui Phân tích trên xuống (top down) S ⇒* w? 1 2 Phân tích trái w đúng cú pháp ⇒cây cú pháp E -> E + T E -> T T -> T * F T -> F F -> ( E ) F -> ident „ Phân tích trái của α là dãy các sản xuất được sử dụng trong suy dẫn trái ra α từ S „ Phân tích là danh sách các số từ 1 đến p Biểu diễn cây cú pháp bằng cách nào? 3 4 fb.com/groups/ 1 21/1/2010 Ví dụ „ Giải thuật phân tích top down quay lui Xét văn phạm G, các sản xuất được đánh số như sau „ 1.E → T+E 2.E → T 3.T → F* T 4.T → F 5.F → (E) 6.F → a „ Tư tưởng chủ yếu của giải thuật là xây dựng cây phân tích cú pháp (cây suy dẫn) cho xâu w „ Đánh số thứ tự các sản xuất có cùng vế phải, như vậy, các A - sản xuất của văn phạm sẽ được xếp thứ tự A → α1 | α2 | . . . .| αn Phân tích trái của xâu a*(a+a) là 23645124646 5 Nút hoạt động là ký hiệu không kết thúc A Mô tả giải thuật „ Bắt đầu từ nút gốc S „ Chọn vế phải đầu tiên của A- sản xuất : X1X2. . . .Xk. „ Tạo k nút con trực tiếp của A với nhãn „ Nút S được coi là nút hoạt động X1, X2, . . . .Xk. „ Nút hoạt động là nút nhãn X1. „ Nếu k = 0, (sản xuất A → ε) thì nút hoạt động sẽ là nút „ Tạo ra các nút con một cách đệ quy bên phải (ngay sau) A khi duyệt cây theo thứ tự trái 7 6 8 fb.com/groups/ 2 21/1/2010 Nút được xét có nhãn là ký hiệu kết thúc a Điều kiện để thực hiện giải thuật „ So sánh với ký hiệu đang xét. Nếu trùng với ký hiệu đang xét thì chuyển đầu đọc sang phải 1 ô, chuyển sang xét nút bên phải. Nếu a không trùng với ký hiệu đang xét thì quay lui tới nút mà tại đó đã sử dụng sản xuất trước (Thay thế một ký hiệu không kết thúc (chẳng hạn A) bằng vế phải một sản xuất). Chuyển đầu đọc sang trái (nếu cần) và thử với lựa chọn tiếp theo. Nếu không còn lựa chọn nào khác thì quay lui tới bước trước đó „ Văn phạm G cần thoả điều kiện khôn