Tham khảo tài liệu 'toán rời rạc ứng dụng trong tin học part 10', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Phấn IV. NGÔN NGỬ HÌNH THỨC 369 Vậy xyyz e L G và cây dẫn xuất trái Top - Down có dạng Xâu xyyz e L G đoán nhận được bởi phương pháp phân tích tất định. . Các hàm FIRST FOLLOW Phân tích Top - Down đòi hỏi vãn phạm không có đệ quy trái vì nếu có thì ta có thể dùng thuật toán để xoá đệ quy trái tức là thay quy tắc độ quy trái bằng quy tắc không đệ quy trái nhưng văn phạm vẫn tương đương . Đối với phân tích tất định người ta chỉ sử dụng văn phạm không đệ quy trái và không nhập nhầng. Thế nào là vãn phạm không nhập nhằng Ta xét ví dụ vể văn phạm sau đây Cho G E A I R trong đó L x y z A I A B R I AIB A - xAly B - xBlz Đoán nhận xâu vào XXXZ L G hay không Stack Input Output Cây dẫn xuất 1 xxxzS 1 SA xxxzS 1- A A Ax xxxzS A- xA SA xxz X A Ax xxz A- xA SA xz X A SAx XZ A- xA A z X A 24-TOÀN RÓI RẠC 370 TOÁN RƠI RẠC ỨNG DỤNG TRONG TIN HỌC Cây dẫn xuất trên không phải là cây dẵn xuất Top - Down vì lá có chứa A e Á của XXXZ. Vì không có quy tắc A z nêh việc đoán nhận không thực hiện được và thuật toán dừng lại không cho kết quả. Tuy nhiên nếu ta đoán nhận theo trình tự sau đây thì thực hiện được Cây dẫn xuất trên là cầy dẫn xuất Top - Down của xâu XXXZ. Hiện tượng trên gọi là hiện tượng quay lui Back - tracking . Văn phạm có hiện tượng quay lui khi áp dụng phương pháp Top - Down cũng gọi là văn phạm nhập nhằng. Làm thế nào dể biết được một văn phạm phi ngữ cảnh là không nhập nhằng. Muốn giải quyết điểu đó ta cần đưa vào khái niệm hàm FIRST và FOLLOW. Định nghĩa hàm FIRST Giả sử trong văn phạm có quy tắc dạng A . I k. Khi đó ta định nghĩa First A tập các ký hiệu kết thúc ở vị trí đầu tiên của xâu có thể dẫn xuất được từ ị i 1 k . Nếu A Ạ thì A e First A . Cách tính hàm First 1 Nếu a e s 2 e S u A thì First a2 aỊ. k 2 Nếu A I k thì First A jFirst . i l Phán IV. NGÔN NGỮ HÌNH THỨC 371 Định nghĩa hàm Follow Follow A tập các ký hiệu kết thúc A mà chúng có thể xuất hiện ngay bên phải A ở trong một số dạng câu tức là tập các ký hiệu kết thúc a sao cho tại dẫn xuất dạng I - aAap .
