usos legítimos de (\ +) // 1

Question

En reglas de la gramática (dcg), hay varias construcciones predefinidas: (',')//2 significado concatenación, ('|')//2 significa alternancia etc. Una construcción que es apoyado por varios pero no todos los sistemas Prolog es (\+)//1.

Personalmente, lo he usado solo por el mero hecho de usarlo. Nunca lo he visto en código escrito por otros.

Entonces, ¿hay usos legítimos de (\+)//1?

Editar: Y, además, hay usos legítimos de (\+)//1 dentro de una consulta phrase(nt, L) con L una variable sin desinstalar.

Answer 1

\ + se puede utilizar para crear gramáticas que son menos ambiguas. ¡La ventaja de usar \ + más! por ejemplo, es una determinada declaratividad de \ +, de modo que, por ejemplo, las reglas DCG resultantes se pueden reordenar.

Vamos a hacer un ejemplo, considere la siguiente gramática:

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

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

La gramática anterior es muy ambigua, por ejemplo consigo múltiples un análisis sintáctico para la siguiente entrada:

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

Supongamos ahora que desea preferir el análisis largo de t sobre el brevemente t. Puedo hacer esto con un corte de la siguiente manera:

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

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

Lamentablemente no puedo reordenar. Dado que hacer lo siguiente no da el resultado deseado. Aunque s (A) produce ahora los resultados en un orden diferente, estamos de vuelta al punto de partida, ya que la gramática es ambigua nuevo:

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

Ahora vamos a intentar lo mismo con \ +. Podemos reemplazar el corte por la siguiente negación:

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

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

Ahora vamos a tratar si podemos reordenar. Nos reordenar las reglas de la gramática de 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 

El declarativity es muy útil. Significa por ejemplo que podemos usar \ + en un analizador sintáctico de derecha a izquierda que elige las reglas gramaticales en un orden arbitrario. La declaratividad asegura que el encadenamiento ascendente del analizador de diagrama produce el mismo resultado independientemente de el orden de entrada de las reglas DCG.

Entonces es posible aplicar la técnica DCG en grandes proyectos de lenguaje natural (NL) y se escala bien. Las gramáticas NL se pueden ajustar empíricamente al determinismo. Cuanto más determinista es una gramática, más eficaz es su análisis sintáctico. Las gramáticas complejas de NL que de lo contrario son intratable, se vuelven factibles.

adiós

Answer 2

Cuando L no se instancia a continuación, la gramática se utiliza para la generación de texto. Entonces no necesita la gramática \ + en absoluto. Ya que no hay más problema de ambigüedad de algún texto.

Vamos a hacer un ejemplo, considere la siguiente gramática:

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

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

Cada análisis sintáctico diferente tiene un árbol de análisis diferente. Y no hay ambigüedad en usando la frase/2 para generar texto. Las siguientes consultas dan exactamente un respuesta:

?- 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] 

Pero hay un pequeño problema reutilización. Supongamos que tengo una gramática NL con \ + para el análisis . Entonces no puedo usarlo para analizar. Dado que el patrón de instanciación del \ + objetivo será diferente, y por lo tanto la semántica del constructo cambia.

La salida es probablemente solo utilizar dos gramáticas. Uno para analizar y otro para sin analizar. Creo que el análisis y el análisis son dos capacidades cognitivas diferentes. Recuerda en la escuela, hubo ejercicios de lectura y ejercicios de escritura. El ocurre lo mismo en informática.

Creo que también se encuentra en algunos casos posibles de utilizar una sola gramática, y la vista \ + como una anotación para la desambiguación, que se deja caer durante unparse o diferente manejado. Uno podría construir tal mecanismo. Pero los problemas con unparsing frente análisis son más profundas: Bidirectionallity de las condiciones auxiliares ({}/1), la recursividad izquierda durante unparsing, etc ...

adiós