|
Avere una grammatica in sè non è sufficiente per analizzare un linguaggio,
serve solo per riconoscere se un programma è sintatticamente corretto. Sfruttando
però il fatto che l'algoritmo di verifica di fatto ricostruisce i passi effettuati
per generare un programma, ovvero calcola una derivazione, si possono intercettare
alcuni passi effettuati per ottenere una struttura dati utile per operazioni
di tipo "semantico": per esempio il calcolo di una espressione o la generazione
di codice. Facciamo un altro esempio per chiarire meglio il concetto di derivazione.
Nel seguito estendiamo la notazione: il '|' abbrevia in un unica regola una
serie di alternative (ovvero una serie di regole con la stessa testa). Per
CIFRA si intende una cifra da 0 a 9, SUM è il più e MUL è l'asterisco).
Grammatica 2
(c) e : CIFRA | t | f
(d) t : f SUM f
(e) f : e MUL e
Consideriamo la stringa '3+5*7': l'intera derivazione può essere ottenuta
con la sequenza rappresentata dall'albero mostrato in
figura 1
. Per leggere l'albero occorre considerare che le foglie sono i terminali.
Quando un nodo ha dei figli si tratta di un non-terminale: i figli sono le
parti in cui si espande il non-terminale applicando una delle regole:
Albero 1
e
|
t
/ | \
f + f
| /|\
e e * e
| | |
3 5 7
Javacup genera il risultato dell'analisi sintattica in questo formato.
La grammatica 2 è più complicata della grammatica 3, che può sembrare equivalente
ma più semplice:
Grammatica 3
e : CIFRA | e '+' e | e '*' e
ma questa ha dei seri problemi, soffre del peggior difetto che possa avere
una grammatica: è ambigua. Infatti è possibile derivare il nostro programma
in più di un modo :
e e
/ | \ / | \
3 + e e * 7
/|\ /|\
e * e e + e
| | | |
5 7 3 5
quindi non è possibile stabilire univocamente la sequenza di applicazioni
di regole che genera il programma. Di una grammatica come la 3 non è possibile
generare automaticamente il parser: JavaCup riporta vari errori. Una delle
conseguenze di questo problema è che la grammatica non riflette la maggiore
associatività della moltiplicazione rispetto all'addizione. La grammatica
2 infatti è scritta in modo tale che tenga conto del fatto che il prodotto
ha priorità sulla somma. Infatti ogni algoritmo di ricostruzione della grammatica
a partire dalla stringa in presenza di moltiplicazione applicherà la regola
(e) prima delle altre, risolvendo così implicitamente il problema di stabilire
la priorità.
Ritorniamo all'albero 1, che è il risultato dell'analisi sintattica, ed
è detto albero di sintassi concreta. Non è particolarmente comodo da utilizzare,
perché mantiene traccia di una serie di dettagli sintattici, utili per risolvere
problemi come la priorità della moltiplicazione sull'addizione, ma inutili
per il resto del lavoro. Quello che realmente è utile è una forma semplificata
di questo albero, il cosiddetto albero di sintassi astratta, per esempio:
Albero 2
+
/ \
3 *
/ \
5 7
Questo albero viene costruito dall'albero di sintassi concreta, semplificando
tutti i dettagli sintattici non necessari ed è ciò che realmente si cerca
di ricavare dall'analisi sintattica. In un certo senso è il “succo semantico”,
sul quale si può comodamente operare per le fasi successive della compilazione.
|