Prólogo: Combinación de gramáticas DCG con otras restricciones

Question

Estoy muy impresionado con el DCG de Prolog y con la rapidez con que puedo producir todas las estructuras posibles que se ajustan a una gramática en particular.

Pero me gustaría combinar esta búsqueda con otras limitaciones. Por ejemplo, defina una gramática compleja y pida a Prolog que genere todas las oraciones con no más de 10 palabras. O todas las oraciones que no repiten la misma palabra dos veces.

¿Es posible agregar restricciones adicionales como esta a una gramática DCG? ¿O básicamente tengo que traducir el DCG a las cláusulas de Prolog normales y comenzar a modificarlas?

Answer 1

Si sólo desea ver todas las frases que se generan, que es muy cómodo de usar lo siguiente:

?- length(Xs, N), phrase(mynonterminal, Xs). 

Por supuesto que genera todas las frases. Pero es muy útil y te ahorra tiempo para pensar en un límite concreto. Si desea restringirlo más, agregue el objetivo between(0,10,N) en el frente.

Si quiere decir dentro de una gramática, que cierto no terminal debe tener una cierta longitud, lo mejor es decir explícitamente:

seq([]) --> []. 
seq([E|Es]) --> [E], seq(Es). 

a --> {length(Es,10)}, seq(Es), {phrase(mynonterminal,Es)}. 

Si aún no está satisfecho, entonces usted quiere para expresar la intersección de dos no terminales. Esto es equivalente a pedir la intersección de dos lenguajes libres de contexto que, en el caso general, es indecidible. Pero mucho antes, tendrá problemas con la terminación. Así que ser conscientes de que, en lo que sigue:

^(V0, Goal, V0, V) :- 
     call(Goal,V). 

^(V, Goal, V) :- 
    call(Goal). 

lo que este le permite ahora a expresar la intersección de dos no terminales:

:- op(950, xfx, &). 

(NT1 & NT2) --> 
    call(Xs0^Xs^(phrase(NT1,Xs0,Xs),phrase(NT2,Xs0,Xs))). 

El único que se necesita si no se utiliza library(lambda) siguiente. Pero, por favor, tenga en cuenta que la terminación es muy frágil aquí. En particular, la terminación del primer no terminal no necesariamente limita el segundo.

Answer 2

así, siempre se puede utilizar {} y escribir cualquier tipo de predicado prólogo en el medio, por ejemplo:

foo(X)--> 
    { valid(X) }, 
    [a]. 
foo(X)--> 
    [b]. 

por lo que podría añadir algún tipo de contador de palabras. por supuesto, si cada token es una palabra, simplemente podría escribir algo como: length (L, N), N < 11, start (L, []).

Por otro lado, quizás sea mejor, dependiendo de la complejidad de las restricciones, codificarlas en una parte diferente. algo así como analizador semántico analizador en compiladores.