%  Linguistics 484 -- Example: PDA_C Prolog
%
%  Push-Down Automata: Configurations of the Machine.
%
%  The predicates comprising this program cause the Prolog interpreter
%  to emulate the operations of a Push-Down Automaton that has been
%  adapted to display output consisting of the sequence of its
%  configurations, together with the contents of its input tape, during
%  the course of its accepting an input string.  (Note that the
%  CONFIGURATION of a Push-Down Automaton is specified by the contents
%  of its store and by its current state.)  For example, typing the
%  following query:
%
%      s([some, dogs, like, the, cat]).
%
%  will cause the following output to be displayed:
%
%         <[#], $, [some,dogs,like,the,cat]>
%      => <[#], det, [dogs,like,the,cat]>
%      => <[#,det], n, [like,the,cat]>
%      => <[#], np, [like,the,cat]>
%      => <[#,np], v, [the,cat]>
%      => <[#,np,v], det, [cat]>
%      => <[#,np,v,det], n, []>
%      => <[#,np,v], np, []>
%      => <[#,np], vp, []>
%      => <[#], s, []>
%
%  where the contents of the push-down store, the state of the machine,
%  and the contents of the input tape during the course of the automaton's
%  processing of the sentence are shown as a sequence of ordered triples.
%  In the initial state, with the label '$', the store contains the
%  empty store symbol '#', and the tape contains the string to be
%  processed.  In the final state, the store again contains only the
%  empty store symbol '#', while the tape is empty, as indicated by the
%  null list '[]', while the machine is in an accepting state with the
%  label 's'.


%s/1          s(Tape) : The list of data tokens, Tape, comprises a
%                       sentence if it is accepted by a PDA the control
%                       unit of which is emulated by the predicate
%                       control/4.
%
      s(Tape) :- control(['#'], '$', Tape, [Stack, State, Data | Configs]),
                 nl, write( '   ' ),
                 show_config( Stack, State, Data ),
                 list_configs(Configs).


%control/4    control(Stack, State, Tape, Configs) : 
%
%        State is the label of the current state of the automaton,
%        and in this state, Tape is a list of the as yet unread
%        data tokens (words). Stack is a list of the symbols
%        currently in the push-down store.  Configs is the sequence
%        of configurations of the machine, together with the
%        contents of the input tape, during the course of a
%        recognition.
%
%  Empty store condition.
      control(['#'], State, [], [['#'], State, []] ).

%  Final state condition.
      control(Stack, s, [], [Stack, s, []] ).

%  Initial Finite-State Transition:  A --> a (Eg., Det --> some)
      control(['#'], '$', [Token | Tape],
             [['#'], '$', [Token | Tape] | Configs]) :-
              rule(Next, Token),
              control(['#'], Next, Tape, Configs).

%  Lambda/Pop Transition:  A --> B C (Eg., S --> NP VP)
      control([Top | Stack], State, Tape,
             [[Top | Stack], State, Tape | Configs]) :-
              rule(Next, Top, State),
              control(Stack, Next, Tape, Configs).

%  Read/Push Transition:  A --> a (Eg., V --> like)
      control(Stack, State, [Token | Tape],
             [Stack, State, [Token | Tape] | Configs]) :-
              rule(Next, Token),
              control([State | Stack], Next, Tape, Configs).



%list_configs/1
%
%  list_configs( C ) : C is a list of the configurations visited by the
%                      machine during a recognition.

   list_configs( [] ).

   list_configs( [Stack, State, Data | Configs] ) :-
             write( '=> ' ),
             show_config( Stack, State, Data ),
              list_configs( Configs ) .

%show_config/3
%
%  show_config( Stack, State, Data ) :  Display the contents of the
%                                       push-down (Stack), the contents
%               of the input tape (Date), and the current state (State)
%               of the machine at an ordered triple.  Note that, the
%               order of the symbols in the push-down store is
%               reversed by the reverse/2, reverse/3 predicates.
%               The store is emulated by a Prolog list, which means
%               symbols are added, or pushed onto the left-end hand,
%               which therefore acts as the top of the store.
%               For the display produced here it is required that the
%               top of the store be the right-hand end of the list.

   show_config( Stack, State, Data ) :-
             reverse( Stack, Store ),
             write( '<' ), write( Store ), write( ', ' ),
                           write( State ), write( ', ' ),
                           write( Data ), write( '>'  ), nl.
   

% reverse/2, reverse/3
% Predicates to reverse the order of the elements of a list.

  reverse(AB, BA) :- reverse(AB, BA, []).

  reverse([], U, U).

  reverse([H | AB], U, W) :- reverse(AB, U, [H | W]).


%rule/2
%
%       rule(Qj, Ti) : Qj is the label of the state to which the PDA moves
%                     in a read/push transition, during which the data
%                     token Ti is read, corresponding to the rewriting
%                     rules of the form:   Qj --> Ti .

      rule(a,   nice).
      rule(det, the).          rule(det, some).

      rule(n,   dog).          rule(n,   dogs).
      rule(n,   cat).          rule(n,   cats).

      rule(v,   like).         rule(v,   likes).
      rule(v,   chase).        rule(v,   chases).


%rule/3
%
%       rule(Qj, Zi, Qi) : Qj is the label of the state to which the PDA
%                        moves from the state labelled Qi in a lambda/pop
%                        transition, during which the symbol Zi is popped
%                        from its stack, corresponding to the rewriting
%                        rules of the form:    Qj --> Zi Qi .


      rule(np, det,  n).      rule(np,   a,  n).

      rule(vp,   v, np).

      rule(s,   np, vp).