Riassunto esame Linguaggi di Programmazione, prof Covino, libro consigliato Linguaggi di programmazione, Gabrielli, Martini

Macchina astratta

Una macchina astratta è un'astrazione di un calcolatore fisico. Dato un linguaggio di programmazione L definito formalmente con una specifica sintassi e una specifica semantica, si definisce macchina astratta M di L qualsiasi insieme di strutture dati e algoritmi capaci di memorizzare ed eseguire programmi scritti nel linguaggio L. La macchina astratta è formata dagli strumenti di memorizzazione dove vengono memorizzati i dati e da un interprete che ha il compito di elaborare le informazioni delle istruzioni.

Interprete

Nonostante esistano infiniti tipi di interpreti dipendenti dal tipo di linguaggio L e dal tipo di macchina astratta, ci sono delle categorie di operazioni e anche una modalità di esecuzione comune a tutti gli interpreti:

• Operazioni per l’elaborazione dei tipi di dati primitivi; tutte le macchine astratte possiedono dei tipi di dati primitivi, cioè dei dati direttamente comprensibili dalla macchina; quindi la macchina deve avere delle operazioni per l’elaborazione di questi tipi di dati. ES tipi di dato primitivi: Interi Operazioni: somma ecc.
• Operazioni e strutture dati per il controllo del flusso di esecuzione delle operazioni; l’interprete deve possedere delle strutture dati o operazioni per controllare e gestire il flusso di esecuzione delle istruzioni in quanto deve disporre di meccanismi per risolvere situazioni in cui la normale sequenza di esecuzione sequenziale viene a mancare.
• Operazioni e strutture dati per il controllo dei trasferimenti di dati; la macchina deve disporre di meccanismi di controllo per il trasferimento di dati e operazioni dalla memoria all’interprete e viceversa. Queste operazioni riguardano le varie modalità di indirizzamento della memoria e l’ordine con cui gli operandi devono essere recuperati della memoria. In alcuni casi possono essere necessarie delle strutture dati ausiliarie come la pila.
• Operazioni e strutture dati per la gestione della memoria. Bisogna disporre di strutture di controllo che possono essere sia hardware che software per la gestione della memoria cioè per l’allocazione e deallocazione della memoria ad un relativo programma.

Il ciclo di esecuzione dell’interprete è comune a tutti ed è costituito dalle seguenti fasi: viene prelevata la prossima istruzione dalla memoria, l’interprete la decodifica per individuare il tipo di operazione da effettuare e per individuare gli operandi; legge gli operandi dalla memoria e viene eseguita l'operazione. Successivamente il risultato viene memorizzato in memoria. Quindi, a meno che l’istruzione elaborata sia un’istruzione di arresto, si passa all’istruzione successiva e così via.

Linguaggio macchina

Data una macchina astratta M di L, il linguaggio accettato e compreso da questa macchina si definisce linguaggio macchina di M di L. L’esempio di macchina astratta più lampante è la macchina hardware. MH e LH è il linguaggio macchina compreso da MH. Si definisce la macchina hardware LH.

Ciclo di esecuzione della macchina hardware: fetch-decode-execute.

Implementazione di un linguaggio

Una macchina astratta corrisponde univocamente a un linguaggio, il suo linguaggio macchina, mentre a un linguaggio di programmazione corrispondono infinite macchine astratte che comprendono L. Queste macchine si differenziano in base a come sono realizzate le strutture dati e le operazioni. Implementare un linguaggio significa realizzare una macchina astratta che accetti L e, prima di vedere le reali tecniche di implementazioni, bisogna vedere la possibilità teorica di realizzazione di una macchina astratta:

• Realizzazione hardware: la realizzazione della macchina astratta viene fatta utilizzando solamente dispositivi fisici come memorie, bus, unità logiche ecc. Questa realizzazione permette di avere velocità di esecuzione molto alte a discapito però della difficoltà di progettazione che aumenta esponenzialmente all’aumentare della complessità del linguaggio.
• Realizzazione mediante software: questa realizzazione sfrutta un secondo linguaggio L’ già implementato riconosciuto da M’ di L’ per simulare le funzionalità di M di L. Questa tecnica permette di avere una flessibilità altissima, ma una velocità di elaborazione molto bassa in quanto si aggiunge un ulteriore livello di interpretazione.
• Emulazione mediante firmware: in questa realizzazione consiste l’emulazione delle operazioni della macchina astratta mediante dei micro programmi. Questa realizzazione è simile a quella mediante software con la sola differenza che le istruzioni sono memorizzate in memoria di sola lettura ad alta velocità, permettendo di avere prestazioni migliori rispetto alla realizzazione mediante software. La flessibilità di questa realizzazione però è minore di quella software perché necessita di apparati specifici per riprogrammare le memorie di sola lettura che sono riprogrammabili. In pratica è una via di mezzo tra le due.

