Here is a solution that should at least point you to the right direction. It is different, because I have directly defined the terminals, non-terminals and rules as Prolog facts:
nt(a). nt(b).
t(t). t(q). t(y). t(z).
rule(a, [t]).
rule(a, [z]).
rule(b, [y]).
rule(b, [a,q]).
From here, you need a predicate that takes a starting sequence and applies the rules:
gen([], []).
gen([A|As], S) :-
( t(A)
-> S = [A|Ts]
; nt(A)
-> rule(A, Bs),
gen(Bs, Cs),
append(Cs, Ts, S)
),
gen(As, Ts).
If the symbol is a terminal, it belongs to the end sequence. If it is a non-terminal, you apply a rule to it, then apply gen/2
to the result. I assume you know how recursion in Prolog works, the if-else, and what append/3
does.
?- [gen].
% gen compiled 0.00 sec, 13 clauses
true.
?- gen([a,b], S).
S = [t, y] ;
S = [t, t, q] ;
S = [t, z, q] ;
S = [z, y] ;
S = [z, t, q] ;
S = [z, z, q].
To transform this into the predicate you are looking for, consider the following:
A list can be enumerated using member/2
:
?- member(NT, [a,b]).
NT = a ;
NT = b.
You can add facts and rules to the database using assertz/1
:
?- assertz(t(t)), assertz(t(q)). % etc
You could use forall/2
to avoid writing an explicit loop:
?- forall(member(R, Rules), assertz(R)).
You could use member/2
directly on the lists if you want.
I am sure there is another way too.