GLL.Types.Derivations

Documentation

type SlotL t = (Slot t, Int)

type PrL t = (Prod t, Int)

type NtL = (Nt, Int)

type SPPF t = (SymbMap t, ImdMap t, PackMap t, EdgeMap t)

An SPPF contains symbol nodes, intermediate nodes, packed nodes and edges between them. See Scott and Johnstone (2013) for an explanation of the SPPF.

type PackMap t = IntMap (IntMap (IntMap (Map (Prod t) IntSet)))

Stores packed nodes using nested Data.IntMaps, nesting is as follows:

• left extent
• right extent
• dot position (from left to right)
• mapping from productions to set of pivots

type SymbMap t = IntMap (IntMap (Set (Symbol t)))

Stores symbol nodes using nested Data.IntMaps, nesting is as follows:

• left extent
• right extent
• set of symbols

type ImdMap t = IntMap (IntMap (Set (Slot t)))

Stores intermediate nodes using nested Data.IntMaps, nesting is as follows:

• left extent
• right extent
• set of slots

type EdgeMap t = Map (SPPFNode t) (Set (SPPFNode t))

Stores edges, potentially costly.

data SPPFNode t

An SPPFNode is either a symbol node, an intermediate node, a packed node or a dummy.

Constructors

SNode (Symbol t, Int, Int)

INode (Slot t, Int, Int)

PNode (Slot t, Int, Int, Int)

Dummy

Instances

Eq t => Eq (SPPFNode t)

Defined in GLL.Types.Derivations

Methods

(==) :: SPPFNode t -> SPPFNode t -> Bool

(/=) :: SPPFNode t -> SPPFNode t -> Bool

Ord t => Ord (SPPFNode t)

Defined in GLL.Types.Derivations

Methods

compare :: SPPFNode t -> SPPFNode t -> Ordering

(<) :: SPPFNode t -> SPPFNode t -> Bool

(<=) :: SPPFNode t -> SPPFNode t -> Bool

(>) :: SPPFNode t -> SPPFNode t -> Bool

(>=) :: SPPFNode t -> SPPFNode t -> Bool

max :: SPPFNode t -> SPPFNode t -> SPPFNode t

min :: SPPFNode t -> SPPFNode t -> SPPFNode t

Show t => Show (SPPFNode t)

Defined in GLL.Parser

Methods

showsPrec :: Int -> SPPFNode t -> ShowS

show :: SPPFNode t -> String

showList :: [SPPFNode t] -> ShowS

type SNode t = (Symbol t, Int, Int)

type PNode t = (Prod t, [Int])

type SEdge t = Map (SNode t) (Set (PNode t))

type PEdge t = Map (PNode t) (Set (SNode t))

emptySPPF :: Ord t => SPPF t

pNodeLookup :: Ord t => SPPF t -> ((Prod t, Int), Int, Int) -> Maybe [Int]

pMapInsert :: Ord t => SPPFNode t -> SPPFNode t -> SPPF t -> SPPF t

sNodeLookup :: Ord t => SPPF t -> (Symbol t, Int, Int) -> Bool

sNodeInsert :: Ord t => SPPFNode t -> SPPFNode t -> SPPF t -> SPPF t

sNodeRemove :: Ord t => SPPF t -> (Symbol t, Int, Int) -> SPPF t

iNodeLookup :: Ord t => SPPF t -> (Slot t, Int, Int) -> Bool

iNodeInsert :: Ord t => SPPFNode t -> SPPFNode t -> SPPF t -> SPPF t

iNodeRemove :: Ord t => SPPF t -> (Slot t, Int, Int) -> SPPF t

eMapInsert :: Ord t => SPPFNode t -> SPPFNode t -> SPPF t -> SPPF t

inU :: Ord a => (a, Key, Key) -> IntMap (IntMap (Set a)) -> Bool

toU :: Ord a => (a, Key, Key) -> IntMap (IntMap (Set a)) -> IntMap (IntMap (Set a))

showD :: (Show a1, Show a2) => Map a1 [a2] -> String

showG :: (Show a1, Show a2) => Map a1 [a2] -> String

showP :: (Show a1, Show a2) => IntMap (IntMap (IntMap (Map a1 a2))) -> String

showS :: Show a => IntMap (IntMap a) -> String

showSPPF :: Show t => SPPF t -> String

type ProdMap t = Map Nt [Prod t]

type PrefixMap t = Map (Prod t, Int) ([t], Maybe Nt)

type SelectMap t = Map (Nt, [Symbol t]) (Set t)

type FirstMap t = Map Nt (Set t)

type FollowMap t = Map Nt (Set t)

fixedMaps :: (Eq t, Ord t, Parseable t) => Nt -> [Prod t] -> (ProdMap t, PrefixMap t, FirstMap t, FollowMap t, SelectMap t)