Analisi del linguaggio naturale

USO DI REGOLE GRAMMATICALI

Regole grammaticali

Lo scopo tradizionale di una grammatica per un certo linguaggio consiste nello specificare la classe di frasi di quel linguaggio formate correttamente e nell'assegnare a ciascuna di esse quella che potremmo chiamare una descrizione strutturale; esso consiste, cioe` nel presentare le unita` che compongono la frase, la maniera in cui piu` frasi si combinano, le relazioni formali di una frase con altre frasi, e cosi` via.

 Per comprendere meglio quanto asserito, consideriamo la definizione data da Noam Chomsky nel tentativo di descrivere i linguaggi naturali [Chomsky 1959]:

 "per grammatica di una lingua L si intende un insieme di regole che fornisce, almeno, una specificazione completa di un insieme infinito di frasi grammaticali di L con le loro descrizioni strutturali".

 Volendo formalizzare il concetto di regole di una grammatica (o regole di riscrittura, o produzioni), possiamo dire che una regola e` una coppia ordinata (S,D) che possiamo scrivere come:

 S --> D

dove S e` un simbolo e D e` una stringa di simboli non vuota e di lunghezza finita. S e` detta parte sinistra della regola e D e` detta parte destra.

Consideriamo, per esempio, il seguente insieme di regole:

  proposizione --> sintagma_nominale, sintagma_verbale.
 sintagma_nominale --> articolo, sostantivo.
 sintagma_verbale --> verbo, sintagma_nominale.
 articolo --> [il].
 sostantivo --> [gatto].
 sostantivo --> [topo].
 verbo --> [mangia].

analizzando la grammatica G1 definita dall'insieme di regole sopra riportate, troviamo simboli che compaiono come parte sinistra di una regola; tali simboli sono detti non terminali.

 L'insieme di tutti i simboli non terminali costituisce il vocabolario dei simboli non terminali VNT per quella grammatica. Gli altri simboli, non appartenenti a VNT, sono detti terminali. L'insieme di tutti i simboli terminali di una grammatica costituisce il vocabolario dei simboli terminali VT per quella grammatica.

Per la grammatica G1 abbiamo:

 VNT: {proposizione, sintagma_nominale, sintagma_verbale, articolo, sostantivo,verbo}

 VT : {[il], [gatto], [topo], [mangia]}

 L'unione di VNT e VT costituisce il vocabolario della grammatica.

Dato un insieme di regole, esse possono essere utilizzate per derivare o produrre una proposizione applicando il metodo riportato qui di seguito.
 Si parte dal simbolo non terminale proposizione, si cerca una regola avente proposizione come parte sinistra, e si sostituisce la sua parte destra al posto di proposizione. In questo modo si rimpiazza un simbolo non terminale con una delle stringhe di cui puo` essere composto.
 Visualizziamo questa operazione utilizzando opportuni diagrammi, detti alberi sintattici, che permettono di descrivere la struttura di un regola scomponendola nelle sue parti costituenti:

 

                                                      proposizione
                                                            /        \
                                                          /            \
                                                        /                \
                                                      /                    \
                               sintagma_nominale       sintagma_verbale

 

Si ripete il processo applicandolo ad uno dei simboli non terminali, ad esempio sintagma_nominale; questo porta ad avere:

 

                                                      proposizione
                                                            /        \
                                                          /            \
                                                        /                \
                                                      /                    \
                               sintagma_nominale       sintagma_verbale
                                     /       \
                                    /          \
                             articolo   sostantivo

 

La derivazione completa della proposizione "il gatto mangia il topo" risulta essere:

                                                      proposizione
                                                            /        \
                                                          /            \
                                                        /                \
                                                      /                    \
                               sintagma_nominale       sintagma_verbale
                                     /       \                              /      \
                                    /          \                           /         \
                             articolo   sostantivo           verbo      sintagma_nominale
                                |             |                         |                   /        \
                               [il]       [gatto]             [mangia]             /           \
                                                                                   articolo     sostantivo
                                                                                       |               |
                                                                                     [il]          [topo]

 
