FormalLanguage.CFG.Parser

We define a simple domain-specific language for context-free languages.

TODO we still need to make sure to handle NTs correctly. It should be that we write [X,Y] in multidim cases and then we check in rules if [X,Y] is available ... of course for [X,eps] we then need to check if eps is an epsilon symbol.

Documentation

data GrammarEnv

The environment captures both the current grammar we work with (current) as well as everything we have parsed until now (env).

Constructors

GrammarEnv

Fields

• _current :: Grammar

  The grammar declaration we currently evaluate

• _env :: Map String Grammar

  grammars within the environment

• _emit :: Seq Grammar

  sequence of grammars to emit (in order)

• _verbose :: Bool

  emit lots of informative messages

Instances

Show GrammarEnv

Methods

showsPrec :: Int -> GrammarEnv -> ShowS

show :: GrammarEnv -> String

showList :: [GrammarEnv] -> ShowS

Default GrammarEnv

Methods

def :: GrammarEnv

Monad m => MonadState GrammarEnv (GrammarParser m)

Methods

get :: GrammarParser m GrammarEnv

put :: GrammarEnv -> GrammarParser m ()

state :: (GrammarEnv -> (a, GrammarEnv)) -> GrammarParser m a

verbose :: Lens' GrammarEnv Bool

env :: Lens' GrammarEnv (Map String Grammar)

emit :: Lens' GrammarEnv (Seq Grammar)

current :: Lens' GrammarEnv Grammar

test :: MonadIO m => m (Maybe (Seq Grammar))

parse :: String -> Result (Seq Grammar)

parseEverything :: Parse m () -> Parse m (Seq Grammar)

Parse everything in the grammar source. The additional argument, normally empty :: Alternative f a, allows for providing additional parsing capabilities -- e.g. for grammar products..

parseGrammar :: Parse m ()

The basic parser, which generates a grammar from a description.

setIndices :: Parse m [Index]

Collect all indices and set them as active

parseEmitGrammar :: Parse m ()

Which of the intermediate grammar to actually emit as code or text in TeX. Single line: Emit: KnownGrammarName

parseNormStartEps :: Parse m ()

Normalize start and epsilon rules in a known Source:, thereby generating a new grammar.

parseOutside :: Parse m ()

Try to generate an outside grammar from an inside grammar. The From: name is looked up in the environment.

Outside: NAME
From: (inside)NAME
//

parseCommands :: Parse m ()

Some additional commands that change the parsing state.

TODO MonoidOfPairs should generate an adapter function that turns any 2-tape eval function into its k-tape version. This means collecting all name pairs, then emitting the corresponding adapter. We'll also need a monoidal function for combining pairs. (this is along the lines of sum-of-pairs).

Helper parsers

fgIdents :: TokenParsing m => IdentifierStyle m

newGrammarName :: Parse m String

knownGrammarName :: Parse m Grammar

parseSyntacticDecl :: EvalReq -> Parse m SynTermEps

Parses a syntactic (or non-terminal) symbol (for the corresponding index type). Cf. parseSynTermDecl.

parseSynTermDecl :: EvalReq -> Parse m SynTermEps

Parses a syntactic terminal declaration; an inside syntactic variable in an outside context.

parseTermDecl :: Parse m SynTermEps

parseStartSym :: Parse m Symbol

The syntactic variable here needs to either have no index at all, have a grammar-based index, or have a fully calculated index.

data EvalReq

Constructors

EvalFull

Happens when we actually emit a grammar product (in development)

EvalRule

Happens when we work through the rules

EvalSymb

Happens when we encounter N: and define a symbol

EvalGrammar

Happens when we define grammar-global parameters

knownSynVar :: EvalReq -> Stately m Symbol

knownSynTerm :: EvalReq -> Stately m Symbol

parseIndex :: EvalReq -> Stately m [Index]

Parses indices { ... } within curly brackets (braces).

When parsing the EvalSymb case, indexed symbols are being created.

Parsing in rules is handled via EvalRule and actually requires us saying which explicit index we use.

knownTermVar :: EvalReq -> Stately m Symbol

knownSymbol :: EvalReq -> Stately m Symbol

Parses an already known symbol, either syntactic or terminal.

TODO Correctly parse inside-syntactics in outside grammars? Do we want this explicitly?

parseRule :: Parse m [Rule]

updateSplitCounts :: [Symbol] -> [Symbol]

For split syntactic variables used in split manner (i.e. @S -> X Y X Y)

TODO error control!

expandIndexed :: Rule -> Parse m [Rule]

Once we have parsed a rule, we still need to extract all active indices in the rule, and enumerate over them. This will finally generate the set of rules we are interested in.

type Parse m a = (TokenParsing m, MonadState GrammarEnv (Unlined m), MonadState GrammarEnv m, MonadPlus m) => m a

type Stately m a = (TokenParsing m, MonadState GrammarEnv m, MonadPlus m) => m a

newtype GrammarParser m a

Constructors

GrammarParser

Fields

• runGrammarParser :: StateT GrammarEnv m a

Instances

Monad m => MonadState GrammarEnv (GrammarParser m)

