Materia:Fondamenti di programmazione
Da Wikiversità, l'università aperta.
Per l'elenco completo degli stub, vedi la relativa categoria
Questa pagina contiene il testo delle lezioni legate alla materia generale, per una più agevole lettura necessita di essere divisa in lezioni.
Per una lista completa delle materie da suddividere in lezioni, consulta la relativa categoria.
| Fondamenti di programmazione | ||
 Facoltà di Scienze matematiche, fisiche e naturali |
SSD = ING-INF/05 |
 Corso di Informatica |
|
Presentazione |
Programma 
|
|
Risorse |
Verifiche d'apprendimento  È possibile, e fortemente consigliato, integrare le lezioni e valutare la propria preparazione attraverso queste esercitazioni. È possibile verificare la conoscenza di un argomento specifico o dell'intero programma.
|
|
Utenti interessati |
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 strighe 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, e quindi possiamo 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; in questi ultimi due casi, 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 stò 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 chiamana 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 freccie; sia i nodi che gli archi sono etichettati con dei simboli, ovvero i nodi sono etichettati con il simbolo dello stato che rappresentano, gli archi sono rappresentati con l simbolo del linguaggio che permette di passare da uno stato precedente ad uno successivo.
Tra i nodi possibili, esistono due tipi di nodi particolari: il nodo di inizio, rappresentato da un arco entrante ma che non proviene da nessun altro nodo; questo nodo ci rappresenta lo stato iniziale. I nodi terminali o finali sono >=1, e ci rappresentano tutti quei possibili stati in cui la computazione può terminare, e sono rappresentati da un doppio cerchio.
