Does a word match a pattern?

Compile a RegExtended Bnf into a Transducer, using a combination of Thompson's algorithm for regular expressions and Earley's algorithm for context-free grammars. See Jim & Mandelbaum, Efficient Earley Parsing with Regular Right-hand Sides, and McIlroy, Enumerating the strings of regular languages.

A transducer is a form of finite state machine that can be run in various ways like =~, expectNext, languageSample, parseForest & unreachableRules.

The parse forest of a string of tokens.

languageSample lazily produces all words in a language from shortest to longest. However since TokenClasses can resolve to infinite sets of tokens, and the relevant case of Char tokens while not infinite is huge, it samples tokens in an Applicative TokenAlgebra.

What token is expected next? The scanner frontier, expectNext returns the TokenClass that can be scanned next after the given input prefix. A falseB result means the current chart has no scanner transitions, i.e. the prefix is a dead end for recognition.

Rule names that can never be entered from the start expression — dead productions. A non-empty result is a grammar-hygiene warning: those rules can be deleted without changing the recognized language.

A Transducer is a tuple

T = (Σ, Δ, Q, I ⊆ Q, F ∈ Q, transition ⊆ Q × (Σ ∪ ∆) × Q, output ⊆ Q × ∆)

• Σ is a (possibly infinite) set of terminal token classes, represented by TokenClasses.
• Δ is a finite set of nonterminals, represented by the key set of transducerRules.
• Q is a set of states, which is represented by the key set of transducerRelations.
• I are initial states represented by transducerStarts.
• F is a final state represented by 0.
• transition is a relation represented by transducerRelations with TransitionTokenClass and TransitionNonTerminal transitions.
• output is a relation represented by transducerRelations with EmitNonTerminal outputs.

A TransducerStep in a Transducer.