% -*- prolog -*-

%%% string in lang = list of symbols

%%% language of balanced parens

%%% E ::= '(' Elist ')'
%%% Elist ::= E Elist | ''

e(['(' | X]) :- append(Y, [')'], X), elist(Y).
elist([]).
elist(X) :- append(Y, Z, X), e(Y), elist(Z).

%%% F ::= '(' Flist
%%% Flist ::= F* ')'            <--- Not this ...
%%% Flist ::= ')' | F Flist     <--- instead, this!

f(['('|X]) :- flist(X).
flist([')']).
flist(X) :- append(W, Z, X), f(W), flist(Z).

%%% actually count the parens

%%% g(S, N) means S has N open parens that need to be closed.
%%% Eg g([')'], 1).    g([')', '(', ')' ')'], 2).

g(S) :- g(S, 0).

g([], 0).
g([')'|S], N) :- N>0, M is N-1, g(S, M).
g(['('|S], N) :-      M is N+1, g(S, M).

%%% English!

%%% SENT ::= NP VP
%%% NP ::= ADJ* N                  better...   NP ::= N | ADJ NP
%%% VP ::= V ADV*
%%% N ::= joe | box | cat | dog | ...
%%% V ::= ran | sat | jumped | ate | ...
%%% ADJ ::= red | fast | sly | ...
%%% ADV ::= quickly | ...

sent(SENT) :- append(NP, VP, SENT), np(NP), vp(VP).

np([N]) :- n(N).
np([ADJ|NP]) :- adj(ADJ), np(NP).

np([the,left]).
np([A,N]) :- article(A), n(N).

article(A) :- member(A, [the,a]).

vp([V|ADVlist]) :- v(V), advlist(ADVlist).

advlist([]).
advlist([ADV|ADVlist]) :- adv(ADV), advlist(ADVlist).

n(N) :- member(N, [joe,box,cat,dog]).
v(V) :- member(V, [ran,sat,jumped,ate]).
adj(ADJ) :- member(ADJ, [red,fast,sly]).
adv(ADV) :- member(ADV, [quickly, slowly, brutishly, lovingly]).

%%% Equality

%%% X=X    is syntax for equal(X,X), where equal/2 is defined by:
%%% equal(X,X).

sent(SENT,ST) :- append(NP, VP, SENT), np(NP), vp(VP), ST=sent(NP,VP).