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

Default GrammarEnv

MonadState GrammarEnv (Unlined (GrammarParser Parser))

Monad m => MonadState GrammarEnv (GrammarParser m)

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

MonadState GrammarEnv (Unlined (GrammarParser Parser))

Monad m => MonadState GrammarEnv (GrammarParser m)

Monad m => Monad (GrammarParser m)

Functor m => Functor (GrammarParser m)

Monad m => Applicative (GrammarParser m)

MonadPlus m => Alternative (GrammarParser m)

MonadPlus m => MonadPlus (GrammarParser m)

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

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

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

data Result a :: * -> *

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

Constructors

Success a

Failure Doc

Instances

Functor Result

Applicative Result

Foldable Result

Traversable Result

Alternative Result

Show a => Show (Result a)

Show a => Pretty (Result a)

AsResult (Result a) (Result b) a b