2012-10-06 10 views
8

Nelle regole grammaticali (), ci sono diversi costrutti predefiniti: (',')//2 significato concatenazione, ('|')//2 significato alternanza ecc Un costrutto che è supportato da più ma non tutti i sistemi Prolog è (\+)//1.usi legittimi ( +) // 1

Personalmente, ho usato solo per il bene di usarlo. Non l'ho mai visto in codice scritto da altri.

Quindi, ci sono legittimi usi di (\+)//1?

Edit: E inoltre, ci sono usi legittimi delle (\+)//1 all'interno di una query phrase(nt, L) con L una variabile non istanziato.

risposta

4

\ + può essere utilizzato per creare grammatiche che sono meno ambigue. Il vantaggio dell'uso di \ + over! ad esempio, c'è una certa dichiaratività di \ +, così che per esempio le regole DCG risultanti possono essere riordinate.

Lascia per fare un esempio, si consideri la seguente grammatica:

s([X|Y]) --> t(X), s(Y).    % 1 
s([]) --> [].      % 2 

t(2)  --> [a,a].     % 3 
t(1)  --> [a].      % 4 

La grammatica di cui sopra è molto ambiguo, per esempio ho multipla analizza per il seguente testo:

?- phrase(s(A),[a,a,a,a,a]). 
A = [2,2,1] ; 
A = [2,1,2] ; 
A = [2,1,1,1] ; 
etc.. 

Ora assumo io voglio preferire la lunga analisi di t sopra l'analisi breve di di t. Posso fare questo con un taglio come segue:

t(2)  --> [a,a], !.     % 5 
t(1)  --> [a].      % 6 

?- phrase(s(A),[a,a,a,a,a]). 
A = [2,2,1] ; 
No 

purtroppo non posso riordinare. Poiché il seguente non fornisce il risultato desiderato. Anche se s (A) ora produce i risultati in un ordine diverso, siamo di nuovo al punto di partenza, dal momento che la grammatica è ancora ambiguo:

t(1)  --> [a].      % 7 
t(2)  --> [a,a], !.     % 8 

?- phrase(s(A),[a,a,a,a,a]). 
A = [1,1,1,1,1] ; 
A = [1,1,1,2] ; 
A = [1,1,2,1] ; 
etc... 

Ora proviamo lo stesso con \ +. Siamo in grado di sostituire il taglio dal seguente negazione:

t(2)  --> [a,a].     % 9 
t(1)  --> [a], \+ [a].    % 10 

?- phrase(s(A),[a,a,a,a,a]). 
A = [2,2,1] ; 
No 

Ora proviamo se siamo in grado di riordinare. Abbiamo riordinare le regole grammaticali di t // 1:

t(1)  --> [a], \+ [a].    % 11 
t(2)  --> [a,a].     % 12 

?- phrase(s(A),[a,a,a,a,a]). 
A = [2,2,1] ; 
No 

Il dichiaratività è molto utile. Significa, ad esempio, che possiamo usare \ + in un parser grafico da destra a sinistra che lo preleva le regole grammaticali in un ordine arbitrario. Il dichiaratività assicura che basso verso l'alto in avanti concatenamento del parser grafico produce lo stesso risultato indipendentemente dell'ordine ingresso delle regole DCG.

È quindi possibile applicare la tecnica DCG nei grandi progetti di linguaggio naturale (NL) e si adatta bene. Le grammatiche NL possono essere sintonizzate empiricamente nel determinismo. Più una grammatica è deterministica, più efficiente è la sua analisi . Le grammatiche complesse di NL che altrimenti sarebbero incomplete diventano fattibili.

Bye

+0

+1, ma io sono * molto * scettico sulla tua affermazione di dichiaratività: 'frase (s ([1]), [a]).' succede, ma 'frase (s ([1]), L)' fallisce. Esattamente quel tipo di impurità è ciò che mi dà fastidio. – false

+0

Cioè: come si traccia la linea tra usi legittimi e non legittimi? – false

+0

Non rivendico la dichiaratività generale. Ho scritto "certa dichiaratività". È possibile stabilire la dichiaratività contro un adorment (= gergo di database per la dichiarazione della modalità Prolog). Le tecniche possono essere applicate anche a grammatiche. Vedi anche: ftp://ftp.inf.ethz.ch/doc/tech-reports/1xx/177.pdf –

1

Quando L non viene creata un'istanza quindi la grammatica viene utilizzato per la generazione di testo. Quindi non hai affatto bisogno della grammatica \ +. Dal momento che non c'è più alcun problema di ambiguità da un testo.

Lascia per fare un esempio, si consideri la seguente grammatica:

s([X|Y]) --> t(X), s(Y).    % 1 
s([]) --> [].      % 2 

t(2)  --> [a,a].     % 3 
t(1)  --> [a].      % 4 

Ogni parse diversa ha un albero sintattico diverso. E non c'è alcuna ambiguità in usando phrase/2 per generare testo. Le seguenti query danno esattamente un risposta:

?- phrase(s([2,1]),L). 
L = [a,a,a] 
?- phrase(s([1,2]),L). 
L = [a,a,a] 
?- phrase(s([1,1,1]),L). 
L = [a,a,a] 

ma c'è un piccolo problema riutilizzo. Supponiamo di avere una grammatica NL con \ + per l'analisi . Quindi non posso usarlo per unpare. Poiché il modello di istanziazione dell'obiettivo \ + sarà diverso e pertanto la semantica del costrutto cambia.

L'uscita è probabilmente solo per utilizzare due grammatiche. Uno per l'analisi e uno per il non analizzabile. Immagino che l'analisi e il non analizzamento siano due diverse capacità cognitive. Ricordate a scuola, c'erano esercizi di lettura e esercizi di scrittura. Lo stesso avviene in informatica.

penso che sia anche, in alcuni casi possibili di utilizzare un unico grammatica e vista \ + come un'annotazione per chiarimento delle ambiguità, che è caduto durante la deanalisi o diversamente maneggiato. Si potrebbe costruire un meccanismo del genere. Ma i problemi con Unparsing contro analisi sono più profonde: Bidirectionallity delle condizioni di ausiliari ({}/1), la ricorsione sinistra durante Unparsing, ecc ...

Bye

+0

Ancora una volta una tecnologia di database deduttivo può aiutare qui. Stabilire l'adorazione bidirezionale (= gergo database per la dichiarazione in modalità Prolog) è un primo passo. Ma questo non è più il normale Prolog. –