Copyright	Chua Hou 2021
License	MIT
Maintainer	Chua Hou <human+github@chuahou.dev>
Stability	experimental
Portability	non-portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

CFGEq.CNF

Description

Compilation of CFGs from CFG to Chomsky normal form.

Synopsis

data CNF v t = CNF {
- rulesCNF :: Map v (Set (CNFProduction v t))
- startCNF :: v
- producesEmpty :: Bool
}
type CNFProduction v t = Either (v, v) t
compile :: forall v t. (Ord v, Ord t) => (Int -> v) -> CFG v t -> CNF v t
enumerate :: forall v t. (Ord v, Ord t) => Int -> CNF v t -> Set [t]

Documentation

data CNF v t Source #

CNF v t is the type of Chomsky normal form grammars with variables of type v and terminals of type t.

Constructors

CNF
Fields rulesCNF :: Map v (Set (CNFProduction v t)) Map of variables to their set of rules. startCNF :: v The start symbol. producesEmpty :: Bool Whether the start symbol produces epsilon.

Instances

Instances details

(Show v, Show t) => Show (CNF v t) Source #
Instance details Defined in CFGEq.CNF Methods showsPrec :: Int -> CNF v t -> ShowS Source # show :: CNF v t -> String Source # showList :: [CNF v t] -> ShowS Source #

type CNFProduction v t = Either (v, v) t Source #

The type of productions in a rule for CNF. Does not allow epsilon productions since CNF captures that for the start symbol as a Bool.

compile Source #

Arguments

:: forall v t. (Ord v, Ord t)
=> (Int -> v)	Fresh variable supplier.
-> CFG v t	Grammar to compile.
-> CNF v t

Compiles a CFG to CNF. Requires the caller to supply a function that supplies fresh variables of the correct type, that should be guaranteed to return a different variable when given a different Int argument.

enumerate Source #

Arguments

:: forall v t. (Ord v, Ord t)
=> Int	Maximum length of string to generate.
-> CNF v t	Chomsky normal form grammar to use.
-> Set [t]

enumerate n c returns the set of all strings generated by c of length n or less.