Il simbolo non terminale proposizione viene chiamato radice dell'albero, mentre i simboli terminali foglie.
Espandendo il vocabolario dei simboli terminali, e` possibile descrivere un numero maggiore di proposizioni.

 

 

Analisi sintattica

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.

L'analisi di una frase di un linguaggio L e` la costruzione di una derivazione e, se possibile, del corrispondente albero sintattico. Un programma di analisi sintattica o parser e` anche detto riconoscitore poiche' riconosce solo frasi del linguaggio in questione.

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.

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.
Gli algoritmi di analisi sintattica vengono ulteriormente classificati in discendenti ( top-down ) ed ascendenti

( bottom-up ).

I termini fanno riferimento al modo in cui vengono costruiti gli alberi sintattici.

 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.

 

Analisi sintattica in Prolog

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]).
 

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.

Per limitare questa generazione, si puo` tener conto della forma delle regole della grammatica.
Per esempio, se il sintagma nominale e` composto da un articolo seguito da un sostantivo, si puo` utilizzare questo fatto per limitare la ricerca solo alle possibili combinazioni di questi due simboli non terminali.
Possiamo allora ridefinire il predicato sn nel seguente modo:

sn(X,Y): e` vero se c'e` un sintagma nominale all'inizio della sequenza X, e la parte rimanente della sequenza dopo il sintagma nominale e` Y.
Dobbiamo allora riscrivere le regole della grammatica G1 tenendo conto di questo nuovo predicato, cioe`:

sn(X,Y) :- articolo(X,Z),sostantivo(Z,Y).
 

Questo significa che esiste un sintagma nominale se possiamo trovare un articolo nella parte anteriore di X seguito da Z e se possiamo trovare un sostantivo nella parte anteriore di Z; possiamo schematizzare questo fatto con il seguente diagramma:

[il,gatto,mangia,il,topo]
--------- X ------------------
------------- Z ---------
------ Y -------

Il procedimento di aggiunta di un argomento dovra` ovviamente essere esteso a tutti i predicati della grammatica. Essa diventa dunque:

proposizione(X,Y) :- sn(X,Z),sv(Z,Y).
sn(X,Y) :- articolo(X,Z),sostantivo(Z,Y).
sv(X,Y) :- verbo(X,Z),sn(Z,Y).
articolo([il|Y],Y).
sostantivo([gatto|Y],Y).
sostantivo([topo|Y],Y).
verbo([mangia|Y],Y).

Il significato del fatto articolo([il|Y],Y) e` che e` possibile trovare un articolo all'inizio di una sequenza che inizia con la parola "il".

Possiamo a questo punto interrogare il sistema sottoponendogli la seguente domanda:

?- proposizione([il,gatto,mangia,il,topo],[]).

  In Prolog esiste definito il funtore --> tale per cui i due argomenti definiti in precedenza vengono riconosciuti dallo stesso senza il bisogno di dichiararli:

proposizione --> sn,sv.
sn --> articolo,sostantivo.
sv --> verbo,sn.
articolo-->[il].
sostantivo-->[gatto].
sostantivo-->[topo].
verbo-->[mangia].

 

 

Concordanze
Consideriamo il problema delle concordanze fra le parti costituenti una frase.
Frasi del tipo:

"il gatto mangiano il topo"
"i gatti mangia il topo"
"il gatto mangia il topi"

sono "sgrammaticate" in italiano anche se possono essere analizzate dalla grammatica G1 con la semplice estensione:

sostantivo --> [gatti].
sostantivo --> [topi].
verbo --> [mangiano].
articolo --> [i].

