2.2Analisi sintattica
    Indietro Avanti

    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.

    num --> cifra, num.

    num --> cifra.

    cifra --> [0].

    ...

    cifra --> [9].

    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.


    Quiz

     IndietroAvanti