Backus Naur Form

Backus Naur Form

Paolo Bison

Fondamenti di Informatica 1 A.A. 2004/05 Universit`a di Padova

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.1/19

Linguaggio di programmazione

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

computazione

 descritto da

 sintassi

 semantica

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.2/19

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, ...}

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.5/19

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

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.6/19

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 = ∅

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

aa volte espressi nella forma

<

nome

>

bil simbolo

→

pu`o essere sostituito da ::=

c

(V ∪ N )

⁺

= (V ∪ N )

^∗

− {λ}

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.7/19

Esempio grammatica

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

P = {

A → aAb, aA → Bc, B → bc }

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.8/19

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

a

α

`e una sottostringa in

w

ise e solo se esistono due stringhe

u

e

v

(eventualmente vuote) tali che

uαv = w

i, allora

w

i+1

= uβv

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.9/19

Albero sintattico

 rappresentazione grafica del processo di derivazione

A A

a b

aA b

B c b c

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.10/19

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

a C

a

a

A B A b A B A

A

C b C a

C a a

Tipi di grammatica

 Tipo 0

 Tipo 1 - sensibile al contesto per ogni produzione α → β in P

|α| ≤ |β|

^d

 Tipo 2 - libera dal contesto per ogni produzione α → β in P α ∈ N

 Tipo 3 - regolare

ogni produzione in P ha la forma A → σB o A → σ

con A, B ∈ N e σ ∈ V ^∗

d

|x|

`e la lunghezza della stringa

x

, ovvero il numero di simboli di

x

Extended BNF (EBNF)

 γ → α 1 | α 2 | α 3

scelta multipla, equivale a γ → α 1

γ → α 2

γ → α 3

 γ → [α]β

elemento opzionale, equivale a γ → αβ | β

 γ → {α}β

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

 γ → {α} ⁿ β

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

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.13/19

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 >

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.14/19

Diagrammi sintattici

 rappresentazione grafica delle regole di generazione

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.15/19

Esercizio 1

Quali dei seguenti insiemi sono alfabeti:

A = {a, b, c, d}

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

C = ∅ D = {∅}

E = {0}

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

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.16/19

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.

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.17/19

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]]

BNF , Paolo Bison, A.A. 2004-05, 2004-10-28 – p.18/19

Esercizio 4

Si definisca una grammatica G = (V, N, P, S) per

generare numeri complessi nella forma a+ib oppure

a-ib,dove a e b sono sequenze di cifre.