-- | Syntax structures of Bnf.
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

module Data.Cfg.Bnf.Syntax
  ( Grammar(..)
  ) where

import Data.Cfg.Cfg (Cfg(..), Production, V(..), Vs)
import Data.Data (Data, Typeable)
import qualified Data.Set as S

-- | A simple, concrete instance of 'Cfg'.  The terminal and
-- nonterminal symbols of a 'Grammar' are defined to be exactly those
-- appearing the productions.  The start symbol is defined to be the
-- head of the first of the productions.
newtype Grammar t nt = Grammar
  { Grammar t nt -> [Production t nt]
grammarProductions :: [Production t nt]
    -- ^ the productions of the 'Grammar'
  } deriving (Typeable (Grammar t nt)
DataType
Constr
Typeable (Grammar t nt)
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Grammar t nt -> c (Grammar t nt))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Grammar t nt))
-> (Grammar t nt -> Constr)
-> (Grammar t nt -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (Grammar t nt)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (Grammar t nt)))
-> ((forall b. Data b => b -> b) -> Grammar t nt -> Grammar t nt)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> Grammar t nt -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> Grammar t nt -> r)
-> (forall u. (forall d. Data d => d -> u) -> Grammar t nt -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> Grammar t nt -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt))
-> Data (Grammar t nt)
Grammar t nt -> DataType
Grammar t nt -> Constr
(forall b. Data b => b -> b) -> Grammar t nt -> Grammar t nt
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Grammar t nt -> c (Grammar t nt)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Grammar t nt)
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (Grammar t nt))
forall a.
Typeable a
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> Grammar t nt -> u
forall u. (forall d. Data d => d -> u) -> Grammar t nt -> [u]
forall t nt. (Data t, Data nt) => Typeable (Grammar t nt)
forall t nt. (Data t, Data nt) => Grammar t nt -> DataType
forall t nt. (Data t, Data nt) => Grammar t nt -> Constr
forall t nt.
(Data t, Data nt) =>
(forall b. Data b => b -> b) -> Grammar t nt -> Grammar t nt
forall t nt u.
(Data t, Data nt) =>
Int -> (forall d. Data d => d -> u) -> Grammar t nt -> u
forall t nt u.
(Data t, Data nt) =>
(forall d. Data d => d -> u) -> Grammar t nt -> [u]
forall t nt r r'.
(Data t, Data nt) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Grammar t nt -> r
forall t nt r r'.
(Data t, Data nt) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Grammar t nt -> r
forall t nt (m :: * -> *).
(Data t, Data nt, Monad m) =>
(forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt)
forall t nt (m :: * -> *).
(Data t, Data nt, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt)
forall t nt (c :: * -> *).
(Data t, Data nt) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Grammar t nt)
forall t nt (c :: * -> *).
(Data t, Data nt) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Grammar t nt -> c (Grammar t nt)
forall t nt (t :: * -> *) (c :: * -> *).
(Data t, Data nt, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Grammar t nt))
forall t nt (t :: * -> * -> *) (c :: * -> *).
(Data t, Data nt, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (Grammar t nt))
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Grammar t nt -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Grammar t nt -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Grammar t nt)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Grammar t nt -> c (Grammar t nt)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Grammar t nt))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (Grammar t nt))
$cGrammar :: Constr
$tGrammar :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt)
$cgmapMo :: forall t nt (m :: * -> *).
(Data t, Data nt, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt)
gmapMp :: (forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt)
$cgmapMp :: forall t nt (m :: * -> *).
(Data t, Data nt, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt)
gmapM :: (forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt)
$cgmapM :: forall t nt (m :: * -> *).
(Data t, Data nt, Monad m) =>
(forall d. Data d => d -> m d) -> Grammar t nt -> m (Grammar t nt)
gmapQi :: Int -> (forall d. Data d => d -> u) -> Grammar t nt -> u
$cgmapQi :: forall t nt u.
(Data t, Data nt) =>
Int -> (forall d. Data d => d -> u) -> Grammar t nt -> u
gmapQ :: (forall d. Data d => d -> u) -> Grammar t nt -> [u]
$cgmapQ :: forall t nt u.
(Data t, Data nt) =>
(forall d. Data d => d -> u) -> Grammar t nt -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Grammar t nt -> r
$cgmapQr :: forall t nt r r'.
(Data t, Data nt) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Grammar t nt -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Grammar t nt -> r
$cgmapQl :: forall t nt r r'.
(Data t, Data nt) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Grammar t nt -> r
gmapT :: (forall b. Data b => b -> b) -> Grammar t nt -> Grammar t nt
$cgmapT :: forall t nt.
(Data t, Data nt) =>
(forall b. Data b => b -> b) -> Grammar t nt -> Grammar t nt
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (Grammar t nt))
$cdataCast2 :: forall t nt (t :: * -> * -> *) (c :: * -> *).
(Data t, Data nt, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (Grammar t nt))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (Grammar t nt))
$cdataCast1 :: forall t nt (t :: * -> *) (c :: * -> *).
(Data t, Data nt, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Grammar t nt))
dataTypeOf :: Grammar t nt -> DataType
$cdataTypeOf :: forall t nt. (Data t, Data nt) => Grammar t nt -> DataType
toConstr :: Grammar t nt -> Constr
$ctoConstr :: forall t nt. (Data t, Data nt) => Grammar t nt -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Grammar t nt)
$cgunfold :: forall t nt (c :: * -> *).
(Data t, Data nt) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Grammar t nt)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Grammar t nt -> c (Grammar t nt)
$cgfoldl :: forall t nt (c :: * -> *).
(Data t, Data nt) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Grammar t nt -> c (Grammar t nt)
$cp1Data :: forall t nt. (Data t, Data nt) => Typeable (Grammar t nt)
Data, Typeable)

