Definite Clause Grammar (DCG)

Algo fácil de hacer en Prolog es escribir ``parsers''. De hecho Prolog fué usado inicialmente para procesamiento de lenguaje natural. Prolog tiene la facilidad de traducir directamente sus cláusulas de Horn en DCGs.

DCG son una extensión de CFG:

• Un símbolo no terminal o terminal puede ser cualquier predicado de Prolog
• Se pueden incluir condiciones extras del lado derecho
• Permite tener ``;'' y ``!''

Ejemplo de CFG (solo 1 símbolo del lado izq.)

oracion --> sujeto, predicado.
sujeto --> articulo, sustantivo.
predicado --> verbo, sujeto.
predicado --> verbo.
articulo --> [el].
articulo --> [la].
sustantivo --> [manzana].
sustantivo --> [hombre].
verbo --> [come]

La primera regla dice que una oración está compuesta por un sujeto seguida de un predicado.

En Prolog podríamos ``parsear'' una oración, donde los símbolos terminales simplemente tienen lo que aceptan y los demás símbolos son listas con frases que aceptan. Una forma simple (pero ineficiente) de hacerlo es:

oracion(Lista) :-
     sujeto(Suj),
     predicado(Pred),
     append(Suj,Pred,Lista).

sujeto(Suj) :-
     articulo(Art),
     sustantivo(Sust),
     append(Art,Sust,Suj).

articulo([el]).
articulo([la]).

Esto se puede mejorar, eliminando el ``append'' si cada parte de la oración nos dice cuanto ocupa:

?- oracion([el,hombre,come,la,manzana],[]).

oracion(L1,L3)) :- sujeto(L1,L2), predicado(L2,L3).
sujeto(L1,L3) :- articulo(L1,L2), sustantivo(L2,L3).
predicado(L1,L3) :- verbo(L1,L2), sujeto(L2,L3).
predicado(L1,L2) :- verbo(L1,L2).
articulo([el|T],T).
articulo([la|T],T).
sustantivo([hombre|T],T).
sustantivo([manzana|T],T).
verbo([come|T],T).

Hay que notar que lo mismo se puede representar (casi igual) como diferencia de listas, i.e., oracion(L1-L3) :- ...

Prolog tiene una forma de traducir la representación de arriba en notación de CFG + le dá facilidad de incluir argumentos y llamar a predicados de Prolog. Esto es, nosotros especificamos como un CFG y se traduce al código de arriba. Para hacer preguntas hay que recordar que se hizo la traducción, i.e.:
?- oracion([el,hombre,come,la,manzana],[]).

Algunos Prolog (no todos) tienen ``phrase'':

?- phrase(oracion,[el,hombre,come,la,manzana]).
?- phrase(sujeto,[la,manzana]).

En la notación, se permiten incluir llamados entre corchetes. También podemos añadir más argumentos. Por ejemplo, si queremos guardar el árbol que genera el ``parser'', podemos poner:

oracion(oracion(S,P)) --> sujeto(S) predicado(P).
sujeto(suj(A,S)) --> articulo(A), sustantivo(S).
predicado(pred(V,S)) --> verbo(V), sujeto(S).
predicado(pred(V)) --> verbo(V).
articulo(art(el)) --> [el].
...

?- oracion(Arbol,[el,hombre,come,la,manzana],[]).
Arbol = oracion(suj(art(el),
                    sust(hombre)),
                pred(verb(come),
                     suj(art(la),
                         sust(manzana)))).

Algo común es checar por género y número:

oracion --> sujeto(Num), predicado(Num).
sujeto(N) --> articulo(Num,Gen), sustantivo(Num,Gen).
predicado(Num) --> verbo(Num), sujeto(_).
articulo(sing,fem)      -->     [la].
articulo(sing,masc)     -->     [el].
articulo(plural,fem)    -->     [las].
articulo(plural,masc)   -->     [los].
verbo(sing)             -->     [come].
verbo(plural)           -->     [comen].
sustantivo(sing,masc)   -->     [hombre].
sustantivo(sing,fem)    -->     [manzana].

Para ``parsear'' una expresión matemática y regresar su resultado:

expr(Z) --> term(X), ``+'', expr(Y), {Z is X + Y}.
expr(Z) --> term(X), ``-'', expr(Y), {Z is X - Y}.
expr(Z) --> term(X).

term(Z) --> numero(X), ``*'', term(Y), {Z is X * Y}.
term(Z) --> numero(X), ``/'', term(Y), {Z is X / Y}.
term(Z) --> numero(Z).

numero(N) --> ``+'', numero(N).
numero(N) --> ``-'', numero(M), {N is - M}.
numero(N) --> [X], {48 =< X, X =< 57, N is X - 48}.

Alternativamente, se puede poner la expresion en un lista, todos los que están entre doble comillas, cambian a elementos en listas, e.g., ``+'' =$>$ [+], y la última de número cambia:
numero(N) --> [N], {member(N,[0,1,2,3,4,5,6,7,8,9])}.

Con DCG podemos hacer más que con CFG (e.g., $a^{n}b^{n}c^{n}$)

s --> [a], s(i).
s(I) --> [a], s(i(I)).
s(I) --> nb(I), nc(I).

nb(i(I)) --> [b], nb(I).
nb(i) --> [b].

nc(i(I)) --> [c], nc(I).
nc(i) --> [c].