Jak używać algorytmu Warshall do przechodzenia w tryb przechodni w celu określenia zamknięć kanonicznych LR (1)?

Question

Próbuję wdrożyć algorytm Warshall, aby szybko obliczyć zamknięcia LR (1).

myślę rozumiem jak to działa dla LR (0):

• Węzły grafu są LR items, jak A → B • C
• Krawędzie są "przejścia", począwszy od A → B • C do C → • D

Problem polega na tym, że LR (1) wymaga obliczenia wyprzedzającego i nie mogę wymyślić, jak włączyć je do algorytmu thm.
Wydaje mi się, że , nawet jeśli znam, przechodnie zamknięcie dowolnego elementu LR I nadal musi przejść przez te same obliczenia tylko po to, aby dowiedzieć się, co to jest wcześniej ustawiony dla każdego elementu.

Czy możliwe jest wykorzystanie algorytmu Warshall do obliczania zamknięć LR (1) kanonicznych, czy jest to możliwe tylko w przypadku bardziej ograniczonych przypadków (takich jak LR (0), SLR (1) itp.)?

Answer 1

Nie sądzę, że można użyć do tego algorytmu Warshall, ponieważ za każdym razem, gdy dodajesz nowy element, może być konieczne dodanie innych elementów. To proces iteracyjny. Kierowany wykres lub macierz łączności będą się zmieniać. Mogę się mylić. Obliczyłem zamknięcie zestawów przedmiotów LR (1) procesem iteracyjnym, zachowując szereg elementów już zawartych w zestawie zamknięcia. Możesz pobrać mój LRSTAR Parser Generator i zajrzeć do kodu źródłowego, jeśli chcesz. Możesz zdecydować, że nie musisz pisać własnego generatora analizatora składni i używać LRSTAR. Uwaga: Użyłem algorytmu Digraph z artykułu DeRemera, zamiast algorytmów Warshall, do obliczania zestawów wyprzedzających. Zobacz list of papers implemented in LRSTAR on the website.