module RecursiveDescent where

import CF

import Control.Monad

recog :: (Eq a,Eq b) => CF a b -> [b] -> Bool
recog cf xs = [] `elem` recognize cf (start cf) xs

recognize :: (MonadPlus m, Eq a,Eq b) => CF a b -> a -> [b] -> m [b]
recognize cf c xs = m `mplus` l
  where m = msum [ matches cf rhs xs | rhs <- rhss cf c ]
	l = case xs of
		    [] -> mzero
		    (y:ys) -> msum [return ys | c' <- tokenCats cf y, c' == c]
		    

matches :: (MonadPlus m, Eq a,Eq b) => CF a b -> [a] -> [b] -> m [b]
matches _ [] xs = return xs
matches cf (c:cs) xs = recognize cf c xs >>= matches cf cs