circuits-parser
Safe HaskellNone
LanguageGHC2024

Circuit.Parser.Syntax

Description

Reifiable parser syntax.

The parser type in Circuit.Parser hides primitive operations inside K m closures over a Body (,) f (K m) base. This module exposes those primitives as constructors in a syntax tree, so the same parser can be executed and analyzed.

The plumbing — sequential composition and the structural combinators — is the free category over the pure ambient-state arrow Body (,) f (->) (Body (,) f (->)), extended with SigPrim and SigComb signatures. The stream f is ambient state throughout: primitives consume it, and choice is a structural combinator, not a trace. There is no SigKnot / Loop Either here — the knot-body category Body is the fold target, and the stream is never hidden in a feedback channel.

Executing a syntax tree is an algebra fold into Body (,) f (K m); static analysis is a fold into other targets (FirstSet, Regex, the Brzozowski derivative).

doctests

>>> import Data.Functor.Identity (Identity)
>>> import Data.These (These(..))
>>> import Control.Applicative ((<|>))
>>> import Circuit.Parser.Syntax (charS, stringS, manyS, firstSet, toRegex)

>>> runParserSyntaxIdentity (charS 'a') "abc"
These 'a' "bc"

>>> runParserSyntaxIdentity (stringS "ab" <|> stringS "a") "ab"
These "ab" ""

>>> runParserSyntaxIdentity (stringS "ab" <|> stringS "a") "a"
These "a" ""

>>> runParserSyntaxIdentity (manyS (charS 'a')) "aaab"
These "aaa" "b"

>>> firstSet (charS 'a' <|> charS 'b' :: ParserSyntax String Char Char)
FirstSet {nullable = False, firstKind = FSPred <function>}

>>> toRegex (manyS (charS 'a') :: ParserSyntax String Char String)
Just REStar (REChar 'a')
Synopsis

Signatures

data SigPrim f s (arr :: Type -> Type -> Type) (rec :: Type -> Type -> Type) a b where Source #

One-step parser primitives. Each constructor names a leaf operation on a stream of elements s with stream type f. The stream is ambient state, so the source object is unit and the target carries the result plus leftover stream.

Constructors

PrimNext :: forall f s (arr :: Type -> Type -> Type) (rec :: Type -> Type -> Type). SigPrim f s arr rec () (These s f) 
PrimSatisfy :: forall s f (arr :: Type -> Type -> Type) (rec :: Type -> Type -> Type). (s -> Bool) -> SigPrim f s arr rec () (These s f) 
PrimChar :: forall s f (arr :: Type -> Type -> Type) (rec :: Type -> Type -> Type). Eq s => s -> SigPrim f s arr rec () (These s f) 
PrimString :: forall s f (arr :: Type -> Type -> Type) (rec :: Type -> Type -> Type). Eq s => [s] -> SigPrim f s arr rec () (These [s] f) 
PrimEndOfInput :: forall f s (arr :: Type -> Type -> Type) (rec :: Type -> Type -> Type). SigPrim f s arr rec () (These () f) 
PrimTakeRest :: forall f s (arr :: Type -> Type -> Type) (rec :: Type -> Type -> Type). SigPrim f s arr rec () (These f f) 

Instances

Instances details
(Monad m, Uncons f s) => Algebra (SigPrim f s) (Body (,) f (->)) (Body (,) f (K m)) Source #

Map primitive operations to their implementations in Body (,) f (K m).

Instance details

Defined in Circuit.Parser.Syntax

Associated Types

type Ctx (SigPrim f s) (Body (,) f (->)) (Body (,) f (K m)) 
Instance details

Defined in Circuit.Parser.Syntax

type Ctx (SigPrim f s) (Body (,) f (->)) (Body (,) f (K m)) = (Monad m, Uncons f s)

Methods

alg :: Ctx (SigPrim f s) (Body (,) f (->)) (Body (,) f (K m)) => (forall x y. Body (,) f (->) x y -> Body (,) f (K m) x y) -> (forall x y. rec x y -> Body (,) f (K m) x y) -> SigPrim f s (Body (,) f (->)) rec a b -> Body (,) f (K m) a b #

type Ctx (SigPrim f s) (Body (,) f (->)) (Body (,) f (K m)) Source # 
Instance details

Defined in Circuit.Parser.Syntax

type Ctx (SigPrim f s) (Body (,) f (->)) (Body (,) f (K m)) = (Monad m, Uncons f s)

data SigComb f s (arr :: Type -> Type -> Type) (rec :: Type -> Type -> Type) a b where Source #

