Schreiben Kontext freie Grammatik in Prolog

Question

Lassen Sie uns sagen, ich hatte den folgenden Kontext kostenlose Grammatik.

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

Wie sieht das im Prolog aus? Das habe ich ausprobiert, aber es funktioniert nicht. Die zweite Zeile scheint das Problem zu sein.

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

Answer 1

da die Grammatik nicht linksrekursiv wird, können wir eine DCG verwenden:

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

dann können wir alle akzeptierten Sequenzen analysieren oder erzeugen. Zum Beispiel Erzeugungs:

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

den Prolog-Code zu inspizieren:

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

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

keine append/3 erforderlich, dank Differenz listet

bearbeiten anhängen mit/3

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

SWI-Prolog hat append/2 (einfach basierend auf App Ende/3 richtig verkettet), die eine besser lesbare Alternative

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

sowieso geben, müssen wir eine/1 rekursiv nach rufen die Liste/split

Answer 2

In dieser Antwort wurde gebaut, die wir verwenden das allgemein verfügbare Prädikat append/3.

 
s(Xs) :- 
    a(Xs). 

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

Beispielabfrage:

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

HINWEIS:append/3 statt dcg Verwendung ist in der Regel eine schlechte Wahl und kann sowohl auf eine geringere Laufzeit-Performance und die Lesbarkeit des Codes beitragen. Wenn möglich, verwenden Sie stattdessen dcg!