Implementazione: Il caso ideale

Consideriamo un linguaggio L che si vuole implementare, cioè di cui si vuole realizzare una macchina astratta M di L. Escludendo un’implementazione hardware, supponiamo di avere a disposizione una macchina astratta M, già implementata, che ci permette di utilizzare i costrutti del suo linguaggio macchina L. Intuitivamente l’implementazione di L sulla macchina ospite M avviene mediante una qualche traduzione di L in L, e ci sono due implementazioni a seconda che si abbia una traduzione implicita o esplicita. Le due rispettive implementazioni si chiamano:

• Implementazione interpretativa pura
• Implementazione compilativa pura

Implementazione interpretativa pura

Nell’implementazione interpretativa pura, si realizza l’interprete di M di L mediante un insieme di istruzioni di L e cioè si realizza un programma che è un interprete chiamato I di L nel linguaggio L che interpreta tutte le istruzioni di L. Una volta che viene fatto questo interprete, per eseguire un programma scritto in L, bisogna eseguire sulla macchina M l’interprete con dati di input il programma in linguaggio L e i dati.

Nell’implementazione interpretativa pura quindi non vi è una traduzione esplicita dei programmi scritti in L ma vi è un procedimento di decodifica in quanto l’interprete fa corrispondere un certo numero di istruzioni di L alle istruzioni di L.

Implementazione compilativa pura

In questo tipo di compilazione, l’implementazione di L avviene traducendo esplicitamente i programmi scritti in L in programmi scritti in L. Questa traduzione viene fatta da un programma detto compilatore C. In questo tipo di implementazione, L è detto linguaggio sorgente mentre L è detto linguaggio oggetto. Per eseguire un programma in L, innanzitutto bisognerebbe eseguire il compilatore con il programma come input. Questo produrrà come risultato un programma Pc scritto in Lo, quindi a questo punto si può lanciare l’esecuzione di Pc in Lo sulla macchina M o L.

Si noti che qui la fase di traduzione è detta compilazione ed è separata dalla fase di esecuzione. Infatti la compilazione produce un programma che potrebbe essere successivamente eseguito.

Vantaggi e svantaggi

L’implementazione interpretativa pura ha lo svantaggio principale di avere una scarsa efficienza. Infatti, a causa della fase di traduzione, l’interprete deve effettuare, al momento dell’esecuzione, una decodifica dei costrutti del linguaggio L, quindi ai tempi di esecuzione richiesti dalle operazioni del programma in L si aggiungono i tempi necessari alla decodifica. È importante puntualizzare che la decodifica non genera codice come la compilazione. L’implementazione interpretativa offre però un vantaggio in termini di flessibilità in quanto l’interpretazione permette di interagire in maniera diretta con l’esecuzione del programma e in generale lo sviluppo di un linguaggio interpretato è più semplice di uno compilato e inoltre permette di usare molta meno memoria in quanto il programma viene memorizzato solo nella sua versione sorgente in L.

Lo svantaggio principale dell’implementazione compilativa è la perdita di informazioni riguardo alla struttura del programma sorgente causando più difficoltà nell’interazione con il programma a runtime.

La macchina intermedia

Le due implementazioni sono spesso considerate i due estremi. Infatti, nella pratica, sono quasi sempre presenti entrambi. Tra il linguaggio L e la macchina Mo si crea un altro livello caratterizzato da un proprio linguaggio Li e da una propria macchina M i Li, che sono rispettivamente il linguaggio intermedio e la macchina intermedia. Qui abbiamo sia un compilatore che traduce da L a Li, sia un interprete eseguito sulla macchina Mo. Un programma in L è prima tradotto dal compilatore e poi eseguito dall’interprete in linguaggio intermedio. L’interprete non deve essere per forza realizzato interamente nel caso in cui il linguaggio intermedio e il linguaggio Lo della macchina non siano molto distanti. Quando si ha questa macchina intermedia si parla di implementazione di tipo interpretativo.

