Lezione1-Linguaggiperladescrizionedi algoritmihomes.di.unimi.it/anisetti/Teaching/Unit5.pdf · q...

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/

Università degli Studi di Milano — Dipartimento di informatica

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 naturaledevo individuare:

Le istruzioni operativeIl controllo del flusso delle istruzioni. Ad esempio unacondizione per eseguire una determinata operazione, unsalto ad una determinata locazione dell'algoritmo

Algoritmo operazioni: esempio

• Esempio euclide

Calcola il resto della divisione di x per y : istruzioneoperativa (r ← x mod y)Se il resto è diverso da zero, ricomincia dal punto 1utilizzando come x il valore attuale di y, e come y il valoredel resto: controlloaltrimenti prosegui con il passo successivo: controlloIl 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 umanoPseudo-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, facentiparte, del linguaggio)Un insieme di tipi di dato primitivi (numeri interi, numerireali, caratteri, ecc.)Un insieme di operazioni primitive su tali dati (somma esottrazione 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 dialgoritmi perchè è inadatto per una macchina:

AmbiguoVagoComplicato

• 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



programmazione

Marco 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 diesecuzione)

Se una variabile verifica una condizione fai una cosaaltrimenti fanne un'altraEs: Se la pasta è cotta scolala altrimenti lasciala cuocereEs: 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 aduna 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 diripetizione, che permette di far ripetere una serie diistruzioni (corpo) fino a che la decisione non assume unvalore 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 54: goto 7

5 Mem[3]:=Mem[0]-Mem[1]

6: if Mem[3]≥ 0 then goto 167: write(Mem[1])

8: read(Mem[2])

9: Mem[3]:= Mem[2]-Mem[1]

10: if Mem[3]≥ 0 then goto 1211: goto 14

12: Mem[3]:=Mem[1]-Mem[2]

13: if Mem[3]≥ 0 then goto 814: 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 ∗ yPasso 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 dellaprogrammazionePermette di definite facilmente la traccia del programmaper seguire l'evolversi del processo relativo al programmaGeneralmente contiene operazioni definite in un linguaggiodi programmazione formalizzato

Lezione 3 - Linguaggi di Programmazione

(Sintassi e Semantica)



programmazione

Marco 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 dataIl giorno a cui si riferisce non è identificabile considerandosolo 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 datovita a diverse forme di descrizione di un linguaggio.

Tutorial: per esempi sintassi e semantica introdottigradualmenteManuale di riferimento: Organizzato solitamente attornoalla sintassiDefinizioni formali: descrizione precisa di sintassi esemantica, 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 mixdi notazioni differenti

Prefissa: l'operatore è indicato prima degli operandi +a bPostfissa: 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∗ = 900similmente 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 programmazionerappresenta la corrispondenza tra una rappresentazionescritta del linguaggio e i token o i terminatori dellagrammatica del linguaggio.

Determina come una sequenza di caratteri venga suddivisain lessemi e come questi vengano catalogati rispetto allagrammaticaEsempio grammatica italiana: classifica il lessema comeverbo avverbio sostantivo ecc.

Sintassi e lessico

• Le sequenze di caratteri alfabetici che vengono trattaticome un unica cosa da un linguaggio sono chiamatekeyword

Keyword diventano delle parole riservate se non possonoessere usate come nome in un linguaggio

• Considerando il token name per i nomi e il token numberper 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



programmazione

Marco Anisetti





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 segnipossano essere combinati per formare enunciati;Semantico: regole che permettono di associare a ciascunsegno e a ciascun enunciato il loro significato;Pragmatico: implicazioni pratiche e le conseguenze di unenunciato.


• Alfabeto Σ

• Simboli o token

• Parola w su un alfabeto

• Σ∗ denota l'insieme di tutte le parole composte daelementi di Σ, compresa ε.


• 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 unenunciato di Lw non appartiene al linguaggio, w /∈ L, cioè nonrappresenta 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 regolaviene applicata, un'istanza di una stringa α può essereriscritta in una istanza della stringa β

• S simbolo non terminale speciale, S ∈ N ed è il punto dipartenza che denota un enunciato valido.

Grammatica (2)

[Relazione di produzione e derivazione]

Produzione: ⇒G⊆ (N ∪ Σ)∗ × (N ∪ Σ)∗ : γ ⇒G δ sse δ si ottieneda γ mediante l'applicazione di una singola regola diproduzione 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 allinguaggio.

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



programmazione

Marco Anisetti





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 mediantestringhe alfanumeriche racchiuse tra parentesi angolari (adesempio <espressione>)I simboli terminali, o token del linguaggio, sono di normaracchiusi tra virgolette (' ' o ′′ ′′)Notazione compatta per più regole con lo stesso membrosinistro

<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 > |′(′< espr >′)′| < espr >< op >< espr > |< espr >′=′< espr >< num >::=< cifra > | < num >< cifra >< cifra >::=′ 0′|′1′| . . . |′9′< op >::=′ +′|′ −′ |′ · ′|′/′

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 >::=′′ 0′′|′′1′′|′′2′′|′′3′′|′′4′′|′′5′′|′′6′′|′′7′′|′′8′′|′′9′′

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 complementosoggetto ::= articolo nomearticolo ::= il | la | lonome ::= cane | mela | gattoverbo ::= mangia | graffiacomplemento ::= 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)

��

��

��

@@@

@@@

@@@

��

QQ

QQ

QQ

QQ

AAA

articolo nome articolo nome complemento

articolo nome

soggetto verbo complemento

frase

lo mela

graffia

lo gatto

,

il cane

Esempio tratto dal libro: Pighizzini, Ferrari, ``Dai fondamenti agli oggetti''

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 andrannoespansi con le carte sintattiche corrispondenti)Gli ovali o rettangoli con gli angoli arrotondati, indicanosimboli terminali, che quindi non devono essere espansiulteriormenteLe frecce sono definite in modo tale che, seguendo ipercorsi da esse delineati, sia possibile ricostruire unasequenza lecita di simboliOgni 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



programmazione

Marco Anisetti





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 diun linguaggioEfficaci per specificare i tipi di strutture di cuieffettivamente si avvalgono i linguaggi di programmazioneper 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 dimetasimboli +, ∗ ,(,), · ,∅ non appartenenti a Σ, è unastringa r appartenente all'alfabeto (Σ ∪+, ∗ ,(,), · ,∅) taleche valga una delle seguenti condizioni (alcune espresseper induzione)

r = ∅r = εr = x, x ∈ Σr = (s + t), s,t espressioni regolari su Σ e + è l'unioner = s · t, s,t espressioni regolari su Σ e · è la concatenazioner = s∗, s espressione regolare su Σ e ∗ è la chiusura diKleene

Espressioni regolari: esempi

• Regole

st equivale a s · ts|t equivale a s + tε = ∅∗

Operatore potenza rh = 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|abbcL(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 xtermina con a}Espressione regolare per L = {w ∈ {0,1}∗ : 0 e 1 alternati inw}(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, . . . ,X1, . . . ,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 valeuna 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



programmazione

Marco 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 eseguireGli 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

Lezione1-Linguaggiperladescrizionedi algoritmihomes.di.unimi.it/anisetti/Teaching/Unit5.pdf · q...

Documents

Transcript of Lezione1-Linguaggiperladescrizionedi algoritmihomes.di.unimi.it/anisetti/Teaching/Unit5.pdf · q...