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)

Methods

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

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

Ord t => Ord (SPPFNode t)

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

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 a2, Show a1) => Map a1 [a2] -> String

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

showP :: (Show a2, Show a1) => 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)