Programmazione I e Laboratorio

www.di.unipi.it/tadd.... DISPENSA

1^o Compitino fine ottobre - inizio novembre

Lun - mar - gio → teoria

mer → programmazione

~ Sintassi vs Semantica

sintassi →

"Il bimbo mangia la mela" → italiano OK

"bimbo mela mangia le..." → struttura grammaticale che non ha un corrispettivo in It.

"La mela mangia il bimbo" → non è significativa ma sintatticamente è seguita.

~ Linguaggio imperativo

Ho un insieme di stati iniziali, un programma che mi porta ad un insieme di stati finali.

• TRANS formatore di stati: prendo un comando del tipo:

ST. INIZIALE { } int x, y [ iniziali: 2, 3. Var. intere ]

{x < , x > y, y < } _{← o}

{x, or, yz, yx < } _{← 0}

{x, or, ey, yz} y ← x + 1

tutta la componente iterativa è interpretabile come una funzione che prende uno stato e ne associa un altro.

• se io ho solo y ← x + 1...
• < x, k > , < y, l > → < x, k >, < y, k + 1 >

→ Per costruire la semantica cerco di capire la struttura della sintassi ed i suoi operatori

~ Stato

Insieme di coppie dove ad ogni variabile è associato un valore

{ <x₁, k₁>, <x_n, k_n>}

⁄ x_j → / → devo vedere quanto vale x_j e poi sommare

{ x₁, 5 > < x₂, 4 > , < x₃, 6 > }

∈ ℤ

x₃ + 2 < x₂, 3 ⁴

X₃ + 7 = x₃

B -> boolean

x₄ + 7 non ha significato se x₄ è un booleano.

wt x₁, x₂, x₃

bool x₄

x₄ + 7 ERRORE! L’operatore “ + ” è applicato ad una variabile che può non essere intera.

COMANDI DI BASE

• Assegnamento

x ← e

x₂ ← x₃ + x₂ { x₁, 5 > < x₂, 4 > } { < x₃, 6 >, x₄, true }

X₂ = 10

Stato aggiornato, tutto uguale ma < x₂, 10 >

• Comandi condizionali

if (c_e)

C₁

ejs_e

C₂

C1 e C2 possono essere comandi.

Valuto c_e; se è un valore vero eseguo un comando, altrimenti l’altro.

if (x₁ < x₂)

~ il valore associato alla var X₁ è minore di x₂?

x₁ ← x₂

NO! Quindi x₂ prende il valore di x₁.

ejs_e ←

x₂ ← x₁

ASSEGNA IL MASSIMO AL PIÙ PICCOLO

Data una funzione c’è sempre un programma che ne la calcola? NO.

Soluzioni delle 3 funzioni

• Massimo Comune Divisore
  1. {<x, y, ->} → parto da uno stato in cui sono definita.
  2. while (x ≠ y)
     • do if (x > y)
       • x ← x - y
     • else
       • y ← y - x

  Da ricorsiva a iterativa

  • {<x, MCD(k₁, k₂)>}
  • {<y, MCD(k₁, k₂)>}

• Fattoriale
  1. fatt ← 1
  2. f{<x, ->}
  3. while (x ≠ 0) do
     • fatt ← x * fatt
     • x ← x - 1

  Se è 0 la x si ferma direttamente e restituisce 1

  • {<x, 2>}
  • {<x, 2>, <fatt, 1>}
  • {<x, 2>, <fatt, 2>} → 1° while: 1x1
  • {<x, 1>, <fatt, 2>} → 1° while, x decrementato
  • {<x, 1>, <fatt, 2>}
  • {<x, 0>, <fatt, 2>} → 2° while mi fermo

• Dato un rettangolo di dimensioni x e y quale è il numero minimo di quadrati che lo ricopre?
  • N° massimo → x * y
  • N° minimo →
    • 4

• quar (3, 2) → 1 + quar (2, 1)
  • → 1 + quar (1, 1)
  • → 1

L₂ = { stringhe che contengono esattamente 2 'a' }

N° PARI DI 2

ε lettera qualunque

2 lettera specifica

aabaa, aabb

andava bene quello che avevi fatto lo sotto.

27/09

Se un linguaggio è riconosciuto da un AFD allora esiste un ASF equivalente, ovvero che riconosce lo stesso linguaggio.

Gli ASFND sono al più ma riconoscono lo stesso n° di linguaggi.

Possiamo parlare di linguaggi riconosciuti da ASF senza specificare se det. o non det. poichè hanno la stessa potenza.

L₁ = { aⁿb^m | n > 0 }

L₂ = { a^kb | aabb aaabbb... }

Non esiste un ASF che riconosca L₁ avrei bisogna di INFINITI stati.

L₃ = { aⁿb^m | n > 0 }

L₂' = { a^2mb^m | m, u > 0 }

C'è un modo per definire L₂' e usa strumenti più potenti degli aut. chi definisce i lingugg. sono le GRAMMATICHE

L ∉ L₁

L ⊂ L₁

Se prendiamo una stringa abba aaabba è un sotto insieme di tutte le stringhe di n° pari con A termina con B.

Nonostante L₂ sia più piccolo di L₁ non è riconosciuto da un ASF, mentre L₂' è riconosciuto e più complesso.

GRAMMATICA A STRUTTURA DI FRASE

(grammatiche libere da contesto)

Una grammatica G = è una quaterpla composta da un insieme finito di simboli (alfabeto) V, insieme finito di simboli (e⁰ = = V) che chiamano categorie sintattiche anche simboli non terminali. S ∈ V = Ev ed una categoria sintattica iniziale (dominatra particolare) infine P che è un insieme FINITO di PRODUZIONI.

G = < L, V, S, P >

Disambiguare una grammatica

Date una grammatica G ambigua che definisce un linguaggio L, è possibile trovare una grammatica G' non ambigua equivalente, cioè che definisce lo stesso linguaggio L?

IN GENERALE NO.

Esistono linguaggi intrinsecamente ambigui, cioè sono definiti da grammatiche che sono tutte ambigue.

Però sulle parentesi bilanciate ci si riesce!

S → (S) | (SS) | ε

doppia ricorsione, che dà ambiguità

S → (S) | (S) (S) | A

A → (S) | ε

Ho tolto la doppia ricorsione

Non posso espandere A quindi non è più ambigua. Devo sempre generare la parte con A e poi utilizz _z S.

ESEMPIO

L = {a, b, +, *}

Linguaggio delle espressioni sibilibili su L

• a + a b ∈ L
• a x b + a b ∈ L
• a a ∉ L
• a * b ∅ ∈ L

S → a | b | S + S | S * S

a + b x a

AMBIGUA!

Grammatiche Regolari:

• A → aB
• A → a

Grammatiche Libere:

• A → α

I linguaggi riconosciuti da ASF sono gli stessi generati dalle grammatiche regolari.

L = {aⁿbⁿ | n > 0}

Esempio:

1. L = {aⁿbⁿcⁿ | n > 0}

• È generabile da G regolare? È riconosciuto da ASF? NO

perché non posso tenere traccia delle n volte.

La grammatica libera che lo genera è:

• S → aSb | aSb

2. L = {aⁿb^m | m ≥ n ≥ 0}

È regolare? NO!!

• S → aAb | aC b | b
• Può avere quante b in più voglio

3. L = {a^mb^n | n, m > 0}

• S → aSc | aAc
• A → b | bA

Λ = {a, b, c}