Algoritmi - Convertire un' espressione regolare in un dfa.

Ciao a tutti spero di aver postato nella sezione giusta.

Sto studiando da autodidatta Il libro "Compilatori Principi, tecniche e strumenti", solo che sono arrivato in una parte(analizzatori lessicali) dove spiega come convertire un'espressione regolare in un dfa, utilizzando le funzioni nullable(n),firstpos(n),lastpos(n) ed followpos(p).

Nel libro c'è scritto:
1)nullable(n): è vera per un nodo dell'albero sintattico se il linguaggio relativo alla sottoespressione rappresentata da n contiene ε. In questo caso la sottoespressione può essere "resa nulla" ovvero può essere fatta coincidere con la stringa vuota anche se in generale la stessa sottoespressione può rappresentare altre stringhe.
2)firstpos(n): è l'insieme delle posizioni del sottoalbero con radice n corrispondenti al primo simbolo di almeno una stringa del linguaggio
descritto dalla sottoespressione con radice n.
3)lastpos(n): è l'insieme delle posizioni nel sottoalbero nel sottoalbero con radice n corrispondenti all'ultimo simbolo di almeno una stringa del linguaggio descritto dalla sottoespressione con radice n.
4)followpos(p): per una posizione p, è l'insieme delle posizioni q nell'intero albero sintattico tali che esiste unastringa x=A1 A2 ... An
nel linguaggio L((r)#) tale che per qualche valore di i c'è un modo di giustificare l'appartenenza di x a L((r)#) per cui a: corrisponde alla posizione p nell'albero sintattico e Ai+1 corrisponde alla posizione q.

L'espressione regolare di esempio è: (a|b)*abb# ed il suo albero sintattico è nell'immagine allegata(firstpos(n) a sinistra del nodo e lastpos(n) a destra del nodo).
Quello che non riesco a capire è come si calcolano, avendo già pronto l'albero sintattico, le funzioni firstpos(n), lastpos(n) e followpos(n).
Grazie in anticipo .

In che senso "come si calcolano"? Sono delle funzioni... sono definite in una certa maniera. Niente calcoli.

Grazie per la risposta. Quello che non capisco è come ad esempio la funzione firstpos(n) "lavora" sull'albero sintattico. Ad esempio perchè la funzione firstpos(n) restituisce {1,2,3} per il nodo-cat dell'espressione (a|b)*a ?

Fare un diagramma per il DFA e' solitamente un buon modo per visualizzare cosa sta succedendo.

(Vedi allegato).

In pratica firstpos ritorna l'insieme dei possibili stati della prima "posizione" dell'espressione (a|b)*a.

Prova a pensare un po' qual'e' una stringa valida per l'espressione:
- Una stringa deve almeno contenere una "a" per essere valida (0 (a|b) e 1 a).
- Ogni stringa che contiene una "a", o una "b", o una combinazione di "a" e "b" (anche solo di "a" oppure solo di "b" e che termina in "a" e' valida.
- Una stringa vuota non e' un'espressione valida.

Quindi esempi validi sono:
a
aa
ba
aba
aaa
aaba
abba

ecc.

Partendo dallo stato 1, se incontriamo una "b" possiamo andare nello stato 2. Se incontriamo una "a" possiamo andare allo stato 3 (e a quel punto la stringa e' valida). Da 2 torniamo sempre a 1 e da 3 possiamo tornare a 1. C'e' un minimo di 3 stati (1,2,3) per rappresentare quest'espressione in un DFA. Nel momento in cui una stringa raggiunge lo stato 3, e' valida per l'espressione (a|b)*a.

Ad esempio usando abba come input:

Stato 1, "a" e' il primo carattere, vado a 3.
Da 3 torno a 1.
"b" e' il prossimo carattere, vado a 2.
Da 2 vado a 1.
"b" e' il prossimo carattere, vado a 2.
Da 2 vado a 1.
"a" e' il prossimo carattere, vado a 3.

Non ci sono piu' caratteri nella stringa e sono nello stato 3. abba e' una stringa valida.

Penso era questa la tua domanda.

Grazie mille adesso ho capito, hai spiegato benissimo. Ciao .