khoanguyenkind
New Member
Chia sẻ miễn phí cho các bạn tài liệu
. Tóm tắt
Giải thuật Earley là một giải thuật cơ bản, được sử dụng tương đối rộng rãi trong các hệ thống phân tích cú pháp. Tuy nhiên, giải thuật này vẫn còn hạn chế như sinh ra quá nhiều luật dư thừa trong quá trình phân tích. Trong bài này, chúng tui đề xuất ra phương pháp phân tích cú pháp theo giải thuật Earley.
Giải thuật Earley là một trong những giải thuật được sử dụng phổ biến trong việc xây dựng các hệ thống phân tích cú pháp. Giải thuật này sử dụng chiến lược phân tích kiểu trên xuống (top-down), bắt đầu với một ký hiệu không kết thúc thay mặt cho câu và sử dụng các luật khai triển cho đến khi thu được câu vào. Hạn chế của cách tiếp cận này là không chú trọng nhiều đến các từ đầu vào. Vì vậy trong quá trình phân tích, giải thuật Earley sản sinh ra rất nhiều luật dư thừa.Ngoài ra, giải thuật Earley được xây dựng cho tiếng Anh nên khi áp dụng cho tiếng Việt sẽ có hạn chế. Mỗi câu vào tiếng Anh chỉ có một cách tách từ, trong khi với tiếng Việt, mỗi câu vào có thể có nhiều cách tách từ khác nhau. Với đặc điểm đầu vào của giải thuật Earley chỉ là một câu với một cách tách, bộ phân tích cú pháp sẽ phải thực hiện lặp đi lặp lại giải thuật này cho từng trường hợp tách từ đối với tiếng Việt. Để giải quyết vấn đề này, chúng tui nhận thấy trong các cách tách từ Việt tồn tại các cặp cách tách giống nhau ở danh sách các từ loại đầu tiên và chỉ khác nhau ở phần đuôi của chúng.
Giải thuật Earley cơ bản, giúp người đọc có thể hình dung một cách khái quát về giải thuật này.
2. Giải thuật Earley
Giải thuật Earley cơ bản được phát biểu như sau:
Đầu vào: Văn phạm G = (N, T, S, P), trong đó:
• N: tập kí hiệu không kết thúc.
• T: tập kí hiệu kết thúc.
• S: kí hiệu không kết thúc bắt đầu.
• P: tập luật cú pháp.
Xâu vào w = a1a2 ... an.
Đầu ra: Phân tích đối với w hay "sai".
Kí hiệu:
• α, β, γ biểu diễn xâu chứa các kí hiệu kết thúc, không kết thúc hay rỗng.
• X, Y, Z biểu diễn các kí hiệu không kết thúc đơn.
• a biểu diễn kí hiệu kết thúc.
Earley sử dụng cách biểu diễn luật thông qua dấu chấm “• ”
X→ α • β có nghĩa :
• Trong P có một luật sản xuất X→ α β.
• α đã được phân tích.
• β đang được chờ phân tích.
• Khi dấu chấm “ • ” được chuyển ra sau β có nghĩa đây là một luật hoàn thiện. Thành phần X đã được phân tích đầy đủ, ngược lại nó là một luật chưa hoàn thiện.
Đối với mỗi từ thứ j của xâu đầu vào, bộ phân tích khởi tạo một bộ có thứ tự các trạng thái S(j).
Mỗi bộ tương ứng với một cột trong bảng phân tích. Mỗi trạng thái có dạng (X → α • β, i), thành phần sau dấu phẩy xác định rằng luật này được phát sinh từ cột thứ i.
a.Khởi tạo
• S(0) được khởi tạo chứa ROOT → • S.
• Nếu tại bộ cuối cùng ta có luật (ROOT → S•, 0) thì có nghĩa xâu vào được phân tích thành công.
b. Thuật toán
Thuật toán phân tích thực hiện 3 bước: đoán (Predictor), Duyệt (Scanner), và Hoàn thiện (Completer) đối với mỗi bộ S(j).
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
. Tóm tắt
Giải thuật Earley là một giải thuật cơ bản, được sử dụng tương đối rộng rãi trong các hệ thống phân tích cú pháp. Tuy nhiên, giải thuật này vẫn còn hạn chế như sinh ra quá nhiều luật dư thừa trong quá trình phân tích. Trong bài này, chúng tui đề xuất ra phương pháp phân tích cú pháp theo giải thuật Earley.
Giải thuật Earley là một trong những giải thuật được sử dụng phổ biến trong việc xây dựng các hệ thống phân tích cú pháp. Giải thuật này sử dụng chiến lược phân tích kiểu trên xuống (top-down), bắt đầu với một ký hiệu không kết thúc thay mặt cho câu và sử dụng các luật khai triển cho đến khi thu được câu vào. Hạn chế của cách tiếp cận này là không chú trọng nhiều đến các từ đầu vào. Vì vậy trong quá trình phân tích, giải thuật Earley sản sinh ra rất nhiều luật dư thừa.Ngoài ra, giải thuật Earley được xây dựng cho tiếng Anh nên khi áp dụng cho tiếng Việt sẽ có hạn chế. Mỗi câu vào tiếng Anh chỉ có một cách tách từ, trong khi với tiếng Việt, mỗi câu vào có thể có nhiều cách tách từ khác nhau. Với đặc điểm đầu vào của giải thuật Earley chỉ là một câu với một cách tách, bộ phân tích cú pháp sẽ phải thực hiện lặp đi lặp lại giải thuật này cho từng trường hợp tách từ đối với tiếng Việt. Để giải quyết vấn đề này, chúng tui nhận thấy trong các cách tách từ Việt tồn tại các cặp cách tách giống nhau ở danh sách các từ loại đầu tiên và chỉ khác nhau ở phần đuôi của chúng.
Giải thuật Earley cơ bản, giúp người đọc có thể hình dung một cách khái quát về giải thuật này.
2. Giải thuật Earley
Giải thuật Earley cơ bản được phát biểu như sau:
Đầu vào: Văn phạm G = (N, T, S, P), trong đó:
• N: tập kí hiệu không kết thúc.
• T: tập kí hiệu kết thúc.
• S: kí hiệu không kết thúc bắt đầu.
• P: tập luật cú pháp.
Xâu vào w = a1a2 ... an.
Đầu ra: Phân tích đối với w hay "sai".
Kí hiệu:
• α, β, γ biểu diễn xâu chứa các kí hiệu kết thúc, không kết thúc hay rỗng.
• X, Y, Z biểu diễn các kí hiệu không kết thúc đơn.
• a biểu diễn kí hiệu kết thúc.
Earley sử dụng cách biểu diễn luật thông qua dấu chấm “• ”
X→ α • β có nghĩa :
• Trong P có một luật sản xuất X→ α β.
• α đã được phân tích.
• β đang được chờ phân tích.
• Khi dấu chấm “ • ” được chuyển ra sau β có nghĩa đây là một luật hoàn thiện. Thành phần X đã được phân tích đầy đủ, ngược lại nó là một luật chưa hoàn thiện.
Đối với mỗi từ thứ j của xâu đầu vào, bộ phân tích khởi tạo một bộ có thứ tự các trạng thái S(j).
Mỗi bộ tương ứng với một cột trong bảng phân tích. Mỗi trạng thái có dạng (X → α • β, i), thành phần sau dấu phẩy xác định rằng luật này được phát sinh từ cột thứ i.
a.Khởi tạo
• S(0) được khởi tạo chứa ROOT → • S.
• Nếu tại bộ cuối cùng ta có luật (ROOT → S•, 0) thì có nghĩa xâu vào được phân tích thành công.
b. Thuật toán
Thuật toán phân tích thực hiện 3 bước: đoán (Predictor), Duyệt (Scanner), và Hoàn thiện (Completer) đối với mỗi bộ S(j).
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links