Entfernen der linken Rekursion in DCG - Prolog

Question

Ich habe ein kleines Problem mit der linken Rekursion in dieser Grammatik. Ich versuche es in Prolog zu schreiben, aber ich weiß nicht, wie ich die linke Rekursion entfernen kann.

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

Ich habe so etwas geschrieben, aber es wird überhaupt nicht funktionieren. Wie kann ich es ändern, damit dieses Programm funktioniert?

Answer 1

Das Problem mit Ihrem Programm ist in der Tat links Rekursion; es sollte anders entfernt werden Sie in einer Endlosschleife stecken werden

sofort Linksrekursion So entfernen Sie jede Regel der

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

mit:

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

so Funktion wäre

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

wiki page

Answer 2

Die Antwort von @thanosQR ist ziemlich gut, gilt aber für einen allgemeineren Kontext als DCG und erfordert eine Änderung im Parse Tree. Effektiv wurde das "Ergebnis" der Analyse entfernt, das ist nicht gut.

Wenn Sie interessiert sind nur in Parsing Ausdrücke, ich postete here etwas nützliches.

Answer 3

Das Problem tritt nur auf, da Sie die Rückwärtsverkettung verwenden. Bei der Vorwärtsverkettung ist es möglich, direkt mit links rekursiven Grammatikregeln umzugehen. Vorausgesetzt, die Grammatikregeln des Formulars:

NT ==> NT' 

Bilden Sie keinen Zyklus. Sie können auch Hilfsberechnungen verwenden, d. H. Die {}/1, wenn Sie sie nach den Nicht-Terminals des Körpers platzieren und wenn die Nicht-Terminals im Kopf keine Parameter haben, die ausschließlich in die Hilfsberechnungen gehen. d.h. der Bottom-Up-Zustand.

Hier ist ein Beispiel rekursive Grammatik links, die perfekt auf diese Weise in Vorwärtsverkettungs funktioniert:

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

Hier ist eine link auf den Quellcode des Diagramms Parser. Von diesem Link kann auch der Quellcode des Forward Chainers gefunden werden. Im folgende Beispiel Sitzung wird angezeigt:

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

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

Während der Diagramm-Parser Parsing wird ein Diagramm in einer Bottom-up-Mode füllen. Für jedes nicht-terminale p/n in den obigen Produktionen gibt es die Fakten p/n + 2. Hier ist das Ergebnis des Diagramms für das obige Beispiel:

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

Viele Prolog Systeme bieten Tabling. Mit Tabling Termination kann in vielen Situationen auch zu linken rekursiven Grammatiken erweitert werden.Hier ist eine Lösung, die Verwendung des neuen SWI-Prolog Einreichungs Funktion macht:

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

Seit dieser feature ist relativ neu in SWI-Prolog, ist es nur Arbeiten für den Moment, wenn Sie auf den Debug-Modus wechseln:

?- debug. 

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