FormalGrammars- (Context-free) grammars in formal language theory

Safe HaskellNone



This module provides the functionality for automatic calculation of outside grammars from their inside progenitors.

TODO If we already have an inside rule: S -> A | B | C with inside syntactic variable S whose sole purpose is to collect results, than we don't need an extra symbol for Outside. What happens if this is not the case?



outsideFromInside :: Grammar -> Maybe Grammar Source #

Given an inside grammar, return Just an outside grammar, otherwise return Nothing.

genOutsideRules :: Rule -> [Rule] Source #

Given a single inside rule, create the outside rules.

TODO rules with only terminals on the RHS may need some consideration (this INCLUDES epsilon rules!)

TODO How do I know what an epsilon rule is? I might actually have to say in the formal language... actually this might work. say e is a free variable, but terminal: X -> e has the epsilon form X -> e eps because there are only "non-epsilon" rhs terminals -- we don't know yet that e is epsilon. This generates the outside rule S -> e X* which is what we want, except for the superfluous e on the rhs. Because this generates an algebra type that is incompatible with the inside version, users should not do this. We are probably save, if all rules FROM the start symbol are of the form S -> A | B | C and all terminal ending rules are of the form A -> eps (i.e. rewrite A -> c to A -> c E and have E -> eps.

outsideSymb :: Symbol -> Symbol Source #

Helper function that turns an inside symbol into an outside symbol. Simply by attaching a ' (prime) symbol.

toOutside :: Grammar -> Grammar Source #

If necessary add a special "start" rule to the set of rules.

Take a grammar and transform it into an outside grammar. If the given grammar is already in outside form, the grammar is returned as is.