Linguaggi per la descrizione di algoritmi

Lezione 1 - Linguaggi per la descrizione di
algoritmi
Corso — Programmazione
Fondamenti di programmazione— Linguaggi di
programmazione
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Algoritmo riepilogo (1)
• Un algoritmo è come una ricetta da cucina, un insieme di
passi da eseguire per arrivare alla soluzione del problema
• Un algoritmo viene concretizzato in un programma con un
dato linguaggio a seconda dell'esecutore che deve
comprenderne il linguaggio
• Le ricette sono scritte per un esecutore umano in
linguaggio naturale
• Nel descrivere un algoritmo anche in linguaggio naturale
devo individuare:
Le istruzioni operative
Il controllo del flusso delle istruzioni. Ad esempio una
condizione per eseguire una determinata operazione, un
salto ad una determinata locazione dell'algoritmo
Algoritmo operazioni: esempio
• Esempio euclide
Calcola il resto della divisione di x per y : istruzione
operativa (r ← x mod y)
Se il resto è diverso da zero, ricomincia dal punto 1
utilizzando come x il valore attuale di y, e come y il valore
del resto: controllo
altrimenti prosegui con il passo successivo: controllo
Il massimo comune divisore è uguale al valore attuale di y:
istruzione operativa
Algoritmo riepilogo(2)
• A volte nascosti dalle tipicità dell'esecutore per cui è stato
ideato l'algoritmo
• Nel nostro caso essendo sempre algoritmi orientati ad
esecutori automatici occorre vestire i panni dell'esecutore
anche in fase di scrittura dell'algoritmo
• Scrivere la ricetta degli spaghetti alla carbonara per un
esecutore umano e per un esecutore ``robotico''
• Occorre qualche cosa di più rigoroso per descrivere un
algoritmo per evitare fraintendimenti e per garantire la
trasposizione dell'algoritmo in un programma
Linguaggi per la descrizione di
algoritmi(1)
• Linguaggi informali: Linguaggio Naturale
• Linguaggi semi-formali: Pseudo-codice, Flow chart
(diagrammi di flusso)
Specifiche iniziali, ancora intelleggibili all'essere umano
Pseudo-codice : se A > 0 allora A = A + 1 altrimenti A = 0
• Formale: Linguaggio di programmazione (esempio
assembler)
Linguaggi per la descrizione di algoritmi
(2)
• Il linguaggio è un formalismo costituito da:
Un insieme di istruzioni primitive (elementi propri, facenti
parte, del linguaggio)
Un insieme di tipi di dato primitivi (numeri interi, numeri
reali, caratteri, ecc.)
Un insieme di operazioni primitive su tali dati (somma e
sottrazione per i numeri interi e reali, ecc.)
Linguaggi semi-formali e formali
• Linguaggi grafici, come quello dei Flow chart o il più
recente e generale linguaggio UML (Unified Modeling
Language). Anche in questo caso si tratta di linguaggi
pensati per un esecutore umano
• Linguaggi di programmazione, come ad esempio C++,
Pascal, Java, VisualBasic, ecc., che sono per loro natura
adatti ad un esecutore automatico, specificatamente il
calcolatore.
Linguaggio naturale
• Il linguaggio naturale non si usa per la descrizione di
algoritmi perchè è inadatto per una macchina:
Ambiguo
Vago
Complicato
• Nessuno ha ancora costruito una macchina che capisce
l'italiano (o l'inglese)
Pseudo-codice
• Risulta più chiaro percepirlo quando si sa già scrivere del
codice piuttosto che al contrario
• Si rischia di scrivere in pseudo-naturale al posto che
pseudo-codice
• Keyword o insieme di keyword che hanno una semantica
precisa (es goto)
• Bisogna ricordarsi sempre dell'esecutore
Diagrammi di flusso (Flow chart)
• I diagrammi di flusso sono un formalismo grafico di
descrizione degli algoritmi. I diversi tipi di istruzioni che
caratterizzano questo formalismo sono rappresentati
tramite blocchi di varia forma, connessi da frecce.
• Orientato principalmente ad un esecutore umano
• Ha il pregio di mettere ben in evidenza il control flow (la
presenza di cicli, di salti, di biforcazioni, ecc..)
Linguaggio di programmazione
• Ideato per tradurre algoritmi in un linguaggio
comprensibile al calcolatore
• Può essere definito in aderenza dettagliata alla macchina
(assembler) o ad un livello più vicino al programmatore
(alto livello)
• Quelli ad alto livello possono seguire paradigmi di
programmazione differenti fornendo strumenti differenti
per la codifica di algoritmi
• Non è generalmente utile nella fase di analisi concentrarsi
sul linguaggio
• E' utile pensare ad un paradigma
• Spesso i programmi non risolvono algoritmi di natura
direttamente matematica ma di natura interattiva
Lezione 2 - Nozione di variabile e
istruzione
Corso — Programmazione
Fondamenti di programmazione— Linguaggi di
programmazione
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Linguaggi per la descrizione di algoritmi
• Importanza dell'esecutore nella definizione dell'algoritmo
• Il ruolo del linguaggio per descrivere l'algoritmo
• Tipologie di linguaggi (informale, semi-formale, formale)
• Importanza di individuare primitive (istruzioni, dati,
operazioni) da usare nella descrizione dell'algoritmo
Variabile
• Concetto di variabile come incognita matematica
• Gli algoritmi agiscono su contenitori di valori che possono
variare
• La variabile risiede in memoria RAM ed ha associato un
identificatore ed una dimensione
• Serve aver ben chiara in mente l'architettura
dell'elaboratore
• La variabile è un oggetto fisico l'incognita matematica è
un oggetto mentale, entrambe vivono durante
l'esecuzione della procedura che le coinvolge
• La vita di una variabile è ben definita in fase di
programmazione (dichiarazione, scopo) non lo è quasi mai
in fase preliminare di analisi e scrittura dell'algoritmo
Istruzioni
• Operazioni da eseguire
• Manipolano le variabili
• Valutazioni sulle variabili che generano dei salti (flusso di
esecuzione)
Se una variabile verifica una condizione fai una cosa
altrimenti fanne un'altra
Es: Se la pasta è cotta scolala altrimenti lasciala cuocere
Es: Se il resto è diverso da zero, ricomincia dal punto 1
• Nel momento in cui si scrive un algoritmo con un
formalismo tra quelli introdotti si inizia a parlare di
programma
Costrutti elementari di descrizione di un
algoritmo
• Primo set di costrutti utili a descrivere un algoritmo
• Assegnamento: Analogo all' = matematico, assegna ad
una variabile il risultato di una operazione
• Decisione: Specifica la condizione che deve essere
valutata in termini di predicato di verità
• Salto: spostamento del flusso esecutivo
• L'accoppiata Decisione salto genera un costrutto di
ripetizione, che permette di far ripetere una serie di
istruzioni (corpo) fino a che la decisione non assume un
valore di verità specifico
Ripeti le seguenti istruzioni fino a che il resto non è zero
Descrizione tramite flow chart
• Assegnamenti racchiusi in rettangoli
• Decisioni racchiuse in rombi
• Flusso definito da frecce
• Una ripetizione è indicata da un loop, ovvero una
sequenza ciclica di istruzioni contenente almeno una
decisione che determina la fine del loop
• I loop vedono la presenza di una freccia di retroazione
Valutazione del flusso
1: Mem[0]:=0
2: read(Mem[1])
3: if Mem[1]≥ 0 then goto 5
4: goto 7
5 Mem[3]:=Mem[0]-Mem[1]
6: if Mem[3]≥ 0 then goto 16
7: write(Mem[1])
8: read(Mem[2])
9: Mem[3]:= Mem[2]-Mem[1]
10: if Mem[3]≥ 0 then goto 12
11: goto 14
12: Mem[3]:=Mem[1]-Mem[2]
13: if Mem[3]≥ 0 then goto 8
14: Mem[1]:=Mem[2] +Mem[0]
15: goto 3
16: halt
Problema - algoritmo - flow chart(1)
• Problema: Moltiplicare due numeri naturali x e y,
ottenendo il risultato r considerando un esecutore che
sappia fare solo somme
• x, r, y denotano delle variabili ovvero un identificativo per
un oggetto che è appunto variabile.
• l'assegnamento avviene espresso con il simbolo ←
• Formalizzazione del problema: r ← x ∗ y
Passo 1:
r ← 0;
u ← y;
Passo 2:
r ← r + x;
u ← u − 1;
Esegui il passo 2 fino a che u = 0;
Esempio di Traccia
• Per verificare la correttezza dell'algoritmo proposto è
possibile fare delle prove e valutarne la tabella contenente
le successioni dei risultati assegnati alle variabili (detta
traccia).
• Esistono numerose varianti per risolvere lo stesso
problema
• Esempio di traccia per l'istanza x = 3 y = 13
Moltiplicazione per somme
• Immaginiamoci di dover scrivere il programma che
esegue una moltiplicazione come somme successive
• Scriviamolo in forma di diagramma di flusso
Flow chart: moltiplicazione per somme
• Trovare delle formulazioni alternative più efficienti per la
moltiplicazione per somme
Esercizio: soluzione
Problema - algoritmo - flow chart(2)
• Problema: Dividere un numero naturale x per un numero
naturale y, ricavando il quoziente intero q e il resto r
• Formalizzazione del problema tramite l'istruzione:
(q,r) ← x div y
• div non è eseguibile va scomposto in sottrazioni ripetute
Passo 1:
q ← 0;
r ← x;
Passo 2: fintanto che r ≥ y ripetere quanto segue
q ← q + 1;
r ← r − y;
• Questo esempio come il precedente descrive un processo
sequenziale.
Flow chart: operazione div
Scrivere il flow chart per l'algoritmo dell'operazione div
descritto in precedenza
Considerazioni
• Quando il problema è di natura matematica, la
formalizzazione matematica è di grande aiuto per la
scrittura del programma
• Un programma descrive delle trasformazioni di stato delle
proprie variabili
• Tali trasformazioni di stato ne definiscono il processo
(programma in esecuzione)
• Il formalismo dei flow chart
Evidenzia dei costrutti che sono alla base della
programmazione
Permette di definite facilmente la traccia del programma
per seguire l'evolversi del processo relativo al programma
Generalmente contiene operazioni definite in un linguaggio
di programmazione formalizzato
Lezione 3 - Linguaggi di Programmazione
(Sintassi e Semantica)
Corso — Programmazione
Fondamenti di programmazione— Linguaggi di
programmazione
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Sintassi e Semantica
• Sintassi di un programma: descrive come viene scritto
• Semantica di un programma: descrive il significato del
programma
• La descrizione della sintassi è la parte più semplice nella
descrizione di un programma
• Un linguaggio di programmazione è descritto da una
sintassi formale e da una semantica informale
• Esempio:
Consideriamo la data come un insieme di caratteri D e / :
01/03/2013 è una data
Il giorno a cui si riferisce non è identificabile considerando
solo la sintassi
Sintassi e semantica: descrizione
• La grammatica ha una importante applicazione nella
definizione della sintassi di un linguaggio di
programmazione
• La semantica può essere resa comprensibile tramite delle
descrizioni in linguaggio naturale
• Esiste un conflitto tra precisione e leggibilità che ha dato
vita a diverse forme di descrizione di un linguaggio.
Tutorial: per esempi sintassi e semantica introdotti
gradualmente
Manuale di riferimento: Organizzato solitamente attorno
alla sintassi
Definizioni formali: descrizione precisa di sintassi e
semantica, per specialisti
• La semantica formale non interessa per questo corso ma
per un corso di linguaggi
Notazione delle espressioni matematiche
(1)
• Espressioni tipo a − b + c sono utilizzate dalla matematica
da secoli
• Alcuni linguaggi di programmazione cercano di utilizzare
una notazione simile per renderla più familiare
• In generale i linguaggi di programmazione usano dei mix
di notazioni differenti
Prefissa: l'operatore è indicato prima degli operandi +a b
Postfissa: l'operatore è indicato dopo gli operandi a b+
Infissa: l'operatore è indicato tra gli operandi a + b
• Le notazioni prefissa e post fissa non richiedono parentesi
per essere eseguite correttamente (nell'ordine corretto)
Notazione delle espressioni matematiche
(2)
• Il numero di operandi di un operatore è detto arità
• Es. notazione prefissa ∗ + 10 20 30 = ∗30 30 = 900 similmente
∗10 + 20 30 = ∗10 50
• Es. notazione postfissa 10 20 + 30∗ = 30 30∗ = 900
similmente 10 20 30 + ∗ = 10 50∗
• La notazione infissa richiede delle regole di precedenza o
l'uso di parentesi
• Operatori con la stessa precedenza (e.g. + e -) vengono
raggruppati usando nella norma la associazione sinistra
• Esiste la notazione mista
Alcuni varianti della notazione prefissa sono ad esempio le chiamate a funzione tipo
max(x,y) dove l'arità è variabile dipendente da quello che c'è in parentesi
Abstract Syntax Tree (AST)
• Evidenzia i componenti più significativi di un linguaggio e
li mostra nella forma di un albero (struttura sintattica)
• Esempio per espressioni matematiche E costituite da
operatore e operandi
Abstract Syntax Tree (AST)
• Esercizio: Disegnare l'AST delle espressioni nelle forme
prefissa +a b infissa a + b e postfissa a b+
• L'AST è indipendente dalla notazione (equivale a dire
indipendente dalla grammatica)
• Esercizio: Disegnare l'AST dell'espressione − ∗ b b ∗ ∗4 a c
Il concrete syntax tree (parse tree) è la versione specifica dell'AST per una data
grammatica
AST soluzioni
Abstract Syntax Tree
• AST per la valutazioni dei condizioni nella forma: se
< condizione > allora < istruzione > altrimenti
< istruzione >
• Esempio: se a>0 allora b altrimenti c
• Consideriamo l'operatore se allora altrimenti come se
fosse un singolo operatore
• E' un operatore ternario
• Albero con la radice se allora altrimenti 3 figli per le 3
sottoparti
Abstract Syntax Tree
Sintassi e lessico
• Lessico: l'insieme di regole formali per la scrittura di
parole in un linguaggio
• Sintassi: l'insieme di regole formali per la scrittura di
frasi in un linguaggio
• La sintassi di un linguaggio di programmazione è
specificata in termini di token o terminatori.
• La sintassi lessicale di un linguaggio di programmazione
rappresenta la corrispondenza tra una rappresentazione
scritta del linguaggio e i token o i terminatori della
grammatica del linguaggio.
Determina come una sequenza di caratteri venga suddivisa
in lessemi e come questi vengano catalogati rispetto alla
grammatica
Esempio grammatica italiana: classifica il lessema come
verbo avverbio sostantivo ecc.
Sintassi e lessico
• Le sequenze di caratteri alfabetici che vengono trattati
come un unica cosa da un linguaggio sono chiamate
keyword
Keyword diventano delle parole riservate se non possono
essere usate come nome in un linguaggio
• Considerando il token name per i nomi e il token number
per i numeri:
b ∗ b − 4 ∗ a ∗ c diventa come sequenza di token :
nameb ∗ nameb − number4 ∗ namea ∗ namec
• Generalizzo l'espressione in termini di token
Lezione 4 - Linguaggi e Grammatica
Corso — Programmazione
Fondamenti di programmazione— Linguaggi di
programmazione
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Università degli Studi di Milano — Dipartimento di informatica
Linguaggio di programmazione (1)
• Un repertorio di segni convenzionali e di regole per
combinarli in enunciati più complessi ed un insieme di
regole che permettano di associare un significato a
ciascun enunciato.
• Si distinguono 3 livelli
Sintattico: regole che specificano in quali modi i segni
possano essere combinati per formare enunciati;
Semantico: regole che permettono di associare a ciascun
segno e a ciascun enunciato il loro significato;
Pragmatico: implicazioni pratiche e le conseguenze di un
enunciato.
Linguaggio di programmazione (2)
• Alfabeto Σ
• Simboli o token
• Parola w su un alfabeto
• Σ∗ denota l'insieme di tutte le parole composte da
elementi di Σ, compresa .
Linguaggio di programmazione (3)
• Un linguaggio L è un sottoinsieme delle parole costruibili
su un alfabeto Σ, L ⊆ Σ∗ .
• Data una parola w ∈ Σ∗ , ci sono due possibilità:
w appartiene al linguaggio, w ∈ L, cioè rappresenta un
enunciato di L
w non appartiene al linguaggio, w ∈
/ L, cioè non
rappresenta un enunciato valido di L.
• In seguito vedremo un sistema generativo fondamentale
che è la grammatica
Introduzione alla grammatica
• Si può dire che la grammatica di un linguaggio impone
una struttura gerarchica (parse tree) ai programmi definiti
con quel linguaggio
• Consideriamo un numero reale tipo 7.13 il relativo parse
tree similmente al AST sarà
Introduzione alla grammatica
• Le foglie della gerarchia sono i token o terminali
• I nodi contengono i simboli non terminali
• Un non terminale è un costrutto del linguaggio
• Ogni nodo è generato da un processo detto di produzione,
ovvero una regola che definisce un simbolo non terminale
in termini di una sequenza di altri non terminali o terminali
• I token, i non terminali, le produzioni, il non terminale
iniziale, costituiscono la grammatica per un linguaggio
Grammatica (1)
• Una grammatica è una quartupla G = (N,Σ,R,S)
• N insieme dei simboli non terminali, o metasimboli, cioè
che non possono comparire negli enunciati del linguaggio
ma che ci servono per denotare elementi di un enunciato
N∩Σ=∅
• Σ alfabeto del linguaggio costituito da simboli terminali.
• R insieme finito delle regole di produzione nella forma
α → β con α ∈ N ∗ \ {} e β ∈ (N ∪ Σ)∗ . Quando la regola
viene applicata, un'istanza di una stringa α può essere
riscritta in una istanza della stringa β
• S simbolo non terminale speciale, S ∈ N ed è il punto di
partenza che denota un enunciato valido.
Grammatica (2)
[Relazione di produzione e derivazione]
Produzione: ⇒G ⊆ (N ∪ Σ)∗ × (N ∪ Σ)∗ : γ ⇒G δ sse δ si ottiene
da γ mediante l'applicazione di una singola regola di
produzione di R nella grammatica G.
• Regole di riscrittura dei non terminali
Derivazione: ⇒∗G : γ ⇒∗G δ sse δ si ottiene da γ mediante
l'applicazione di zero o più regole di produzione di R nella
grammatica G
• Regole da applicare per verificare la derivabilità rispetto a
delle produzioni partendo dal simbolo iniziale
[Linguaggio generato da G denominato L(G)]
L'insieme di tutte le sequenze di simboli terminali ottenibili
applicando le regole di produzione dell'insieme R, a partire dal
simbolo iniziale S. L(G) = {w : w ∈ Σ∗ ∧ S ⇒∗G w}
AST e parse tree
• La grammatica viene scritta per
riflettere la sintassi astratta
• Significa che le regole di produzione sono fatte per far in
modo che il parse tree sia il più possibile simile all' AST
Esempio (1)
• Linguaggio delle espressioni aritmetiche
• Σ = {0,1,2,3,4,5,6,7,8,9, + ,?, × ,/,(,)}
• E simbolo di partenza A sta per argomento, O per
operazione, N per numero naturale, I per cifra iniziale di
un numero naturale, M per sequenza delle eventuali cifre
successive di numero naturale, e C denota una qualsiasi
cifra decimale.
Esempio (2)
• Esempio di derivazione per la stringa 2 × (3 + 4)
• Si ricava che E ⇒∗ 2 × (3 + 4) quindi 2 × (3 + 4) appartiene al
linguaggio.
Esercizio (1)
Data la seguente grammatica:
S ⇒ CVRT
C⇒T
C⇒R
C⇒h
V ⇒a
V ⇒i
V ⇒u
T ⇒p
T ⇒t
T ⇒k
R⇒n
R⇒l
R⇒r
Esercizio (2)
S ⇒ CVRT ; C ⇒ T ; C ⇒ R ; C ⇒ h ; V ⇒ a ; V ⇒ i ; V ⇒ u ;
T ⇒ p ; T ⇒ t ; T ⇒ k ; R ⇒ n ; R ⇒ l ; R ⇒ r ; Quale delle
seguenti espressioni fa parte del linguaggio?
tank
tar
bin
leak
Lezione 5 - BNF e carte sintattiche
Corso — Programmazione
Fondamenti di programmazione— Linguaggi di
programmazione
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Università degli Studi di Milano — Dipartimento di informatica
Formato di Backus e Naur BNF(1)
• La grammatica non contestuale è indipendente dalla
notazione con la quale si esprime
• Formalismo utilizzato nell'informatica
→ delle regole viene sostituita da ::=
I simboli non terminali sono rappresentati mediante
stringhe alfanumeriche racchiuse tra parentesi angolari (ad
esempio <espressione>)
I simboli terminali, o token del linguaggio, sono di norma
racchiusi tra virgolette (' ' o 00 00 )
Notazione compatta per più regole con lo stesso membro
sinistro
<cifra iniziale> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
Formato di Backus e Naur BNF(2)
• Esistono alcune varianti a seconda dell'autore (esempio
Extended BNF)
• Gli elementi opzionali sono spesso racchiusi tra parentesi
tonde o quadre, mentre le parentesi graffe sono usate
praticamente in tutte le varianti del BNF per denotare
elementi che possono essere ripetuti zero o più volte
• Esercizio: Ridefinire in BNF la grammatica dell'esempio
delle espressioni matematiche
Esercizio: soluzione
< espr >::=< num > |0 (0 < espr >0 )0 | < espr >< op >< espr > |
< espr >0 =0 < espr >
< num >::=< cifra > | < num >< cifra >
< cifra >::=0 00 |0 10 | . . . |0 90
< op >::=0 +0 |0 −0 |0 · 0 |0 /0
Esempio: numero reale
Il simbolo ::= può essere letto come può essere e il simbolo |
come oppure
< real − number >::=< integer − part >. < fraction >
< integer − part >::=< digit > | < integer − part >< digit >
< fraction >::=< digit > | < digit >< fraction >
< digit >::=00 000 |00 100 |00 200 |00 300 |00 400 |00 500 |00 600 |00 700 |00 800 |00 900
Esercizio
Si consideri la seguente definizione in BNF di un linguaggio:
< expr >::=< const > | < fn >00 (00 < args >00 )00
< args >::=< expr > | < expr >00 ,00 < args >
< const >::=00 a00 |00 b00 |00 c 00 |00 d 00 |00 e00
< fn >::=00 f 00 |00 g00 |00 h00
Quale delle seguenti espressioni fa parte del linguaggio?
a|e(f ,h)
g(a)
g()
g
Esempio BNF linguaggio naturale
• Σ = {il,lo,la,cane,mela,gatto,mangia,graffia,,}
• N = {frase,soggetto,verbo,complemento,articolo,nome}
• P, regole espresse in BNF (forma di Backus-Naur):
frase ::= soggetto verbo complemento
soggetto ::= articolo nome
articolo ::= il | la | lo
nome ::= cane | mela | gatto
verbo ::= mangia | graffia
complemento ::= articolo nome | articolo nome
complemento
,
• S = frase
Esempio tratto dal libro: Pighizzini, Ferrari, ``Dai fondamenti agli oggetti''
Parse tree
• E' un albero ordinato con radice, che rappresenta la
struttura sintattica di una stringa relativamente ad una
grammatica formale
• Si differenzia dall' AST perchè i suoi elementi riflettono più
concretamente la sintassi di un linguaggio in input
• Una grammatica per un linguaggio impone un parse tree
sui programmi scritti in quel linguaggio
Esempio di produzione (Parse tree)
frase
soggetto
Q
Q
Q
Q
complemento
verbo
Q
AA @
@ QQ
A @ Q
@
@
articolo
nome graffia articolo nome
@
,
complemento
@
@
lo
mela
lo
gatto articolo
il
Esempio tratto dal libro: Pighizzini, Ferrari, ``Dai fondamenti agli oggetti''
@
nome
cane
Ambiguità sintattiche
• Se una stringa ha più di un parse tree allora la
grammatica associata è ambigua
• Un linguaggio di programmazione va sempre descritto con
una grammatica non ambigua, quindi serve disambiguare
dove necessario
• Esempio: E::= E - E | 0 | 1
• La stringa 1 - 0 - 1 ha due parse tree quindi è ambigua la
grammatica
Grammatica per espressioni matematiche
• Una lista di elementi in notazione infissa
• Gli elementi non terminali sono: termini T (tra somme),
fattori F (tra moltiplicazioni) ed il simbolo iniziale di
espressione E
• Ecco la grammatica:
E::= E + T | E - T | T; T::=T * F | T / F | F; F::= number |
name | (E)
Carte sintattiche
• Le carte sintattiche sono dei diagrammi che esprimono le
regole di una grammatica in forma grafica.
• Per specificare una grammatica mediante carte
sintattiche, si deve fornire un diagramma per ciascun
simbolo non terminale
• In una carta sintattica:
I rettangoli indicano simboli non terminali (che andranno
espansi con le carte sintattiche corrispondenti)
Gli ovali o rettangoli con gli angoli arrotondati, indicano
simboli terminali, che quindi non devono essere espansi
ulteriormente
Le frecce sono definite in modo tale che, seguendo i
percorsi da esse delineati, sia possibile ricostruire una
sequenza lecita di simboli
Ogni biforcazione indica un'alternativa
Carte sintattiche esempio espressione
Definire la grammatiche dell'esempio delle espressioni usando
il formalismo delle carte sintattiche
Lezione 6 - Espressioni Regolari
Corso — Programmazione
Fondamenti di programmazione— Linguaggi di
programmazione
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Università degli Studi di Milano — Dipartimento di informatica
Espressioni regolari
• Necessità di individuare un insieme limitato di regole
capaci di generare tutte le frasi di un linguaggio
• Una importante notazione per indicare queste regole:
espressioni regolari
Non sono in grado di esprimere tutte le possibili strutture di
un linguaggio
Efficaci per specificare i tipi di strutture di cui
effettivamente si avvalgono i linguaggi di programmazione
per costruire i tipici token che l'analizzatore lessicale è
chiamato a riconoscere
Espressioni regolari: costruzione
• Utilizzano le operazioni tipiche di un linguaggio formale L
• Alfabeto Σ, unione Σ ∪ Σ, concatenazione Σ · Σ, Σ∗ , Σ+
• Partendo da un linguaggio formato da stringhe di
lunghezza unitaria se ne creano altri di lunghezza 2, 3, ...
• Questo processo applicato ad un alfabeto è molto utile ed
ha preso il nome di espressione regolare
Espressioni regolari: definizione
• Espressione regolare r ,definita su Σ e su un insieme di
metasimboli +, ∗ ,(,), · ,∅ non appartenenti a Σ, è una
stringa r appartenente all'alfabeto (Σ ∪ +, ∗ ,(,), · ,∅) tale
che valga una delle seguenti condizioni (alcune espresse
per induzione)
r =∅
r =
r = x, x ∈ Σ
r = (s + t), s,t espressioni regolari su Σ e + è l'unione
r = s · t, s,t espressioni regolari su Σ e · è la concatenazione
r = s∗ , s espressione regolare su Σ e ∗ è la chiusura di
Kleene
Espressioni regolari: esempi
• Regole
st equivale a s · t
s|t equivale a s + t
= ∅∗
Operatore potenza r h = r . . . r(h volte)
Precedenza tra operatori: ∗, · , +
Le parentesi servono per modificare le precedenze
• Esempi
R = a|(ab) S = c|(bc)
RS = (a|(ab))(c|(bc)) = ac|(ab)c|a(bc)|(ab)(bc) = ac|abc|abbc
L(RS) = {ac,abc,abbc}
R∗ = (a|b)∗ ; L(R∗ ) = {,a,b,aa,ab,bb,ba,aaa,aba, . . . }
(a + b)∗ a rappresenta il linguaggio L = {x|x ∈ ({a} ∪ {b})∗ e x
termina con a}
Espressione regolare per L = {w ∈ {0,1}∗ : 0 e 1 alternati in
w}
(01)∗ + (10)∗ + 0(10)∗ + 1(01)∗
Espressioni regolari: varabili
• Nomi di variabili di un linguaggio
• Stringhe che iniziano con una lettera e che possono
contenere caratteri alfanumerici
• caratteri = A|B|C|…|Z|a|b| . . . |z|
• numeri = 0|1|2|3|4|5|6|7|8|9
• Espressione regolare:
variabile = caratteri(caratteri|numeri)∗
L(variabile) =
A,B, . . . ,a, . . . ,z,AA, . . . ,X 1, . . . ,j1, . . . ,contatore, . . .
Espressioni regolari: generazione
• L'espressione regolare r genera l'espressione s (notazione
r → s) se:
• r = xαy
• s = xβy
• Le espressioni x, y, α sono sotto-espressioni di r e vale
una delle seguenti condizioni:
• α = e1 ∪ . . . ,ek ∪ . . . en e β = ek
• α = e∗ e β = e . . . e (h volte)
Grammatiche regolari e linguaggi regolari
• Tipo 3 di Chomsky
• Produzioni nella forma A → β A ∈ N e β ∈ (N ∪ Σ)∗
• Produzione destra A → aB B → b
• Produzione sinistra B → Ab A → a
• Con A,B ∈ N e a,b ∈ Σ
• Un linguaggio regolare è un linguaggio le cui stringhe
sono implicate da un'espressione regolare
• Un linguaggio è detto regolare se è prodotto da
un'espressione regolare
Uso delle espressioni regolari
• Le espressioni regolari vengono utilizzate come linguaggio
di input per vari sistemi che trattano stringhe
• Comandi UNIX (grep) per la ricerca di stringhe
(metacaratteri)
• Generatori di analizzatori lessicali, tipo Lex (Lexical
analyzer generator) e Flex (Fast Lex))
• Grammatiche di tipo 3 sono adatte a rappresentare un
ristrettissimo insieme di linguaggi formali
Lezione 7 - Classificazione dei linguaggi di
programmazione
Corso — Programmazione
Fondamenti di programmazione— Linguaggi di
programmazione
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Programmazione a basso livello
• A seconda di dove ci poniamo il basso livello e l'alto
cambia
• Per il programmatore assembler il basso livello è il
linguaggio macchina
• Per il programmatore Java il basso livello è il c
Linguaggio macchina
• Il linguaggio macchina è il linguaggio in cui sono scritti i
Programmi che la CPU è in grado di eseguire (è il risultato
della decode)
• Ogni istruzione (es. lettura, somma, etc.) è definita da un
codice binario speciale detto codice operativo
• Ogni processore ha un proprio linguaggio macchina con
un proprio formato delle istruzioni
• Un'istruzione è costituita da una stringa di bit contenente:
L'operazione da eseguire
Gli operandi su cui tale operazione deve essere eseguita
(registri, locazioni di memoria, costanti ...)
Linguaggio macchina
• Operazione complessa, serve indicare istruzioni e
operandi in codice binario
• Il linguaggio assembler di un processore è la versione
simbolica del linguaggio macchina
• Vengono adoperati dei simboli per la rappresentazione del
codice operativo (tipo add per la somma) e degli operandi
di un'istruzione
• Corrispondenza biunivoca tra l'insieme delle istruzioni in
linguaggio macchina ed in linguaggio assembler per una
stessa CPU
• L' assembler deve essere tradotto in linguaggio macchina
per essere eseguito dalla CPU (Assemblatore)
Istruzioni assembler(1)
• Aritmetico-logiche: manipolano dati in ingresso e
restituiscono il risultato in uscita, specificando dove
depositare il risultato, solitamente in un Registro della
CPU (es. ADD R01, R02)
• Salti: alterano l'esecuzione sequenziale del programma
• Salto incondizionato: specificano l'indirizzo di memoria
in cui si trova la prossima istruzione da eseguire (es.
JUMP label1)
Istruzioni assembler(2)
• Salto condizionato: salto soggetto al verificarsi di una
condizione che se non verificata lascia proseguire il
programma in sequenza (JZERO R01, label1)
• Ingresso/uscita: servono a trasferire dati da e verso la
CPU (es. LOAD R01,x STORE R01,y)
M.C.D in assembler
LOAD R01, 101
LOAD R02, 102
label1: DIV R01, R02
MUL R01, R02
LOAD R02, 101
SUB R02, R01
JZERO R02, fine
LOAD R01, 102
STORE R01, 101
STORE R02, 102
JUMP label1
fine:
LOAD R01, 102
STORE R01, 103
Esempio tratto dal libro: Pighizzini, Ferrari, Dai fondamenti agli oggetti
Svantaggi del linguaggio macchina
• Richiedono competenze sui dettagli dell'architettura della
macchina ed il relativo linguaggio che varia a seconda
della CPU
• I programmi così scritti non sono assolutamente portabili
• Il programmatore si specializza nella programmazione di
una particolare macchina
• I programmi così sviluppati risultano di difficile
comprensione e molto difficili da modificare
• La struttura logica del programma è nascosta, il
debugging diventa davvero complesso
• Il ciclo di vita del programma è limitato alla sola macchina
per cui è stato scritto
Linguaggi di programmazione:
classificazione (1)
• Linguaggi ad alto livello e linguaggi a basso livello
• La distinzione, in generale, non è così netta
• I linguaggi a basso livello sono quelli che sono
strettamente dipendenti da una specifica macchina
hardware
00000010101111001010
00000010111111001000
00000011001110101000
Addiziona i numeri nella locazione 10 e 11 e li salva in 12
• I linguaggi ad alto livello nascondono, le caratteristiche
delle diverse macchine hardware
• Sono scritti per funzionare su una macchina astratta M e
offrono al programmatore una sintassi molto più vicina al
linguaggio naturale
Linguaggi di programmazione:
classificazione (2)
• General purpose: una caratteristica del linguaggio di
programmazione che dice che tale linguaggio può essere
adottato per un vasto range di applicazioni.
• Inizialmente i linguaggi si svilupparono con degli obiettivi
ben precisi, in seguito tendettero a diventare general
purposes
• Esempi: Fortran (numerical computing), Lisp (artificial
intelligence), Prolog (natural language processing)
[Benefici linguaggi ad alto livello]
•
•
•
•
Leggibilità
Indipendenza dalla macchina (portabilità)
Possibilità di packaging in librerie
Controllo di consistenza durante lo sviluppo