writing context free grammar in prolog

Question

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

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

How would this look in prolog? This is what I tried but it doesn't work. The second line seems to be the issue.

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

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

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

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

to inspect 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 append/3 required, 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 (simply based on append/3 properly chained), that give a more readable alternative

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

anyway, we must call a/1 recursively after the list has been built/split

Answer 2

In this answer, we use the commonly available predicate append/3.

s(Xs) :-
   a(Xs).

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

Sample query:

?- 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, in general, a bad choice and can contribute to both lower runtime performance and code readability. Whenever possible, use dcg instead!