In che modo questa grammatica libera dal contesto utilizza gli elenchi di differenze nel funzionamento di Prolog?

Question

Sto leggendo questo tutorial sul contesto grammatiche gratuiti a Prolog, e parlare in fondo alla pagina l'implementazione di una grammatica libera dal contesto in Prolog utilizzando gli elenchi di differenza, con il seguente blocco di codice incluso:

s(X,Z):- np(X,Y), vp(Y,Z). 

np(X,Z):- det(X,Y), n(Y,Z). 

vp(X,Z):- v(X,Y), np(Y,Z). 
vp(X,Z):- v(X,Z). 

det([the|W],W). 
det([a|W],W). 

n([woman|W],W). 
n([man|W],W). 

v([shoots|W],W). 

E ' menzioni:

Considerare attentamente queste regole. Ad esempio, la regola s dice: So che la coppia di liste X e Z rappresenta una frase se (1) posso consumare X e lasciare una Y, e la coppia X e Y rappresenta una frase nominale e (2) Posso quindi continuare a consumare Y lasciando Z dietro, e la coppia YZ rappresenta una frase verbale. La regola np e la seconda delle regole vp funzionano in modo simile.

E

Pensate al primo elenco di ciò che deve essere consumata (o se preferite: la lista di input), e la seconda lista come quello che dovremmo lasciare alle spalle (o: l'uscita elenco). Visto da questa prospettiva (piuttosto procedurale) l'elenco differenza

[a,woman,shoots,a,man] []. 

rappresenta la frase una donna spara un uomo perché dice: Se ho consumare tutti i simboli a sinistra, e lasciarsi alle spalle i simboli sulla destra, poi Ho la frase che mi interessa. Cioè, la frase che ci interessa è la differenza tra i contenuti di queste due liste.

Questo è tutto ciò che dobbiamo sapere sugli elenchi di differenze per riscrivere il nostro riconoscitore. Se ci limitiamo a tenere a mente l'idea di consumare qualcosa, e lasciando qualcosa dietro in mente, si ottiene la seguente riconoscitore:

Come una spiegazione, ma che proprio non sta facendo nulla per chiarire questo codice per me. Capisco che sia più efficiente dell'uso di append/3, ma per quanto riguarda la nozione di consumo di cose e di lasciare indietro gli altri, sembra molto più complicato della precedente implementazione append/3, e non riesco a farne a testa o croce. Inoltre quando copio e incollo quel codice in un Prolog visualizer per cercare di capirlo, il visualizzatore dice che ci sono errori. Qualcuno potrebbe far luce su questo?

Answer 1

Listing come fatti

Proviamo a spiegare questo con un controesempio. Diamo specificare i nomi, verbi, ecc, con semplici fatti:

det(the). 
det(a). 

n(woman). 
n(man). 

v(shoots). 

Ora possiamo implementare una sostantivo frasenp come:

np([X,Y]) :- 
    det(X), 
    n(Y). 

In altre parole si dice "una frase sostantivo è un frase con due parole, la prima è una det, la seconda una n ". E questo funzionerà: se interrogiamo np([a,woman]), avrà successo ecc.

Ma ora dobbiamo fare qualcosa di più avanzato, definire la frase del verbo.Ci sono due possibili sintagmi verbali: quello con un verbo e un sintagma nominale che è stato originariamente definito come:

vp(X,Z):- v(X,Y),np(Y,Z). 

potremmo definire come:

vp([X|Y]) :- 
    v(X), 
    np(Y). 

E quella con un solo verbo :

vp(X,Z):- v(X,Z). 

che può essere convertito in:

vp([X]) :- 
    v(X). 

Il problema di indovinatura

Il problema tuttavia è che entrambe le varianti hanno un numero diverso di parole: ci sono frasi verbali con una parola e con tre parole. Questo non è davvero un problema, ma ora dicono - so che questo non è corretto Inglese - esiste una sentenza definita come vp seguita da np, quindi questo sarebbe:

s(X,Z):- vp(X,Y), np(Y,Z). 

nella grammatica originale.

Il problema è che, se vogliamo trasformare questo nel nostro nuovo modo di rappresentarla, abbiamo bisogno di sapere quanto sarà vpconsumare (quanto parole sarà mangiato da vp). Non possiamo saperlo in anticipo: dato che a questo punto non sappiamo molto della frase, non possiamo indovinare se lo vp mangerà una o tre parole.

potremmo naturalmente indovinare il numero di parole con:

s([X|Y]) :- 
    vp([X]), 
    np(Y). 
s([X,Y,Z|T]) :- 
    vp([X,Y,Z]), 
    np(Z). 

Ma spero che si può immaginare che se si definirebbe sintagmi verbali con 1, 3, 5 e 7 parole, le cose andranno problematico. Un altro modo per risolvere questo problema, è lasciare che questo Prolog:

s(S) :- 
    append(VP,NP,S), 
    vp(VP), 
    np(NP). 

Ora Prolog indovinare come suddividere la frase in due parti prima e poi cercare di soddisfare ogni sua parte. Ma il problema è che per una frase con n parole, ci sono n punti di interruzione.

Così Prolog volontà, per esempio prima divisione come:

VP=[],NP=[shoots,the,man,the,woman] 

(ricordiamo abbiamo scambiato l'ordine del verbo frase e la frase sostantivo). Evidentemente il numero vp non sarà molto felice se riceverà una stringa vuota. Così sarà respinto facilmente. Ma la prossima si dice:

VP=[shoots],NP=[the,man,the,woman] 

Ora vp è felice con solo shoots, ma richiederà un certo sforzo computazionale per rendersi conto che. np non è tuttavia divertito da questa lunga parte. Così Prolog marcia indietro di nuovo:

VP=[shoots,the],NP=[man,the,woman] 

ora vp si lamentano ancora una volta che è stato dato troppo parole.Finalmente Prolog lo dividerà correttamente con:

VP=[shoots,the,woman],NP=[the,woman] 

Il punto è che richiede un gran numero di ipotesi. E per ognuna di queste ipotesi, vp e np richiederanno anche il lavoro. Per una grammatica veramente complicata, vp e np potrebbero dividere ulteriormente la frase, con conseguente enorme quantità di tentativi ed errori.

Il vero motivo è che lo append/3 non ha indizi "semantici" su come suddividere la frase, quindi tenta tutte le possibilità. Uno è tuttavia più interessato ad un approccio in cui vp potrebbe fornire informazioni su quale parte della frase desidera realmente.

Inoltre, se è necessario dividere la frase in 3 parti, il numero di modi per farlo aumenta anche a O (n^2) e così via. Quindi indovinare non farà il trucco.

Si potrebbe anche provare a generare una frase di verbo a caso, e poi sperare la frase verbo corrisponde:

s(S) :- 
    vp(VP), 
    append(VP,NP,S), 
    np(NP). 

Ma in questo caso il numero di sintagmi verbali indovinati si saltare in aria in modo esponenziale. Naturalmente puoi dare "suggerimenti" ecc. Per accelerare il processo, ma ci vorrà ancora del tempo.

La soluzione

Che cosa si vuole fare è quello di fornire la parte della frase ad ogni predicato in modo tale che un predicato assomiglia:

predicate(Subsentence,Remaining) 

Subsentence è una lista di parole che iniziano per che predicato. Ad esempio per una frase nominale, potrebbe apparire come [the,woman,shoots,the,man]. Ogni predicato consuma le parole a cui è interessato: le parole fino a un certo punto. In questo caso, la frase-nome è interessata solo a ['the','woman'], perché quella è una frase-nome. Per fare il parsing rimanente, restituisce la parte restante [shoots,the,woman], nella speranza che qualche altro predicato possa consumare il resto della frase.

per il nostro tavolo di fatti che è facile:

det([the|W],W). 
det([a|W],W). 

n([woman|W],W). 
n([man|W],W). 

v([shoots|W],W). 

Ciò significa quindi che se si interroga un setence: [the,woman,shoots,...], e si chiede al det/2 che sia un determinante, si dirà: "Sì, the è un determinante, ma la parte restante [woman,shoots,...] "non fa parte del determinatore, si prega di abbinarlo con qualcos'altro.

Questa corrispondenza viene eseguita perché un elenco è rappresentato come un elenco collegato. [the,woman,shoots,...], in realtà è rappresentato come [the|[woman|[shoots|...]]] (quindi punta al successivo "Sottolista"). Se corrispondono:

[the|[woman|[shoots|...]]] 
det([the|W]     ,W) 

Sarà unificare [woman|[shoots|...]] con W e quindi provocare:

det([the|[woman|[shoots|...]],[woman|[shoots|...]]). 

Così la restituzione del restante lista, ha così consumato la parte the.livello

superiore predicati

Ora nel caso in cui definiamo il sostantivo frase:

np(X,Z):- det(X,Y), n(Y,Z). 

E noi ancora una volta chiamata con [the,woman,shoots,...], si interrogherà unificante X con quella lista. Chiamerà per prima cosa det che consumerà the, senza bisogno di backtracking. Successivo Y è uguale a [woman,shoots,...], ora il n/2 consuma donna e restituisce [shoots,...]. Questo è anche il risultato che lo np restituirà e un altro predicato dovrà consumarlo.

utilità

Di 'si introduce il vostro nome come un sostantivo aggiuntivo:

n([doug,smith|W],W). 

(scusate per l'utilizzo di piccoli casi, ma per il resto Prolog vede questi come variabili).

Si cercherà semplicemente di abbinare le prime due parole con doug e smith, e se ciò riesce, provare a far corrispondere il resto della frase. Quindi si può creare una serie come: [the,doug,smith,shoots,the,woman] (mi dispiace per il fatto che, in inglese, alcune frasi nominali si associano ad un nome direttamente np(X,Y) :- n(X,Y) così che lo the possa essere rimosso per una grammatica inglese più complessa).

Indovinare completamente eliminato?

L'ipotesi è completamente eliminata? No. È ancora possibile che ci sia una sovrapposizione nel consumo. Per esempio si potrebbe aggiungere:

n([doug,smith|W],W). 
n([doug|W],W). 

In tal caso, se si esegue una query per [the,doug,smith,shoots,the,woman]. In primo luogo consumerà/mangi il det, successivamente cercherà un nome da consumare da [doug,smith,...]. Ci sono due candidati. Prolog prima tenterà di mangiare solo doug e corrisponderà a [smith,shoots,...] come una frase intera di un verbo, ma poiché smith non è un verbo, tornerà indietro, riconsidererà solo una parola e quindi decinderà di mangiare sia doug che smith come nome.

Il punto è che quando si utilizza append, Prolog dovrebbe tornare indietro.

Conclusione

Utilizzando gli elenchi di differenza, si può mangiare una quantità arbitraria di parole. Il resto viene restituito in modo che altre parti della frase come la frase del verbo mirino a consumare il resto. L'elenco è inoltre sempre completamente fondato, quindi non si usa assolutamente la forza bruta per generare prima tutti i tipi di frasi verbali.

Answer 2

Gli elenchi di differenze funzionano in questo modo (spiegazione di un laico).

consideri accodamento è utilizzato per unire due treni X e Y

X = {1}[2][3][4]  Y = {a}[b][c] 

{ } - rappresenta il compartimento avente il motore o la testa.

[ ] - rappresenta compartimenti o elementi nella coda. Supponiamo di poter rimuovere il motore da un compartimento e inserirlo in un altro.

procede accodamento come questo: nuova stazione Z è ora Y esempio, {a}[b][c] prossimo il motore viene rimosso dalla testa Z s' e si inserisce nello scomparto coda rimosso da X e il nuovo treno Z è:

Z = {4}[a][b][c] 

Lo stesso processo viene ripetuto

Z = {3}[4][a][b][c] 
Z = {2}[3][4][a][b][c] 
Z = {1}[2][[3][4][a][b][c] 

nostro nuovo treno lungo.

L'introduzione di liste di differenze è come avere un toa hook alla fine di X che può essere facilmente collegato a Y. Il gancio finale viene scartato.

n([man|W],W). 

W è il gancio qui, unificazione W con la testa della lista successore è il processo di fissaggio.

Answer 3

So esattamente cosa intendi. All'inizio è piuttosto difficile pensare in termini di differenze di lista. La buona notizia è che tu di solito non devi fare questo .

C'è un formalismo incorporato definito Definite Clause Grammars (DCG) che rende completamente inutile codificare manualmente le differenze di elenco in casi come il vostro.

Nel tuo esempio, vi consiglio di scrivere semplicemente questo come:

s --> np, vp. 

np --> det, n. 

vp --> v, np. 
vp --> v. 

det --> [the]. 
det --> [a]. 

n --> [woman]. 
n --> [man]. 

v --> [shoots]. 

e accettare il fatto che all'interno di DCGs, [T] rappresenta il terminale T e , viene letto come "e poi". Ecco come descrivere le liste con DCG.

È già possibile utilizzare questo per chiedere tutte le soluzioni, utilizzando l'interfaccia phrase/2 a DCGs:

?- phrase(s, Ls). 
Ls = [the, woman, shoots, the, woman] ; 
Ls = [the, woman, shoots, the, man] ; 
Ls = [the, woman, shoots, a, woman] ; 
etc. 

E 'difficile capire questo in termini procedurali in un primo momento, quindi suggerisco che non si tenta questo . Invece, focalizza una lettura dichiarativa della grammatica e vedi che descrive le liste.

Successivamente, è possibile accedere a ulteriori dettagli di implementazione. Inizia con il modo in cui i terminali semplici vengono tradotti, quindi passa a costrutti grammaticali più avanzati: regole contenenti un terminale singolo, quindi regole contenenti un terminale e un terminale non lineare ecc.

Answer 4

Questa risposta è un seguito a the answer by @mat.Procediamo passo per passo:

1. Si comincia con il codice riportato nella risposta @ di mat:

    
   s --> np, vp. 
   
   np --> det, n. 
   
   vp --> v, np. 
   vp --> v. 
   
   det --> [the]. 
   det --> [a]. 
   
   n --> [woman]. 
   n --> [man]. 
   
   v --> [shoots]. 
   

2. Finora, abbiamo usato (',')/2: (A,B) significa sequenza A seguita da successione B.

   Avanti, useremo anche ('|')/2: (A|B) significa sequenza A o sequenza B.

   Per informazioni sui costrutti di controllo nei corpi grammaticali read this manual section.

    
   s --> np, vp. 
   
   np --> det, n. 
   
   vp --> v, np | v. 
   
   det --> [the] | [a]. 
   
   n --> [woman] | [man]. 
   
   v --> [shoots]. 
   

3. Possiamo rendere il codice più conciso da "inlining" un po ':

    
   s --> np, vp. 
   
   np --> ([the] | [a]), ([woman] | [man]). 
   
   vp --> v,np | v. 
   
   v --> [shoots]. 
   

4. Che ne dite di un po' di inlining --- come suggerito dal @mat nel suo commento ...

    
   s --> np, [shoots], (np | []). 
   
   np --> ([the] | [a]), ([woman] | [man]). 
   

5. Portalo al massimo! (Il seguente potrebbe essere scritta come una battuta.)

    
   ?- phrase((([the] 
         | [a]), ([woman] 
           | [man]), [shoots], (([the] 
                | [a]), ([woman] 
                  | [man]) 
                | [])), 
         Ws). 
   

Formulazioni differenti tutti hanno i/down-lati a monte, ad esempio, codice compatto è più difficile da estendere, ma potrebbe essere necessaria quando lo spazio è scarso quando si inserisce il codice sulle diapositive della presentazione.

---

interrogazione Esempio:

?- phrase(s,Ws). 
    Ws = [the, woman, shoots, the, woman] 
; Ws = [the, woman, shoots, the, man] 
; Ws = [the, woman, shoots, a, woman] 
; Ws = [the, woman, shoots, a, man] 
; Ws = [the, woman, shoots] 
; Ws = [the, man, shoots, the, woman] 
; Ws = [the, man, shoots, the, man] 
; Ws = [the, man, shoots, a, woman] 
; Ws = [the, man, shoots, a, man] 
; Ws = [the, man, shoots] 
; Ws = [a, woman, shoots, the, woman] 
; Ws = [a, woman, shoots, the, man] 
; Ws = [a, woman, shoots, a, woman] 
; Ws = [a, woman, shoots, a, man] 
; Ws = [a, woman, shoots] 
; Ws = [a, man, shoots, the, woman] 
; Ws = [a, man, shoots, the, man] 
; Ws = [a, man, shoots, a, woman] 
; Ws = [a, man, shoots, a, man] 
; Ws = [a, man, shoots].     % 20 solutions