%  Linguistics 484 -- Example:  TD_DFMP.TXT
%
%  Production Systems:  A Top-Down, Depth-First Parser that yields
%  multiple parses for structurally ambiguous sentences.
%
%  Very small changes have been made to the previous top-down,
%  depth-first parser in order to produce this example.  These changes
%  include the addition of a reference to the fail/0 system predicate.
%  This predicate, that has been added as the last goal in the body of
%  the s/1 predicate, forces the Listener to find alternative analyses
%  of ambiguous sentences.  All other predicates remain unchanged from
%  those in the earlier top-down, depth-first parser.
%

%s/1
%
%  s(Data) : The list of tokens in  Data  constitutes a sentence if all
%            the tokens in  Data  are consumed, and a phrase marker is
%            returned at  Parse.
%

   s( Data ) :-
              test_prod( s, Data, [], Parse ),
              nl, write( Parse ), nl,
              nl, write( 'Another parse?' ),
              nl, fail .


%test_rule/4
%
%  test_prod( LHS, Data, Data_i, Tree ) : A rule with left-hand side  LHS
%                                     (and with right-hand side  RHS) is
%                               selected, if it can be applied, and as a
%                               consequence, the initial data tokens in
%                               Data are consumed, leaving the remaining
%                               tokens in  Data_i, and a (partial) phrase
%                               marker at  Tree.
%

   test_prod( LHS, Data, Data_i, [LHS | Tree_i] ) :-
              prod( LHS, RHS ),
              apply( RHS, Data, Data_i, Tree_i ) .


%apply/4
%
%  apply( RHS, Data, Data_i, Tree ) :  A rule with the right-hand side
%                                  symbols RHS is (or, has been) applied,
%                            with the initial data tokens in  Data  being
%                            consumed, leaving the remaining tokens in
%                            Data_i, and with a (partial) phrase marker in
%                            Tree, if --
%
%             - all the right-hand side symbols are matched; or,
%
%             - the right-hand side symbol matches the initial data
%               token; or,
%
%             - a right-hand side symbol matches the left-hand side of a
%               production which can be applied, and the other right-hand
%               symbols result in other productions being selected.
%

   apply( [], Data, Data, [] ) .

   apply( [Word], [Word | Data_i], Data_i, [[Word]] ) .

   apply( [Symbol | Symbols], Data, Data_j, [Tree_i | Tree_j] ) :-
              test_prod( Symbol, Data, Data_i, Tree_i ),
              apply( Symbols, Data_i, Data_j, Tree_j ) .


%prod/2
%
%  prod( LHS RHS ) : LHS  is the left-hand side symbol of a production
%                    with right-hand side symbol(s) in the list  RHS.

   prod( s,  [vp, s ] ) .
   prod( s,  [np, vp] ) .
   prod( np, [ n ]   ) .
   prod( np, [ a, n ] ) .
   prod( vp, [ v, np] ) .
   prod( vp, [ v ]   ) .

   prod( n, [radio] ) .
   prod( a, [radio] ) .
   prod( v, [radio] ) .
   prod( v, [pay]   ) .
   prod( n, [pay]   ) .
   prod( n, [broadcasts] ) .
   prod( v, [broadcasts] ) .