instance (Ord nt, Ord t) => Cfg Grammar t nt where
  terminals :: Grammar t nt -> Set t
terminals = [t] -> Set t
forall a. Ord a => [a] -> Set a
S.fromList ([t] -> Set t) -> (Grammar t nt -> [t]) -> Grammar t nt -> Set t
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Production t nt -> [t]) -> [Production t nt] -> [t]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Production t nt -> [t]
forall t nt. Production t nt -> [t]
terminalsProd ([Production t nt] -> [t])
-> (Grammar t nt -> [Production t nt]) -> Grammar t nt -> [t]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Grammar t nt -> [Production t nt]
forall t nt. Grammar t nt -> [Production t nt]
grammarProductions
  nonterminals :: Grammar t nt -> Set nt
nonterminals = [nt] -> Set nt
forall a. Ord a => [a] -> Set a
S.fromList ([nt] -> Set nt)
-> (Grammar t nt -> [nt]) -> Grammar t nt -> Set nt
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Production t nt -> [nt]) -> [Production t nt] -> [nt]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Production t nt -> [nt]
forall t nt. Production t nt -> [nt]
nonterminalsProd ([Production t nt] -> [nt])
-> (Grammar t nt -> [Production t nt]) -> Grammar t nt -> [nt]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Grammar t nt -> [Production t nt]
forall t nt. Grammar t nt -> [Production t nt]
grammarProductions
  productionRules :: Grammar t nt -> nt -> Set (Vs t nt)
productionRules Grammar t nt
g nt
nt =
    [Vs t nt] -> Set (Vs t nt)
forall a. Ord a => [a] -> Set a
S.fromList [Vs t nt
rhs | (nt
nt', Vs t nt
rhs) <- Grammar t nt -> [Production t nt]
forall t nt. Grammar t nt -> [Production t nt]
grammarProductions Grammar t nt
g, nt
nt nt -> nt -> Bool
forall a. Eq a => a -> a -> Bool
== nt
nt']
  startSymbol :: Grammar t nt -> nt
startSymbol = Production t nt -> nt
forall a b. (a, b) -> a
fst (Production t nt -> nt)
-> (Grammar t nt -> Production t nt) -> Grammar t nt -> nt
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Production t nt] -> Production t nt
forall a. [a] -> a
head ([Production t nt] -> Production t nt)
-> (Grammar t nt -> [Production t nt])
-> Grammar t nt
-> Production t nt
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Grammar t nt -> [Production t nt]
forall t nt. Grammar t nt -> [Production t nt]
grammarProductions

nonterminalsVs :: Vs t nt -> [nt]
nonterminalsVs :: Vs t nt -> [nt]
nonterminalsVs Vs t nt
vs = [nt
nt | NT nt
nt <- Vs t nt
vs]

terminalsVs :: Vs t nt -> [t]
terminalsVs :: Vs t nt -> [t]
terminalsVs Vs t nt
vs = [t
t | T t
t <- Vs t nt
vs]

nonterminalsProd :: Production t nt -> [nt]
nonterminalsProd :: Production t nt -> [nt]
nonterminalsProd (nt
nt, Vs t nt
rhs) = nt
nt nt -> [nt] -> [nt]
forall a. a -> [a] -> [a]
: Vs t nt -> [nt]
forall t nt. Vs t nt -> [nt]
nonterminalsVs Vs t nt
rhs

terminalsProd :: Production t nt -> [t]
terminalsProd :: Production t nt -> [t]
terminalsProd = Vs t nt -> [t]
forall t nt. Vs t nt -> [t]
terminalsVs (Vs t nt -> [t])
-> (Production t nt -> Vs t nt) -> Production t nt -> [t]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Production t nt -> Vs t nt
forall a b. (a, b) -> b
snd