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

 File: bottomup_recognizer.pl

 Patrick Blackburn, 1999.
 Kristina Striegnitz, 2002.

 This file contains the code for a (very simple and *very* 
 inefficient) bottom up recognizer for CFGs.

 Usage: recognize_bottomup(+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 is very simple and *very* 
        inefficient, because it doesn't use a chart and
        uses append to split the input list into three 
        pieces in all possible ways.
****************************************************************/

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

%%% SWI Prolog provides the basic list manipulation 
%%% predicates. Uncomment the following line, if you
%%% are working with Sicstus.
% :- use_module(library(lists), [append/3]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% recognize_bottomup(+list_of_terminals_and_nonterminals)

%%% the base case: we managed to analyze the full input as 
%%% a sentence
recognize_bottomup([s]).
	
%%% the recursive case: choose a part of the incoming
%%% string which matches with the right hand side of a
%%% rule and replace it with the category symbol 
%%% on the left hand side of that rule. Recursivel
%%% recognize the result.
recognize_bottomup(String) :-
	/*** uncomment the following line to see which states
             the recognizer goes through ***/
	% nl,write('STATE: '),write(String),
        split(String,Front,Middle,Back),
	( Cat ---> Middle 
         ;
	  (Middle = [Word], lex(Word,Cat))
        ),
	/*** uncomment to see which rules are applied ***/
	% tab(5),write('RULE: '),write((Cat ---> Middle)),nl,
	append(Front,[Cat|Back],NewString),
	recognize_bottomup(NewString).
  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% split(+list, ?list, ?list, ?list)
%%% splits a list into three segments

split(ABC, A, B, C) :-
	append(A, BC, ABC),
	append(B, C, BC).

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