Sintassi e Semantica

Nei linguaggi di programmazione, esistono due aspetti fondamentali: la sintassi e la semantica. Per introdurre questi concetti, è necessario chiarire il concetto di linguaggio, di alfabeto e di stringa; con alfabeto si intende un insieme di simboli, con stringa si intende un raggruppamento di simboli di un certo alfabeto, che hanno un certo significato nell'ambito del linguaggio stesso.
In queste condizioni, la sintassi si occupa di verificare che una certa stringa appartenga o no al linguaggio, mentre la semantica riguarda la generazione di tutte le stringhe di un certo linguaggio.
Per far questo, ci vengono in aiuto diversi strumenti:

• i grafi a stato finito e gli alberi (per la sintassi);
• i sistemi di transizione (per la semantica).

La sintassi: gli automi a stati finiti

I riconoscitori in grado di verificare che una certa stringa appartenga o meno ad un certo linguaggio possono essere definiti come macchina a stati. Questo perché, nel processo di riconoscimento di una stringa, c'è un preciso momento in cui, quando stiamo esaminando un singolo simbolo della stringa, il processo può proseguire nel riconoscimento oppure fermarsi; questi vari momenti vengono chiamati stati.

Il processo di riconoscimento funziona in questo modo: viene presa una certa stringa di simboli del linguaggio, nel primo stato della macchina viene controllato il primo simbolo: se questo trova una o più "vie" verso lo stato successivo, la computazione continua andando a considerare il simbolo successivo e così via. La computazione termina quando i simboli sono finiti e ci troviamo in uno stato finale, possiamo quindi affermare che la stringa fa parte del linguaggio. Quando i simboli sono finiti ma non ci troviamo in uno stato finale, oppure quando il simbolo che esaminiamo no trova una "via" da continuare, la stringa non è riconosciuta.
Formalmente, un automa (macchina a stati) può essere definito con la seguente quintupla: <A, E, S, F, G>, dove A rappresenta l'alfabeto del linguaggio che stiamo considerando, E l'insieme finito degli stati dell'automa, S lo stato iniziale (quindi S appartiene all'insieme E), F l'insieme finito degli stati finale, G ci rappresenta un'associazione tra una coppia ed uno stato, del tipo:
<a, s>-->s1; ovvero se mi trovo nello stato s e sto esaminando il simbolo a, posso continuare la computazione nello stato s1 esaminando il simbolo successivo ad a.

Macchina a stati

Per poter meglio rappresentare il funzionamento dei riconoscitori che abbiamo descritto prima, esiste una speciale rappresentazione grafica che prende il nome di macchina a stati. Questo perché, durante la computazione, è possibile specificare i precisi momenti in cui avviene una transizione; questi particolari momenti nella computazione si chiamano appunti stati.
Vengono utilizzati particolari simboli: nodi per rappresentare stati, archi per rappresentare le transizioni tra due stati.
I nodi sono rappresentati come cerchi, mentre gli archi sono rappresentati come frecce; sia i nodi che gli archi sono etichettati con dei simboli: i nodi sono etichettati con il simbolo dello stato che rappresentano, gli archi sono rappresentati con il simbolo del linguaggio che permette di passare da uno stato precedente ad uno successivo.
Tra i nodi possibili ne esistono due tipi particolari: il nodo di inizio, rappresentato da un arco entrante ma che non proviene da nessun altro nodo rappresenta lo stato iniziale. I nodi terminali o finali sono >= 1 e rappresentano tutti quei possibili stati in cui la computazione può terminare; sono rappresentati da un doppio cerchio.