I want to write gen(G,S) in Prolog to generate a valid sequence S for a given grammar G, where G is of the format grammar([list of nonterminals], [list of terminals], [list of rules], [starting sequence]). The rules are in the format rule(nt,[x]) where x can be any list of nonterminals and/or terminals.
e.g. gen(grammar([a,b], [t,q,y,z], [rule(a,[t]), rule(a,[z]), rule(b,[y]), rule(b,[a,q])], [a,b]), X).
Returns: X = [t,y]. X = [t,t,q]. X = [t,z,q]. X = [z,y]. X = [z,t,q]. X = [z,z,q].
With all the info out there on CFG for Prolog (been trying for 2 days), I s/b able to figure out at least 1 way to do this, either using the built-in --> and phrase/2 or from scratch, but no luck. (Never posted on SO b4 & I'm a beginner, so my apologies if this Q is inappropriate.)
There is no need to resort to special, non-logical predicates. This does the trick:
gen(grammar(_NTE, _TE, _Rules, []), []).
gen(grammar(NTE, TE, Rules, [H|T]), X) :-
member(H, NTE),
member(rule(H, Res), Rules),
append(Res, T, NewT),
gen(grammar(NTE, TE, Rules, NewT), X).
gen(grammar(NTE, TE, Rules, [H|T]), [H|X2]) :-
member(H, TE),
gen(grammar(NTE, TE, Rules, T), X2).