Traduttore diretto dalla sintassi (prima parte)

Sintassi
(prima parte)
Giuseppe Morelli
Introduzione
• Abbiamo già visto come la fase di analisi di un
compilatore
consente
di
suddividere
un
programma sorgente in “pezzi” e produce una
rappresentazione interna (codice intermedio)
• L’analisi è organizzata attorno alla sintassi del
linguaggio in cui il programma sorgente è
scritto.
– Sintassi: descrive la forma di un programma
– Semantica: descrive cosa il programma fa quando è in esecuzione
• La specifica della sintassi viene fatta secondo la
notazione delle Grammatiche Context Free
Grammatiche [Context Free] - definizioni
• Una grammatica descrive naturalmente la
struttura gerarchica della maggior parte
costrutti
dei
diversi
linguaggi
di
programmazione; es:
– If (expression) statement else statement
• Si tratta della concatenzione di più elementi
• Utilizzando un’altra
espressa come
notazione
può
essere
stmt -> if (expr) stmt else stmt
• Una regola così fatta è chiamata produzione
stmt -> if (expr) stmt else stmt
• If , (, ), else sono detti simboli Terminali
• stmt, expr sono sequenze di simboli terminali e
sono detti simboli non terminali
• La -> si legge “può avere la forma”
• I simboli non terminali in corsivo
• Lettere in Neretto, non corsivo, digits ed
operatori, aritmetici e ralazionali sono terminali
Definizione di grammatica
1. Un insieme di simboli terminali (token)
2. Un insieme di non terminali (variabili sintattiche)
3. Un insieme di produzioni,dove ognuna consiste
di:
1. Un simbolo non terminale (head or left side)
2. Una freccia
3. Una sequenza di simboli terminali e/o non
terminali (body or right side); permette di
specificare un costrutto
4. Un simbolo non terminale è designato quale
Iniziale (Start symbol)
.. continua
• Una grammatica è specificata attraverso la lista
delle sue produzioni.
• La produzione per il simbolo iniziale è
posizionata in testa alla lista
• Le produzioni con lo stesso simbolo non
terminale come Head (left side) hanno il corpo
(body) accorpato ovvero i diversi bodies sono
separati dal simbolo | (or)
• NOTA: equivalenza tra token e simboli terminali
Esempio (ricorrente)
• Costruiamo una grammatica in grado di
rappresentare l’espressione 9 -5 +2, e simili
list -> list + digit
list -> list – digit
list -> digit
digit -> 0|1|2|3|4|5|6|7|8|9
• In pratica stiamo affermando che chiamiamo list
due o più digit separati da + o –
• In sintesi
list -> list + digit | list – digit | digit
digit -> 0|1|2|3|4|5|6|7|8|9
Derivazione
• Una grammatica deriva una stringa, iniziando
con il simbolo iniziale e rimpiazzando
ripetutamente un simbolo non terminale con la
produzione per lo stesso simbolo.
• L’insieme delle stringhe derivabili a partire del
simbolo iniziale si dice il linguaggio definito dalla
grammatica.
Esempio
• Si consideri la grammatica:
1. list -> list + digit
2. list -> list – digit
3. list -> digit
4. digit -> 0|1|2|3|4|5|6|7|8|9
• La stringa 9-5+2 può essere derivata(dedotta):
1. Il 9 è una list (3) poichè 9 è un digit (4)
2. 9-5 è una list poiché 9 è list e 5 è digit (2)
3. 9-5+2 è una list poiché 9-5 è list e 2 è digit
(1)
Esempio
• Supponiamo di voler scrivere la grammatica e
voler riconoscere una chiamata a funzione con
relativa lista parametri ( nomefunz(x,y) ).
1.
2.
3.
4.
Call -> id ( optparams )
Optparams -> params | E
Params -> params, params | param
Param ????? (dipende dal linguaggio …..)
• Note:
– Lista dei parametri può essere vuota
– Params coincide con la definizione di list esempio
precedente (, al posto di + e – e param per digit)
Parsing
• È il nome del problema di prendere una stringa
di simboli terminali e mostrare come è possibile
derivarla a partire dal simbolo iniziale della
grammatica.
• Nel caso la derivazione non possa avvenire
permette di segnalare errori di sintassi nella
stringa
• Il parsing è propedeutico alla esecuzione del
lexer (lessemi --- Token)
• Negli esempi successivi si partirà sempre da
stringhe di terminali
Alberi di parsing
• Un albero sintattico permette di illustrare il
procedimento di parsing ovvero come si può
derivare una stringa del linguaggio a partire dal
simbolo iniziale della grammatica
• Sia A un generico simbolo non terminale che ha
a produzione A->XYZ, il suo “parse tree” avrà
un nodo interno etichettato con A con tre figli
etichettati da sinistra a destra con X,Y, e Z
ovvero:
A
X
Y
Z
..continua
• Data una grammatica context free, il suo
albero sintattico è un albero con le seguenti
caratteristiche:
1. La root è etichettata con il simbolo iniziale
2. Ogni foglia è etichettata con un simbolo terminale
3. Ogni nodo interno è etichettato con un simbolo nonterminale
4. Se A è un non terminale che etichetta un nodo
interno e X1, X2, …. , Xn sono etichette per i figli di
detto nodo allora la grammatica deve possedere la
produzione A -> X1 X2…. Xn
Esempio
Start symbol (1)
• Esperssione 9-5+2
list
1.
2.
3.
4.
list -> list + digit
list -> list – digit
list -> digit
digit -> 0|1|2|3|4|5|6|7|8|9
9-5 (2)
2 (4)
list
digit
9 (3)
5 (4)
list
9 (4)
digit
Yield ()
9
digit
-
5
+
Stringa derivata o generata
2
Ambiguità
• Una grammatica si dice ambigua quando un
stringa di terminali può essere generata da due
o più parse tree.
• Ciò dipende da come vengono scritte le
produzioni
• Per la realizzazione dei applicazioni di
compilazione è necessario scrivere grammatiche
non ambigue, o utilizzare grammatiche ambigue
ma con regole addizionali che permetto di
risolvere tali ambiguità.
Esempio
1. list -> list + list
2. list -> list – list
3. list -> 0|1|2|3|4|5|6|7|8|9
9-5+2
list
list
list
9
-
+
list
list
list
2
9
list
-
list
list
5
5
list
+
2
Associatività degli operatori
• La proprietà associativa, in presenza di una
espressione in cui un operando compare fra due
operatori, ci permette di scegliere quale
operatore applicare all’operando.
• Quando si dice che l’operatore + è associativo a
sinistra significa che in presenza di un
operando con due segni + (dx e sx) appartiene
all’operatore di sinistra ( 9+5+2 - (9+5)+2 )
• Gli operatori + - * / sono associativi a sinistra
• ^p è associativo a destra
• Operatore di assegnazione = è associativo a
destra
Esempio
right -> letter = right
right -> letter
letter -> a | b | …. |z
• Permette di riconoscere stringe del tipo a=b=c e
generarle attraverso l’albero:
right
• Nota sbilanciamento
letter
a
right
=
letter
b
right
= letter
c
Precedenza degli operatori
•
•
•
•
Si consideri 9+5*2
2 interpretazioni possibili (9+5)*2 o 9+(5*2)
L’associatività a sinistra di entrambi non aiuta
Quando sono presenti differenti tipi di operatore
è necessario definire delle regole di precedenza
• Un operatore ha precedenza maggio re rispetto
ad un altro quando prende l’operando prima
dell’altro
• * ha precedenza maggiore rispetto a + così
l’espressione precedente è valutata come
9+(5*2)
Esempio: espressioni aritmetiche
• l’associatività è evidenziata esplicitamente
left-associative +,- ……(expr)
left-associative *,/ ……(term)
expr -> expr + term | expr – term | term
term -> term * factor | term / factor | factor
factor –> digit | (expr)
• Attraverso i due non terminali vengono
evidenziati i livelli di precedenza (+,- e *,/)
Parse tree di espressioni aritmetiche
expr -> expr + term | expr – term | term
term -> term * factor | term / factor | factor
factor –> digit | (expr)
expr
Deriviamo: 9+5*2
term
expr
term
term
factor
factor
factor
9
+
5
*
2
Esercizio
• Consideriamo la grammatica
S -> S S + | S S * | a
- Mostrare che aa+a* può essere generata dalla
grammatica
- Costruire l’albero di parsing
Esercizi
• Quali linguaggi sono generati dalle
grammatiche:
A.
B.
C.
D.
E.
S
S
S
S
S
->
->
->
->
->
0 S 1 | 01
+SS|-SS|a
S(S)S|ε
aSbS|bSaS|ε
a | S + S | S S | S* | ( S )