ePrometeusCorsoJavaJava
testi articoli
Testi Articoli  Download
Home | Eshop | Java | Tools | Web | 
CorsoJava è ora Video! Free for all!
Clicca Qui!

PARSER IN JAVA
Sviluppare parser in Java
Generatori di Parser
Grammatiche
Alberi Sintattici
Classe AST
Annotazione della grammatica
Valutazione dell'albero sintattico
Conclusioni
Bibliografia
L'Autore

<<< Alberi Sintattici >>>

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.

ePrometeus s.r.l. - Web Software House & Open Source System Integrator
MILANO - SAN BENEDETTO DEL TRONTO(AP)
Contatti: info@eprometeus.com