Corso di Laurea in Informatica
(AA 2005/2006)
Linguaggi di Programmazione - elementi
Gabriella Pasi e Carla Simone
[email protected]
[email protected]
1
Linguaggi e programmi
Dato un algoritmo, un programma è la sua descrizione in
un particolare linguaggio di programmazione.
Un linguaggio di programmazione è caratterizzato da
due aspetti:
Insieme di regole formali che
definiscono le modalità per costruire
– SINTASSI
espressioni corrette (valide) del
linguaggio
– SEMANTICA
Il significato da attribuire alle frasi
(sintatticamente
corrette)
del
linguaggio mediante un’interpretazione.
N.B.: una frase può essere sintatticamente corretta ma
2
priva di significato.
GRAMMATICHE
Una grammatica è uno strumento formale per
definire un linguaggio attraverso la descrizione
delle proprietà strutturali delle sue frasi.
Tale costruzione si effettua partendo da una
frase particolare e riscrivendo via via parti di essa
applicando una delle regole specificate nella
grammatica stessa.
3
GRAMMATICHE
Le grammatiche formali generalmente studiate
nel contesto informatico sono denominate
Grammatiche di Chomsky perché furono
introdotte dal linguista Noam Chomsky.
Le grammatiche formali hanno un ruolo
fondamentale nello studio delle proprietà
sintattiche dei programmi e dei linguaggi di
programmazione.
4
GRAMMATICHE
ELEMENTI BASE DELLA SINTASSI DI UN LINGUAGGIO
V : alfabeto Un alfabeto è un insieme finito e non vuoto di
simboli. L’insieme di tutte le sequenze finite di simboli in V,
dette stringhe o frasi su V, è denotato da V*.
V* : universo linguistico su V. Il simbolo e denota la
stringa vuota ed appartiene a V*.
L : un linguaggio su V è un insieme di stringhe su V, cioè
un sottoinsieme di frasi in V* generato da una
grammatica.
5
GRAMMATICHE
Una grammatica G = (V,N,P,S) per la generazione di un
linguaggio L è definita da:
V: insieme di simboli terminali, alfabeto di L
N: insieme di simboli non terminali o metasimboli
(categorie sintattiche come per esempio: <frase>, <soggetto>,
<verbo>, <complemento>, <articolo>, <nome>, ...)
P: insieme finito di regole sintattiche (o produzioni) del
tipo X  Y
S : elemento di N (assioma o simbolo iniziale)
6
GRAMMATICHE
Si dice forma di frase (sentential form) una qualsiasi stringa
comprendente sia simboli terminali sia simboli non terminali
derivabile dall’assioma S.
L’insieme delle forme di frase di G è l’insieme delle parole su
V  N derivabili a partire da S, cioè le parole su V  N tali
che S * v.
Si dice frase una forma di frase comprendente solo simboli
terminali.
Il linguaggio generato dalla grammatica G è l’insieme di frasi
applicando in sequenza le possibili regole in P, iniziando da S.
7
GRAMMATICHE
Notazione:
• simboli terminali in minuscolo
• simboli non terminali in maiuscolo
• regole di produzione X  Y: dalla parte a sinistra per
sostituzione si deriva la parte a destra. Il simbolo/stringa
X viene cioè sostituito dal simbolo/stringa Y in un passo di
derivazione.
Esempio di grammatica: V = {a,b} N = {A,S}
P = {S  A;
start symbol S
A  bAb;
A  a }
Linguaggio generato da G: L(G) = {bnabn |n0}
8
GRAMMATICHE
Data una grammatica G = (V,N,P,S), diciamo che da una
stringa u = u1Au2  (V  N)* possiamo derivare in un passo
una stringa v = u1wu2  (V  N)* se esiste una produzione
A  w e scriviamo u  v
Diciamo che v è derivabile da u, e scriviamo u * v , se esiste
una catena finita di stringhe u1, u2 ….. un  (V  N)* tale
u = u1  u2  …..  un = v
per mezzo di applicazione delle regole in P.
Esempio di derivazione della grammatica precedente:
S  A  bAb  bbAbb  bbabb
9
CLASSIFICAZIONE
DELLE GRAMMATICHE
– TIPO 0: ricorsivamente enumerabile
quando le stringhe che appaiono nelle produzioni a  b non
sono soggette ad alcuna limitazione (a e b non vuote)
– TIPO 1: dipendente dal contesto (context dependent)
quando le produzioni sono del tipo aAb  axb dove A è un
non terminale e x è non vuota
– TIPO 2: libera dal contesto (context free)
quando le produzioni sono limitate ad A  x dove A è un
non terminale e x è non vuota
– TIPO 3: regolare (a stati finiti)
quando le produzioni sono limitate ad A  a e A  aB
più eventualmente S  e, oppure a A  a e A  Ba più
eventualmente S  e, dove A e B sono non terminali e a è
10
un terminale
GERARCHIA DI CHOMSKY
11
GRAMMATICHE INDIPENDENTI DAL
CONTESTO (context free)
Le produzioni sono della forma A  w, dove A  N e
w  (V  N)*.
Esempio: V = {a,b,c,d}
start symbol S
P =
N = {A,S}
{S cAd,
Regola di tipo
“self-embedding”
A  bAb,
A  a}
Linguaggio generato da G:
L(G) = {cbnabnd |n0}
Derivazione per cbbbabbbd?
S  cAd  cbAbd  cbbAbbd  cbbbAbbbd  cbbbabbbd
12
GRAMMATICHE INDIPENDENTI DAL
CONTESTO (context free)
Esempio: V = {a}
P =
N = {A,S}
start symbol S
{S Aa,
A  Aa,
A  e}
Linguaggio generato da G: L(G) = {a, aa, aaa, ...}
S  Aa  a
S  Aa  Aaa  aa
13
GRAMMATICHE INDIPENDENTI DAL
CONTESTO (context free)
V = {a,b,c}
N = {S,X} S assioma
P =
{S  X,
S  e,
X  aXa,
X  bXb,
X  c}
NOTA BENE: notazione che sintetizza le produzioni che
hanno lo stesso simbolo non terminale nella parte
sinistra: X  aXa | bXb | c
Linguaggio generato da G: il linguaggio delle stringhe
palindrome su {a,b,c} con una e una sola c al centro, piu’
la stringa vuota.
Derivazione per abcba
S  X  aXa  abXba  abcba
14
GRAMMATICHE INDIPENDENTI DAL
CONTESTO
(context free)
Esempio: V = {a, b}
N = {A,B,S}
start symbol S
P = {S  A,
A  Ba | e,
B  Ab | e }
Linguaggio generato da G: L(G) = {e, a,ba, aba, baba ...}
NOTA BENE: le frasi generate,alternando b ed a, che
terminano sempre con il simbolo terminale a (tranne e
S Ae
S  A  Ba  Aba  ba
S  A  Ba  Aba  Baba  Ababa  baba
15
GRAMMATICHE INDIPENDENTI DAL
CONTESTO (context free)
Esempio: V = {0, 1, … 9} N = {A, S}
start symbol S
P = {S  A,
A  2, A  4, A  6, A  8, A  0
A  0A, A  1A, … A  9A}
Linguaggio generato da G: notazione decimale dei numeri pari
S  A  2A  23A  230
S  1A  10
S  1A  11A  113A  1132
16
GRAMMATICHE INDIPENDENTI DAL
CONTESTO (context free)
Esempio: V = {_,a, … z, A, … Z, 0, …, 9}
N = {A, B}
start symbol A
P = {A  aB, A  bB, …, A  AB, …, A  ZB
B  _B; B  aB, B  bB, …, B  AB, …, B  ZB
B  0B, B  1B, …, B  9B, B  e }
Linguaggio generato da G: questa grammatica genera gli
identificatori del linguaggio C. Infatti come prima
produzione si deve usare una produzione su A, che
aggiunge un carattere iniziale non numerico. Dopo, le
produzioni su B permettono di proseguire con qualsiasi
17
sequenza di caratteri.
GRAMMATICHE REGOLARI (a stati finiti)
TIPO 3: Le produzioni sono della forma A  w, dove A 
N e w  (V  N)  V oppure w  (N  V)  V.
Quindi le produzioni sono limitate alle seguenti forme:
A  a oppure A  aB oppure A  Ba dove A e B sono non
terminali e a è un terminale .
Le grammatiche regolari possono essere lineari a destra o
lineari a sinistra. Il termine “lineare” deriva dal fatto che al
lato destro di ogni produzione compare al più un simbolo non
terminale.
Le grammatiche con SOLE regole del tipo A  a e A  aB
si dicono lineari a destra.
Le grammatiche con SOLE regole del tipo A  a e A  Ba
si dicono lineari a sinistra.
18
(A e B sono non terminali e a è un terminale)
GRAMMATICHE LINEARI
Si dice lineare una grammatica non contestuale in cui la
parte destra di ogni produzione contenga al più un non
terminale.
Esempio di regole di grammatica
lineare ma NON regolare
19
GRAMMATICHE REGOLARI
Esempio: V = {0, 1}
N = {U,V,S} start symbol S
P = {S  U0 | V1,
U  S1 | 1,
V  S0 | 0 }
Grammatica regolare
lineare a sinistra
Linguaggio generato da G:
L(G) = {01, 0101, 0110, 1010, 10 ...}
20
GRAMMATICHE REGOLARI
Per ogni grammatica lineare destra ne esiste una lineare
sinistra equivalente e viceversa.
Esempio:
A)
L = {anb | n  0}
V = {a, b}
N = {S}
P = {S  aS,
S  b}
B)
V = {a, b}
N = {S, A}
P = {S  Ab | b,
A  Aa | a}
Grammatica regolare
lineare a destra
Grammatica regolare
lineare a sinistra
21
Sintassi: notazioni
Le regole sintattiche sono espresse per mezzo di
notazioni formali, come ad esempio:
• BNF (Backus-Naur Form) notazione algebrica
• EBNF (Extended BNF)
notazione algebrica
• diagrammi sintattici
notazione grafica
22
BACKUS NAUR FORM
Per descrivere le grammatiche con notazione più compatta di
quella vista precedentemente si usa la BNF (Backus-Naur
Form). I simboli non terminali vengono descritti da parole,
mentre i terminali in grassetto.
Nelle regole di produzione, al posto di  si utilizza la
notazione ::=
Il simbolo | rappresenta la disgiunzione.
La notazione A ::= a | b | c | d significa che la grammatica
contiene le produzioni A ::= a, A ::= b, A ::= c, A ::= d.
23
BACKUS NAUR FORM
esempio
Esempio: V = {0, 1}
N = {U,V,S} Start Symbol S
P = {S ::= U0 | V1,
U ::= S1 | 1,
V ::= S0 | 0 }
Linguaggio generato da G:
L(G) = {01, 0101, 0110, 1010, 10 ...}
24
EXTENDED BACKUS NAUR FORM
La notazione [w] nella parte destra di una produzione
significa che la parola w può comparire o meno, è cioè
opzionale.
La notazione w} nella parte destra di una produzione
significa che la parola w può comparire zero o più volte.
Le parentesi tonde possono essere utilizzate per
raggruppare: ad esempio, (a | b) [c] è diverso da a | (b [c]),
che è uguale ad a | b [c].
25
EXTENDED BACKUS NAUR FORM
X ::= [a]b
equivale a X ::= b|ab
X ::= {a}nb equivale a
X ::= b|ab|aab|…
ripetendo a fino a n volte
X ::= {a}b
equivale a
X ::= b|ab|aab|…
ripetendo a un numero di volte indefinito
Equivale ad avere nella grammatica la produzione
X ::= b | aX
(ricorsiva)
26
EXTENDED BACKUS NAUR FORM
V: { 0,1,2,3,4,5,6,7,8,9,+,- }
N: {<intero><int-senza-segno><numero>
<cifra-non-nulla><cifra>}
S: <intero>
P contiene le seguenti produzioni:
<intero> ::= [+ | - ] <int-senza-segno>
<int-senza-segno> ::= <cifra> | <cifra-non-nulla><numero>
<numero> ::= <cifra> | <cifra><numero>
<cifra> ::= <cifra-non-nulla> | 0
<cifra-non-nulla> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
27
EXTENDED BACKUS NAUR FORM
Attenzione: nel linguaggio generato da questa
grammatica i simboli { e } sono simboli terminali ! Per
denotare ripetizione si usa il simbolo *
<program> ::= { <statement>* }
<statement> ::= <assignment> | <conditional> | <loop>
<assignment> ::= <identifier> = <expr> ;
<conditional> ::= if <expr> { <statement> + } |
if <expr> { <statement> + } else { <statement> + }
<loop>
::= while <expr> { <statement> + }
<expr>
::= <identifier> | <number> |
( <expr> ) | <expr> <operator> <expr>
28
EXTENDED BACKUS NAUR FORM
<operator>
<identifier>
<ld>
<number>
<letter>
<digit>
::=
::=
::=
::=
::=
::=
+ | - | * | / | = | /= | < | > | <= | >=
<letter> <ld>*
<letter> | <digit>
<digit>+
a|b|c|...|z
0|1|...|9
Nota bene: * è sia un simbolo sia un metasimbolo
29
DIAGRAMMI SINTATTICI
Sono dei grafi:
– nodi: etichettati con simboli (terminali e non
terminali), collegati da archi orientati
– un arco da i a j significa che il simbolo i è seguito
dal simbolo j
– più archi rappresentano alternative
30
DIAGRAMMI SINTATTICI
program
{
}
statement
assignment
statement
conditional
loop
assignment
conditional
if
identifier
eexpression
else
{
{
;
expression
=
statement
statement
}
}
31
DIAGRAMMI SINTATTICI
loop
while
expression
expression
expression
{
operator
statement
}
expression
identifier
number
(
expression
)
32
DIAGRAMMI SINTATTICI
Identificatore in Java
letterale
letterale
cifra
cifra
0 - 9
cifra
Unicode
escape
33
ESEMPIO DI GRAMMATICA
DIPENDENTE DAL CONTESTO
Il linguaggio L= {anbn cn , con n≥ 1} e’ generato dalla
seguente regole, appartenenti a una grammatica
dipendente dal contesto:
1) S  aSBC
4) aB  ab
7) cC  cc
2) S  aBC
5) bB  bb
3) CB  BC
6) bC  bc
34
infatti ….
E’ possibile usare la produzione 1) per n-1 volte ed ottenere
an-1 S (BC)n-1. Quindi, usare la produzione 2) ed ottenere
an (BC)n. La produzione 3) consente di scambiare le B e le C
in modo da avere tutte le B prima delle C, ed ottenere
quindi an Bn Cn. Usando la produzione 4) una volta si ottiene
an bBn-1 Cn. A questo punto, usando la produzione 5) n-1
volte si ottiene an bn Cn . Infine, usando la produzione 6)
una volta si ottiene an bn c Cn -1 e usando la produzione 7)
n-1 volte si ottiene anbn cn
35