%  Linguistics 484 -- Example:  FSA_P PROLOG
%
%  Finite-State Parser:  A Finite-State Automaton (FSA) Parser.
%
%  This example represents an adaptation of a Finite-State Automaton so
%  that it yields a phrase marker for a string it accepts.  For example,
%  if the following query is typed:
%
%       s([dogs, like, them]).
%
%  the following representation of the structure of the sentence will
%  be displayed:
%
%       [s,[dogs],[vpp,[like],[np,[them],[h,[]]]]]


%s/1          s(L) : L is a list of tokens accepted by the finite state
%                    automaton.
%

   s(Data_list) :- control(s, Data_list, Parse),
                   nl, write(Parse), nl.

%
%control/3    control(S, L, P) : L is a list of tokens, S is the
%                              label of the current state of the
%                              automaton, and P is the phrase marker if
%                              data symbols are accepted as a sentence.
%
%             The phrase marker is built as the recursive control/3
%             assertion returns from a successful test of the ground case
%             assertion.  The ground case assertion succeeds if the data
%             tokens are accepted as a sentence.  The phrase marker is
%             "initialised" with the label of the final state of the
%             automaton.  The resulting list is then successively
%             "headed" with the then current token and state label
%             as the assertion returns.
%

   control(h, [], [h, []]).

   control(From, [Token | Rest], [From, [Token] | [Tree]]) :-
              move(From, Token, To),
              control(To, Rest, Tree).

%
%move/3     move(X, T, Y) : There exits a transition from state X to state Y,
%                           given the token T.
%

   move(s,   she,   vps).
   move(s,   he,    vps).
   move(s,   it,    vps).           move(s,   they,  vpp).
   move(s,   dog,   vps).           move(s,   dogs,  vpp).
   move(s,   cat,   vps).           move(s,   cats,  vpp).

   move(vps, likes, np ).           move(vpp, like,  np ).
   move(vps, plays, np ).           move(vpp, play,  np ).

   move(vps, plays, h  ).           move(vpp, play,  h  ).
   move(vps, runs,  h  ).           move(vpp, run,   h  ).

   move(np,  her,   h  ).
   move(np,  him,   h  ).
   move(np,  it,    h  ).           move(np,  them,  h  ).
   move(np,  dog,   h  ).           move(np,  dogs,  h  ).
   move(np,  cat,   h  ).           move(np,  cats,  h  ).