Safe Haskell	None
Language	Haskell2010

CFG

Contents

Converting NTId back to name.
Generic grammar folds.
Guardedness.
Nullability.
First sets

Description

Context-free grammars: syntax and grammar folds.

Synopsis

data Grammar' x r t = Grammar {
- _grmNumNT :: Int
- _grmNTDict :: Map x NTId
- _grmNTDefs :: IntMap (NTDef' x r t)
}
emptyGrammar :: Grammar' x r t
data NTDef' x r t = NTDef {
- _ntName :: x
- _ntDef :: [Alt' x r t]
}
data Alt' x r t = Alt r (Form' x t)
newtype Form' x t = Form {
- theForm :: [Symbol' x t]
}
data Symbol' x t
- = Term t
- | NonTerm (NT' x)
data NT' x = NT {
- ntNum :: NTId
- ntNam :: x
}
type NTId = Int
grmNTDefs :: forall x r1 t1 r2 t2 f. Functor f => (IntMap (NTDef' x r1 t1) -> f (IntMap (NTDef' x r2 t2))) -> Grammar' x r1 t1 -> f (Grammar' x r2 t2)
grmNTDict :: forall x r t f. Functor f => (Map x NTId -> f (Map x NTId)) -> Grammar' x r t -> f (Grammar' x r t)
grmNumNT :: forall x r t f. Functor f => (Int -> f Int) -> Grammar' x r t -> f (Grammar' x r t)
ntDef :: forall x r1 t1 r2 t2 f. Functor f => ([Alt' x r1 t1] -> f [Alt' x r2 t2]) -> NTDef' x r1 t1 -> f (NTDef' x r2 t2)
ntName :: forall x r t f. Functor f => (x -> f x) -> NTDef' x r t -> f (NTDef' x r t)
data WithNTNames x a = WithNTNames {
- _wntNames :: IntMap x
- _wntThing :: a
}
wntNames :: forall x1 a x2 f. Functor f => (IntMap x1 -> f (IntMap x2)) -> WithNTNames x1 a -> f (WithNTNames x2 a)
wntThing :: forall x a1 a2 f. Functor f => (a1 -> f a2) -> WithNTNames x a1 -> f (WithNTNames x a2)
class GetNTNames x a where
- getNTNames :: a -> IntMap x
data GrmAlg r t a = GrmAlg {
- gaTerminal :: t -> a
- gaZero :: a
- gaPlus :: a -> a -> a
- gaEps :: a
- gaConcat :: a -> a -> a
- gaLabel :: r -> a -> a
}
gaProduct :: GrmAlg r t a -> [a] -> a
gaSum :: GrmAlg r t a -> [a] -> a
class GrmFold r t a b where
- grmFold :: GrmAlg r t a -> (NTId -> a) -> b -> a
grmIterate :: forall r t a x. (Eq a, Ord a) => GrmAlg r t a -> Grammar' x r t -> a -> Maybe a -> IntMap a
newtype Guarded = Guarded {
- getGuarded :: Bool
}
guardedAlg :: GrmAlg r t Guarded
computeGuardedness :: Grammar' x r t -> IntMap Guarded
newtype Nullable = Nullable {
- getNullable :: Bool
}
nullableAlg :: GrmAlg r t Nullable
computeNullable :: Grammar' x r t -> IntMap Nullable
newtype First t = First {
- getFirst :: SetMaybe t
}
firstAlg :: Ord t => GrmAlg r t (First t)
emptyFirst :: First t
concatFirst :: Ord t => First t -> First t -> First t
type FirstSets t = IntMap (First t)
computeFirst :: Ord t => Grammar' x r t -> FirstSets t
firstSet :: Ord t => FirstSets t -> Form' r t -> First t
data EGrammar' x r t = EGrammar {
- _eGrm :: Grammar' x r t
- _eStart :: NT' x
- _eFirst :: FirstSets t
}
eFirst :: forall x r t f. Functor f => (FirstSets t -> f (FirstSets t)) -> EGrammar' x r t -> f (EGrammar' x r t)
eGrm :: forall x r1 t r2 f. Functor f => (Grammar' x r1 t -> f (Grammar' x r2 t)) -> EGrammar' x r1 t -> f (EGrammar' x r2 t)
eStart :: forall x r t f. Functor f => (NT' x -> f (NT' x)) -> EGrammar' x r t -> f (EGrammar' x r t)
makeEGrammar :: Ord t => Grammar' x r t -> NT' x -> EGrammar' x r t

