Backus Naur Form

(1)

Backus Naur Form

Paolo Bison

Fondamenti di Informatica Ingegneria Meccanica

Università di Padova A.A. 2008/09

BNF , Paolo Bison, FI08, 2008-09-29 – p.1

Linguaggio di programmazione

strumento linguistico per scrivere una sequenza di istruzioni (programma) che definiscono una computazione

descritto da

sintassi

semantica

Linguaggio formale

sintassi

- Backus Naur Form (BNF)

semantica

- operazionale - denotazionale

Backus Naur Form (BNF)

formalismo per descrivere la sintassi

metalinguaggio

(2)

Concetti - I

alfabeto V

insieme finito non vuoto di simboli terminali {a, b, c}

stringa (frase)

sequenza finita di lunghezza arbitraria di elementi di V aacabc

stringa vuota λ

stringa di lunghezza nulla

universo linguistico V ^∗

l’insieme di tutte le stringhe, compresa la stringa vuota, su V {λ , a, b, c, aa, ab, ac, bb, ba, bc, cc, ca, cb, aaa, ...}

Concetti - II

linguaggio L sottoinsieme di V ^∗

{x ∈ V ^∗ : x termina con c } = {c, ac, bc, cc, aac, ...}

grammatica

descrizione finita di un linguaggio L

Grammatica di tipo 0

G = (V, N, P, S) V un alfabeto

N un insieme finito non vuoto di simboli ^a non

terminali(categorie sintattiche) tali per cui N ∩V = /0 P un insieme finito non vuoto di regole sintattiche

(produzioni) del tipo α → β ^b ^con α ∈ (V ∪ N) ^+c e β ∈ (N ∪V ) ^∗

S simbolo iniziale (assioma) con S ∈ N

a

a volte espressi nella forma <nome>

b

il simbolo → pu`o essere sostituito da ::=

c

(V ∪ N)

⁺

= (V ∪ N)

^∗

− {λ}

Esempio grammatica

G = (N,V, S, P) dove V = {a, b, c} , N = {A, B} , S = A P = {

A → aAb,

aA → Bc,

B → bc

}

(3)

Derivazione

una frase w ∈ V ^∗ è generata da G se esiste una sequenza finita di frasi w _k ∈ (V ∪ N) ^∗ con 0 ≤ k ≤ n

w ₀ ⇒ w ₁ ⇒ w ₁ ⇒ ... ⇒ w _n

tale che w ₀ sia S , w _n = w e w _i+1 sia ottenuta da w _i (0 ≤ i < n) , sostituendo una qualunque occorrenza della sottostringa α ⁱⁿ w _i con la stringa β se esiste la produzione α → β ^a

A ⇒ aAb ⇒ aaAbb ⇒ aBcbb ⇒ abccbb

linguaggio generato L _G

insieme delle frasi di V ^∗ derivabili a partire dall’assioma S

a

α `e una sottostringa in w

_i

se e solo se esistono due stringhe u e v (even- tualmente vuote) tali che uαv = w

i

, allora w

i+1

= uβv

Albero sintattico

rappresentazione grafica del processo di derivazione

A A

a b

aA b B c b c

Grammatica ambigua

esistono due o più derivazioni per generare una frase

G = (N,V, S, P) con

V = {a, b} , N = {A, B,C} , S = A P = {A → ABA, A → C, B → b,C → a}

ababa

A B A

b A B A A

C b C

C a

A B A b A B A

A

C b C

C a

Extended BNF (EBNF)

γ → α 1 | α 2 | α 3

scelta multipla, equivale a γ → α 1

γ → α 2

γ → α ₃

γ → [α]β

elemento opzionale, equivale a γ → αβ | β

γ → {α}β

numero arbitrario ≥ 0 di occorrenze della stringa α ^, equivale a γ → β | αγ

γ → {α} ⁿ β

numero arbitrario ≥ 0 e ≤ n di occorrenze della stringa α

(4)

Costanti numeriche

sequenza di cifre che può essere preceduta o meno dal segno + o dal segno -

grammatica G :

V = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, −},

N = {< digit >, < sign >, < number >}, P = {

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

< sign > ::= + | −

< number > ::= [< sign >] < digit > {< digit >}

},

S =< number >

Diagrammi sintattici

rappresentazione grafica delle regole di generazione

Esercizio 1

Quali dei seguenti insiemi sono alfabeti:

A = {a, b, c, d}

B = {n ∈ N : n ≤ 100 ed è primo } C = /0

D = { /0}

E = {0}

F = {x ∈ R : −1 ≤ x ≤ 1}

Esercizio 2

Sia data la grammatica G = ({x, y}, {S, A}, P, S) le cui produzioni sono:

S ::= xAy A ::= xAy A ::= λ

Si dica quale è il linguaggio L _G generato da questa grammatica.

(5)

Esercizio 3

Sia data la seguente grammatica G = (N,V, S, P) dove

N = {A, B,C} , V = {a, b, c, [, ], (, ), +} , S = A e le produzioni P sono:

