Appunti di Programmazione + Lab

T

2. V : insieme di simboli non terminali (categorie sintattiche).

N

3. P: insieme delle regole di produzione o regole sintattiche.

4. S di V : simbolo non terminale chiamato simbolo iniziale o α (alfa).

N

Quindi G={V , V , P, S}.

T N

N.B. V e V sono insiemi disgiunti, ovvero V Π V =Ø.

N T N T

Alfabeto dei simboli terminali

Gli elementi V sono i simboli con cui si costruiscono le frasi del linguaggio;

T

possono essere costituiti da un unico simbolo o da una stringa di simboli (ad.

es. le parole chiave di un linguaggio: if, else, for...).

Alfabeto di simboli non terminali

V è l’insieme dei simboli non terminali o categorie sintattiche che sono

N

introdotti per descrivere la struttura delle frasi (mediante le regole di

produzione P). Esempio: <istruzione>,<identificatore>.

Regole sintattiche

P è un insieme di regole di produzione (o di riscrittura) del tipo a=>b (cioè a

genera b).

Simbolo iniziale

S è il simbolo iniziale o assioma (scopo della grammatica). Indica il simbolo da

cui iniziare nella costruzione delle frasi, cioè nella applicazione di un insieme di

regole di produzione.

BNF (Backus Naur Form)

Il BNF è un meta-linguaggio, cioè un linguaggio artificiale o formale per

descrivere una grammatica. I meta-simboli sono:

 <categoria sintattica>

 ::= simbolo di produzione (è definito da...)

 | alternativa

Una estensione del BNF è l’EBNF che usa le parentesi quadre per indicare un

costrutto opzionale e le partentesi graffe per indicare zero o più ripetizioni.

Esempio 1

<cifra>::=0|1|2|3|4|5|6|7|8|9

Cioè la categoria sintattica “cifra” può essere riscritta con il simbolo 0,

1,2,...,9.

Esempio 2

Definire un numero intero senza segno.

<intero_senza_segno>::=<cifra_iniziale>|<cifra_iniziale><sequenza_cifre>

<sequenza_cifre>::=<cifra>|<cifra><sequenza_cifre>

<cifra_iniziale>::=1|2|3|4|5|6|7|8|9

<cifra>::=<cifra_iniziale>|0

Esempio 3

Descrivere un identificatore.

<identificatore>::=<lettera>|<lettera><sequenza_caratteri>

<sequenza_caratteri>::<sequenza_caratteri><lettera>|<sequenza_caratteri>

<cifra>

<lettere>::=a|b|c|…|z|A|B|…|Z

<cifra>::=0|1|2|3|4|5|6|7|8|9

Esempio 4

Descrivere il costrutto if in Java.

<selezione_binaria>::=if(<espressione>)<corpo>;|

if(<espressione>){<corpo>}else{<corpo>};

<espressione>::=<costante>|<numero>|<operatore>

Esempio 5

Descrivere un numero pari.

<npari>::=<cifra_pari>|<numero><cifra_pari>

<cifra_pari>::=0|2|4|6|8

<cifra>::=0|1|2|3|4|5|6|7|8|9

<numero>::=<numero><cifra>

Carte sintattiche

Una grammatica può essere descritta graficamente da un diagramma detto

“carta sintattica”.

 I simboli terminali V sono inseriti in forme ovaloidi.

T

 I simboli non terminali V sono inseriti in forme rettangolari.

N

 I simboli sono collegati da frecce.

 Il simbolo inziale dà il nome alla carta.

Esempio 1

Descrivere un numero intero senza segno.

0

Intero senza

segno Cifra Iniziale Cifra

Cifra iniziale={1,2,3,4,5,6,7,8,9}

Cifra={0,1,2,3,4,5,6,7,8,9}

Esempio 2

Descrivere il costrutto if in Java.

Selezione

Binaria if else

Espressione Istruzione Istruzione

Esempio 3 Descrivere un numero pari

0

Numero

pari Cifra Cifra_Pari

Cifra={0,1,2,3,4,5,6,7,8,9}

Cifra_Pari={0,2,4,6,8}

Algoritmi elementari

Algoritmo di scambio

Date due variabili x e y, scambiare i loro valori. Si può procedere in due modi:

 Usando una variabile temporanea:

tx

o xy

o yt

o

 Usando un piccolo artificio:

xx+y

o yx-y

o xx-y

o

N.B. La seconda modalità non si deve usare in quanto l’algoritmo non è

generale, non è intuitivo ed è poco leggibile. L’unico vantaggio è il risparmio di

uno spazio, ma ugualmente conviene usare il primo modo.

Media fra due valori

Calcolare la media fra x e y:

 Media(x+y)/2

 L’espressione restituisce un valore decimale.

Minimo fra due valori

 Bisogna usare una struttura selettiva (if)

if (x<y){

min=x;

}else{

min=y;

}

Minimo fra tre valori

 Il dominio di ingresso è D =(NxNxN)

I

 Il dominio di uscita è D =minimo

O

 Essendoci n coppie avremo n-1 selezioni.

Valore assoluto

 Se a≥b allora risultato a-b

 altrimenti risultatob-a

Somma di n valori

Non avendo affrontato gli array si procede con un algoritmo di elaborazione al

volo (on the fly). Si usa quindi una sola variabile che accumula di volta in volta

il valore corrente.

L’algoritmo sarà di tipo iterativo.

Inizializzazione

Mentre ci sono ancora addenti, esegui

Leggi a i

s=s+a i

Fine mentre

Algoritmi di conteggio

