Copyright	(C) 2026 - Eitan Chatav
License	BSD-style (see the file LICENSE)
Maintainer	Eitan Chatav <eitan.chatav@gmail.com>
Stability	provisional
Portability	non-portable
Safe Haskell	None
Language	Haskell2010

Control.Lens.Grammar.BackusNaur

Contents

BackusNaurForm

Description

See Naur & Backus, et al. Report on the Algorithmic Language ALGOL 60.

Synopsis

class BackusNaurForm bnf where
- rule :: String -> bnf -> bnf
- ruleRec :: String -> (bnf -> bnf) -> bnf
data Bnf rule = Bnf {
- startBnf :: rule
- rulesBnf :: Set (String, rule)
}
liftBnf0 :: Ord a => a -> Bnf a
liftBnf1 :: (Coercible a b, Ord b) => (a -> b) -> Bnf a -> Bnf b
liftBnf2 :: (Coercible a c, Coercible b c, Ord c) => (a -> b -> c) -> Bnf a -> Bnf b -> Bnf c
diffB :: (Categorized token, HasTrie token) => [token] -> Bnf (RegEx token) -> Bnf (RegEx token)

BackusNaurForm

class BackusNaurForm bnf where Source #

BackusNaurForm grammar combinators formalize traced rule abstraction and general recursion with ruleRec, related by this invariant.

rule label bnf = ruleRec label (\_ -> bnf)

The BackusNaurForm interface is reminiscent of two distinct notions of "trace". First as a traced Cartesian monoidal category which models general recursion abstractly, and second as a trace-like label for rule abstraction. The category (->) already has a traced (,)-monoidal structure in the form of unfirst = loop or equivalently the fixpoint function fix, determining default methods for a BackusNaurForm.

rule _ = id

ruleRec _ = fix

The BackusNaurForm interface permits overloading these methods, and tracing them with a label.

Both context-free Grammars & CtxGrammars support the BackusNaurForm interface. See Breitner, Showcasing Applicative, for the original interface.

Minimal complete definition

Nothing

Methods

rule :: String -> bnf -> bnf Source #

Rule abstraction.

ruleRec :: String -> (bnf -> bnf) -> bnf Source #

General recursion.

Instances

Instances details

