module ShiftReduce where

import CF

import Control.Monad
import Data.List

recog :: (Eq a,Eq b) => CF a b -> [b] -> Bool
recog cf xs = not (null (recognize cf xs []))

recognize :: (MonadPlus m,Eq a,Eq b) => CF a b -> [b] -> [a] -> m ()
recognize cf xs st = startsymbol `mplus` shift `mplus` reduce
 where startsymbol = guard (null xs && st == [start cf])
       shift = case xs of
		       [] -> mzero
		       (y:ys) -> msum [recognize cf ys (c:st) | c <- tokenCats cf y]
       reduce = msum [ recognize cf xs (c:drop (length rhs) st) 
		       | (c,rhs) <- allNRules cf, reverse rhs `isPrefixOf` st ]