| << |  <  |  >  | >> |

Indice

    Prefazione, 7

1.  Le strutture informative, 11

    1.  Strutture informative interne, 12
        1.1 Vettori
        1.2 Liste semplici
        1.3 Liste multiple. Il plex di Ross
    2.  Matrici, 22
        2.1 Allocazione in memoria di matrici
            rettangolari
        2.2 I vettori di Iliffe
    3.  Code e pile, 32
        3.1 Allocazione in memoria di code e
            pile
    4.  Alberi, 38
        4.1 Alberi e informazione
        4.2 Allocazione in memoria di alberi
        4.3 Visita di un albero. Ordine
            anticipato e ordine differito.
            Alberi tramati
        4.4 Alberi binari.  Memorizzazione di
            alberi binari.  Ordini binari di
            visita.  Alberi binari tramati.
            Rappresentazione di un albero in
            forma di albero binario
    5.  Grafi, 70
        5.1 Allocazione in memoria di grafi
    6.  Tabelle, 75
        6.1 Ricerca completa
        6.2 Ricerca binaria
        6.3 Codificazione "hash". Tabelle ad
            accesso diretto.  Collisione di
            elementi.  Generazione degli
            indirizzi hash.  La legge di
            scansione.  Il metodo di
            concatenazione.  Eliminazione di
            elementi
        6.4 Considerazioni conclusive
    Bibliografia, 103

2.  Programmi e linguaggi di programmazione,106

    7.  Linguaggio macchina e linguaggio
        simbolico, 108
    8.  Linguaggi algoritmici.  Il FORTRAN, 109
        8.1 Ingresso e uscita dei dati
        8.2 Sottoprogrammi
        8.3 Cicli
        8.4 Matrici
    9.  Altri linguaggi algoritmici, 120
        9.1 L'ALGOL 60
        9.2 Linguaggi per la manipolazione di
            simboli
        9.3 Linguaggi per applicazioni
            commerciali
        9.4 Un linguaggio algoritmico generale:
            il PL/1
    10. Linguaggi specializzati, 132
    Bibliografia, 136

3.  Proprietà formali dei linguaggi, 138

    11. La sintassi di un linguaggio, 139
        11.1 Classificazione secondo Chomsky
    12. Linguaggi a stati finiti, 146
        12.1 L'automa analizzatore e traduttore
        12.2 Estrazione di parole
    13. Linguaggi liberi dal contesto, 160
        13.1 Un sottoinsieme dell'ALGOL
        13.2 Analisi sintattica. Il concetto di
             derivata.  Il concetto di
             proposizione
    14. La precedenza tra gli operatori, 167
        14.1 Linguaggi a operatori con
             precedenza
        14.2 Il procedimento di Floyd.
             Ambiguità nell'analisi canonica e
             proposizioni prime.  Generazione
             dell'albero sintattico. Traduzione
    Bibliografia, 183


 

| << |  <  |  >  | >> |

Pagina 11

Le strutture informative

L'informazione elaborata da un calcolatore si presenta in una varietà di forme differenti che dipendono in genere dalla natura del problema da risolvere. Accanto a problemi che richiedono il trattamento di dati propriamente numerici - semplici variabili o matrici - ve ne sono altri di natura non numerica che richiedono elaborazioni su sequenze di caratteri alfabetici o numerici, su schemi di flusso o grafi e così via.

I dati si presentano dunque strutturati in modi differenti, per ciascuno dei quali è necessario individuare una rappresentazione interna al calcolatore che risulti conveniente per le elaborazioni da eseguire e per lo scambio di informazioni con l'esterno. Poiché la struttura di dati nella memoria deve rispettare i vincoli imposti dalla costituzione della macchina, e sarà di fatto scelta tra un certo numero di strutture note - vettori, liste ecc. - la presentazione stessa del problema potrà richiedere delle modifiche. O meglio, la formulazione di un problema sarà espressa tenendo conto anche del tipo di rappresentazione dei dati in memoria che si pensa di adottare.

Da ciò nasce il termine di struttura informativa, che riguarda sia strutture astratte, cioè proprie del problema e dipendenti unicamente da questo, sia strutture interne alla memoria, cioè insiemi di celle contenenti l'informazione e gruppi di regole per il loro ordinamento logico. Per quanto sopra esposto strutture astratte e interne possono mutuamente influenzarsi, e non è spesso possibile stabilire una precisa linea di demarcazione tra le due. È questo in particolare il caso delle tabelle, che saranno studiate in un apposito capitolo.

Parleremo in seguito di elementi di una struttura, riferendoci ai singoli dati o blocchi di dati che costituiscono le parti indivisibili di cui la struttura è composta. Nella rappresentazione interna, ogni elemento occuperà una frazione di parola, o una parola, o un gruppo di parole di memoria contigue che, agli effetti della struttura, verranno trattate come un unico blocco.

| << |  <  |  >  | >> |

Pagina 106

Programmi e linguaggi di programmazione

Il concetto di programma, inteso come sequenza di istruzioni che una data macchina può interpretare ed eseguire, era già noto e applicato in calcolatrici precedenti la prima macchina di von Neumann. È però improbabile che i progettisti di tali apparecchi ragionassero in termini di "linguaggio di programmazione" nel definire la perforazione di un pacco di schede corrispondente a una qualche procedura contabile; né certo immaginavano la quantità di energia che i successori avrebbero speso nello sviluppo e nella formalizzazione di tecniche per la codificazione di un problema.

