Post on 01-May-2015
transcript
1
Linguaggi di Programmazione - elementiLinguaggi di Programmazione - elementi
Corso di Laurea in InformaticaCorso di Laurea in Informatica(AA 2005/2006)(AA 2005/2006)
Gabriella Pasi e Carla SimoneGabriella Pasi e Carla Simone
gabriella.pasi@itc.cnr.itgabriella.pasi@itc.cnr.itsimone@disco.unimib.itsimone@disco.unimib.it
2
Linguaggi e programmiLinguaggi e programmi
Dato un algoritmo, un programma è la sua descrizione in un particolare linguaggio di programmazione.
Un linguaggio di programmazione è caratterizzato da due aspetti:
– SINTASSI
– SEMANTICA
N.B.: una frase può essere sintatticamente corretta ma priva di significato.
Insieme di regole formali che definiscono le modalità per costruire espressioni corrette (valide) del linguaggio
Il significato da attribuire alle frasi (sintatticamente corrette) del linguaggio mediante un’interpretazione.
3
Una grammatica è uno strumento formale per definire un linguaggio attraverso la descrizione delle proprietà strutturali delle sue frasi.
GRAMMATICHEGRAMMATICHE
Tale costruzione si effettua partendo da una frase particolare e riscrivendo via via parti di essa applicando una delle regole specificate nella grammatica stessa.
4
Le grammatiche formali generalmente studiate nel contesto informatico sono denominate Grammatiche di Chomsky perché furono introdotte dal linguista Noam Chomsky.
GRAMMATICHEGRAMMATICHE
Le grammatiche formali hanno un ruolo fondamentale nello studio delle proprietà sintattiche dei programmi e dei linguaggi di programmazione.
5
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*.
ELEMENTI BASE DELLA SINTASSI DI UN LINGUAGGIOELEMENTI BASE DELLA SINTASSI DI UN LINGUAGGIO
GRAMMATICHEGRAMMATICHE
V* : universo linguistico su V. Il simbolo 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 grammaticagrammatica.
6
Una grammatica G = (V,N,P,S) per la generazione di un linguaggio L è definita da:
V: insieme di insieme di simboli terminalisimboli terminali, alfabeto di L
GRAMMATICHEGRAMMATICHE
N: insieme di simboli non terminalisimboli non terminali o metasimbolimetasimboli (categorie sintattichecategorie sintattiche come per esempio: <frase>, <soggetto>, <verbo>, <complemento>, <articolo>, <nome>, ...)P: insieme finito di regole sintatticheregole sintattiche (o produzioniproduzioni) del tipo X Y
S : elemento di N (assiomaassioma o simbolo inizialesimbolo iniziale)
7
Si dice forma di frase (sentential form) forma di frase (sentential form) una qualsiasi stringa comprendente sia simboli terminali sia simboli non terminali derivabile dall’assioma S.
Si dice frasefrase una forma di frase comprendente solo simboli terminali.
GRAMMATICHEGRAMMATICHE
L’insieme delle forme di frase di G è l’insieme delle parole su V N derivabiliderivabili a partire da S, cioè le parole su V N tali che S * v.
Il linguaggio generato dalla grammatica linguaggio generato dalla grammatica GG è l’insieme di frasi applicando in sequenza le possibili regole in P, iniziando da S.
8
Esempio di grammaticaEsempio di grammatica: V = {a,b} N = {A,S}
start symbol S P = {S A;
A bAb;
A a }
Linguaggio generato da G: L(G) = {bnabn |n0}
GRAMMATICHEGRAMMATICHENotazioneNotazione:
• 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.
9
GRAMMATICHEGRAMMATICHE
Data una grammatica G = (V,N,P,S), diciamo che da una stringa u = u1Au2 (V N)* possiamo derivarederivare in un passo una stringa v = u1wu2 (V N)* se esiste una produzione A w e scriviamo u u vv
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 =
vper mezzo di applicazione delle regole in P.
S A bAb bbAbb bbabb
Esempio di derivazione della grammatica precedente:Esempio di derivazione della grammatica precedente:
10
CLASSIFICAZIONE CLASSIFICAZIONE DELLE GRAMMATICHEDELLE GRAMMATICHE
– TIPO 0: TIPO 0: ricorsivamente enumerabilericorsivamente enumerabilequando le stringhe che appaiono nelle produzioni a a bb non sono soggette ad alcuna limitazione (a e b non vuote) – TIPO 1: TIPO 1: dipendente dal contesto (context dependent)dipendente dal contesto (context dependent)quando le produzioni sono del tipo aAb aAb axb axb dove A è un non terminale e x è non vuota
– – TIPO 2: TIPO 2: libera dal contesto (context free)libera dal contesto (context free)quando le produzioni sono limitate ad A A x x dove A è un non terminale e x è non vuota
– – TIPO 3: TIPO 3: regolare (a stati finiti)regolare (a stati finiti) quando le produzioni sono limitate ad A A a a e A A aBaB più eventualmente S S , oppure a A A a a e A A BaBa più eventualmente S S , dove A e B sono non terminali e a è un terminale
11
GERARCHIA DI CHOMSKYGERARCHIA DI CHOMSKY
12
GRAMMATICHE INDIPENDENTI GRAMMATICHE INDIPENDENTI DAL CONTESTO (context free)DAL CONTESTO (context free)
Le produzioni sono della forma A w, dove A N e w (V N)*. EsempioEsempio: V = {a,b,c,d} N = {A,S} start symbol S
P = {S cAd,
A bAb,
A a}
Linguaggio generato da G: L(G) = {cbnabnd |n0}
Regola di tipoRegola di tipo““self-embedding”self-embedding”
Derivazione per cbbbabbbd?Derivazione per cbbbabbbd?
S cAd cbAbd cbbAbbd cbbbAbbbd cbbbabbbd
13
GRAMMATICHE INDIPENDENTI GRAMMATICHE INDIPENDENTI DAL CONTESTO (context free)DAL CONTESTO (context free)
EsempioEsempio: V = {a} N = {A,S} start symbol S
P = {S Aa,
A Aa,
A }Linguaggio generato da GLinguaggio generato da G: L(G) = {a, aa, aaa, ...}
S Aa aS Aa Aaa aa
14
V = {a,b,c} N = {S,X} S assioma
P = {S X, S
X aXa, X bXb, X c}
Linguaggio generato da GLinguaggio 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 abcbaDerivazione per abcba
S X aXa abXba abcba
GRAMMATICHE INDIPENDENTI GRAMMATICHE INDIPENDENTI DAL CONTESTO (context free)DAL CONTESTO (context free)
NOTA BENENOTA BENE: notazione che sintetizza le produzioni che hanno lo stesso simbolo non terminale nella parte sinistra: X aXa | bXb | c
15
EsempioEsempio: V = {a, b} N = {A,B,S} start symbol S
P = {S A,
A Ba |
B Ab | }
Linguaggio generato da GLinguaggio generato da G: L(G) = {a,ba, aba, baba ...}
S A S A Ba Aba baS A Ba Aba Baba Ababa baba
GRAMMATICHE INDIPENDENTI GRAMMATICHE INDIPENDENTI DAL CONTESTODAL CONTESTO(context free)(context free)
NOTA BENENOTA BENE: le frasi generate,alternando b ed a, che terminano sempre con il simbolo terminale a (tranne
16
EsempioEsempio: 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 GLinguaggio generato da G: notazione decimale dei numeri pari
S A 2A 23A 230S 1A 10S 1A 11A 113A 1132
GRAMMATICHE INDIPENDENTI GRAMMATICHE INDIPENDENTI DAL CONTESTO (context free)DAL CONTESTO (context free)
17
EsempioEsempio: V = {_,a, … z, A, … Z, 0, …, 9}
N = {A, B} start symbol A
P = {A aB, A bB, …, A AB, …, A ZB
B _BB aB, B bB, …, B AB, …, B ZB
B 0B, B 1B, …, B 9B, B }
Linguaggio generato da GLinguaggio 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 sequenza di caratteri.
GRAMMATICHE INDIPENDENTI GRAMMATICHE INDIPENDENTI DAL CONTESTO (context free)DAL CONTESTO (context free)
18
GRAMMATICHE REGOLARI (a stati GRAMMATICHE REGOLARI (a stati finiti)finiti)
TIPO 3TIPO 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 con SOLE regole del tipo A a e A aB si dicono lineari a destralineari a destra.
Le grammatiche con SOLE regole del tipo A a e A Ba si dicono lineari a sinistralineari a sinistra.
(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.
19
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 Esempio di regole di grammatica lineare ma NON regolarelineare ma NON regolare
GRAMMATICHE LINEARIGRAMMATICHE LINEARI
20
EsempioEsempio: V = {0, 1} N = {U,V,S} start symbol S
P = {S U0 | V1,
U S1 | 1
V S0 |}
Linguaggio generato da GLinguaggio generato da G: L(G) = {01, 0101, 0110, 1010, 10 ...}
Grammatica regolareGrammatica regolarelineare a sinistralineare a sinistra
GRAMMATICHE REGOLARIGRAMMATICHE REGOLARI
21
Per ogni grammatica lineare destra ne esiste una Per ogni grammatica lineare destra ne esiste una lineare sinistra equivalente e viceversa.lineare sinistra equivalente e viceversa.
EsempioEsempio:
P = {S aS,
S b}
Grammatica regolareGrammatica regolarelineare a sinistralineare a sinistra
A)
P = {S Ab | b,
A Aa | a}
V = {a, b} N = {S}
B) V = {a, b} N = {S, A}
Grammatica regolareGrammatica regolarelineare a destralineare a destra
L = {anb | n 0}
GRAMMATICHE REGOLARIGRAMMATICHE REGOLARI
22
Le regole sintattiche sono espresse per mezzo di notazioni formali, come ad esempio:
• BNFBNF (Backus-Naur Form) notazione algebrica
• EBNFEBNF (Extended BNF) notazione algebrica
• diagrammi sintattici diagrammi sintattici notazione grafica
Sintassi: notazioniSintassi: notazioni
23
BACKUS NAUR FORMBACKUS NAUR FORM
Per descrivere le grammatiche con notazione più compatta di quella vista precedentemente si usa la BNFBNF (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 ::=
La notazione A ::= a | b | c | d significa che la grammatica contiene le produzioni A ::= a, A ::= b, A ::= c, A ::= d.
Il simbolo Il simbolo || rappresenta la disgiunzione. rappresenta la disgiunzione.
24
BACKUS NAUR FORMBACKUS NAUR FORMesempioesempio
EsempioEsempio: V = {0, 1} N = {U,V,S} Start Symbol S
P = {S ::= U0 | V1,
U ::= S1 | 1
V ::= S0 |0}
Linguaggio generato da GLinguaggio generato da G:
L(G) = {01, 0101, 0110, 1010, 10 ...}
25
EXTENDED BACKUS NAUR FORMEXTENDED 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].
26
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)
EXTENDED BACKUS NAUR FORMEXTENDED BACKUS NAUR FORM
27
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
EXTENDED BACKUS NAUR FORMEXTENDED BACKUS NAUR FORM
28
<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>
EXTENDED BACKUS NAUR FORMEXTENDED BACKUS NAUR FORMAttenzione: nel linguaggio generato da questa Attenzione: nel linguaggio generato da questa grammatica i simboli grammatica i simboli { { e e }} sono simboli sono simboli terminali ! Per denotare ripetizione si usa il terminali ! Per denotare ripetizione si usa il simbolo *simbolo *
29
<operator>::= + | - | * | / | = | /= | < | > | <= | >=<identifier> ::= <letter> <ld>*<ld> ::= <letter> | <digit><number> ::= <digit>+<letter> ::= a | b | c | . . . | z<digit> ::= 0 | 1 | . . . | 9
Nota bene: * è sia un simbolo sia un metasimbolo
EXTENDED BACKUS NAUR FORMEXTENDED BACKUS NAUR FORM
30
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
DIAGRAMMI SINTATTICIDIAGRAMMI SINTATTICI
31
statementassignment
conditional
loop
program
statement
{ }
if eexpression statement{ }
else { statement }
conditional
assignmentidentifier = expression ;
DIAGRAMMI SINTATTICIDIAGRAMMI SINTATTICI
32
expression expressionoperatorexpression
identifier
number
expression( )
DIAGRAMMI SINTATTICIDIAGRAMMI SINTATTICI
while expression statement{ }loop
33
Identificatore in JavaIdentificatore in Java
letterale
letterale
cifra
cifra
Unicodeescape
cifra
0 - 9
DIAGRAMMI SINTATTICIDIAGRAMMI SINTATTICI
34
Il linguaggio L= {anbn cn , con n≥ 1} e’ generato dalla seguente regole, appartenenti a una grammatica dipendente dal contesto:
1) S aSBC 2) S aBC 3) CB BC4) aB ab 5) bB bb 6) bC bc7) cC cc
ESEMPIO DI GRAMMATICA ESEMPIO DI GRAMMATICA DIPENDENTE DAL CONTESTODIPENDENTE DAL CONTESTO
35
infatti ….infatti ….
E’ possibile usare la produzione 1) per n-1 volte ed ottenerean-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 Cin modo da avere tutte le B prima delle C, ed ottenere quindi an Bn Cn. Usando la produzione 4) una volta si ottienean 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