/****************************************************************

 File: topdown_parser.pl

 Patrick Blackburn, 1999.
 Kristina Striegnitz, 2002.

 This file contains the code for a very simple top down parser for
 CFGs. 

 Usage: parse_topdown(+InputString,?ParseTree)

        InputString: list of words you want to recognize    
        ParseTree: parse tree represented as a list. First element in
                   the list is the mother category, rest are subtrees.

        You also have to consult a file containing the 
        specification of a CFG.

  Note: The code is derived from topdown_recognizer.pl by adding an
        extra argument for constructing the parse tree.

        This implementation doesn't use a chart and is therefore still
        naive. But it quite efficient as it uses difference lists for
        splitting up the input string in parts that are already
        recognized and those that still need to be recognized.
****************************************************************/


:- op(700,xfx,--->).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% parse_topdown(category,+sentence,?rest of sentence,?parse tree)
%%% Chooses a rule with 'category' on the left hand side. Checks
%%% whether the right hand side can be expanded to match what comes
%%% next in the input string.


%%% Category can be expanded by a lexical rule.
parse_topdown(Category,[Word|Reststring],Reststring,[Category,Word]) :-
	/*** Uncomment the following lines to see the steps the top
             down parser takes ***/
	%%% nl, write('String to recognize: '), write([Word|Reststring]), 
	%%% nl, write('Category to recognize: '), write(Category),
	lex(Word,Category).
 
parse_topdown(Category,String,Reststring,[Category|Subtrees]) :-
        Category ---> RHS,
	/*** Uncomment the following lines to see the steps the top
             down parser takes ***/
        %%% nl, write('Rule: '), write((Category ---> RHS)),
        matches(RHS,String,Reststring,Subtrees).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% matches(+symbols, +sentence, ?rest of sentence, ?parse tree)
%%% Checks whether the list of symbols can be expanded into terminal
%%% symbols that match whats next on the input string.

%%% The list of symbols is empty. -> Return the string unchanged.
matches([],String,String,[]).

%%% The list of symbols was produced by a phrase structure rule and
%%% therefore contains category symbols. Try to recognize a substring
%%% matching the first category on the list, then try to match the
%%% rest of the categories.
matches([Category|Categories],String,RestString,[Subtree|Subtrees]) :-
        parse_topdown(Category,String,String1,Subtree),
        matches(Categories,String1,RestString,Subtrees).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% parse_topdown(+list,?parse tree)
%%% Driver predicate to initialize the category we are looking for
%%% and the difference list. Calls the main predicate
%%% parse_topdown/4. 

parse_topdown(String,Parse) :-
        parse_topdown(s,String,[],Parse).


/**********************************************************************
                    That's all, folks!
***********************************************************************/