E` necessario allora modificare G1 come segue in modo da tener conto delle concordanze in genere e numero fra i costituenti la frase:

proposizione ---> prop_singolare.
proposizione ---> prop_plurale.
prop_singolare ---> sn_singolare,sv_singolare.
prop_plurale ---> sn_plurale,sv_plurale.
sn_singolare ---> art_singolare,sost_singolare.
sv_singolare ---> verbo_singolare,sn_singolare.
sn_plurale ---> art_plurale,sost_plurale.
sv_plurale ---> verbo_plurale,sn_plurale.
art_singolare ---> [il].
art_plurale ---> [i].

sost_singolare ---> [gatto].
sost_singolare ---> [topo].
sost_plurale ---> [gatti].
sost_plurale ---> [topi].
verbo_singolare ---> [mangia].
verbo_plurale ---> [mangiano].

L'effetto complessivo e` pero` quello di aumentare enormemente il numero delle produzioni della grammatica.

 

Un modo piu` elegante per risolvere questo tipo di problema e` quello di introdurre un argomento che tenga conto, per esempio, del fatto che una frase sia plurale o singolare.

Nella grammatica G1 si potrebbe quindi modificare il predicato proposizione in proposizione(singolare) per indicare una frase singolare, o, piu` ingenerale, proposizione(X) per indicare una frase con pluralita` X.

La grammatica G1 diventa quindi:

proposizione ---> proposizione(X).
proposizione(X) ---> sn(X),sv(Y).
sn(X) ---> articolo(X),sostantivo(X).
sv(X) ---> verbo(X),sn(X).

articolo(singolare) ---> [il].
articolo(plurale) ---> [i].
sostantivo(singolare) ---> [topo].
sostantivo(singolare) ---> [gatto].
sostantivo(plurale) ---> [topi].
sostantivo(plurale) ---> [gatti].
verbo(singolare) ---> [mangia].
verbo(plurale) ---> [mangiano].


 

Introducendo opportunamente questi argomenti aggiuntivi, si e` in grado di rappresentare una maggior quantita` di informazioni per poter, ad esempio, tener conto della semantica di una frase, ovvero del significato della frase stessa sia essa una frase di un linguaggio naturale o di un qualche linguaggio di programmazione.

 

 

Costruzione dell’albero sintattico

Gli alberi sintattici sono un utile strumento per capire la sintassi delle proposizioni; e` importante pero` il concetto di unicita` dell'albero sintattico.
Si consideri, ad esempio, la grammatica:

proposizione ---> sostantivo,verbo.
proposizione ---> verbo,sostantivo.
sostantivo([time]).
sostantivo([flies]).
verbo([time]).
verbo([flies]).

 

Sono stati introdotti vocaboli inglesi in quanto illustrano le ambiguita` di significato meglio di quanto si possa fare con vocaboli della lingua italiana.

Applicando le regole sopra riportate, possiamo generare la proposizione "time flies" in due modi diversi, con due diversi alberi sintattici:

                                                proposizione                                      proposizione
                                                 /             \                                            /         \
                                               /                 \                                        /             \
                                         sostantivo        verbo                               verbo       sostantivo
                                              |                    |                                      |                |
                                           time               flies                                 time            flies

In entrambi i casi la proposizione ha senso compiuto, "il tempo vola" oppure "cronometrare le mosche".
Il problema e` che, al di fuori del contesto, non possiamo decidere che cosa affermi la proposizione perche'
non siamo in grado di analizzarla correttamente; non riusciamo cioe` a separare in modo non ambiguo le parti che la compongono.
 

Gli argomenti aggiuntivi delle regole grammeticali del Prolog permettono di costruire l'albero sintattico come risultato dell'analisi.
Supponiamo di voler costruire, ad esempio, per la frase "il gatto mangia il topo" l'albero sintattico avente la struttura seguente:

frase(
       sn(det(il),
          nome (gatto),
         ),
       sv(v (mangia),
          sn(det(il),
             nome(topo)
             )
         )
      )

Per ottenere tale struttura, dovremo aggiungere degli argomenti a ciascun predicato che ci dicano come costruire l'albero sintattico complessivo a partire dai sottoalberi di ogni non terminale.
A questo scopo possiamo modificare la prima regola di G1 nel seguente modo:

proposizione (frase(T1,T2)) ---> sintagma_nominale(T1), sintagma_verbale(T2).
 

Tale regola dice che e` possibile trovare una proposizione formata da un sintagma nominale con albero sintattico sn seguita da un sintagma verbale con albero sintattico sv.

Estendendo il ragionamento a tutte le regole della grammatica abbiamo:
 

sintagma_nominale (sn(T1,T2)) --->articolo(T1),sostantivo(T2).
sintagma_verbale (sv(T1,T2)) --->verbo(T1),sintagma_nominale(T2).
articolo(det(il)) ---> [il].
sostantivo(nome(gatto)) ---> [gatto].
sostantivo(nome(topo)) ---> [topo].
verbo(V(mangia)) ---> [mangia].

 
Se volessimo a questo punto tener conto anche delle concordanze dovremmo introdurre altri argomenti aggiuntivi; per la prima regola avremo ad esempio:

