|
|
Un LINGUAGGIO DI PROGRAMMAZIONE è definito dalla sintassi (punto di vista formale), dalla semantica (significato), e dall'uso (tecniche di programmazione, astrazioni procedurali e sui dati).
ALGORITMO: sequenza di azioni che risolvono il problema. Ogni azione deve essere svolgibile in tempo finito e l'algoritmo deve avere una sequenza finita di comandi.
PROGRAMMA: descrizione di un algoritmo, cioè dei metodi da seguire per risolvere un problema.
I COMANDI sono le azioni che modificano lo stato corrente su cui sono applicate,
Uno STATO è un insieme di associazioni (nome, valore) oppure nome valore. I comandi modificano lo stato corrente sul quale vengono applicati.
DEFINIZIONE RICORSIVA di un algoritmo: definizione dell'algoritmo in termini di se stesso (ex. La funzione fattoriale: f(x) = 1 se x = 0; f(x) = x* f(x-1) se x >0).
SINTASSI del linguaggio: può essere definita sotto due aspetti diversi. Il modo riconoscitivo (attraverso gli automi a stati finiti) e quello generativo (attraverso le grammatiche).
AUTOMI A STATI FINITI: strutture matematiche con un determinato numero di stati ed archi che rappresentano le possibili transizioni fra uno stato e l'altro. Sono strumenti che ci permettono di verificare se una frase è sintatticamente corretta , poiché un automa riconosce tutte le stringhe appartenenti al linguaggio per cui è stato costruito.
LINGUAGGIO = dizionario + sintassi.
DIZIONARIO = alfabeto di simboli, insieme che contiene le basi per costruire le fasi del linguaggio.
STRINGA: sequenza finita di simboli appartenenti ad un determinato alfabeto. Una stringa è riconosciuta da un automa se e solo se esiste una sequenza di stati So, S1, . , Sn tali che So è stato iniziale e Sn stato d'accettazione ed esiste una transizione tra uno stato e l'altro tale che ci porti dallo stato iniziale fino allo stato d'accettazione.
AUTOMI DETERMINISTICI: automi che hanno per ogni stato, al più un solo arco uscente con la stessa etichetta. Sono un sottoinsieme degli automi non deterministici.
AUTOMI NON DETERMINISTICI: automi che possono avere per ogni stato anche più di un arco uscente con la medesima etichetta. Per alcuni di essi possiamo trovare l'equivalente automa deterministico grazie alla tecnica dei sottoinsiemi.
GRAMMATICHE LIBERE DA CONTESTO: strumenti matematici formali che ci permettono di definire la sintassi dei linguaggi con l'approccio generativo. Una grammatica di un linguaggio può infatti generare, attraverso grafi detti alberi di derivazione, tutte le stringhe appartenenti a quel linguaggio. Si dicono libere da contesto perché le categorie sintattiche possono espandersi indipendentemente dai simboli terminali, ovvero il contesto, che sta loro intorno. Le componenti di una grammatica sono l'alfabeto (o insieme dei simboli terminali), le categorie sintattiche ( o simboli non terminali), le quali possono espandersi liberamente. La categoria sintattica con cui inizia una grammatica è detto simbolo iniziale o simbolo distinto. Ciascuna definizione presente nella grammatica è detta produzione.
GRAFO CON STRUTTURA AD ALBERO: serve per definire le stringhe del linguaggio generate da una grammatica. Esso è : aciclico, ogni nodo ha al più un arco entrante, il nodo che non ha nessun arco entrante è detto radice. I nodi che non hanno nessun arco uscente sono detti foglie e contengono esclusivamente simboli terminali. Quindi una stringa a appartiene al linguaggio definita da una grammatica G se e solo se esiste un albero di derivazione in G per la stringa a.
GRAMMATICHE AMBIGUE = una grammatica è ambigua se esistono due diversi alberi di derivazione in G per una stringa a. Di solito basta aumentare e modificare opportunamente (non c'è una tecnica precisa) le categorie sintattiche e le produzioni della grammatica per togliere la sua ambiguità. Esistono comunque dei linguaggi intrinsecamente ambigui, cioè che possono essere definite solo da grammatiche ambigue.
CONFRONTO FRA GRAMMATICHE E AUTOMI: le grammatiche sono più potenti degli automi, cioè esiste almeno un linguaggio generato da una grammatica che non può essere riconosciuto da nessun automa a stati finiti (per esempio il linguaggio delle stringhe costituite da una sequenza di a ed una sequenza di b in uguale numero) . Se un linguaggio è riconosciuto da un automa, allora esiste necessariamente una grammatica che definisce tale linguaggio. Queste grammatiche sono dette regolari e sono una sottoclasse delle grammatiche libere poiché i loro alberi di derivazione hanno una struttura diagonale.
SISTEMI DI TRANSIZIONE: generalizzazione di un automa a stati finiti. Nei sistemi di transizione gli stati possono essere infiniti, possono esistere più di uno stato iniziale e gli stati finali non sono quelli di accettazione, come per gli automi, ma sono gli stati dai quali non è possibile effettuare alcuna transizione. Sono 3 le componenti principali di un sistema di transizione: 1. Le configurazioni, che equivalgono agli stati dell'automa; 2. Le configurazioni finali; 3. Le relazioni di transizioni. I sistemi sono costituiti da metaregole, le quali possono rappresentare in modo finito infinite transizioni. Se sopra alle regole sono presenti delle premesse, la regola viene applicata se e solo se tutte le premesse sono verificate. I sistemi possono essere big step (o di semantica naturale) quando non ci sono configurazioni intermedie, ma si arriva direttamente ad una configurazione finale attraverso chiamate ricorsive dello stesso sistema fra le premesse. Sono chiamati invece small step se non ci sono chiamate ricorsive nelle premesse e si arriva alle configurazioni finali attraverso stadi intermedi ed iterazioni.
OGGETTI = associazioni + metodi.
DINAMICITA' DEGLI OGGETTI: essi possono essere creati in qualsiasi momento e non vengono cancellati alla fine del blocco in cui sono stati creati, in quanto non vivono sullo steck di frame, ma sono allocati in un altro tipo di memoria: la memoria heap.
Privacy |
Articolo informazione
Commentare questo articolo:Non sei registratoDevi essere registrato per commentare ISCRIVITI |
Copiare il codice nella pagina web del tuo sito. |
Copyright InfTub.com 2024