Methods

get :: GrammarParser m GrammarEnv

put :: GrammarEnv -> GrammarParser m ()

state :: (GrammarEnv -> (a, GrammarEnv)) -> GrammarParser m a

Monad m => Monad (GrammarParser m)

Methods

(>>=) :: GrammarParser m a -> (a -> GrammarParser m b) -> GrammarParser m b

(>>) :: GrammarParser m a -> GrammarParser m b -> GrammarParser m b

return :: a -> GrammarParser m a

fail :: String -> GrammarParser m a

Functor m => Functor (GrammarParser m)

Methods

fmap :: (a -> b) -> GrammarParser m a -> GrammarParser m b

(<$) :: a -> GrammarParser m b -> GrammarParser m a

Monad m => Applicative (GrammarParser m)

Methods

pure :: a -> GrammarParser m a

(<*>) :: GrammarParser m (a -> b) -> GrammarParser m a -> GrammarParser m b

(*>) :: GrammarParser m a -> GrammarParser m b -> GrammarParser m b

(<*) :: GrammarParser m a -> GrammarParser m b -> GrammarParser m a

MonadPlus m => Alternative (GrammarParser m)

Methods

empty :: GrammarParser m a

(<|>) :: GrammarParser m a -> GrammarParser m a -> GrammarParser m a

some :: GrammarParser m a -> GrammarParser m [a]

many :: GrammarParser m a -> GrammarParser m [a]

MonadPlus m => MonadPlus (GrammarParser m)

Methods

mzero :: GrammarParser m a

mplus :: GrammarParser m a -> GrammarParser m a -> GrammarParser m a

(MonadPlus m, CharParsing m) => TokenParsing (GrammarParser m)

Methods

someSpace :: GrammarParser m ()

nesting :: GrammarParser m a -> GrammarParser m a

semi :: GrammarParser m Char

highlight :: Highlight -> GrammarParser m a -> GrammarParser m a

token :: GrammarParser m a -> GrammarParser m a

(MonadPlus m, CharParsing m) => CharParsing (GrammarParser m)

Methods

satisfy :: (Char -> Bool) -> GrammarParser m Char

char :: Char -> GrammarParser m Char

notChar :: Char -> GrammarParser m Char

anyChar :: GrammarParser m Char

string :: String -> GrammarParser m String

text :: Text -> GrammarParser m Text

(MonadPlus m, Parsing m) => Parsing (GrammarParser m)

Methods

try :: GrammarParser m a -> GrammarParser m a

(<?>) :: GrammarParser m a -> String -> GrammarParser m a

skipMany :: GrammarParser m a -> GrammarParser m ()

skipSome :: GrammarParser m a -> GrammarParser m ()

unexpected :: String -> GrammarParser m a

eof :: GrammarParser m ()

notFollowedBy :: Show a => GrammarParser m a -> GrammarParser m ()

data Result a :: * -> *

The result of parsing. Either we succeeded or something went wrong.

Constructors

Success a

Failure ErrInfo

Instances

Functor Result

Methods

fmap :: (a -> b) -> Result a -> Result b

(<$) :: a -> Result b -> Result a

Applicative Result

Methods

pure :: a -> Result a

(<*>) :: Result (a -> b) -> Result a -> Result b

(*>) :: Result a -> Result b -> Result b

(<*) :: Result a -> Result b -> Result a

Foldable Result

Methods

fold :: Monoid m => Result m -> m

foldMap :: Monoid m => (a -> m) -> Result a -> m

foldr :: (a -> b -> b) -> b -> Result a -> b

foldr' :: (a -> b -> b) -> b -> Result a -> b

foldl :: (b -> a -> b) -> b -> Result a -> b

foldl' :: (b -> a -> b) -> b -> Result a -> b

foldr1 :: (a -> a -> a) -> Result a -> a

foldl1 :: (a -> a -> a) -> Result a -> a

toList :: Result a -> [a]

null :: Result a -> Bool

length :: Result a -> Int

elem :: Eq a => a -> Result a -> Bool

maximum :: Ord a => Result a -> a

minimum :: Ord a => Result a -> a

sum :: Num a => Result a -> a

product :: Num a => Result a -> a

Traversable Result

Methods

traverse :: Applicative f => (a -> f b) -> Result a -> f (Result b)

sequenceA :: Applicative f => Result (f a) -> f (Result a)

mapM :: Monad m => (a -> m b) -> Result a -> m (Result b)

sequence :: Monad m => Result (m a) -> m (Result a)

Alternative Result

Methods

empty :: Result a

(<|>) :: Result a -> Result a -> Result a

some :: Result a -> Result [a]

many :: Result a -> Result [a]

Show a => Show (Result a)

Methods

showsPrec :: Int -> Result a -> ShowS

show :: Result a -> String

showList :: [Result a] -> ShowS

Show a => Pretty (Result a)

Methods

pretty :: Result a -> Doc

prettyList :: [Result a] -> Doc

AsResult (Result a) (Result b) a b

Methods

_Result :: Prism (Result a) (Result b) (Result a) (Result b)