Language.ContextFree.Cfg

The type of Context Free Grammars. A production is modeled as a list of symbols, where the head of the list models the LHS and the tail models the RHS.

Constructors

Cfg

terminals :: [Symb t nt]	Set of Terminal Symbols
nonterminals :: [Symb t nt]	Set of Nonterminal Symbols
root :: (Symb t nt)	Root Symbol
prods :: [Prod t nt]	Set of (named) productions

Instances

??? nt t => Show (Cfg t nt)

cfg2dotGraph :: (Eq t, Eq nt, Show t, Show nt) => Cfg t nt -> String

cfg2dotList :: (Eq t, Eq nt, Show t, Show nt) => Cfg t nt -> String

type RHS t nt = [Symb t nt]

type Prod t nt = (ProdName, [Symb t nt])

type ProdName = String

data Symb t nt

Constructors

Dollar	End of input
Root	Root symbol
T t	Terminal symbol
NT nt	Non-terminal symbol

Instances

(Eq nt, Eq t) => Eq (Symb t nt)

(Ord nt, Ord t) => Ord (Symb t nt)

(Show nt, Show t) => Show (Symb t nt)

(Read nt, Read t) => Read (Symb t nt)

(|->) :: a -> [a] -> [a]

To make the notation of the grammars as similar to BNF as possible we define an infix operator to denote the usual 'derives to' operator

prods2cfg :: (Eq t, Eq nt) => [Prod t nt] -> nt -> Cfg t nt

Complete a list of productions to a well-formed grammar.

get_terminals :: (Eq t, Eq nt) => [Prod t nt] -> [Symb t nt]

Compute the list of terminals from a list of productions.

get_nonterminals :: (Eq t, Eq nt) => [Prod t nt] -> [Symb t nt]

Compute the list of non-terminals from a list of productions.

Access functions

lhs_prod :: [Symb t nt] -> Symb t nt

The left-hand side and th right-hand side of a prodution are easily defined by the head and tail functions

rhs_prod :: [Symb t nt] -> RHS t nt

Simple queries on grammars

sizeProd :: [Symb t nt] -> Int

Computes the length of a prodution: the number of symbols on its right-hand side

is_terminal :: (Eq t, Eq nt) => Symb t nt -> Cfg t nt -> Bool

Checks whether a terminal is declared as such in a grammar

prods_nt :: (Eq t, Eq nt) => Cfg t nt -> Symb t nt -> [[Symb t nt]]

Selects the productions from a Cfg that have a common given non-terminal as left-hand side.

rhs_nt :: (Eq t, Eq nt) => Cfg t nt -> Symb t nt -> [RHS t nt]

Selects the produtions RHSs from a Cfg that have a common given non-terminal as left-hand side.

rhs_with_nt :: (Eq t, Eq nt) => Cfg t nt -> Symb t nt -> [RHS t nt]

Selects the produtions RHSs from a Cfg that have a common given non-terminal in the right-hand side.

prods_rhs_with_nt :: (Eq t, Eq nt) => Cfg t nt -> Symb t nt -> [[Symb t nt]]

Selects the productions from a Cfg that have a common given non-terminal as right-hand side.

elemNT :: (Eq t, Eq nt) => Symb t nt -> RHS t nt -> Bool

Advanced queries on grammars

nullable

:: (Eq t, Eq nt)
=> Cfg t nt	Grammar
-> [Symb t nt]	Accumulator: non-terminals visited so far.
-> [Symb t nt]	List of grammar symbols (from RHS)
-> Bool
Verifies whther a sequence of symbols derives in the empty strig or not.

nullable_nt' :: (Eq t, Eq nt) => Cfg t nt -> [Symb t nt] -> Symb t nt -> Bool

nullable_nt :: (Eq t, Eq nt) => Cfg t nt -> Symb t nt -> Bool

first

:: (Eq t, Eq nt)
=> Cfg t nt	Grammar
-> RHS t nt	Sequence of grammar symbols
-> [Symb t nt]	`first` set
Computes the set of terminal symbols that begin the strings derived from the given sequence of symbols

first_N

:: (Eq nt, Eq t)
=> Cfg t nt	Grammar
-> Symb t nt	Nonterminal symbol
-> [Symb t nt]	`first` set
Computes the set of terminal symbols that begin the strings derived from the given nonterminal symbol

first' :: (Eq t, Eq nt) => Cfg t nt -> [Symb t nt] -> RHS t nt -> [Symb t nt]

follow

:: (Eq t, Eq nt)
=> Cfg t nt	Grammar
-> Symb t nt	Nonterminal symbol
-> [Symb t nt]	`follow` set
Computes the set of terminal symbols that can appear immediately to the right of a given nonterminal symbol in some sentential form

follow' :: (Eq t, Eq nt) => Cfg t nt -> [Symb t nt] -> Symb t nt -> [Symb t nt]

follow_prods_with_nt :: (Eq t, Eq nt) => Cfg t nt -> [Symb t nt] -> Symb t nt -> [[Symb t nt]] -> [Symb t nt]

suffices_after_sy :: (Eq t, Eq nt) => Cfg t nt -> [Symb t nt] -> Symb t nt -> [Symb t nt] -> [Symb t nt]

f :: (Eq t, Eq nt) => Cfg t nt -> [Symb t nt] -> Symb t nt -> RHS t nt -> [Symb t nt]

lookahead

:: (Eq t, Eq nt)
=> Cfg t nt	Grammar
-> [Symb t nt]	Production
-> [Symb t nt]	`lookahead` set
Computes the set of terminal symbols that begins the strings derived from the given production

all_lookaheads

:: (Eq t, Eq nt)
=> Cfg t nt	Grammar
-> [[Symb t nt]]	Sequence of `lookahead` set

lookaheads_nt

:: (Eq t, Eq nt)
=> Cfg t nt	Grammar
-> nt	Nonterminal symbol
-> [[Symb t nt]]	Sequence of `lookahead` set
Computes the lookahead set of a nonterminal symbols, that is the union of the lookaheads of the productions with this nonterminal symbol as lhs

Check the category in which the grammar falls.

ll_1_nt

:: (Eq nt, Eq t)
=> Cfg t nt	Grammar
-> Symb t nt	Nonterminal symbol
-> Bool
Verifies whether the given non-terminal verifies the LL(1) condition or not.

ll_1 :: (Eq t, Eq nt) => Cfg t nt -> Bool

Verifies whether a grammar verifies the LL(1) condition or not.

Produced by Haddock version 0.6