Removing left recursion grammar using DCG

Question

The following Grammar has left-recursion

Grammar :

Expr ::= E1|E2|E3|E4|E5|E6|E7

E1 ::= "(" Expr ")"
E2 ::= "not""(" Expr ")"
E3 ::= Expr "=>" Expr
E4 ::= Expr "=/=" Expr
E5 ::= Expr "*" Expr
E6 ::= Func "=>" Func
Func ::= Ter  (Ters)+","
...

and I'm trying to remove the LR in this manner ;

Expr ::= E1|...

E1 ::= Expr "*" Expr ==>   E1   ::= Expr Expr'
                           Expr'::= *Expr Expr'

but the problem still exists, How to fix it to get this program working?

example query and test

| ?- phrase(e(T),"not((2+3)=/=5))").
! Resource error: insufficient memory

expected answer

 | ?- phrase(e(T),"not((2+3)=/=5))").
    error 13 ')'
 | ?- phrase(e(T),"(2+3)=>>5))").
    error 7 '>'

Please always include a usable example query, the system's current answer, and the expected answer. — mat
I've coded the @false suggestion (see this), as a DCG extension, via term_expansion, but I'm using SWi-Prolog. Are you interested in alpha testing it in SICSTUS Prolog ? — CapelliC
forget it, in SICSTUS the interface dcg_translate_rule/2 is missing... — CapelliC

CapelliC CapelliC · Accepted Answer · 2016-02-19T22:29:50

You could try to bottom parse bottom up.

This is the processor:

:- op(150, xfx, ---> ).

parse(Phrase) -->
    leaf(SubPhrase),
    lc(SubPhrase, Phrase).

leaf(Cat) --> [Word], {word(Word,Cat)}.
leaf(Phrase) --> {Phrase ---> []}.

lc(Phrase, Phrase) --> [].

lc(SubPhrase, SuperPhrase) -->
    {Phrase ---> [SubPhrase|Rest]},
    parse_rest(Rest),
    lc(Phrase, SuperPhrase).

parse_rest([]) --> [].
parse_rest([Phrase|Phrases]) -->
    parse(Phrase),
    parse_rest(Phrases).

An example of grammar specification (but func seems ill specified, and there is no precedence or associativity specification...)

expr(E) ---> [opp, expr(E), clp].
expr(not(E)) ---> [not, opp, expr(E), clp].
expr(impl(L,R)) ---> [expr(L), impl, expr(R)].
expr(ne(L,R)) ---> [expr(L), ne, expr(R)].
expr(mul(L,R)) ---> [expr(L), mul, expr(R)].
expr(add(L,R)) ---> [expr(L), add, expr(R)].
expr(func(L,R)) ---> [func(L), impl, func(R)].
expr(num(N)) ---> [num(N)].

func(f(F, As)) ---> [name(F), args(As)].

args([A|As]) ---> [arg(A), comma, args(As)].
args([A]) ---> [arg(A)].
arg(E) ---> [expr(E)].


word(N, name(N)) :- atom(N).
word(N, num(N)) :- integer(N).
word(=>, impl).
word('(', opp).
word(')', clp).
word(*, mul).
word(+, add).
word(not, not).
word(=/=, ne).
word(',', comma).

an example run

?- phrase(parse(E), [not,'(',2,+,2,*,3,')']).
E = func(f(not, [mul(add(num(2), num(2)), num(3))])) ;
E = func(f(not, [add(num(2), mul(num(2), num(3)))])) ;
E = expr(not(mul(add(num(2), num(2)), num(3)))) ;
E = arg(not(mul(add(num(2), num(2)), num(3)))) ;
E = args([not(mul(add(num(2), num(2)), num(3)))]) ;
E = expr(not(add(num(2), mul(num(2), num(3))))) ;
E = arg(not(add(num(2), mul(num(2), num(3))))) ;
E = args([not(add(num(2), mul(num(2), num(3))))]) ;
false.

but maybe this is no so useful for your task...

Removing left recursion grammar using DCG

2 Answers