Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
Synopsis
- data TreeT f n t c
- type Tree = TreeT NoExt
- type TreeSet = TreeT Choice
- type TruncatedTree = TreeT (Sum Ellipsis NoExt)
- type TruncatedTreeSet = TreeT (Sum Ellipsis Choice)
- data NoExt a
- data Choice a = a :|: a
- class HasChoice f where
- (.:|:) :: a -> a -> f a
- (|:) :: HasChoice f => TreeT f n t c -> TreeT f n t c -> TreeT f n t c
- data Ellipsis a = Ellipsis
- ellipsis :: TreeT (Sum Ellipsis f) n t c
- data Sum f g a
- parseTreeSet :: (Ord n, Ord t) => Grammar n t c -> n -> [c] -> Maybe (TreeSet n t c)
- parseTreeSet_ :: (Ord n, Ord t) => Grammar n t c -> n -> [c] -> (Seq1 (Set (Item n t)), Maybe (TreeSet n t c))
- endOfSeq1 :: Seq1 a -> Int
- lookupSeq1 :: Int -> Seq1 a -> a
- growTree :: (Ord n, Ord t) => Grammar n t c -> Seq c -> Seq1 (Set (Item n t)) -> n -> Int -> Int -> Maybe (TreeSet n t c)
- matchItems :: (Ord n, Ord t) => Seq1 (Set (Item n t)) -> n -> Int -> [Item n t]
- unionTrees :: [TreeSet n t c] -> Maybe (TreeSet n t c)
- growBranches :: (Ord n, Ord t) => Grammar n t c -> Seq c -> Seq1 (Set (Item n t)) -> RuleId n -> Int -> Int -> [TreeSet n t c]
- sortAndGroupBy :: Ord b => (a -> b) -> [a] -> [[a]]
- growBranchesFrom :: (Ord n, Ord t) => Grammar n t c -> Seq c -> Seq1 (Set (Item n t)) -> Int -> Int -> [Atom n t] -> [TreeSet n t c] -> [[TreeSet n t c]]
- truncateTree :: Functor f => Int -> TreeT f n t c -> TreeT (Sum Ellipsis f) n t c
- fromSingleton :: TreeSet n t c -> Maybe (Tree n t c)
- data Lazy a
- forceLazy :: Lazy a -> a
- arbTree :: TreeSet n t c -> Tree n t c
- arbTree_ :: TreeSet n t c -> Lazy (Tree n t c)
- data Range = Range {}
- mkRange :: Int -> Int -> Range
- treeRange :: Tree n t c -> Range
- leftEnd :: Tree n t c -> Int
- rightEnd :: Tree n t c -> Int
- data Ambiguity n t c = Ambiguity (Tree n t c) (Tree n t c)
- type LocAmbiguity n t c = (Range, Ambiguity n t c)
- (><) :: [a] -> [a] -> [a]
- ambiguities :: TreeSet n t c -> [LocAmbiguity n t c]
- ambiguities' :: TreeSet n t c -> [LocAmbiguity n t c]
Documentation
Generalized parse tree.
A basic parse tree (Tree
) consists of leaves labeled terminal symbols t
(Leaf
)
and nodes labeled with grammar rules associated to nonterminal symbols ((
).Brch
)
Other variants of parse trees (TreeSet
, TruncatedTreeSet
) can be represented
using extension nodes (Ext
).
Trees may be infinite due to an input string matching infinitely many parse trees.
Note that even though StrictData
is enabled, we get laziness via the list type []
and tuple type (,)
.
Leaf Int t c | The |
Brch (RuleId n) Int Int [TreeT f n t c] | The |
Ext (f (TreeT f n t c)) |
type TruncatedTree = TreeT (Sum Ellipsis NoExt) Source #
Result of truncateTree
applied to a Tree
.
type TruncatedTreeSet = TreeT (Sum Ellipsis Choice) Source #
Result of truncateTree
applied to a TreeSet
.
Functors for extending TreeT
Choice constructor to represent TreeSet
.
a :|: a infixr 1 |
(|:) :: HasChoice f => TreeT f n t c -> TreeT f n t c -> TreeT f n t c infixr 1 Source #
Construct the disjunction of two trees featuring the Choice
functor.
Ellided by truncateTree
.
Like Sum
from Data.Functor.Sum but with more basic instances
parseTreeSet :: (Ord n, Ord t) => Grammar n t c -> n -> [c] -> Maybe (TreeSet n t c) Source #
Parse a chain of tokens [c]
into a parse tree.
Simplified variant of parse
.
parseTreeSet_ :: (Ord n, Ord t) => Grammar n t c -> n -> [c] -> (Seq1 (Set (Item n t)), Maybe (TreeSet n t c)) Source #
lookupSeq1 :: Int -> Seq1 a -> a Source #
growTree :: (Ord n, Ord t) => Grammar n t c -> Seq c -> Seq1 (Set (Item n t)) -> n -> Int -> Int -> Maybe (TreeSet n t c) Source #
growBranches :: (Ord n, Ord t) => Grammar n t c -> Seq c -> Seq1 (Set (Item n t)) -> RuleId n -> Int -> Int -> [TreeSet n t c] Source #
sortAndGroupBy :: Ord b => (a -> b) -> [a] -> [[a]] Source #
growBranchesFrom :: (Ord n, Ord t) => Grammar n t c -> Seq c -> Seq1 (Set (Item n t)) -> Int -> Int -> [Atom n t] -> [TreeSet n t c] -> [[TreeSet n t c]] Source #
truncateTree :: Functor f => Int -> TreeT f n t c -> TreeT (Sum Ellipsis f) n t c Source #
Truncate a tree to finite depth.
truncateTree
:: Int ->TreeSet
n t c ->TruncatedTreeSet
n t ctruncateTree
:: Int ->Tree
n t c ->TruncatedTree
n t c
arbTree :: TreeSet n t c -> Tree n t c Source #
Get an arbitrary Tree
from a TreeSet
, even if it is ambiguous.
An interval in some input sequence.
Evidence of ambiguity: two parse trees for the same input.
type LocAmbiguity n t c = (Range, Ambiguity n t c) Source #
Ambiguity at a given location.
(><) :: [a] -> [a] -> [a] Source #
Interleave two lists together. This combines enumerations somewhat fairly.
ambiguities :: TreeSet n t c -> [LocAmbiguity n t c] Source #
Enumerate (some) ambiguous parses.
If there are multiple ambiguities at the same location, we just pick an arbitrary example.
ambiguities' :: TreeSet n t c -> [LocAmbiguity n t c] Source #