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.CFG

Description

The DSL used to describe CFGs.

Synopsis

data CFG v t = CFG {
- rules :: Set (Rule v t)
- start :: v
}
data Rule v t = v :-> (Production v t)
type Production v t = [Either v t]

Documentation

data CFG v t Source #

CFG v t is the type of context-free grammars with variables of type v and terminals of type t. Each such grammar contains the set of Rules and the start symbol. The list of terminals and non-terminals does not need to be explicitly stated for our purposes.

Constructors

CFG
Fields rules :: Set (Rule v t) Set of rules in the CFG. start :: v The start symbol.

Instances

Instances details

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

data Rule v t Source #

Rule v t is a CFG rule with variables of type v and terminals of type t. Variables with more than one rule should have multiple Rules, for example, \(S \to AB \mid \epsilon\) should have rules [S :-> [Left A, Left B], S :-> []].

Constructors

v :-> (Production v t)

S :-> s is the rule generating the string given by the list s from the variable S.

Instances

Instances details

(Eq v, Eq t) => Eq (Rule v t) Source #
Instance details Defined in CFGEq.CFG Methods (==) :: Rule v t -> Rule v t -> Bool Source # (/=) :: Rule v t -> Rule v t -> Bool Source #
(Ord v, Ord t) => Ord (Rule v t) Source #
Instance details Defined in CFGEq.CFG Methods compare :: Rule v t -> Rule v t -> Ordering Source # (<) :: Rule v t -> Rule v t -> Bool Source # (<=) :: Rule v t -> Rule v t -> Bool Source # (>) :: Rule v t -> Rule v t -> Bool Source # (>=) :: Rule v t -> Rule v t -> Bool Source # max :: Rule v t -> Rule v t -> Rule v t Source # min :: Rule v t -> Rule v t -> Rule v t Source #
(Show v, Show t) => Show (Rule v t) Source #
Instance details Defined in CFGEq.CFG Methods showsPrec :: Int -> Rule v t -> ShowS Source # show :: Rule v t -> String Source # showList :: [Rule v t] -> ShowS Source #

type Production v t = [Either v t] Source #

The type of productions in a Rule. The string is a list of Eithers, with Lefts representing variables and Rights representing terminals.