Espressioni regolari to DFA

[hamming_burst]

Salve,
nel DragonBook si fa un esempio di algoritmo che calcola un DFA direttamente da un'espressione regolare.
Per far ciò bisogna creare un albero sintattico (decorato) e aggiungendo un terminale # alle espressioni.

L'algoritmo lavora su questo albero sintattico, ed utilizza 4 funzioni aggiuntive:
- followpos()
- nullable()
- firstpos()
- lastpos()

ora, non riesco a capire che diavolo fanno queste funzioni. Sono legate alla posizione dell'albero sintattico e al linguaggio validato dell'espressione regolare in esame.
Qualcuno che ha studiato questo algoritmo mi farebbe un piacere a farmi un mini-sunto del significato di quelle funzioni...


Ringrazio

[Rggb1]

Non ho visto l'algoritmo, ma dovrebbe essere equivalente a creare l'automa (Thompson) e poi trasformarlo in DFA minimo, "all in one step"... La cosa mi incuriosisce, puoi metterlo/descriverlo qui?

[hamming_burst]

L'algoritmo sì è interessante da un punto di vista di analisi si evita di passare per più algoritmi, ma operativamente è piuttosto complicato...almeno per quanto lo ho visto finora (lo ho saltato).
Cercando gli autori è stato creato da "McNaughton-Yamada" e perfezionato da Aho. la versione del libro è quella di Aho.

Questo algoritmo non dovrebbe creare DFA minimi direttamente, ma non ho approfondito ancora...

Ma ora, non riprenderò in mano Linguaggi Formali per qualche giorno, perciò se ti va bene, riprendiamo il discorso in quel momento

Comunque, se vuoi dare un'occhiata all'algoritmo e a quelle funzioni, misi una copia del libro qui
l'algoritmo è il 3.36 "Converting a regular expression directly to DFA" pag. 179

Ti ringrazio, intanto, della disponibilità