Structural combinators that cannot be expressed as pure sequential composition while preserving the syntax tree. These are eliminated by the execution algebra into the corresponding Parser combinators.

Constructors

CombAp :: forall (rec :: Type -> Type -> Type) a1 b1 f s (arr :: Type -> Type -> Type). rec () (These (a1 -> b1) f) -> rec () (These a1 f) -> SigComb f s arr rec () (These b1 f) 
CombBind :: forall (rec :: Type -> Type -> Type) a1 f b1 s (arr :: Type -> Type -> Type). rec () (These a1 f) -> (a1 -> rec () (These b1 f)) -> SigComb f s arr rec () (These b1 f) 
CombAlt :: forall (rec :: Type -> Type -> Type) a1 f s (arr :: Type -> Type -> Type). rec () (These a1 f) -> rec () (These a1 f) -> SigComb f s arr rec () (These a1 f) 
CombMany :: forall (rec :: Type -> Type -> Type) a1 f s (arr :: Type -> Type -> Type). rec () (These a1 f) -> SigComb f s arr rec () (These [a1] f) 
CombTry :: forall (rec :: Type -> Type -> Type) a1 f s (arr :: Type -> Type -> Type). rec () (These a1 f) -> SigComb f s arr rec () (These a1 f) 
CombFmap :: forall a1 b1 (rec :: Type -> Type -> Type) f s (arr :: Type -> Type -> Type). (a1 -> b1) -> rec () (These a1 f) -> SigComb f s arr rec () (These b1 f) 

Instances

Instances details
(Monad m, Uncons f s) => Algebra (SigComb f s) (Body (,) f (->)) (Body (,) f (K m)) Source # 
Instance details

Defined in Circuit.Parser.Syntax

Associated Types

type Ctx (SigComb f s) (Body (,) f (->)) (Body (,) f (K m)) 
Instance details

Defined in Circuit.Parser.Syntax

type Ctx (SigComb f s) (Body (,) f (->)) (Body (,) f (K m)) = (Monad m, Uncons f s)

Methods

alg :: Ctx (SigComb f s) (Body (,) f (->)) (Body (,) f (K m)) => (forall x y. Body (,) f (->) x y -> Body (,) f (K m) x y) -> (forall x y. rec x y -> Body (,) f (K m) x y) -> SigComb f s (Body (,) f (->)) rec a b -> Body (,) f (K m) a b #

type Ctx (SigComb f s) (Body (,) f (->)) (Body (,) f (K m)) Source # 
Instance details

Defined in Circuit.Parser.Syntax

type Ctx (SigComb f s) (Body (,) f (->)) (Body (,) f (K m)) = (Monad m, Uncons f s)

Syntax tree

newtype ParserSyntax f s a Source #

A parser syntax tree with stream type f, element type s, and result type a. The stream is ambient state (Body (,) f (->) base arrow), the source object is unit, and the target carries the result plus leftover stream.

Constructors

ParserSyntax 

Fields

Instances

Instances details
Uncons f s => Alternative (ParserSyntax f s) Source # 
Instance details

Defined in Circuit.Parser.Syntax

Methods

empty :: ParserSyntax f s a #

(<|>) :: ParserSyntax f s a -> ParserSyntax f s a -> ParserSyntax f s a #

some :: ParserSyntax f s a -> ParserSyntax f s [a] #

many :: ParserSyntax f s a -> ParserSyntax f s [a] #

Uncons f s => Applicative (ParserSyntax f s) Source # 
Instance details

Defined in Circuit.Parser.Syntax

Methods

pure :: a -> ParserSyntax f s a #

(<*>) :: ParserSyntax f s (a -> b) -> ParserSyntax f s a -> ParserSyntax f s b #

liftA2 :: (a -> b -> c) -> ParserSyntax f s a -> ParserSyntax f s b -> ParserSyntax f s c #

(*>) :: ParserSyntax f s a -> ParserSyntax f s b -> ParserSyntax f s b #

(<*) :: ParserSyntax f s a -> ParserSyntax f s b -> ParserSyntax f s a #

Uncons f s => Functor (ParserSyntax f s) Source # 
Instance details

Defined in Circuit.Parser.Syntax

Methods

fmap :: (a -> b) -> ParserSyntax f s a -> ParserSyntax f s b #

(<$) :: a -> ParserSyntax f s b -> ParserSyntax f s a #

Uncons f s => Monad (ParserSyntax f s) Source # 
Instance details

