Safe Haskell	None
Language	GHC2024

Circuit.Parser.ProcessCompiler

Contents

Plain Process compiler

Description

Coalgebraic compiler: parser syntax trees become Process state machines.

A parser in Syntax is already a relation. This module turns that relation into a coalgebra by Brzozowski derivation:

machine state = a parser syntax tree;
input token = the next stream element;
transition = Brzozowski derivative of the current tree;
output = the nullable value of the current tree, if any.

The regular/applicative fragment is fully supported: primitives, @<|>@, @<*@, fmap, and many. CombBind is rejected because it is dependent composition. Explicit SigCompose nodes are also rejected; use the FunctorApplicativeAlternative constructors instead.

doctests

>>> import Circuit.Process (scan, fold)
>>> import Circuit.Parser.Syntax (charS, stringS, manyS)
>>> import Control.Applicative ((<|>))

>>> scan (compileProcess (stringS "ab" <|> stringS "a" :: ParserSyntax String Char String)) "ab"
[Just "a",Just "ab"]

>>> fold (compileProcess (stringS "ab" <|> stringS "a" :: ParserSyntax String Char String)) "ab"
Just (Just "ab")

>>> scan (compileProcess (manyS (charS 'a') :: ParserSyntax String Char String)) "aaab"
[Just "a",Just "aa",Just "aaa",Nothing]

Synopsis

compileProcess :: (Eq s, Uncons f s) => ParserSyntax f s a -> Process s (Maybe a)
compileProcessWithInput :: forall f s a. (Eq s, Uncons f s) => f -> ParserSyntax f s a -> Process s (Maybe (a, f))

Plain Process compiler

compileProcess :: (Eq s, Uncons f s) => ParserSyntax f s a -> Process s (Maybe a) Source #

Compile a parser into a Process machine whose output is the parse result of the prefix consumed so far.

The machine state is the Brzozowski derivative of the original parser after the tokens seen to date. Extraction succeeds exactly when that derivative is nullable.

>>> scan (compileProcess (stringS "ab" <|> stringS "a" :: ParserSyntax String Char String)) "ab"
[Just "a",Just "ab"]

compileProcessWithInput :: forall f s a. (Eq s, Uncons f s) => f -> ParserSyntax f s a -> Process s (Maybe (a, f)) Source #

Compile a parser into a Process machine tied to a known input stream.

The state carries the current derivative and the remaining suffix of the input. This lets extraction return both a parse result and the leftover stream, matching the usual parser output shape.

Because a Process has no explicit initial state, the input stream is captured at compile time and threaded through inject and step.

>>> scan (compileProcessWithInput "ab" (stringS "ab" <|> stringS "a" :: ParserSyntax String Char String)) "ab"
[Just ("a","b"),Just ("ab","")]