|
Una grammatica è un formalismo che descrive tutti i
programmi esprimibili in un dato linguaggio. In questo contesto
per programma si intende l'aspetto sintattico del programma, una
stringa. Poiché generalmente i programmi esprimibili con un
linguaggio sono infiniti, la grammatica li descrive tutti dando
delle regole per generarli: sarebbe impensabile che li elencasse
tutti. Per esempio:
Grammatica 1
(a) lang : '(' ')'
(b) lang : '(' lang ')'
è una grammatica che descrive tutte le stringhe che
cominciano con n parentesi tonde aperte e finiscono con
altrettante parentesi tonde chiuse. In questa notazione abbiamo
due tipi di simboli: i terminali come '(' e ')', (che si
distinguono perché racchiusi in virgolette singole) e i
non-terminali (come lang); le regole, come (a) e (b), si dicono
produzioni. I terminali sono simboli “definitivi”,
cioè se compaiono non possono essere più rimpiazzati; i
non-terminale possono invece essere rimpiazzati dal corpo di una
regola che ha quel non-terminale in testa. Il processo di
generazione di un linguaggio è una semplice applicazione
delle regole, a partire da un non-terminale che viene normalmente
chiamato simbolo iniziale e da cui si derivano tutti i programmi
descritti da quella grammatica. Nel nostro caso il simbolo
iniziale sarà necessariamente lang (non abbiamo molta
scelta) e possiamo cominciare una generazione. La generazione
(che potrebbe anche non terminare mai) termina quando nel
programma generato non ci sono più simboli non terminali.
Per esempio:
lang
(b) => '(' lang ')'
(a) => '(' '(' ')' ')'
Quindi (()) fa parte del linguaggio generato dalla nostra
grammatica. In pratica le grammatiche non vengono utilizzate in
questo modo ma a ritroso: cioè dato un programma si cerca di
stabilire se la grammatica è in grado di generare quel
programma (il che vuol dire che il programma è
grammaticalmente corretto) e, altrettanto importante, la sequenza
di regole che hanno consentito di generare quel programma. Un
problema teorico che è stato studiato a fondo è quello
della costruzione del parser di una grammatica. Il parser è
quel particolare programma in grado di ricostruire la derivazione
del programma dal simbolo iniziale applicando le regole della
grammatica. Il che significa sostanzialmente ricostruire la
struttura grammaticale di un programma, primo passo della
compilazione. Il problema della costruzione del parser data una
grammatica non è risolvibile nella sua formulazione più
generale. È risolvibile invece solo per particolari
grammatiche, con determinare limitazioni nel formato delle
regole. La casistica è ampia e variegata, e non entreremo
nei dettagli. Diciamo solo che Yacc è un generatore di
parser: data una grammatica di tipo LALR(1) non ambigua è in
grado di generare il sorgente C di un parser per il linguaggio
descritto da quella grammatica. Facciamo un altro esempio per
chiarire meglio il concetto di derivazione (estendiamo la
notazione: il '|' abbrevia in un unica regola una serie di regole
con la stessa testa, CIFRA in maiuscolo sta per una cifra da 0 a
9).
Grammatica 2
(c) e : CIFRA | t | f
(d) t : f '+' f
(e) f : e '*' e
Consideriamo la stringa '3+5*7': l'intera derivazione può
essere ottenuta con la sequenza rappresentata da questo albero
(in figura le foglie sono i terminali, mentre i figli di un
non-terminale sono i simboli in cui si espande il non-terminale
applicando una delle regole):
Albero 1
e
|
t
/ | \
f + f
| /|\
e e * e
| | |
3 5 7
I parser (e Yacc in particolare) generano 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. Innanzitutto 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: Yacc 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. Questo è il risultato
dell'analisi 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.
| 
Clicca Qui!