Gerarchia di macchine astratte

Si usano sempre gerarchie di macchine astratte dove ogni macchina usa le funzionalità del livello sottostante e ne fornisce di nuove al livello soprastante. Una macchina M di L non può accedere direttamente alle risorse delle macchine sottostanti ma può solo sfruttare quelle che fornisce il linguaggio L. Una tale struttura gerarchica è utile per dominare la complessità del sistema e per mettere una certa indipendenza tra i vari livelli. Un esempio è la pila ISO/OSI.

Descrivere un linguaggio

Un linguaggio di programmazione è un formalismo artificiale nel quale poter esprimere algoritmi. Morris individuò i tre grandi ambiti per cui può avvenire la descrizione di un linguaggio: grammatica, semantica e pragmatica.

• Grammatica è quella parte della descrizione di un linguaggio che risponde alla domanda “Quali frasi sono corrette?”. Per prima cosa nella grammatica si definisce l’alfabeto, tramite quest'ultimo si compongono delle sequenze di lettere, ossia le parole (o token) e ne seleziona un sottoinsieme di queste che costituiscono le frasi del linguaggio.
• Semantica è quella parte della descrizione di un linguaggio che cerca di dare risposta alla domanda “Cosa significa una frase corretta?”. Essa dunque attribuisce un significato ad ogni frase corretta del linguaggio.
• Pragmatica è quella parte della descrizione di un linguaggio che si chiede “Come usare una frase corretta e sensata?”. Frasi con lo stesso significato possono essere usate in modo diverso da utenti diversi o contesti linguistici diversi possono richiedere l’uso di frasi diverse.

Nel caso dei linguaggi di programmazione si può aggiungere un altro livello, cioè quello dell’implementazione. Questo risponde alla domanda “Come eseguire una frase corretta in modo da rispettare la semantica?”.

Grammatiche libere

Supponiamo di avere a disposizione un alfabeto A definito come segue: A={a,b}. Dato questo alfabeto ci poniamo il problema di ricavare tutte le parole palindrome. Una generica stringa palindroma P potrà essere una stringa vuota, una a, una b oppure una stringa palindroma preceduta e seguita da una a o una b.

P→P→aP→b→P aPa→P bPb

L’esempio appena riportato è una grammatica libera dal contesto. Fissato un insieme finito o numerabile A, che chiamiamo alfabeto, indichiamo con A* l’insieme di tutte le stringhe finite di elementi di A ( * è detto stella di Kleene ). Di A* fa parte anche l’insieme vuoto che si denota con ε. Un linguaggio formale sull’alfabeto A non è altro che un sottoinsieme di A* e infatti una grammatica formale serve proprio a definire un certo sottoinsieme di A*. Una grammatica libera da contesto o non contestuale è una quadrupla (NT,T,R,S) dove:

• NT è un insieme finito di simboli cioè i simboli non terminali o le variabili.
• T è un insieme di simboli che sono terminali.
• R è un insieme finito di produzioni o regole, ciascuna delle quali in forma V -> w dove V è la testa della produzione appartenente a NT e w è il corpo della produzione ed è costituito da più simboli terminali e non (T U NT).
• S è un elemento di NT cioè il simbolo iniziale.

Nell’esempio di prima la grammatica è { {P} , {a,b}, R, P }.

Derivazione diretta

Fissata una grammatica G = (NT,T,R,S) e assegnate due stringhe v e w su T U NT, diciamo v -> w se w si ottiene da v sostituendo ad un simbolo non terminale di V presente in v il corpo di una produzione di R la cui testa sia V.

Derivazione

Una derivazione non è altro che una sequenza di derivazioni dirette. Diciamo che da v si deriva w e scriviamo v -> *w, se esiste una sequenza finita, eventualmente vuota, di derivazioni dirette. v -> w0 -> w1 -> w2 -> w.

Linguaggio generato

Il linguaggio generato da una grammatica G = (NT,T,R,S) è l’insieme L|G| = { w ∈ T* | S -> *w }

Alberi di derivazione