proposizione(frase(T1,T2),X) ---> sintagma_nominale(T1,X),sintagma_verbale(T2,X).

 

 

Esecuzione di goal Prolog

Consideriamo ora il problema di voler introdurre nuovi simboli terminali, per esempio la parola "canarino", tenendo conto delle concordanze; dovremo aggiungere la regola:

sostantivo(singolare,nome(canarino)) ---> [canarino].

Se i simboli terminali da introdurre sono in numero elevato, questa scrittura puo` risultare molto pesante e puo`, inoltre, portare ad uno spreco di memoria. Un modo piu` conveniente per gestire questa operazione
potrebbe essere quello di separare le informazioni raccogliendo da qualche parte quelle relative a tutti i nomi.

Questo puo` essere realizzato combinando insieme le regole grammaticali con clausole del Prolog nel
seguente modo:

sostantivo(X,nome(Y)) ---> [Y],{isa_nome(Y,X)}.

dove il predicato isa_nome esprime quali sono le parole che sono nomi e il loro numero:

isa_nome(canarino,singolare).
isa_nome(canarini,plurale).

 

Una soluzione di questo tipo e` gia` migliore delle precedenti, pero` non tiene ancora conto del fatto che molti nomi di un linguaggio naturale, pur cambiando il numero, mantengono inalterata una parte, la radice del nome, e modificano solo la desinenza. Possiamo allora modificare ancora la grammatica tenendo conto di queste considerazioni ed utilizzando il predicato di sistema name nel seguente modo:

 

sostantivo(singolare,nome(RadiceY)) ---> [Y],
  {name(Y,Singnome)
  append(Radice,'o',Singnome),
  name(RadiceY,Radice),
  isa_nome(RadiceY)}.
 

Questa regola puo` essere parafrasata in:

"se X e` la radice di un nome, allora la forma singolare del nome viene formata aggiungendo una o alla fine di X".

