grammatica free context in prolog

Question

diciamo che ho avuto la seguente grammatica free context.

S -> A 
A -> mAn 
A -> o 

Come apparire in prolog? Questo è quello che ho provato ma non funziona. La seconda linea sembra essere il problema.

S(Z) :- A(Z). 
A(Z) :- append([m],X,Z2), A(X), append(Z2,[n],Z). 
A([o]). 

Answer 1

poiché la grammatica non è lasciato ricorsiva, possiamo usare una DCG:

s --> a. 
a --> [m], a, [n]. 
a --> [o]. 

allora possiamo analizzare o di generare tutte le sequenze accettati. Ad esempio, generare:

?- length(L, _), phrase(s, L). 
L = [o] 
L = [m, o, n] 
L = [m, m, o, n, n] 
... 

per ispezionare il codice Prolog:

?- listing(s). 
s(A, B) :- 
    a(A, B). 

?- listing(a). 
a([m|A], C) :- 
    a(A, B), 
    B=[n|C]. 
a([o|A], A). 

senza accodamento/3 richiesto, grazie alla differenza elenca

modifica utilizzando aggiungere/3

s(Z) :- a(Z). 
a(Z) :- append([m|X],[n],Z), a(X). 
a([o]). 

SWI-Prolog ha append/2 (basato semplicemente sull'app end/3 correttamente incatenato), che danno un più leggibile alternativa

a(Z) :- append([[m],X,[n]], Z), a(X). 

in ogni caso, dobbiamo chiamare un/1 ricorsivamente dopo l'elenco è stato costruito/split

Answer 2

In questa risposta, usiamo il predicato comunemente disponibile append/3.

 
s(Xs) :- 
    a(Xs). 

a([o]). 
a([m|Xs]) :- 
    append (Xs0,[n],Xs), 
    a(Xs0). 

interrogazione Esempio:

 
?- length (Xs,_), s(Xs). 
    Xs = [o] 
; Xs = [m,o,n] 
; Xs = [m,m,o,n,n] 
; Xs = [m,m,m,o,n,n,n] 
... 

NOTA: Utilizzando append/3 invece di dcg è, in generale, una cattiva scelta e può contribuire sia le prestazioni di esecuzione più basso e la leggibilità del codice. Quando possibile, usa invece dcg!