interfaz - ¿Cómo puedo crear este DCG en Prolog?

interfaz grafica en prolog

Question

Quiero crear un DCG para que se acepten idiomas como este:

• do
• bbbcbbb
• bbacbba
• abacaba
• aababacaababa

Como puede ver, esto significa que hay un orden específico de ayb, luego uno c y luego el mismo orden exacto que antes de la c. Si no se cumplen estas condiciones, fallará.

Actualmente estoy aquí con mi enfoque (funciona, pero también reconoce palabras equivocadas)

s --> x, s, x. 
s --> [c]. 
x --> [a]. 
x --> [b]. 

¿Puede alguien de ti ayudarme con lo que necesito cambiar? No sé cómo continuar. Muchas gracias.

Answer 1

El idioma que describes no es regular ni libre de contexto. Por lo tanto, debe recurrir a las extensiones de Prolog que se ofrecen en los DCG. Hay algunos modismos a los que te puedes acostumbrar:

% any sequence

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

Con este terminal no terminal, podríamos describir una secuencia que se repite y se separa por un carácter:

rep(Seq, Sep) --> 
   seq(Seq),
   [Sep],
   seq(Seq).

Eso es claramente demasiado general. Solo querías ab y c . Ahora puede agregar requisitos adicionales:

rep(Seq, Sep) -->
   seq(Seq),
   {phrase(abs,Seq)},
   [Sep],
   seq(Seq).

 abs --> [] | ("a"|"b"), abs.

Y ahora:

 s -->
     rep(_,c).

La alternativa es "codificar" la gramática, como ha demostrado @CapelliC. El uso de la seq//1 hace que el enfoque sea un poco más flexible.

Es bastante conveniente usar comillas dobles para la lista de caracteres. Vea esta respuesta sobre cómo permitir el uso de comillas dobles para representar una lista de caracteres.

Answer 2

Un DCG es realmente solo un programa Prolog, preprocesado que agrega argumentos ocultos que implementan una lista de diferencias. Siempre podemos agregar nuestros propios parámetros y usar la coincidencia de patrones. Entonces

s --> ab(X), [c], ab(X). 
ab([a|T]) --> [a], ab(T).
ab([b|T]) --> [b], ab(T).
ab([]) --> [].

?- atom_chars(aababacaababa,Cs),phrase(s, Cs).
Cs = [a, a, b, a, b, a, c, a, a|...]