BackusNaurForm RegBnf Source #
Instance details Defined in Control.Lens.Grammar Methods rule :: String -> RegBnf -> RegBnf Source # ruleRec :: String -> (RegBnf -> RegBnf) -> RegBnf Source #
BackusNaurForm (ReadP a) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods rule :: String -> ReadP a -> ReadP a Source # ruleRec :: String -> (ReadP a -> ReadP a) -> ReadP a Source #
(Ord rule, NonTerminalSymbol rule) => BackusNaurForm (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods rule :: String -> Bnf rule -> Bnf rule Source # ruleRec :: String -> (Bnf rule -> Bnf rule) -> Bnf rule Source #
BackusNaurForm k => BackusNaurForm (Grammor k a b) Source #
Instance details Defined in Data.Profunctor.Grammar Methods rule :: String -> Grammor k a b -> Grammor k a b Source # ruleRec :: String -> (Grammor k a b -> Grammor k a b) -> Grammor k a b Source #
BackusNaurForm (Parsector s a b) Source #
Instance details Defined in Data.Profunctor.Grammar.Parsector Methods rule :: String -> Parsector s a b -> Parsector s a b Source # ruleRec :: String -> (Parsector s a b -> Parsector s a b) -> Parsector s a b Source #
BackusNaurForm (Parsor s m a b) Source #
Instance details Defined in Data.Profunctor.Grammar Methods rule :: String -> Parsor s m a b -> Parsor s m a b Source # ruleRec :: String -> (Parsor s m a b -> Parsor s m a b) -> Parsor s m a b Source #
BackusNaurForm (Printor s m a b) Source #
Instance details Defined in Data.Profunctor.Grammar Methods rule :: String -> Printor s m a b -> Printor s m a b Source # ruleRec :: String -> (Printor s m a b -> Printor s m a b) -> Printor s m a b Source #
(forall x. BackusNaurForm (f x)) => BackusNaurForm (Joker f a b) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods rule :: String -> Joker f a b -> Joker f a b Source # ruleRec :: String -> (Joker f a b -> Joker f a b) -> Joker f a b Source #

data Bnf rule Source #

A Bnf consists of a distinguished starting rule and a set of named rules. When a Bnf supports NonTerminalSymbols, then it supports the BackusNaurForm interface by replacing recursive calls with nonTerminals.

ruleRec label f = rule label (f (nonTerminal label))

Constructors

Bnf
Fields startBnf :: rule rulesBnf :: Set (String, rule)

Instances

Instances details

(Ord rule, TokenAlgebra token rule) => TokenAlgebra token (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods tokenClass :: TokenClass token -> Bnf rule Source #
(Ord rule, TerminalSymbol token rule) => TerminalSymbol token (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods terminal :: [token] -> Bnf rule Source #
(Ord rule, Tokenized token rule) => Tokenized token (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods anyToken :: Bnf rule Source # token :: token -> Bnf rule Source # oneOf :: Foldable f => f token -> Bnf rule Source # notOneOf :: Foldable f => f token -> Bnf rule Source # asIn :: Categorize token -> Bnf rule Source # notAsIn :: Categorize token -> Bnf rule Source #
(Ord rule, Monoid rule) => Monoid (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods mempty :: Bnf rule # mappend :: Bnf rule -> Bnf rule -> Bnf rule # mconcat :: [Bnf rule] -> Bnf rule #
(Ord rule, Semigroup rule) => Semigroup (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods (<>) :: Bnf rule -> Bnf rule -> Bnf rule # sconcat :: NonEmpty (Bnf rule) -> Bnf rule # stimes :: Integral b => b -> Bnf rule -> Bnf rule #
(Read rule, Ord rule) => Read (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods readsPrec :: Int -> ReadS (Bnf rule) # readList :: ReadS [Bnf rule] # readPrec :: ReadPrec (Bnf rule) # readListPrec :: ReadPrec [Bnf rule] #
Show rule => Show (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods showsPrec :: Int -> Bnf rule -> ShowS # show :: Bnf rule -> String # showList :: [Bnf rule] -> ShowS #
(Ord rule, NonTerminalSymbol rule) => BackusNaurForm (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods rule :: String -> Bnf rule -> Bnf rule Source # ruleRec :: String -> (Bnf rule -> Bnf rule) -> Bnf rule Source #
(Ord rule, KleeneStarAlgebra rule) => KleeneStarAlgebra (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods starK :: Bnf rule -> Bnf rule Source # plusK :: Bnf rule -> Bnf rule Source # optK :: Bnf rule -> Bnf rule Source # (>\|<) :: Bnf rule -> Bnf rule -> Bnf rule Source # zeroK :: Bnf rule Source #
(Ord rule, NonTerminalSymbol rule) => NonTerminalSymbol (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods nonTerminal :: String -> Bnf rule Source #
Eq rule => Eq (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods (==) :: Bnf rule -> Bnf rule -> Bool # (/=) :: Bnf rule -> Bnf rule -> Bool #
Ord rule => Ord (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods compare :: Bnf rule -> Bnf rule -> Ordering # (<) :: Bnf rule -> Bnf rule -> Bool # (<=) :: Bnf rule -> Bnf rule -> Bool # (>) :: Bnf rule -> Bnf rule -> Bool # (>=) :: Bnf rule -> Bnf rule -> Bool # max :: Bnf rule -> Bnf rule -> Bnf rule # min :: Bnf rule -> Bnf rule -> Bnf rule #
Categorized token => Matching [token] (Bnf (RegEx token)) Source #
Instance details Defined in Control.Lens.Grammar.Machine Methods (=~) :: [token] -> Bnf (RegEx token) -> Bool Source #

liftBnf0 :: Ord a => a -> Bnf a Source #

Lift a rule to a Bnf.

liftBnf1 :: (Coercible a b, Ord b) => (a -> b) -> Bnf a -> Bnf b Source #

Lift a function of rules to Bnfs.

liftBnf2 :: (Coercible a c, Coercible b c, Ord c) => (a -> b -> c) -> Bnf a -> Bnf b -> Bnf c Source #

Lift a binary function of rules to Bnfs.

diffB :: (Categorized token, HasTrie token) => [token] -> Bnf (RegEx token) -> Bnf (RegEx token) Source #

The Brzozowski derivative of a RegExtended Bnf, with memoization.

word =~ diffB prefix pattern = prefix <> word =~ pattern

Unfortunately, despite elegance & optimization, Brzozowski's pattern matching algorithm is worst case exponential in grammar size. See Might, Darais & Spiewak, Parsing With Derivatives.