Reputation: 23
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.)
Upvotes: 2
Views: 779
Reputation:
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.
Upvotes: 0
Reputation: 21384
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).
Upvotes: 1