Removing left recursion in DCG - Prolog

Question

I've got a small problem with left recursion in this grammar. I'm trying to write it in Prolog, but I don't know how to remove left recursion.

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

I've written something like that, but it won't work at all. How to change it to get this program working?

Answer 1

The problem only arises since you are using backward chaining. In forward chaining it is possible to deal with left recursive grammar rules directly. Provided the grammar rules of the form:

NT ==> NT'

Don't form a cycle. You can also use auxiliary computations, i.e. the {}/1, if you place them after the non-terminals of the body and if the non-terminals in the head don't have parameters exclusively going into the auxiliary computations. i.e. the bottom-up condition.

Here is an example left recursive grammar that works perfectly this way in forward chaining:

:- 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)}.

Here is a link to the source code of the chart parser. From this link the source code of the forward chainer can be also found. In the following an example session is shown:

?- use_module(library(minimal/hypo)).

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

During parsing the chart parser will fill a chart in a bottom up fashion. For each non-terminal p/n in the above productions there will be facts p/n+2. Here is the result of the chart for the above example:

:- 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 2

The answer from @thanosQR is fairly good, but applies to a more general context than DCG, and requires a change in the Parse Tree. Effectively, the 'outcome' of parsing has been removed, that's not good.

If you are interested just in parsing expressions, I posted here something useful.

Answer 3

Many Prolog systems provide tabling. With tabling termination can be also extended to left recursive grammars in many situation. Here is a solution that makes use of the new SWI-Prolog tabling feature:

:- 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)}.

Since this feature is relatively new in SWI-Prolog, it only works for the moment when you switch on the debug mode:

?- debug.

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

Answer 4

The problem with your program is indeed left recursion; it should be removed otherwise you'll get stuck in an infinite loop

To remove immediate left recursion you replace each rule of the form

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

with:

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

so function would be

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

wiki page