3.1Analisi sintattica in Prolog
    Indietro Avanti

    Vediamo ora come sviluppare un programma Prolog per verificare se una sequenza di parole e` una frase per il linguaggio definito dalla grammatica G1 definita in precedenza. Definiamo a tale scopo i seguenti predicati:
    proposizione(X): e` vero se X e` una frase grammaticalmente corretta per il linguaggio definito da G1;
    sn(X): e` vero se X e` un sintagma nominale;
    sv(X): e` vero se X e` un sintagma verbale.


    Analizzando la grammatica G1 risulta che una frase X e` una proposizione corretta per il nostro linguaggio se puo` essere scomposta in due componenti Y e Z, tali che Y e` un sintagma nominale e Z e` un sintagma verbale.

    Pensando di rappresentare le frasi del nostro linguaggio come liste Prolog e supponendo di avere a disposizione un predicato append che concatena due liste in una terza lista, cosi` definito:

    append([],Lista,Lista).
    append([T|Lista1],Lista2,[T|Lista3]) :- append(Lista1,Lista2,Lista3).

    possiamo scrivere:

    proposizione(X) :- append(Y,Z,X),sn(Y),sv(Z).

    Estendendo lo stesso ragionamento a tutta la grammatica, abbiamo: sn(X) :- append(Y,Z,X),articolo(Y),sostantivo(Z). sv(X) :- append(Y,Z,X),verbo(Y),sn(Z).

    Possiamo infine tener conto dei simboli terminali introducendo i fatti:

    articolo([il]). sostantivo([gatto]). sostantivo([topo]). verbo([mangia]).

    A questo punto possiamo verificare se una proposizione e` una frase del nostro linguaggio ponendo la domanda:
    ?- proposizione([il,gatto,mangia,il,topo]).
    
    Vedi esempio. Cerchiamo ora di capire cosa succede dopo aver posto tale domanda.

    La variabile X viene istanziata a [il, gatto, mangia, il, topo], mentre Y e Z non sono istanziate; in questo modo il goal genera una possibile coppia di valori di Y e Z tali che, quando Z viene appeso ad Y, fornisce come risultato X.

    Mediante il meccanismo di backtracking vengono generate tutte le possibili coppie: Y=[] Z=[il,gatto,mangia,il,topo] Y=[il] Z=[gatto,mangia,il,topo] Y=[il,gatto] Z=[mangia,il,topo] Y=[il,gatto,mangia] Z=[il,topo] Y=[il,gatto,mangia,il] Z=[topo] Y=[il,gatto,mangia,il,topo] Z=[]

    Il goal sn avra` successo solo se Y e` un sintagma nominale accettabile; se ha successo viene analizzato il goal sv, altrimenti il predicato append gli propone un'altra coppia Y,Z. In questo modo vengono generate, in modo top-down, un numero elevato di soluzioni, molte delle quali, pero`, sono inutili.



      Approfondimenti

       IndietroAvanti