Geek asks and answers

Removing left recursion in DCG - Prolog

I have a little problem with left recursion in this grammar. I am trying to write it to Prolog, but I do not 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 wrote something like this, but it will not work. How to change it to make this program work?

+5
source share
4 answers

The problem with your program is really left behind by recursion; it needs to be deleted, otherwise you are stuck in an infinite loop

To remove immediate left recursion, you replace each form rule

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

with:

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

therefore the function will be

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

wiki page

+2
source

, . . :

NT ==> NT'

. , .. {}/1, - , - , . .. .

, :

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

. . :

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

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

. p/n p/n + 2. :

:- 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).
+2

@thanosQR , , DCG, . , "" , .

, - .

+1

Prolog . . , 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)}.

SWI-Prolog, , :

?- debug.

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

More articles:


All Articles