Defined in Circuit.Parser.Syntax

Methods

(>>=) :: ParserSyntax f s a -> (a -> ParserSyntax f s b) -> ParserSyntax f s b #

(>>) :: ParserSyntax f s a -> ParserSyntax f s b -> ParserSyntax f s b #

return :: a -> ParserSyntax f s a #

Uncons f s => MonadPlus (ParserSyntax f s) Source # 
Instance details

Defined in Circuit.Parser.Syntax

Methods

mzero :: ParserSyntax f s a #

mplus :: ParserSyntax f s a -> ParserSyntax f s a -> ParserSyntax f s a #

Primitive constructors

nextS :: ParserSyntax f s s Source #

anyTokenS :: ParserSyntax f s s Source #

satisfyS :: (s -> Bool) -> ParserSyntax f s s Source #

charS :: Eq s => s -> ParserSyntax f s s Source #

stringS :: Eq s => [s] -> ParserSyntax f s [s] Source #

endOfInputS :: ParserSyntax f s () Source #

takeRestS :: ParserSyntax f s f Source #

Combinator constructors

tryS :: ParserSyntax f s a -> ParserSyntax f s a Source #

optionalS :: Uncons f s => ParserSyntax f s a -> ParserSyntax f s (Maybe a) Source #

manyS :: ParserSyntax f s a -> ParserSyntax f s [a] Source #

someS :: Uncons f s => ParserSyntax f s a -> ParserSyntax f s [a] Source #

skipManyS :: Uncons f s => ParserSyntax f s a -> ParserSyntax f s () Source #

countS :: Uncons f s => Int -> ParserSyntax f s a -> ParserSyntax f s [a] Source #

sepByS :: Uncons f s => ParserSyntax f s a -> ParserSyntax f s b -> ParserSyntax f s [a] Source #

sepBy1S :: Uncons f s => ParserSyntax f s a -> ParserSyntax f s b -> ParserSyntax f s [a] Source #

withOptionS :: Uncons f s => ParserSyntax f s a -> (a -> ParserSyntax f s b) -> ParserSyntax f s b -> ParserSyntax f s b Source #

Execution

runParserSyntax :: forall (m :: Type -> Type) f s a. (Monad m, Uncons f s) => ParserSyntax f s a -> Parser m f s a Source #

Interpret syntax into a concrete parser.

runParserSyntaxIdentity :: Uncons f s => ParserSyntax f s a -> f -> These a f Source #

Interpret syntax into an identity parser.

Static analysis

data FirstSet s Source #

Possible first tokens of a parser, plus whether it can succeed without consuming input.

Constructors

FirstSet 

Fields

Instances

Instances details
Show (FirstSet s) Source # 
Instance details

Defined in Circuit.Parser.Syntax

Methods

showsPrec :: Int -> FirstSet s -> ShowS #

show :: FirstSet s -> String #

showList :: [FirstSet s] -> ShowS #

firstSet :: ParserSyntax f s a -> FirstSet s Source #

Compute the first-set of a parser syntax tree.

unreachableBranches :: ParserSyntax f s a -> [String] Source #

Detect unreachable branches in choice nodes. A branch is unreachable when the left side can consume any token that the right side can consume.

Regex extraction

data Regex s Source #

A simple regular-expression AST.

Constructors

REEmpty 
REAny 
REChar s 
REString [s] 
REClass (s -> Bool) 
REAlt (Regex s) (Regex s) 
RESeq (Regex s) (Regex s) 
REStar (Regex s) 

Instances

Instances details
Show s => Show (Regex s) Source # 
Instance details

Defined in Circuit.Parser.Syntax

Methods

showsPrec :: Int -> Regex s -> ShowS #

show :: Regex s -> String #

showList :: [Regex s] -> ShowS #

toRegex :: ParserSyntax f s a -> Maybe (Regex s) Source #

Extract a regex from a syntax tree, if it is regular. Returns Nothing for primitives or combinators that cannot be expressed as regular expressions.

Brzozowski derivatives

derive :: (Eq s, Uncons f s) => s -> ParserSyntax f s a -> ParserSyntax f s a Source #

The parser that remains after consuming one token.

This is the core of the coalgebraic compiler: a Process machine state is a parser syntax tree, and consuming a token transitions to its derivative. The implementation covers the applicative + alternative + many fragment; CombBind is rejected because it is dependent composition.

nullableValue :: Uncons f s => ParserSyntax f s a -> Maybe a Source #

Check whether a parser can succeed without consuming any input, and if so extract the value it would return.