Documentation

data Grammar' x r t Source #

A grammar over non-terminal names x, rulenames r and an alphabet t consists of definitions of the nonterminals, represented as Ints.

Constructors

Grammar
Fields _grmNumNT :: Int Number of non-terminals. _grmNTDict :: Map x NTId Names-to-number map for non-terminals. _grmNTDefs :: IntMap (NTDef' x r t) Definitions of non-terminals.

Instances

Instances details

GetNTNames x (Grammar' x r t) Source #
Instance details Defined in CFG Methods getNTNames :: Grammar' x r t -> IntMap x Source #

emptyGrammar :: Grammar' x r t Source #

data NTDef' x r t Source #

A nonterminal is defined by a list of alternatives.

Constructors

NTDef
Fields _ntName :: x _ntDef :: [Alt' x r t]

Instances

Instances details

GrmFold r t a (NTDef' x r t) Source #
Instance details Defined in CFG Methods grmFold :: GrmAlg r t a -> (NTId -> a) -> NTDef' x r t -> a Source #
(Show x, Eq x) => Semigroup (NTDef' x r t) Source #	Disregarding `NTName`, we can join non-terminal definitions.
Instance details Defined in CFG Methods (<>) :: NTDef' x r t -> NTDef' x r t -> NTDef' x r t # sconcat :: NonEmpty (NTDef' x r t) -> NTDef' x r t # stimes :: Integral b => b -> NTDef' x r t -> NTDef' x r t #

data Alt' x r t Source #

Each alternative is a rule name plus a sentential form.

Constructors

Alt r (Form' x t)

Instances

Instances details

GrmFold r t a (Alt' x r t) Source #
Instance details Defined in CFG Methods grmFold :: GrmAlg r t a -> (NTId -> a) -> Alt' x r t -> a Source #
(Show r, Show t, Show x) => Show (Alt' x r t) Source #
Instance details Defined in CFG Methods showsPrec :: Int -> Alt' x r t -> ShowS # show :: Alt' x r t -> String # showList :: [Alt' x r t] -> ShowS #
(Eq r, Eq t) => Eq (Alt' x r t) Source #
Instance details Defined in CFG Methods (==) :: Alt' x r t -> Alt' x r t -> Bool # (/=) :: Alt' x r t -> Alt' x r t -> Bool #
(Ord r, Ord t) => Ord (Alt' x r t) Source #
Instance details Defined in CFG Methods compare :: Alt' x r t -> Alt' x r t -> Ordering # (<) :: Alt' x r t -> Alt' x r t -> Bool # (<=) :: Alt' x r t -> Alt' x r t -> Bool # (>) :: Alt' x r t -> Alt' x r t -> Bool # (>=) :: Alt' x r t -> Alt' x r t -> Bool # max :: Alt' x r t -> Alt' x r t -> Alt' x r t # min :: Alt' x r t -> Alt' x r t -> Alt' x r t #

newtype Form' x t Source #

A sentential form is a string of symbols.

Constructors

Form
Fields theForm :: [Symbol' x t]

Instances

Instances details

GrmFold r t a (Form' r' t) Source #
Instance details Defined in CFG Methods grmFold :: GrmAlg r t a -> (NTId -> a) -> Form' r' t -> a Source #
(Show t, Show x) => Show (Form' x t) Source #
Instance details Defined in CFG Methods showsPrec :: Int -> Form' x t -> ShowS # show :: Form' x t -> String # showList :: [Form' x t] -> ShowS #
Eq t => Eq (Form' x t) Source #
Instance details Defined in CFG Methods (==) :: Form' x t -> Form' x t -> Bool # (/=) :: Form' x t -> Form' x t -> Bool #
Ord t => Ord (Form' x t) Source #
Instance details Defined in CFG Methods compare :: Form' x t -> Form' x t -> Ordering # (<) :: Form' x t -> Form' x t -> Bool # (<=) :: Form' x t -> Form' x t -> Bool # (>) :: Form' x t -> Form' x t -> Bool # (>=) :: Form' x t -> Form' x t -> Bool # max :: Form' x t -> Form' x t -> Form' x t # min :: Form' x t -> Form' x t -> Form' x t #

data Symbol' x t Source #

A symbol is a terminal or a non-terminal.

Constructors

Term t
NonTerm (NT' x)

Instances

Instances details

GrmFold r t a (Symbol' r' t) Source #
Instance details Defined in CFG Methods grmFold :: GrmAlg r t a -> (NTId -> a) -> Symbol' r' t -> a Source #
(DebugPrint x, DebugPrint t) => DebugPrint (Symbol' x t) Source #
Instance details Defined in ParseTable.Pretty Methods debugPrint :: Symbol' x t -> String Source #
(Show t, Show x) => Show (Symbol' x t) Source #
Instance details Defined in CFG Methods showsPrec :: Int -> Symbol' x t -> ShowS # show :: Symbol' x t -> String # showList :: [Symbol' x t] -> ShowS #
Eq t => Eq (Symbol' x t) Source #
Instance details Defined in CFG Methods (==) :: Symbol' x t -> Symbol' x t -> Bool # (/=) :: Symbol' x t -> Symbol' x t -> Bool #
Ord t => Ord (Symbol' x t) Source #
Instance details Defined in CFG Methods compare :: Symbol' x t -> Symbol' x t -> Ordering # (<) :: Symbol' x t -> Symbol' x t -> Bool # (<=) :: Symbol' x t -> Symbol' x t -> Bool # (>) :: Symbol' x t -> Symbol' x t -> Bool # (>=) :: Symbol' x t -> Symbol' x t -> Bool # max :: Symbol' x t -> Symbol' x t -> Symbol' x t # min :: Symbol' x t -> Symbol' x t -> Symbol' x t #

data NT' x Source #

Non-terminals are natural numbers. We store the original name for printing purposes.

Constructors

NT
Fields ntNum :: NTId ntNam :: x

Instances

Instances details

GrmFold r t a (NT' x) Source #
Instance details Defined in CFG Methods grmFold :: GrmAlg r t a -> (NTId -> a) -> NT' x -> a Source #
DebugPrint x => DebugPrint (NT' x) Source #
Instance details Defined in ParseTable.Pretty Methods debugPrint :: NT' x -> String Source #
Show x => Show (NT' x) Source #
Instance details Defined in CFG Methods showsPrec :: Int -> NT' x -> ShowS # show :: NT' x -> String # showList :: [NT' x] -> ShowS #
Eq (NT' x) Source #
Instance details Defined in CFG Methods (==) :: NT' x -> NT' x -> Bool # (/=) :: NT' x -> NT' x -> Bool #
Ord (NT' x) Source #
Instance details Defined in CFG Methods compare :: NT' x -> NT' x -> Ordering # (<) :: NT' x -> NT' x -> Bool # (<=) :: NT' x -> NT' x -> Bool # (>) :: NT' x -> NT' x -> Bool # (>=) :: NT' x -> NT' x -> Bool # max :: NT' x -> NT' x -> NT' x # min :: NT' x -> NT' x -> NT' x #

type NTId = Int Source #

grmNTDefs :: forall x r1 t1 r2 t2 f. Functor f => (IntMap (NTDef' x r1 t1) -> f (IntMap (NTDef' x r2 t2))) -> Grammar' x r1 t1 -> f (Grammar' x r2 t2) Source #

grmNTDict :: forall x r t f. Functor f => (Map x NTId -> f (Map x NTId)) -> Grammar' x r t -> f (Grammar' x r t) Source #

grmNumNT :: forall x r t f. Functor f => (Int -> f Int) -> Grammar' x r t -> f (Grammar' x r t) Source #

ntDef :: forall x r1 t1 r2 t2 f. Functor f => ([Alt' x r1 t1] -> f [Alt' x r2 t2]) -> NTDef' x r1 t1 -> f (NTDef' x r2 t2) Source #

ntName :: forall x r t f. Functor f => (x -> f x) -> NTDef' x r t -> f (NTDef' x r t) Source #

Converting `NTId` back to name.

data WithNTNames x a Source #

Decoration of something with a NT printing dictionary.

Constructors

WithNTNames
Fields _wntNames :: IntMap x Number-to-names map for non-terminals. _wntThing :: a The decorated thing.

Instances

Instances details

GetNTNames x (WithNTNames x a) Source #
Instance details Defined in CFG Methods getNTNames :: WithNTNames x a -> IntMap x Source #
DebugPrint x => DebugPrint (WithNTNames x IGotoActions) Source #
Instance details Defined in ParseTable.Pretty Methods debugPrint :: WithNTNames x IGotoActions -> String Source #
(Ord r, Ord t, DebugPrint x, DebugPrint r, DebugPrint t) => DebugPrint (WithNTNames x (IPT' x r t)) Source #
Instance details Defined in ParseTable.Pretty Methods debugPrint :: WithNTNames x (IPT' x r t) -> String Source #

wntNames :: forall x1 a x2 f. Functor f => (IntMap x1 -> f (IntMap x2)) -> WithNTNames x1 a -> f (WithNTNames x2 a) Source #

wntThing :: forall x a1 a2 f. Functor f => (a1 -> f a2) -> WithNTNames x a1 -> f (WithNTNames x a2) Source #

class GetNTNames x a where Source #

Methods

getNTNames :: a -> IntMap x Source #

Instances

Instances details

GetNTNames x (WithNTNames x a) Source #
Instance details Defined in CFG Methods getNTNames :: WithNTNames x a -> IntMap x Source #
GetNTNames x (EGrammar' x r t) Source #
Instance details Defined in CFG Methods getNTNames :: EGrammar' x r t -> IntMap x Source #
GetNTNames x (Grammar' x r t) Source #
Instance details Defined in CFG Methods getNTNames :: Grammar' x r t -> IntMap x Source #

Generic grammar folds.

data GrmAlg r t a Source #

A grammar algebra provides an implementation for the operations constituting CFGs.

Constructors

GrmAlg
Fields gaTerminal :: t -> a Single terminal. gaZero :: a Empty language. gaPlus :: a -> a -> a Language union. gaEps :: a Language of the empty word. gaConcat :: a -> a -> a Language concatenation. gaLabel :: r -> a -> a Labelled language.

gaProduct :: GrmAlg r t a -> [a] -> a Source #

n-ary concatenation, with a special case for empty concatenation.

gaSum :: GrmAlg r t a -> [a] -> a Source #

n-ary alternative, with a special case for empty language.

class GrmFold r t a b where Source #

Generic fold over a grammar.

Methods

grmFold :: GrmAlg r t a -> (NTId -> a) -> b -> a Source #

Instances

Instances details

GrmFold r t a (NT' x) Source #
Instance details Defined in CFG Methods grmFold :: GrmAlg r t a -> (NTId -> a) -> NT' x -> a Source #
GrmFold r t a (Form' r' t) Source #
Instance details Defined in CFG Methods grmFold :: GrmAlg r t a -> (NTId -> a) -> Form' r' t -> a Source #
GrmFold r t a (Symbol' r' t) Source #
Instance details Defined in CFG Methods grmFold :: GrmAlg r t a -> (NTId -> a) -> Symbol' r' t -> a Source #
GrmFold r t a (Alt' x r t) Source #
Instance details Defined in CFG Methods grmFold :: GrmAlg r t a -> (NTId -> a) -> Alt' x r t -> a Source #
GrmFold r t a (NTDef' x r t) Source #
Instance details Defined in CFG Methods grmFold :: GrmAlg r t a -> (NTId -> a) -> NTDef' x r t -> a Source #

grmIterate Source #

Arguments

:: forall r t a x. (Eq a, Ord a)
=> GrmAlg r t a	Grammar algebra.
-> Grammar' x r t	Grammar.
-> a	Default/start value.
-> Maybe a	Best value (if it exists).
-> IntMap a	Final value for each non-terminal.

Computing properties of non-terminals by saturation. The iteration is needed to handle the recursion inherent in CFGs. Requires a bounded lattice a.

Guardedness.

newtype Guarded Source #

Constructors

Guarded
Fields getGuarded :: Bool

Instances

Instances details

Bounded Guarded Source #
Instance details Defined in CFG Methods minBound :: Guarded # maxBound :: Guarded #
Show Guarded Source #
Instance details Defined in CFG Methods showsPrec :: Int -> Guarded -> ShowS # show :: Guarded -> String # showList :: [Guarded] -> ShowS #
Eq Guarded Source #
Instance details Defined in CFG Methods (==) :: Guarded -> Guarded -> Bool # (/=) :: Guarded -> Guarded -> Bool #
Ord Guarded Source #
Instance details Defined in CFG Methods compare :: Guarded -> Guarded -> Ordering # (<) :: Guarded -> Guarded -> Bool # (<=) :: Guarded -> Guarded -> Bool # (>) :: Guarded -> Guarded -> Bool # (>=) :: Guarded -> Guarded -> Bool # max :: Guarded -> Guarded -> Guarded # min :: Guarded -> Guarded -> Guarded #

guardedAlg :: GrmAlg r t Guarded Source #

computeGuardedness :: Grammar' x r t -> IntMap Guarded Source #

Nullability.

newtype Nullable Source #

Constructors

Nullable
Fields getNullable :: Bool

Instances

Instances details

Bounded Nullable Source #
Instance details Defined in CFG Methods minBound :: Nullable # maxBound :: Nullable #
Show Nullable Source #
Instance details Defined in CFG Methods showsPrec :: Int -> Nullable -> ShowS # show :: Nullable -> String # showList :: [Nullable] -> ShowS #
Eq Nullable Source #
Instance details Defined in CFG Methods (==) :: Nullable -> Nullable -> Bool # (/=) :: Nullable -> Nullable -> Bool #
Ord Nullable Source #
Instance details Defined in CFG Methods compare :: Nullable -> Nullable -> Ordering # (<) :: Nullable -> Nullable -> Bool # (<=) :: Nullable -> Nullable -> Bool # (>) :: Nullable -> Nullable -> Bool # (>=) :: Nullable -> Nullable -> Bool # max :: Nullable -> Nullable -> Nullable # min :: Nullable -> Nullable -> Nullable #

nullableAlg :: GrmAlg r t Nullable Source #

computeNullable :: Grammar' x r t -> IntMap Nullable Source #

First sets

newtype First t Source #

Constructors

First
Fields getFirst :: SetMaybe t

Instances

Instances details

Show t => Show (First t) Source #
Instance details Defined in CFG Methods showsPrec :: Int -> First t -> ShowS # show :: First t -> String # showList :: [First t] -> ShowS #
Eq t => Eq (First t) Source #
Instance details Defined in CFG Methods (==) :: First t -> First t -> Bool # (/=) :: First t -> First t -> Bool #
Ord t => Ord (First t) Source #
Instance details Defined in CFG Methods compare :: First t -> First t -> Ordering # (<) :: First t -> First t -> Bool # (<=) :: First t -> First t -> Bool # (>) :: First t -> First t -> Bool # (>=) :: First t -> First t -> Bool # max :: First t -> First t -> First t # min :: First t -> First t -> First t #