Il metodo è descritto in Dragon Book, tuttavia ne ho letto in "" Parsing Techniques "di D.Grune e C.J.H.Jacobs".
Comincio dalla mia comprensione della creazione di canali per NFA:
-
I canali
- vengono creati una volta, sono come canali d'acqua con corrente
- tu "rilascia" i simboli lookahead nelle giuste posizioni (fonti) del canale e si propagano con "corrente"
- quando il simbolo si propaga, non ci sono barriere (le sole cose sufficienti per la propagazione sono la presenza di canale e direzione / corrente); vale a dire lookahead non può morire dal nulla
È giusto?
Se sono corretto, allora eof lookahead dovrebbe essere presente in tutti gli stati, perché la fonte è la produzione iniziale e tutti gli altri stati di produzione sono raggiungibili dallo stato iniziale.
Il modo in cui il DFA è ricavato da questo NFA non è perfettamente chiaro per me - gli autori del libro menzionato scrivono sulla conservazione dei canali, ma non vedo alcuno scopo, se propagassi i tuoi punti di vista. Se i canali devono essere preservati, vengono interrotti dall'origine se lo stato di DFA non include lo stato NFA di origine? Suppongo di no - i canali continuano a funzionare tra gli stati DFA, non solo all'interno dello stato DFA specificato.
Nell'effetto eof dovrebbe essere ancora presente in tutti gli articoli in tutti gli stati. Ma quando dai un'occhiata a DFA presentato nel libro (pdf è da errata):
DFA per LALR (figura 9.34 nel libro, p.301)
vedrai che ci sono elementi senza eof in lookahead.
La grammatica di questo DFA è:
S -> E
E -> E - T
E -> T
T -> ( E )
T -> n
Quindi come è stato calcolato, quando eof è stato eliminato e in quali condizioni?
Aggiornamento
È pdf testuale, quindi due stati interessanti (in DFA; # è eof ):
Stato 1:
S--- >•E[#]
E--- >•E-T[#-]
E--- >•T[#-]
T--- >•n[#-]
T--- >•(E)[#-]
Stato 6:
T--- >(•E)[#-)]
E--- >•E-T[-)]
E--- >•T[-)]
T--- >•n[-)]
T--- >•(E)[-)]
L'arco da 1 a 6 è etichettato ( .