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

 File: leftcorner_recognizer.pl

 Kristina Striegnitz, 2002.

 This file contains the code for a left-corner recognizer for
 CFGs. Needs phrase structure rules of the form C ---> [C1,C2,...,Cn]
 and lexical rules of the form lex(Word,Cat).

 Usage: leftcorner_recognize(+InputString)

        InputString: list of words you want to recognize    

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

  Note: This implementation doesn't use a left-corner table. 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,--->).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% leftcorner_recognize(+cat,+list of words,?list of words)
%%% Tries to detect a prefix of the input string (2nd argument) that
%%% is a string of category cat. Returns the remaining suffix.

leftcorner_recognize(Cat,[Word|StringIn],StringOut) :-
	lex(Word,WCat),
	complete(Cat,WCat,StringIn,StringOut).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% complete(+cat,+cat,+list of words,?list of words)
%%% 1st arg is the category that we want to recognize, 2nd arg the one
%%% that we already have recognized. Tries to fill the gap by reading
%%% more of the input string.

%%% base case: We have detected a string of the category that we were
%%% looking for. Remaining string is returned unchanged. 
complete(Cat,Cat,String,String).

%%% We have detected SubCat and are looking for Cat. Selects a rule
%%% with SubCat at its left corner and then tries to detect the rest
%%% of the right hand side in the input string (matches/3).
complete(Cat,SubCat,StringIn,StringOut) :-
	LHS ---> [SubCat|Cats],
	matches(Cats,StringIn,String1),
	complete(Cat,LHS,String1,StringOut).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% matches(+list of cats, +list of words, ?list of words)
%%% 1st argument is the list of categories that we want to recognize.

%%% base case: no more categories to recognize.
matches([],String,String).

%%% Tries to recognize the first category on the list. Then makes a
%%% recursive call with the list of remaining categories.
matches([Cat|Cats],StringIn,StringOut) :-
	leftcorner_recognize(Cat,StringIn,String1),
	matches(Cats,String1,StringOut).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% leftcorner_recognize(+list)
%%% Driver predicate to initialize the category we are looking for
%%% and the difference list. Calls the main predicate
%%% leftcorner_recognize/3. 

leftcorner_recognize(String) :-
	leftcorner_recognize(s,String,[]).



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