Programmazione I - Appunti

Programmazione I & laboratorio

• Indice ................................................. pag. 1
• Sintassi ............................................ pag. 5
• Ricorsione ....................................... pag. 10
• Programmazione funzionale ... pag. 13
• Tipi elementari ............................. pag. 15
• Liste ................................................ pag. 18
• Tipi derivati .................................. pag. 19
• Linguaggio C: semantica .......... pag. 20
• Procedure ..................................... pag. 31

Programmazione I & laboratorio (seconda versione)

• Indice ...................................................... pag. 1
• Sintassi ...................................................... pag. 5
• Ricorsione ............................................... pag. 10
• Programmazione funzionale ....... pag. 13
• Tipi elementari ...................................... pag. 15
• Liste ......................................................... pag. 18
• Tipi derivati ............................................ pag. 20
• Linguaggio C: semantica ..................... pag. 29
• Procedure ............................................... pag. 34

Sintassi

La sintassi di un linguaggio di programmazione si occupa della sua struttura. Una volta che ho specificato, descrive il linguaggio tramite due metodi:

• Riconoscimento di stringhe (automi a stati finiti)
• Costruzione di stringhe (grammatiche a struttura di fase)

Concetti base della sintassi:

• Alfabeto (Α): insieme di simboli appartenenti al linguaggio,
• Stringhe (s): successione di simboli dell'alfabeto,
• Stringa vuota (ε): stringhe che non contiene simboli,
• Linguaggio (L): l'insieme M di combinazioni possibili di simboli di A,
• Linguaggio L1 ⊆ A combinazione di A.

Tutti gli elementi della sintassi sono soggetti a operazioni insiemistiche (unione (U), intersezione (n), complementazione (¦V), inclusione (E), ecc.). Due stringhe possono essere concatenate, cioè i simboli della prima stringa possono essere successivi ai simboli di una seconda stringa, formando una stringa unica.

Automi a stati finiti (ASF)

Gli automi a stati finiti (ASF) sono un metodo di definizione dei linguaggi basato sul riconoscimento delle stringhe. Essi mappano la stringa di una macchina a stati con elementi componenti un ASF: < A, Σ, S, F, δ > in cui:

• A → alfabeto
• Σ = insieme degli stati
• S = stato iniziale (S ∈ Σ)
• F = insieme degli stati finali, o di accettazione (F ⊆ Σ)
• δ → relazione di transizione da uno stato ad un altro, regola comunque per tutti i passaggi che devono esistere

Automi Deterministica (ASD)

ASF si definisce deterministico quando ad ogni simbolo di A corrisponde esattamente un solo stato i. Esiste un unico δ per cui la relazione si possono stabilire dei vincoli.

Automi non deterministica (ASN)

Gli ASF si differenziano dai deterministici.

Rappresentazione grafica di ASF: i grafi

I grafi sono il modo di rappresentare gli ASF. Σ: i simboli di Σ sulle frecce sono i simboli che permettono la transizione indicata. δ: relazione di transizione che ad un'etichetta comprende un cambio di stato. Nodi: nel cerchio interno ci sono gli stati dell'ASF. Nodo iniziale: seguito dalla freccia che lo indica. Nodi finali: cerchietto gli stati di accettazione. N.B.: Quello rappresentato sopra è un ASF di un grafo differente rappresenta diverso.

Costruzione dei sovrainsiemi

I ASFN possono essere ricondotti a degli ASF tramite il metodo della costruzione dei sovrainsiemi. Si considerano tutte le ε-transizioni. Si traducono gli insiemi di stati di arrivo in un stesso stato, si definisce dunque tutti gli stati di serveo di tutti gli stati. Si sostituisce al precedente la transizione a ε così facendo si ottiene un sistema deterministico. Infine si cancellano le lucine e le succedi, saranno fusi stati dell'ASF.

Esempio con l'ASF precedente:

0,1 → (1) 0,1,2 1 → (1,2) 0,1,2 3,4 → (1,2,3,4) 0,1,2 → (1,4) 0,1,3,4 → (1,4)

N.B. Nel nuovo ASF, se vi ci sarebbe anche un solo stato finale qualsiasi diventa stato finale.

Grammatiche libere di contesto

La grammatica libera da contesto (più brevemente G. contestuale) è un modo di definire i linguaggi tramite la loro struttura sintattica e permette di catturare strutture sintattiche che si definiscono in maniera ricorsiva. Le grammatiche libere da contesto formali sono definite da una quadrupla: <L, V, S, P> in cui:

• L = alfabeto
• V = insieme di ca