A ::= [B + A] | B B ::= C | (A) C ::= a | b |c

Si dica quali delle seguenti stringhe appartengono o meno al linguaggio generato da tale grammatica e se ne disegni l’albero sintattico:

1. ([a+b]) 2. [a+b]+(c)

3. [(c)+a] 4. [[a+b]*(c-b)+[b+a+c]]

Esercizio 4

Si definisca una grammatica G = (V, N, P, S) per generare numeri complessi nella forma a +i b oppure a -i b ,dove a e b sono sequenze di cifre.

Backus Naur Form

Backus Naur Form

Paolo Bison

Fondamenti di Informatica Ingegneria Meccanica

Università di Padova A.A. 2008/09

Linguaggio di programmazione

strumento linguistico per scrivere una sequenza di istruzioni (programma) che definiscono una computazione

descritto da

 sintassi

 semantica

Linguaggio formale

sintassi

- Backus Naur Form (BNF)

semantica

- operazionale - denotazionale

Backus Naur Form (BNF)

formalismo per descrivere la sintassi

metalinguaggio

Concetti - I

alfabeto V

insieme finito non vuoto di simboli terminali {a, b, c}

stringa (frase)

sequenza finita di lunghezza arbitraria di elementi di V aacabc

stringa vuota λ

stringa di lunghezza nulla

universo linguistico V ∗

l’insieme di tutte le stringhe, compresa la stringa vuota, su V {λ , a, b, c, aa, ab, ac, bb, ba, bc, cc, ca, cb, aaa, ...}

Concetti - II

linguaggio L sottoinsieme di V ∗

{x ∈ V ∗ : x termina con c } = {c, ac, bc, cc, aac, ...}

grammatica

descrizione finita di un linguaggio L

Grammatica di tipo 0

G = (V, N, P, S) V un alfabeto

N un insieme finito non vuoto di simboli a non

terminali(categorie sintattiche) tali per cui N ∩V = /0 P un insieme finito non vuoto di regole sintattiche

(produzioni) del tipo α → β b con α ∈ (V ∪ N) +c e β ∈ (N ∪V ) ∗

S simbolo iniziale (assioma) con S ∈ N

a volte espressi nella forma <nome>

il simbolo → pu`o essere sostituito da ::=

(V ∪ N)

= (V ∪ N)

− {λ}

Esempio grammatica

G = (N,V, S, P) dove V = {a, b, c} , N = {A, B} , S = A P = {

A → aAb,

aA → Bc,

B → bc

}

Derivazione

una frase w ∈ V ∗ è generata da G se esiste una sequenza finita di frasi w k ∈ (V ∪ N) ∗ con 0 ≤ k ≤ n

w 0 ⇒ w 1 ⇒ w 1 ⇒ ... ⇒ w n

tale che w 0 sia S , w n = w e w i+1 sia ottenuta da w i (0 ≤ i < n) , sostituendo una qualunque occorrenza della sottostringa α in w i con la stringa β se esiste la produzione α → β a

A ⇒ aAb ⇒ aaAbb ⇒ aBcbb ⇒ abccbb

linguaggio generato L G

insieme delle frasi di V ∗ derivabili a partire dall’assioma S

α `e una sottostringa in w

se e solo se esistono due stringhe u e v (even- tualmente vuote) tali che uαv = w

, allora w

= uβv

Albero sintattico

rappresentazione grafica del processo di derivazione

A A

a b

aA b B c b c

Grammatica ambigua

esistono due o più derivazioni per generare una frase

G = (N,V, S, P) con

V = {a, b} , N = {A, B,C} , S = A P = {A → ABA, A → C, B → b,C → a}

ababa

A B A

b A B A A

C b C

C a

A B A b A B A

A

C b C

C a

Extended BNF (EBNF)

γ → α 1 | α 2 | α 3

sintassi

semantica

universo linguistico V ^∗

linguaggio L sottoinsieme di V ^∗

{x ∈ V ^∗ : x termina con c } = {c, ac, bc, cc, aac, ...}

N un insieme finito non vuoto di simboli ^a non

(produzioni) del tipo α → β ^b ^con α ∈ (V ∪ N) ^+c e β ∈ (N ∪V ) ^∗

una frase w ∈ V ^∗ è generata da G se esiste una sequenza finita di frasi w _k ∈ (V ∪ N) ^∗ con 0 ≤ k ≤ n

w ₀ ⇒ w ₁ ⇒ w ₁ ⇒ ... ⇒ w _n

tale che w ₀ sia S , w _n = w e w _i+1 sia ottenuta da w _i (0 ≤ i < n) , sostituendo una qualunque occorrenza della sottostringa α ⁱⁿ w _i con la stringa β se esiste la produzione α → β ^a

linguaggio generato L _G

insieme delle frasi di V ^∗ derivabili a partire dall’assioma S

γ → α ₃

numero arbitrario ≥ 0 di occorrenze della stringa α ^, equivale a γ → β | αγ

γ → {α} ⁿ β

Si dica quale è il linguaggio L _G generato da questa grammatica.