La derivazione di una stringa è un processo rigidamente sequenziale in quanto ci sono dei passi che devono essere effettuati necessariamente in un certo ordine. Tuttavia ci sono alcuni passi che potrebbero essere scambiati di ordine. Infatti, si potrebbero avere delle derivazioni diverse per lo stesso risultato. Queste derivazioni sono però equivalenti in quanto ricostruiscono nello stesso modo la struttura della stringa e differiscono soltanto nell’ordine con il quale le produzioni sono applicate.

Data una grammatica G = (NT,T,R,S), un albero di derivazione o albero di parsing è un albero orientato in cui:

• Ogni nodo è etichettato con un simbolo in NT U T U {ε}.
• La radice è etichettata con S.
• Ogni nodo interno è etichettato con un simbolo in NT.
• Se un certo nodo ha etichetta A ∈ NT e i suoi figli m1…mk etichettati rispettivamente con x1….xk con Xi ∈ NT U T allora A -> X1…Xk è una produzione di R.
• Se un nodo ha etichetta ε allora quel nodo è figlio unico e, detto A suo padre, la produzione A -> ε è una produzione di R.

È ovvio che, data una derivazione, possiamo ottenere a partire da essa un albero di derivazione. Basta iniziare dalla radice ed ogni volta aggiungere un livello di figli in corrispondenza della produzione usata durante la derivazione. Gli alberi di derivazione sono degli strumenti più importanti dell’analisi sintattica di un linguaggio di programmazione. Infatti, la struttura dell’albero di derivazione esprime, attraverso i sottoalberi, la struttura logica che la grammatica assegna alla stringa. Però, a seconda di come è costruita la derivazione, si ottiene una precedenza diversa fra gli operatori generando due alberi di derivazione diversi per la stessa stringa.

Sia T = (N, A) un albero ordinato non vuoto di radice r. Il risultato della vista da sinistra a destra di T è la sequenza di nodi (foglie) ottenuta dalla seguente definizione ricorsiva:

• Se r non ha figli allora il risultato della visita è il nodo r.
• Se r ha k figli m1,m2…mk siano T1,T2….Tk i sottoalberi di T tali che Ti ha come radice mi. Il risultato della visita è quindi la sequenza di foglie ottenuta visitando da sinistra a destra prima T1 poi T2 fino a Tk.

Quindi si dice che una stringa di caratteri s ammette un albero di derivazione T se s è il risultato della vista da sinistra a destra di T.

Ambiguità

Una grammatica G è ambigua se esiste almeno una stringa di L|G| che ammette più di un albero di derivazione. Si osserva che però l’ambiguità non nasce dall’esistenza di più derivazioni per la stessa stringa, cosa comune, ma dal fatto che almeno una stringa ha più alberi di derivazione. Una grammatica ambigua è inutile per descrivere i linguaggi di programmazione in quanto non può essere usata per tradurre in modo univoco un programma. Fortunatamente, però, ci sono delle tecniche di disambiguazione che permettono di definire un’altra grammatica non ambigua partendo da una ambigua e modificandola.

Vincoli sintattici contestuali

La correttezza sintattica di una frase di un linguaggio di programmazione dipende talvolta dal contesto nel quale la frase si trova. Per esempio, I = R + 3 in un linguaggio fortemente tipizzato, richiede che I e R siano prima dichiarate. Quindi quella frase, nonostante sia corretta, in questo contesto è errata. Quindi stringhe corrette secondo la grammatica possono essere legali solo in un determinato contesto. Questi tipi di vincoli sintattici non sono impossibili da descrivere all’interno di una grammatica libera da contesto in quanto esistono altri tipi di grammatiche che permettono di gestire, chiamate ovviamente grammatiche dipendenti da contesto o contestuali. Si tratta tuttavia di grammatiche pesanti da scrivere e gestire e quindi si suggerisce molto spesso di limitare l’uso delle grammatiche contestuali usando le grammatiche libere per la descrizione della parte non contestuale e poi di utilizzare il linguaggio naturale per la definizione dei vincoli contestuali.

Compilatori

Sappiamo che il traduttore automatico di un programma si chiama compilatore. Esso lavora in una serie di fasi a cascata a partire dalla stringa che rappresenta il codice sorgente fino ad arrivare a generare una stringa.