Reputation: 145
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]).
Upvotes: 5
Views: 1022
Reputation: 18726
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!
Upvotes: 3
Reputation: 60034
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
Upvotes: 4