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
sintassi
- Backus Naur Form (BNF)
semantica
- operazionale - denotazionale
BNF , Paolo Bison, FI08, 2008-09-29 – p.3
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, FI08, 2008-09-29 – p.5
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
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)
∗− {λ}
BNF , Paolo Bison, FI08, 2008-09-29 – p.7
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
a
α `e una sottostringa in w
ise e solo se esistono due stringhe u e v (even- tualmente vuote) tali che uαv = w
i, allora w
i+1= uβv
BNF , Paolo Bison, FI08, 2008-09-29 – p.9
Albero sintattico
rappresentazione grafica del processo di derivazione
A A
a b
aA b
B c
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
BNF , Paolo Bison, FI08, 2008-09-29 – p.11
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 γ → β | αγ
γ → {α} n β
numero arbitrario ≥ 0 e ≤ n di occorrenze della stringa α
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, FI08, 2008-09-29 – p.13
Diagrammi sintattici
rappresentazione grafica delle regole di generazione
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}
BNF , Paolo Bison, FI08, 2008-09-29 – p.15
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.
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, FI08, 2008-09-29 – p.17
