Come utilizzare l'algoritmo di Warshall per la chiusura transitiva per determinare le chiusure di parser LR (1) canoniche?

Question

Sto cercando di implementare l'algoritmo di Warshall per calcolare rapidamente le chiusure LR (1).

I pare capisco come funziona per LR (0):

• I nodi del grafo sono LR items, come A → B • C
• I bordi sono "transizioni" a partire da A → B • C a C → • D

Il problema è che LR (1) richiede il calcolo dei lookaheads e non riesco a capire come incorporarli negli algori THM.
Mi sembra che anche se conosca la chiusura transitiva di un dato articolo LR I ancora necessità di passare attraverso lo stesso calcolo solo per capire quale sia il set di lookahead impostato per ciascun articolo.

È persino possibile utilizzare l'algoritmo di Warshall per calcolare le chiusure LR (1) canoniche, oppure è possibile solo per casi più limitati (come LR (0), SLR (1), ecc.)?

Answer 1

Non penso che sia possibile utilizzare l'algoritmo di Warshall per questo, perché ogni volta che si aggiunge un nuovo elemento, potrebbe essere necessario aggiungere altri elementi. È un processo iterativo. Il grafico diretto o la matrice di connettività continuerebbe a cambiare. Potrei sbagliarmi su questo. Ho calcolato la chiusura di serie di articoli LR (1) con un processo iterativo mantenendo una serie di elementi già inclusi nel set di chiusura. Puoi scaricare il mio LRSTAR Parser Generator e guardare il codice sorgente, se lo desideri. Potresti decidere di non dover scrivere il tuo generatore di parser e utilizzare LRSTAR. Nota: ho usato l'algoritmo Digraph dal documento di DeRemer, invece degli algoritmi di Warshall, per il calcolo dei set look-ahead. Vedi lo list of papers implemented in LRSTAR on the website.