Dati n valori, contare il numero di valori maggiori di s (soglia)=17.

Si usa la strategia iterativa.

Esempio:

Voti: 22 30 17 25 4 18 27

Cont: 1 2 2 3 3 4 5

Inizializza contatore a zero

Mentre ci sono ancora voti da esaminare, esegui

Leggi il prossimo voto

Se voto>17 allora

Aggiorna contatore

Fine se

Fine mentre

Minimo e massimo fra n numeri

maxa

1

Mentre ci sono ancora numeri da acquisire, esegui

if (voto>max) maxvoto

Fine mentre

Inversione di cifre

Ad esempio: 2795335972

Si può elaborare un algoritmo che esegua divisioni successive:

c=n MOD 10 Calcolo cifra meno significativa

n=n DIV 10 Rimozione cifra meno significativa

m=m*10+c Scala verso destra per aggiungere la cifra successiva

Quando il quoziente (cioè n) diventa zero, si ha la condizione di Stop.

Ordinamento fra 3 stringhe

In Java c’è la classe StringSet già predisposta per ordinare 3 stringhe:

 StringSet s=new StringSet(str1,str2,str3);

 s.getSmallest();

 s.getMiddle();

 s.getLargest();

Istruzioni di controllo della esecuzione

Sono istruzioni che modificano la sequenzialità della esecuzione.

Controllo in Java:

 Sequenza: istruzione composta che segue l’ordine naturale

 Selezione: binaria (if), multipla (switch)

 Iterazione: for, while

Enunciati-Statement-Istruzioni

 Assegnamento: istruzione semplice, tutte le altre sono composte

 Blocco: se nell’istruzione composta c’è anche una dichiarazione (non in

tutti i linguaggi)

Selezione binaria: costrutto if-esle

if (<condizione>)

<enunciato>;

else

[ ]

<enunciato> ;

Selezione Multipla: costrutto switch

Switch(espressione di tipo ordinale){

case val1: istruzione1;

break;

case val2: istruzione2;

break;

...

default: istruzione;]

[

}

N.B. Il valore da analizzare deve essere un valore intero ordinale, cioè un

numero senza la virgola. Il break è necessario per evitare che, una volta

individuato il case esatto, Java esegua anche i casi successivi. Quindi il break è

assimilabile ad un salto incondizionato (es. il goto). Il default è opzionale.

Istruzioni iterative

Leading Decision:

Ciclo for:

 Composto da 3 espressioni separate per indicare l’inizio, la fine e il

passo.

 Corpo: istruzioni semplici o composte.

for (i=0; i<10; i++)

corpo;

Ciclo while:

 Parola “while” seguita da una espressione logica

 Il corpo può non essere mai eseguito

while (espressione){

corpo;

}

Trailing Decision

Ciclo do-while:

 Parola “do” seguita dal corpo

 Parola “while” seguita da una espressione logica

 Il corpo viene eseguito almeno una volta

do{ corpo;

}while (espressione);

Interruzione del flusso

 Break:

Determina l’uscita dall’istruzione in cui si trova

o Usabile negli switch (se necessario) e nei cicli (da evitare)

o

 Continue:

Usabile solo nelle istruzioni iterative

o Causa l’interruzione del passo ciclico e dà inizio al successivo

o

 Return:

Nei metodi restituisce immediatamente il controllo e fornisce il

o valore di ritorno

Le espressioni con break, continue e return producono programmi non

strutturati.

Gli array

Tipi di dati strutturati

Variabili:

 Semplici: valore atomico

 Strutturate:

Aggregazione di dati simile ad una tabella (struttura

o bidimensionale)

Dati omogenei (dello stesso tipo)

o Possibile in un linguaggio a tipizzazione forte

o Hanno un unico nome e possono essere manipolate accedendo alle

o singole componenti

Meccanismi/Modalità di strutturazione

 Trasformazione finita: funzione iniettiva, applicazione di trasformazione

(array)

 Prodotto cartesiano: prodotto tra insiemi, cioè n-ple (record, schede,

struct…)

 Insieme potenza: prodotto di insiemi (set)

 Sequenza: raggruppamento a dimensione variabile (file, archivi)

Trasformazione finita

f: tipo indice(int) Tipo base



IndiceDominio=N ValoreCodominio

I valori sono memorizzati in locazioni di memoria contigue.

L’indirizzo di ogni elemento viene calcolato durante l’esecuzione con la

seguente formula (eseguita dal compilatore):

 ind=I +dim_singola*indice

0

In generale: ARRAY [tipo indice] di tipo base

In Java per accedere ad un singolo elemento si scrive a[espressione]; l’indice

parte sempre da zero e la dimensione è specificata da una costante.

N.B. In Java gli array sono oggetti.

Caratteristiche degli array

 Numero fisso di componenti

 Componenti di tipo omogeneo

 Ciascuna componente è singolarmente denotabile tramite un selettore

(indice)

Sconfinamento (Out of Bound)

L’out of bound consiste nell’accesso ad una memoria non significativa a quella

assegnata all’array, cioè prevede l’accesso a dati che non sono attinenti

all’array stesso.

In Java lo sconfinamento di un array produce una eccezione durante

l’esecuzione, in quanto la memoria viene allocata solo allora.

Un problema inverso dell’out of bound è il fatto di non riempire completamente

l’array che definiamo all’inizio e dunque distinguiamo:

 Dimensione Fisica: definita all’inizio del programma, che non cambia

 Dimensione Semantica: cambia a seconda degli elementi effettivamente

presenti nell’array

Matrici

E’ una struttura pi&