21/1/2010 Phân tích tiền định Tư tưởng chính của phân tích cú pháp trên xuống : Bắt đầu từ gốc, phát triển xuống các nút cấp dưới Chọn một sản xuất và thử xem có phù hợp với xâu vào không Có thể quay lui „ Có thể tránh được quay lui? Cho sản xuất A → α | β bộ phân tích cú pháp cần chọn giữa α và β „ Làm thế nào? Cho ký hiệu không kết thúc A và ký hiệu xem trước t, sản xuất nào của A chắc chắn sinh ra một xâu bắt đầu bởi t? „ Bài 7 Phân tích cú pháp tiền định 1 Phân tích tiền định Phân tích tiền định „ Nếu có hai sản xuất: A→α⏐β , ta mong muốn „ Tính FIRST(X): có một phương pháp rõ ràng để chọn đúng sản xuất cần thiết „ Định nghĩa: Nếu X là ký hiệu kết thúc FIRST(X)={X} Nếu X→ε là một sản xuất thì thêm ε vào FIRST(X) Nếu X là ký hiệu không kết thúc và X→Y1Y2...Yn là một sản xuất , thêm FIRST(Yi+1) vào FIRST(X) nếu FIRST(Yj) chứa ε Với α là một xâu chứa ký hiệu kết thúc và không kết thúc, x ∈ FIRST(α) nếu từ α có thể suy dẫn ra xγ (x chứa 0 hoặc 1 ký hiệu) „ Nếu FIRST(α) và FIRST(β) không chứa ký hiệu chung ta biết phải chọn A→α hay A→β khi đã xem trước một ký hiệu 2 3 4 fb.com/groups/ 1 21/1/2010 Phân tích tiền định Tính FOLLOW „ Điều gì xảy ra nếu ta có sản xuất để chọn là FOLLOW(S) chứa EOF Với các sản xuất dạng A→αBβ, mọi ký hiệu trong FIRST(β) trừ ε tham gia vào FOLLOW(B) Với các sản xuất dạng A→αB hoặc A→αBβ trong đó FIRST(β) chứa ε, FOLLOW(B) chứa mọi ký hiệu của FOLLOW(A) A→α với α=ε hoặc α⇒*ε? „ Có thể mở rộng nếu ta biết rằng có một dạng câu mà ký hiệu đang xét xuất hiện sau A „ Định nghĩa: Với A là ký hiệu không kết thúc, x∈FOLLOW(A) nếu và chỉ nếu Scó thể suy dẫn ra αAxβ 5 Phân tích tiền định Bảng phân tích tiền định „ Với các khái niệm „ Dùng cho bộ sinh phân tích cú pháp FIRST FOLLOW „ Căn cứ „ Ta có thể xây dựng bộ phân tích cú pháp mà không đòi hỏi quay lui „ Chỉ có thể xây dựng bộ phân tích cú pháp như vậy cho những văn phạm đặc biệt „ Loại văn phạm như vậy bao gồm văn phạm một số ngôn ngữ lập trình đơn