I calcolatori sono tutti costruiti sul modello della macchina di Von Neumann (vedi appunti di Architettura). La macchina fisica esegue continuamente un ciclo Fetch-Decode-Execute, programmi e dati risiedono nella memoria interna e vi è distinzione fra essi; la macchina funziona esclusivamente per eseguire il proprio linguaggio.
Una macchina corrisponde ad un unico linguaggio, ma un linguaggio può essere eseguito da più macchine.
Una macchina astratta è un'astrazione del concetto di calcolatore fisico.
Gli algoritmi che vogliamo eseguire devono essere rappresentati con le istruzioni di un certo linguaggio di programmazione $L$.
La sintassi di $L$ ci permette di usare un certo numero di costrutti (le istruzioni) per comporre programmi.
Def. di Macchina Astratta: Supponiamo che sia dato un linguaggio di programmazione $L$. Definiamo una macchina astratta per $L$, e la indichiamo con $M_L$, un qualsiasi insieme di strutture dati e di algoritmi che permettano di memorizzare ed eseguire programmi scritti in $L$.
Una generica macchina astratta $M_L$ è composta da:
Ogni interprete compie determinate operazioni che dipendono dal particolare linguaggio che deve interpretare. Queste operazioni possono essere raccolte in tipologie comuni a tutti gli interpreti.
Operazioni per l'elaborazione dei dati primitivi.
Ogni macchina necessita di poter manipolare i dati primitivi (ovvero i dati rappresentabili in modo diretto nella macchina, come gli int, i char, ecc.), quindi parliamo delle classiche operazioni aritmetiche di somma, moltiplicazione, ecc.
Operazioni e strutture dati per il controllo della sequenza di esecuzione.
Si tratta delle operazioni condizionali o i salti, che permettono di alterare il flusso di esecuzione del programma. L'interprete deve quindi disporre di strutture dati (per salvare l'indirizzo dell'istruzione successiva oppure l'indirizzo a cui ritornare al termine dell'istruzione attuale) che vengono manipolate con opportune operazioni.
Operazioni e strutture dati per il controllo del trasferimento dei dati.
Queste operazioni gestiscono le modalità di indirizzamento della memoria e come recuperare i dati da quest'ultima. Spesso per gestire al meglio il trasferimento si usano strutture dati come la pila.
Operazioni e strutture dati per la gestione della memoria.
Queste operazioni sono necessarie per allocare la memoria per i dati e i programmi. Anche in questo caso i linguaggi più complessi si avvalgono di strutture dati come pile e di operazioni dinamiche (eseguite a runtime).
Ciclo di esecuzione dell'interprete classico