Questa impostazione consente di memorizzare i nomi semplicemente cosi`:

isa_nome(canarin).
isa_nome(gatt).
isa_nome(top).  

Ovviamente occorre definire una regola analoga alla precedente per la pluralizzazione dei nomi.

 

COMPRENSIONE DEL LINGUAGGIO NATURALE

 

Il modo piu' naturale per l'uomo per comunicare con i suoi simili e' quello di parlare o scrivere in linguaggio naturale, sia esso italiano, inglese, o cinese.
Al fine di comunicare occorre pero' essere in grado di comprendere enunciati in linguaggio naturale.
Comprendere un enunciato in linguaggio naturale significa avere in precedenza definito una rappresentazione del significato delle parole, e quali sono i processi di riconoscimento e costruzione del significato stesso.
Il significato di una parola e, piu' in generale di una frase, non e' pero' solo un attributo descrittivo legato alla parola o alla frase, ma e' una nozione operativa piu' complessa ed integrata in un modello che simula il processo di comprensione umana.
Ma cosa si intende per comprensione ?
Da un punto di vista computazionale si puo' affermare che un ipotetico utente ha la prova che un ipotetico "robot" ha compreso i suoi comandi in linguaggio naturale, se la risposta del robot e' conforme alle aspettative dell'utente.
Si tratta di una esemplificazione facilmente trasferibile anche nella interazione umana; in effetti non abbiamo nessuna indicazione del fatto che il nostro interlocutore "capisca quello che gli si dice" e del come questa comprensione avvenga, fintanto che egli non ce ne dara' un segno.
Al fine di illustrare le tecniche di comprensione del linguaggio naturale (nel seguito parlando di linguaggio naturale considereremo il linguaggio naturale scritto e non quello parlato) possiamo schematizzare il processo di comprensione in due passi:

* comprensione di ogni singola parola di una frase .

* collegamento reciproco di tutte le parole al fine di creare delle strutture che rappresentino il significato dell'intera frase .

  Il primo dei due passi sembra, a prima vista, piu' banale: basta ricercare ogni parola in un dizionario (chiamato spesso anche lessico) e leggere in corrispondenza di ogni parola il corrispondente significato.
Purtroppo molte parole hanno piu' di un significato, e spesso non e' possibile scegliere quello corretto considerando la parola isolatamente, ma occorre andare ad analizzare l'intero contesto della frase o, addirittura, del periodo.
Per poter eseguire il secondo passo occorre poi tenere conto di vari tipi di informazioni quali, ad esempio, la conoscenza del particolare linguaggio utilizzato, le convenzioni di comunicazione tra chi parla (o scrive) e chi ascolta (o legge), la conoscenza generale sul mondo che ci circonda.
Questo secondo passo, data la sua complessita', viene normalmente suddiviso in:

  1)analisi sintattica, dove la sequenza di parole della frase da analizzare viene trasformata in strutture che mostrano come le parole sono in relazione le une con le altre;

2)analisi semantica, dove viene assegnato, se possibile, un certo significato alle strutture individuate al passo precedente.
Durante questa fase vengono scartate strutture per le quali non sia possibile effettuare tale assegnazione.
Per esempio, la frase "le verdi idee senza colore dormono furiosamente" [Chomsky 1969], corretta dal punto di vista sintattico, dovrebbe essere viceversa scartata dall'analizzatore semantico;

3)analisi pragmatica, in cui le strutture che rappresentano la frase in corso di analisi, vengono reinterpretate per determinare il significato corrente.

Spesso il confine tra queste fasi non e' cosi' marcato e puo' essere necessaria una certa interazione tra un tipo di analisi e l'altro.

  Un approccio semplice alla comprensione di frasi in linguaggio naturale storicamente e' stato quello di riunire le operazioni sopra descritte in un unico passo.
Questo puo' essere fatto ricercando nella frase da analizzare opportune parole chiave ( templates ).
Ricercando solo alcune parole nella frase da analizzare, cioe' quelle che combaciano con i templates, si ha il vantaggio di analizzare anche frasi parzialmente sgrammaticate; vengono pero' ignorate un gran numero di informazioni contenute nella frase stessa.
Tale approccio venne seguito nei primi sistemi in grado di ricevere comandi in linguaggio naturale come ELIZA [Weizenbaum 1966], che simula il colloquio con uno psichiatra, e STUDENT [Bobrow 1968], che risolve problemi esprimibili con equazioni di primo grado.
Per evitare che nessun dettaglio del significato di una frase vada perduto, l'approccio successivamente seguito fu quello di analizzare in dettaglio prima di tutto la struttura della frase ( parsing ).

 

 

TIPI DI GRAMMATICHE

 

Principali obiettivi del processo di parsing sono:

 

a)determinare quali frasi sono grammaticalmente corrette e quali no;

b)assegnare una struttura alle frasi grammaticalmente corrette.

 

Per raggiungere tali obiettivi, gli algoritmi di parsing utilizzano delle grammatiche.

Riprendiamo qui di seguito alcuni concetti visti in precedenza, e li estendiamo.

 

Una grammatica a struttura di frase e' una quadrupla G=(V,VT,R,S) dove:

* V e' un insieme finito non vuoto chiamato vocabolario del sistema;

* VT e' un sottoinsieme non vuoto di V chiamato vocabolario dei simboli terminali;

il vocabolario dei simboli non terminali VNT e' allora dato da V-VT.

* R e' un insieme finito di regole della forma:

A--->B dove A appartiene < V*VNT V* > e B appartiene V*.

(* viene chiamato anche operatore di Kleene, e sta ad indicare che del simbolo in oggetto possono essere presenti qualunque numero di occorrenze, compresa la stringa vuota);

* S e' un elemento che appartiene a VNT e viene chiamato simbolo distintivo.

 

 

 

Per ogni grammatica esiste un linguaggio L(G) che e' costituito dall'insieme di tutti i simboli terminali che possono essere derivati dal simbolo distintivo applicando un numero finito di regole R.

 

Nei linguaggi naturali esiste il problema della ambiguita'; una frase puo' avere piu' significati, come ad esempio:

"la vecchia porta la sbarra"

 

in cui il terminale "porta" puo' essere considerato come derivazione di un sintagma nominale, oppure come derivazione di un sintagma verbale.

 

Dato un linguaggio, possono esistere diverse grammatiche che permettono di descriverlo; tali grammatiche non risultano pero' essere equivalenti in utilita'.

 

Alcune di esse possono essere utilizzate per analizzare efficacementeil linguaggio, mentre altre possono richiedere delle ricerche piu' laboriose; inoltre, grammatiche differenti producono differenti alberi sintattici.

 

Secondo le definizioni date fino a questo punto, non compare nessuna forma di restrizione sulle regole di una grammatica.

 

Sia nella parte sinistra che nella parte destra di una regola possono essere presenti qualunque numero, purche' finito, di simboli; Inoltre le regole possono essere ricorsive.

 

Analizzare frasi mediante una grammatica cosi' definita, puo' risultare molto pesante e complesso dal punto di vista computazionale.

 

Introducendo invece alcune restrizioni sulla forma delle regole, e' possibile effettuare del parsing in modo efficiente.

 

L'introduzione di tali restrizioni impone pero' delle limitazioni sui linguaggi descrivibili con queste grammatiche.

 

Seguendo gli studi di N.Chomsky [1969], e' possibile suddividere le grammatiche a struttura di frase in quattro tipi, a seconda della forma delle produzioni: Tipo 0 ,Tipo 1, Tipo 2,Tipo 3.

 

Nelle grammatiche di tipo 0 non ci sono restrizioni sulla forma delle regole.

 

Come gia' accennato, questo tipo di grammatiche e' troppo generale per essere usato e, in generale, molto difficile. Il linguaggio generato da una grammatica di tipo 0 e' detto linguaggio di tipo 0.

 

Le regole di una grammatica di tipo 1 o grammatica contestuale hanno la forma:

aAb--->aBb dove A appartiene VNT, a,b,B appartiene V con B\=$ (stringa vuota).

Tali regole possono essere lette come: "A genera B all'interno del contesto a,b".

 

Il linguaggio generato da una grammatica di tipo 1 o contestuale e' chiamato linguaggio di tipo 1 o linguaggio contestuale.

 

 

 

Le regole di una grammatica di tipo 2 o grammatica libera da contesto hanno la forma:

 

A--->B dove A VNT, B V*-$.

 

Il linguaggio generato da una grammatica di tipo 2 o libera da contesto e' chiamato linguaggio di tipo 2 o linguaggio libero da contesto.

 

Le regole di una grammatica di tipo 3 o grammatica regolare hanno la forma:

 

A-->aB oppure A--->a dove A,B VNT, a VT

 

oppure la forma:

 

A--->Ba oppure A--->a.

 

Il linguaggio generato da una grammatica di tipo 3 o regolare e' chiamato linguaggio di tipo 3 o linguaggio regolare.

 

I linguaggi regolari possono essere analizzati utilizzando automi a stati finiti.

 

Un automa a stati finiti e' una struttura nella quale l'analisi viene modellata come una transizione da uno stato, appartenente ad un insieme finito di stati, ad un altro stato.

 

Uno stato particolare e' segnato come "stato di partenza", ed esistono uno o piu' stati segnati come "stati finali".

 

In un modello di questo tipo, una frase e' detta grammaticalmente corretta se, analizzandola parola dopo parola da sinistra verso destra, e' possibile effettuare delle transizioni fino a raggiungere uno stato finale.

 

Gli stati dell'automa sono connessi mediante archi etichettati, dove l'etichetta indica il simbolo che deve essere in quel momento presente nella stringa in ingresso per poter effettuare quella transizione.

 

Anche se gli automi a stati finiti sono efficienti, il loro utilizzo nell'analisi del linguaggio naturale e' limitato per le restrizioni imposte sulle regole della grammatica che, per esempio, non permettono di rappresentare piu' frasi relative in cascata.

 

Discorso analogo vale anche per i linguaggi di programmazione in cui e' indispensabile rappresentare espressioni a vari livelli, utilizzando le parentesi.

 

Grammatiche regolari vengono comunque utilizzate per l'analisi lessicale, in cui e' semplicemente richiesto di individuare sequenze di caratteri che rappresentino delle parole.

Per i linguaggi liberi da contesto, e in particolare modo per i linguaggi liberi da contesto deterministici, sono stati sviluppati efficienti algoritmi di parsing, sopratutto nell'ambito dei linguaggi di programmazione [Aho e Ullman 1972, Graham et al. 1980].

 

 

 

Sfortunatamente, a differenza dei linguaggi di programmazione, i linguaggi naturali non possono essere descritti con grammatiche libere da contesto.

 

UNA GRAMMATICA PER L'ITALIANO
 

In questo paragrafo viene riportata una grammatica libera da contesto per un sottoinsieme della lingua italiana. Per renderne piu' semplice la lettura, si e' ritenuto opportuno non esplicitare all'interno della grammatica gli extra argomenti; per fare in modo che la grammatica sia un programma Prolog direttamente funzionante e' sufficiente quindi introdurre in ogni predicato gli opportuni argomenti.

Per quanto riguarda le applicazioni all'italiano delle regole grammaticali espresse in Prolog, abbiamo preso in considerazione in particolare alcune tipologie di frasi quali:
 

1. TRANSITIVE: sono presenti verbi che esprimono un'azione che dal soggetto passa direttamente sull'oggetto, cioe' su chi la riceve.

ES. Elena scrive una lettera.

2. INTRANSITIVE: il verbo esprime uno stato o un'azione che non passa direttamente sull'oggetto, ma si esaurisce direttamente sul soggetto che la compie.

ES. Elena ride.

3. RELATIVE: c'è un pronome relativo che sostituisce un nome e nello stesso tempo mette in relazione proposizioni congiungendole in un'unica frase.

ES. Ho visto Paolo che usciva.

4. INFINITIVE: il verbo esprime un'azione attraverso l'uso dell'infinito.

ES. Il ragazzo dice di mangiare.

5. FRASI COMPLEMENTO: il complemento oggetto anziché supportare un nome si riferisce ad una frase.

ES. Paolo dice che Giovanni va a scuola.

 

Per costruire queste tipologie di frasi abbiamo preso in considerazione alcune elementi comuni, come possono essere:  

* SOGGETTO: si riferisce a cio' di cui si parla.

* VERBO: si riferisce a cio'che si dice del soggetto.

* OGGETTO: si riferisce a cio' che specifica la frase.

  Nel programma sono presenti alcuni meccanismi particolari, come possono essere le liste di estraposizione e i controlli semantici.

Le liste di estraposizione sono un concetto che viene utilizzato in presenza di frasi relative nelle quali a seconda che ci riferiamo ad un soggetto o ad un oggetto questi vengono analizzati all'inizio o in coda alla frase.

 La parte di frase relativa al soggetto e all'oggetto vengono inserite in due variabili chiamate rispettivamente H0 ed H1 che a seconda se viene trattato l'uno o l'altro una delle due rimarrà inutilizzata.

 Per quanto riguarda i controlli semantici possiamo individuare un paio di argomenti sui quali vale al pena di soffermarsi; il primo sono sicuramente le parentesi graffe tra le quali viene racchiuso il controllo vero e proprio.

  L'altro particolare sul quale ci soffermeremo sono i pred; per quanto riguarda quelli riferiti al verbo definiscono la lista dei possibili soggetti e oggetti che possono essere supportati dal verbo in questione, in particolare i pred di nome definiscono il tipo di nome.

 In entrambi i programmi realizzati che si riferiscono rispettivamente ad un file con e senza i controlli semantici; il modo corretto e piu' veloce per lanciare un goal; cioè chiedere l'analisi di un a frase è il seguente:

frase(numero della frase in questione).
Riportiamo di seguito alcuni esempi per ciascuna tipologia di frase presa in considerazione:

 
/*TRANSITIVA*/
ff(1,[mario,legge,il,rapporto]).

/*INTRANSITIVA*/
ff(2,[il,ragazzo,corse,a,casa]).

/*RELATIVA*/
ff(3,[il,padrone,mangia,la,mela,che,gino,ha,perso]).

/*INFINITIVA*/
ff(4,[lo,studente,dice,di,sapere,la,storia]).

/*FRASE COMPLEMENTO*/
ff(5,[il,delegato,ritiene,che,la,casa,sia,del,suocero]).