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

Answer 3

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 4

Answer set programming (ASP) provides another route to implement grammars. ASP can be implemented with non-deterministic forward chaining and this is what our library(minimal/asp) provides. The result of ASP are then different models

of the given rules. We use here ASP models to represent a Cocke-Younger-Kasami chart. We begin our chart with the given words we want to parse which are represented by word/3 facts. Compared to DCG we do not pass around anymore

lists but instead word positions. The Prolog text calc2.p shows such an implementation of an ASP based parser. All rules are now (<=)/2 rules, means they are forward chaining rules. And all heads are now choose/1 heads, means they make a ASP

model choice. We explain how expr is realized, the term is realized similary. Since we do not have an automatic translation, we did the translation manually. We will provide the words from right to left and only trigger at the beginning

of each attributed grammar rule:

choose([expr(C, I, O)]) <= posted(expr(A, I, H)), word('+', H, J), term(B, J, O),  C is A+B.
choose([expr(C, I, O)]) <= posted(expr(A, I, H)), word('-', H, J), term(B, J, O),  C is A-B.
choose([expr(B, I, O)]) <= posted(word('-', I, H)), term(A, H, O), B is -A.
choose([expr(A, I, O)]) <= posted(term(A, I, O)).

As can be seen no extra predicate expr_rest was needed and the translation from grammar to rules was 1-1. The same happens for term. The execution of such a grammar requires that first the words are posted from right to left, and the result can

then be read off from the corresponding non-terminal:

?- post(word(78,7,8)), post(word('+',6,7)), post(word(56,5,6)), post(word('*',4,5)),
    post(word(34,3,4)), post(word('+',2,3)), post(word(12,1,2)), post(word('-',0,1)),
    expr(X,0,8).
X = 1970

We have also made a Prolog text show.p which allows visualizing the ASP model as a parsing chart. We simply use the common triangular matrix representation. The parsing chart for the above arithmetic expression has looks as follows:

Peter Schüller (2018) - Answer Set Programming in Linguistics
https://peterschueller.com//pub/2018/2018-schueller-asp-linguistics.pdf

User Manual - Module "asp"
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/15_min/10_docu/02_reference/07_theory/01_minimal/06_asp.html