Làm cách nào để sử dụng thuật toán của Warshall cho việc đóng cửa chuyển tiếp để xác định đóng cửa phân tích cú pháp LR (1) chuẩn tắc?

Question

Tôi đang cố gắng triển khai thuật toán của Warshall để tính nhanh các kết quả LR (1).

tôi nghĩ Tôi hiểu cách thức hoạt động cho LR (0):

• Các nút của đồ thị là LR items, như A → B • C
• Các cạnh là "chuyển tiếp" bắt đầu từ A → B • C để C → • D

Vấn đề là, LR (1) yêu cầu tính toán các lookaheads và tôi không thể tìm ra cách kết hợp chúng vào algori thm.
Dường như với tôi rằng ngay cả khi tôi biết việc đóng cửa chuyển tiếp của bất kỳ mục LR nào, tôi vẫn cần phải thực hiện tất cả tính toán giống nhau để tìm hiểu xem bộ tính năng được đặt cho từng mục là gì.

Thậm chí có thể sử dụng thuật toán của Warshall để tính toán các đóng gói LR (1) hay chỉ có thể cho các trường hợp bị hạn chế hơn (như LR (0), SLR (1), v.v.)?

Answer 1

Tôi không nghĩ bạn có thể sử dụng thuật toán của Warshall cho điều này, bởi vì mỗi lần bạn thêm một mục mới, bạn có thể phải thêm các mục khác. Đó là một quá trình lặp đi lặp lại. Đồ thị có hướng hoặc ma trận kết nối sẽ tiếp tục thay đổi. Tôi có thể sai về điều này. Tôi tính toán việc đóng LR (1) mục với một quá trình lặp lại trong khi vẫn giữ một loạt các mục đã được bao gồm trong bộ đóng. Bạn có thể tải xuống LRSTAR Parser Generator của tôi và xem mã nguồn nếu bạn muốn. Bạn có thể quyết định rằng bạn không cần phải viết trình tạo trình phân tích cú pháp của riêng bạn và sử dụng LRSTAR. Lưu ý: Tôi đã sử dụng thuật toán Digraph từ giấy của DeRemer, thay vì các thuật toán của Warshall, để tính toán các bộ nhìn phía trước. Xem list of papers implemented in LRSTAR on the website.