L'avvento del calcolatore nel senso attuale dei termine, cioè di una macchina capace di memorizzare un programma oltre ai dati su cui operare, pose subito in grande evidenza il problema della comunicazione con il calcolatore. Il concetto di linguaggio macchina, mediante il quale era possibile scrivere un programma che il calcolatore poteva direttamente interpretare, si rivelò essenziale per la sistematica codificazione dei problemi da sottoporre alla macchina. L'apprendimento e l'uso di tali linguaggi richiede tuttavia una buona conoscenza della struttura del calcolatore impiegato e del modo in cui questo funziona: richiede cioè uno sforzo considerevole al non iniziato. Attorno al calcolatore si sviluppò così immediatamente una élite di "esperti" che soli sapevano come redigere un programma: la necessità di ricorrere a questi spesso non incoraggiava a impiegare il calcolatore.

Risultò inoltre chiaro sin d'allora come il programmatore ideale sia in genere proprio colui che si è posto il problema da codificare, poiché ne considera implicitamente degli aspetti che vengono messi in luce solo al momento di trasformarli in istruzioni per la macchina, e poiché è in grado meglio di ogni altro di interpretare e controllare risultati parziali e finali.

Sotto la spinta di queste prime esigenze si svilupparono i linguaggi di programmazione, allontanandosi dalla forma immediatamente comprensibile dalla macchina per avvicinarsi a modi ed espressioni più semplici e maneggevoli per il programmatore: oltre ai linguaggi simbolici, che costituiscono una semplice ma essenziale trasformazione dei linguaggi macchina (qualche cenno in proposito sarà dato nel prossimo paragrafo), videro la luce numerosissimi linguaggi per la programmazione di particolari classi di problemi. Tali linguaggi, che consentono di scrivere espressioni ed elaborare strutture informative proprie del campo di applicazioni per cui sono stati definiti, sono impiegati nel calcolo scientifico e in particolare algebrico - FORTRAN, ALGOL - nella automatizzazione di procedure commerciali - COBOL -, nella progettazione d'ingegneria e in numerosissimi altri campi tra cui la manipolazione di simboli e formule algebriche. Non è questa la sede per riportarne un elenco sia pure parziale; indicheremo in seguito soltanto le caratteristiche essenziali di alcuni di essi e, per i motivi che verranno esposti, inizieremo dal FORTRAN.

L'impiego di diversi linguaggi richiede naturahnente l'esistenza di traduttori, noti come compilatori, che trasformino il programma originale (programma sorgente) in un equivalente programma redatto in linguaggio macchina (programma oggetto). Benché in linea di principio un traduttore possa essere costituito da un vero e proprio apparato connesso al calcolatore, esso è in realtà un programma che risiede nel calcolatore stesso e lo abilita ad accettare e interpretare programmi in un linguaggio diverso dal proprio: questa interpretazione passa attraverso lo studio formale della struttura di un programma, sviluppato nei paragrafi 11-14 di questo testo.

| << |  <  |  >  | >> |

Pagina

Proprietà formali dei linguaggi

Nel capitolo precedente abbiamo esaminato le caratteristiche applicative dei principali linguaggi di programmazione, visti in funzione delle classi di problemi che con essi si possono affrontare e delle strutture informative che più spontaneamente elaborano. E proprio in virtù del fatto che i programmi in linguaggi a un livello più alto del base o del simbolico sono fortemente legati a problemi specifici, la struttura che essi presentano è così varia e disomogenea da apparire difficilmente costringibile entro schemi comuni.

Il compito, benché complesso, può essere affrontato attraverso lo studio delle proprietà formali dei linguaggi di programmazione, volto a individuare le leggi generali secondo cui un programma si forma come costruzione rispettosa delle regole di un dato linguaggio. Regole quindi che dovranno essere formalizzate per prime.

Vedremo così come gli schemi descrittivi in uso, abbraccino famiglie di linguaggi assai più vaste di quella dei semplici linguaggi programmativi: e presenteremo infatti molti concetti facendo uso di un linguaggio naturale, sottoinsieme sia pure microscopico dell'italiano. Motivo di tanta potenza degli schemi formali è probabilmente da ricercarsi nel fatto che questi studi furono iniziati con l'analisi dei linguaggi naturali; e se la complessità di questi si dimostrò poi tale da sfuggire ai vincoli teorici non appena si cerchi di costringervi le infinite sottigliezze che la lingua dell'uomo sempre comprende, le precise e limitate proprietà dei linguaggi programmativi rientrarono spontaneamente in una formalizzazione sviluppata già in parte.

Prima di affrontare questo studio vogliamo anche chiederci quale ne sia l'importanza nel contesto dei sistemi per l'elaborazione dell'informazione. La risposta può essere multiforme, ma riteniamo che il vantaggio primo che si può ottenere dalla ricerca di una veste unitaria per concetti nati e sviluppatisi in circostanze diverse sia quello di definirne con sicurezza le proprietà e i limiti, regolando e indirizzando i successivi sviluppi della materia. Così dallo studio formale dei linguaggi aspettiamo anzitutto un'indicazione su cosa da questi sia lecito attendersi, nella loro forma presente come nelle evoluzioni future.

Né possiamo dimenticare un secondo scopo di tale formalizzazione, anche se le sue implicazioni escono dall'arco di questo volume. Come già è stato osservato, l'impiego di linguaggi programmativi richiede l'uso di traduttori - detti compilatori - per la conversione dei programmi in linguaggio macchina. Benché sviluppati inizialmente con tecniche artigianali, i compilatori hanno trovato oggi una loro teoria precisamente definita proprio in seguito agli studi sulle proprietà formali dei linguaggi. Per tale motivo, anche se i traduttori non sono compresi nella materia trattata in questo libro, talune idee base sulla traduzione saranno introdotte nel seguito, trovandovi spontanea collocazione. In tale rispetto il capitolo presente potrà anche servire di preparazione allo studio dei compilatori.

| << |  <  |