Come gia` accennato, uno dei fini della grammatica per un linguaggio e` quello di riuscire a descrivere tutte le proposizioni per quel linguaggio; tale obiettivo deve essere pero` raggiunto con un numero finito e ragionevole di regole.
Questo e` importante e significativo se pensiamo che solitamente un linguaggio e` formato da un numero infinito di proposizioni.
Nel seguito, quando parleremo di analisi sintattica, intenderemo sempre analisi da sinistra a destra in quanto,
oltre a risultare piu` naturale, e` il modo in cui lavora il Prolog.
I termini fanno riferimento al modo in cui vengono costruiti gli alberi sintattici.
![]() | Un programma che decide se una frase appartiene ad un linguaggio L viene detto riconoscitore per tale linguaggio. |
![]() | Un programma di analisi sintattica o parser e` la costruzione di una derivazione e del corrispondente albero sintattico (vedi pagina successiva) per una frase, se essa appartiene al linguaggio L. Gli algoritmi di analisi sintattica vengono detti da sinistra a destra quando esaminano ed elaborano prima i simboli piu` a sinistra e proseguono verso destra solo quando e` necessario; dualmente, vengono detti da destra a sinistra quando elaborano per primi i simboli piu` a destra. |
![]() | Gli algoritmi di analisi sintattica vengono ulteriormente classificati in discendenti ( top-down ) ed ascendenti ( bottom-up ). |
![]() | Un analizzatore top-down costruisce l'albero a partire dalla radice ed opera verso il basso fino a raggiungere le foglie. Si consideri, ad esempio, la frase "17" appartenente alla seguente grammatica G2 per numeri interi:
int --> num.
L'analisi viene effettuata sostituendo, ad ogni passo, il simbolo non terminale piu` a sinistra con la sua parte destra.
Un'analisi bottom-up consiste nel partire dalla frase e nel cercare di ridurla alla radice dell'albero.
Il primo passo dell'analisi della frase "17" consiste nel ridurre 1 a cifra generando la frase "cifra 7". Il passo successivo e` quello di ridurre cifra a num; per effettuare tale riduzione e` necessario pero` ridurre prima 7 a cifra e cifra a num.
|