Rimozione della ricorsione sinistra in DCG - Prolog

Question

Ho riscontrato un piccolo problema con la ricorsione sinistra in questa grammatica. Sto provando a scriverlo in Prolog, ma non so come rimuovere la ricorsione a sinistra.

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

Ho scritto qualcosa del genere, ma non funzionerà affatto. Come cambiarlo per far funzionare questo programma?

Answer 1

Il problema con il programma è in effetti ricorsione; dovrebbe essere rimosso altrimenti si rimane bloccati in un ciclo infinito

Per rimuovere la ricorsione subito a sinistra si sostituisce ogni regola della forma

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

con:

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

così la funzione sarebbe

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

wiki page

Answer 2

La risposta da @thanosQR è abbastanza buona, ma si applica a un contesto più generale rispetto a DCG e richiede una modifica nel Parse Tree. In effetti, il "risultato" del parsing è stato rimosso, non va bene.

Se ti interessa solo analizzare le espressioni , ho inviato qualcosa di utile su here.

Answer 3

Il problema sorge solo dal momento che si utilizza il concatenamento all'indietro. Nel concatenamento in avanti è possibile gestire direttamente le regole grammaticali ricorsive. Fornite le regole grammaticali del modulo:

NT ==> NT' 

Non formare un ciclo. È anche possibile utilizzare calcoli ausiliari, ad esempio {}/1, se li si posiziona dopo i non-terminali del corpo e se i non-terminali nella testa non hanno parametri che vanno esclusivamente nei calcoli ausiliari. cioè la condizione dal basso verso l'alto.

Ecco un esempio sinistra grammatica ricorsiva che funziona perfettamente in questo modo in concatenamento avanti:

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

Ecco un link al codice sorgente del parser tabella. Da questo link si trova anche il codice sorgente della forward chainer. Nel seguente esempio una sessione viene mostrato:

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

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

Durante l'analisi del parser tabella riempirà un grafico in un bottom up moda. Per ogni p/n non-terminale nelle produzioni di cui sopra ci saranno fatti p/n + 2. Ecco il risultato del grafico per l'esempio precedente:

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

Molti sistemi Prolog forniscono tabling. Con la terminazione di tabulazione, può essere esteso anche a grammatiche ricorsive lasciate in molte situazioni. Ecco una soluzione che fa uso della nuova funzionalità di presentazione 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)}. 

Dal momento che questo feature è relativamente nuovo nel SWI-Prolog, è solo lavori per il momento in cui si attiva la modalità di debug:

?- debug. 

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