:- op(1200,xfx,'--->').
:- op(300, xfx, fills).
:- op(300, xf, island).


parse(NT, S) :- parse(NT, X-X, S, []).

parse(NT, F0-F) --> 
    {NT ---> Body}, 
    parse(Body, F0-F).

parse(GapType, [GapType|F0]-F0) -->
    {gap(GapType) ---> Body}, 
    parse(Body, F0-F0).

parse(NT island, F0-F0) --> 
    parse(NT, F0-F0).

parse((Body1,Body2),F0-F) --> 
    parse(Body1,F0-F1), 
    parse(Body2,F1-F).

parse((NT fills GapType,Body2), F0-F) --> 
    parse(NT,F0-F0), 
    parse(Body2,[GapType|F0]-F).

parse([], F0-F0) --> [].
parse([Word|Rest], F0-F) --> 
    [Word], 
    parse(Rest, F0-F).

parse({Goals}, F0-F0) --> {call(Goals)}.



s ---> np island, vp.

np ---> det, n, optrel.
np ---> pn.

vp ---> dv, np, np.
vp ---> tv, np.
vp ---> iv.

optrel ---> [].
optrel ---> [that] fills np, s.
optrel ---> [that], vp.

gap(np) ---> [].

det ---> [Det], {det(Det)}.
det(a).     det(every).
det(some).  det(the).

n ---> [N], {n(N)}.
n(author).      n(book).
n(professor).   n(program).
n(programmer).  n(student).

pn ---> [PN], {pn(PN)}.
pn(begriffsschrift).  pn(bertrand).
pn(bill).             pn(gottlob).
pn(lunar).            pn(principia).
pn(shrdlu).           pn(terry).

dv ---> [DV], {dv(DV)}.
dv(gave).

tv ---> [TV], {tv(TV)}.
tv(concerns).  tv(met).
tv(ran).       tv(wrote).

iv ---> [IV], {iv(IV)}.
iv(halted).