Writing context free grammar in a prolog

Question

let's say I had the following free context grammar.

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

What does it look like in the prologue? This is what I tried, but it does not work. The second line seems to be the problem.

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

Answer 1

since the grammar is not left recursive, we can use DCG :

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

then we can parse or generate all the accepted sequences. For example, generating:

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

To check the Prolog code:

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

no need to add / 3 thanks to difference lists

edit using append / 3

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

SWI-Prolog has append / 2 (just based on append / 3 properly docked) that provide a more readable alternative

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

in any case, we must call recursively / 1 after the list has been built / split

Answer 2

In this answer we use the append/3 public predicate.

<Preliminary> s (Xs): - a (X). a ([O]). a ([m | Xs]): - append (Xs0, [n], Xs), and (xs0).

Request example:

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

NOTE: Using append/3 instead of dcg is generally a poor choice and can contribute to both performance degradation and code readability. Use dcg whenever possible !