resueltos - prolog ejemplos sencillos

Eliminar la recursividad izquierda en DCG-Prolog

Question

Tengo un pequeño problema con la recursividad izquierda en esta gramática. Intento escribirlo en Prolog, pero no sé cómo eliminar la recursividad a la izquierda.

<expression> -> <simple_expression>
<simple_expression> -> <simple_expression> <binary_operator> <simple_expression>
<simple_expression> -> <function>
<function> -> <function> <atom>
<function> -> <atom>
<atom> -> <number> | <variable>
<binary_operator> -> + | - | * | /
expression(Expr) --> simple_expression(SExpr), { Expr = SExpr }.
simple_expression(SExpr) --> simple_expression(SExpr1), binary_operator(Op), simple_expression(SExpr2), { SExpr =.. [Op, SExpr1, SExpr2] }.
simple_expression(SExpr) --> function(Func), { SExpr = Func }.
function(Func) --> function(Func2), atom(At), { Func = [Func2, atom(At)] }.
function(Func) --> atom(At), { Func = At }.

He escrito algo así, pero no funcionará en absoluto. ¿Cómo cambiarlo para que este programa funcione?

Answer 1

El problema con tu programa es, de hecho, la recursividad; debería eliminarse, de lo contrario te quedarás atrapado en un ciclo infinito

Para eliminar la recursividad inmediata a la izquierda, reemplace cada regla del formulario

A->A a1|A a2|....|b1|b2|....

con:

A -> b1 A''|b2 A''|....
A'' -> ε | a1 A''| a2 A''|....

por lo que la función sería

function -> atom, functionR.
funtionR -> [].

página wiki

Answer 2

El problema solo surge porque estás usando un encadenamiento hacia atrás. En el encadenamiento hacia adelante, es posible tratar directamente con las reglas gramaticales recursivas de la izquierda. Siempre que las reglas gramaticales de la forma:

NT ==> NT''

No formes un ciclo. También puede usar cómputos auxiliares, es decir, {}/1 , si los coloca después de los no terminales del cuerpo y si los no terminales en el cabezal no tienen parámetros que entren exclusivamente en los cálculos auxiliares. es decir, la condición de abajo hacia arriba.

Aquí hay un ejemplo de gramática recursiva que funciona perfectamente de esta manera en el encadenamiento directo:

:- use_module(library(minimal/chart)).
:- use_module(library(experiment/ref)).
:- static ''D''/3.
expr(C) ==> expr(A), [+], term(B), {C is A+B}.
expr(C) ==> expr(A), [-], term(B), {C is A-B}.
expr(A) ==> term(A).
term(C) ==> term(A), [*], factor(B), {C is A*B}.
term(C) ==> term(A), [/], factor(B), {C is A/B}.
term(A) ==> factor(A).
factor(A) ==> [A], {integer(A)}.

Aquí hay un enlace al código fuente del analizador de gráficos. Desde este enlace también se puede encontrar el código fuente del chainer delantero. A continuación, se muestra una sesión de ejemplo:

?- use_module(library(minimal/hypo)).
?- chart([1,+,2,*,3], N) => chart(expr(X), N).
X = 7

Durante el análisis, el analizador de gráficos completará un gráfico de abajo hacia arriba. Para cada p / n no terminal en las producciones anteriores, habrá hechos p / n + 2. Aquí está el resultado de la tabla para el ejemplo anterior:

:- thread_local factor/3.
factor(3, 4, 5).
factor(2, 2, 3).
factor(1, 0, 1).
:- thread_local term/3.
term(3, 4, 5).
term(2, 2, 3).
term(6, 2, 5).
term(1, 0, 1).
:- thread_local expr/3.
expr(3, 4, 5).
expr(2, 2, 3).
expr(6, 2, 5).
expr(1, 0, 1).
expr(3, 0, 3).
expr(7, 0, 5).

Answer 3

Muchos sistemas Prolog proporcionan presentación. Con la terminación de la presentación también se puede extender a las gramáticas recursivas a la izquierda en muchas situaciones. Aquí hay una solución que hace uso de la nueva función de presentación de SWI-Prolog:

:- use_module(library(tabling)).
:- table expr/3.
:- table term/3.
:- table factor/3.
expr(C) --> expr(A), [+], term(B), {C is A+B}.
expr(C) --> expr(A), [-], term(B), {C is A-B}.
expr(A) --> term(A).
term(C) --> term(A), [*], factor(B), {C is A*B}.
term(C) --> term(A), [/], factor(B), {C is A/B}.
term(A) --> factor(A).
factor(A) --> [A], {integer(A)}.

Como esta característica es relativamente nueva en SWI-Prolog, solo funciona en el momento en que enciende el modo de depuración:

?- debug.
?- phrase(expr(X), [1,+,2,*,3], []).
X = 7

Answer 4

La respuesta de @thanosQR es bastante buena, pero se aplica a un contexto más general que DCG, y requiere un cambio en el árbol de análisis. Efectivamente, el ''resultado'' del análisis ha sido eliminado, eso no es bueno.

Si estás interesado solo en analizar expresiones , publiqué aquí algo útil.