Safe Haskell | None |
---|

Grammar construction combinators.

A grammar in grempa consists of a number of rules and an entry rule. Constructing a grammar is similar to doing it in BNF, but the grammars also have the information of what semantic action to take when a production has been found, which is used by the parsers that can be generated from the grammars.

Rules, constructed with the `rule`

function, consist of lists of productions.

A production in Grempa starts with a function which acts as the semantic
action to be taken when that production has been parsed. After the `<@>`

operator follows what the production accepts, which consists of a number of
grammar symbols (terminals (tokens) or non-terminals (grammar rules)).

The two combinator functions that construct productions come in two flavours each: One that signals that the result from parsing the symbol to the right of it should be used in the semantic action function and one that signals that it should not:

`action `

An action function followed by a symbol
`<@>`

symbol =

`action `

An action function followed by a symbol which will
not be used when taking the semantic action of the
production.
`<@`

symbol =

`prod `

A production followed by a symbol
`<#>`

symbol =

`prod `

A production followed by a symbol which will not be
used when taking the semantic action of the
production.
The grammars have the type `<#`

symbol =

, which tells us that the grammar
describes a language operating on `Grammar`

t a`[t]`

returning `a`

.

Grammars can be recursively defined by using recursive do-notation.

- type Grammar t a = GrammarState t (RId t a)
- type Rule t a = [Prod t a]
- data Prod t a where
- data Symbol t a where
- data RId s a where
- type GrammarState t = State (RuleIDs t)
- rule :: (Typeable a, Typeable t) => Rule t a -> Grammar t a
- evalGrammar :: GrammarState t a -> a
- augment :: (Typeable t, Typeable a) => Grammar t a -> Grammar t a
- getFun :: Prod t a -> DynFun
- class ToSym t a where
- (<@>) :: (ToSym t x, ToSymT t x ~ b, Typeable a, Typeable b) => (b -> a) -> x -> Prod t a
- (<@) :: (ToSym t x, Typeable a) => a -> x -> Prod t a
- (<#>) :: (ToSym t x, ToSymT t x ~ b) => Prod t (b -> a) -> x -> Prod t a
- (<#) :: ToSym t x => Prod t a -> x -> Prod t a
- epsilon :: Typeable a => a -> Prod t a
- levels :: Monad m => RStateT (Maybe a) m r -> m r
- lrule :: (Typeable a, Typeable t) => Rule t a -> RStateT (Maybe (RId t a)) (GrammarState t) (RId t a)
- several0 :: (ToSym s x, ToSymT s x ~ a, Typeable a, Typeable s) => x -> Grammar s [a]
- several :: (ToSym s x, ToSymT s x ~ a, Typeable a, Typeable s) => x -> Grammar s [a]
- severalInter0 :: (ToSym s x, ToSymT s x ~ a, ToSym s t, ToSymT s t ~ s, Typeable a, Typeable s) => t -> x -> Grammar s [a]
- severalInter :: (ToSym s x, ToSymT s x ~ a, ToSym s t, ToSymT s t ~ s, Typeable a, Typeable s) => t -> x -> Grammar s [a]
- cons :: (ToSym s x, ToSymT s x ~ a, ToSym s xs, ToSymT s xs ~ [a], Typeable a, Typeable s) => x -> xs -> Grammar s [a]

# Documentation

type Grammar t a = GrammarState t (RId t a)Source

A grammar production

Rule ID

type GrammarState t = State (RuleIDs t)Source

evalGrammar :: GrammarState t a -> aSource

Get the result from a Grammar computation

augment :: (Typeable t, Typeable a) => Grammar t a -> Grammar t aSource

Create an augmented grammar (with a new start symbol)

Class for writing grammars in a nicer syntax. This class allows one to use both rules and tokens with the grammar combinator functions. For the grammars to typecheck, it is often necessary to give their type.

ToSym t t |

:: (ToSym t x, ToSymT t x ~ b, Typeable a, Typeable b) | |

=> (b -> a) | The semantic action function for the production |

-> x | A grammar symbol |

-> Prod t a |

Start a production, where the symbol directly to the right of the operator is used in the semantic action.

:: (ToSym t x, Typeable a) | |

=> a | The semantic action function for the production |

-> x | A grammar symbol |

-> Prod t a |

Start a production, where the symbol directly to the right of the operator is not used in the semantic action.

(<#>) :: (ToSym t x, ToSymT t x ~ b) => Prod t (b -> a) -> x -> Prod t aSource

Sequence a production and a grammar symbol, where the symbol directly to the right of the operator is used in the semantic action.

(<#) :: ToSym t x => Prod t a -> x -> Prod t aSource

Sequence a production and a grammar symbol, where the symbol directly to the right of the operator is not used in the semantic action.

epsilon :: Typeable a => a -> Prod t aSource

The empty production, taking the semantic action (in this case just the value to return) as the argument.

levels :: Monad m => RStateT (Maybe a) m r -> m rSource

Start a levels block. Usage:

expr <- levels $ do rec e <- lrule [ Plus <@> e <# '+' <#> t ] t <- lrule [ Times <@> t <# '*' <#> f ] f <- lrule [ Var <@ 'x' , id <@ '(' <#> e <# ')'] return e

is equivalent to

e <- rule [ Plus <@> e <# '+' <#> t , id <@> t ] t <- rule [ Times <@> t <# '*' <#> f , id <@> f ] f <- rule [ Var <@ 'x' , id <@ '(' <#> e <# ')' ]

Put simply, every lrule save for the last one gets an additional identity production pointing to the next lrule. This is a common pattern when creating grammars with precedence levels.

lrule :: (Typeable a, Typeable t) => Rule t a -> RStateT (Maybe (RId t a)) (GrammarState t) (RId t a)Source

A rule in a levels block

several0 :: (ToSym s x, ToSymT s x ~ a, Typeable a, Typeable s) => x -> Grammar s [a]Source

Create a new rule which consists of 0 or more of the argument symbol.
Example: `several0 x`

matches `x x ... x`

Creates one new rule.

several :: (ToSym s x, ToSymT s x ~ a, Typeable a, Typeable s) => x -> Grammar s [a]Source

Return a new rule which consists of 1 or more of the argument symbol.
Example: `several x`

matches `x x ... x`

Creates one new rule.

severalInter0 :: (ToSym s x, ToSymT s x ~ a, ToSym s t, ToSymT s t ~ s, Typeable a, Typeable s) => t -> x -> Grammar s [a]Source

Create a new rule which consists of a list of size 0 or more interspersed
with a symbol.
Example: `severalInter0 ';' x`

matches `x ';' x ';' ... ';' x`

If `x :: a`

then the result is of type `[a]`

.

Creates two new rules.

severalInter :: (ToSym s x, ToSymT s x ~ a, ToSym s t, ToSymT s t ~ s, Typeable a, Typeable s) => t -> x -> Grammar s [a]Source

Return a new rule which consists of a list of size 1 or more interspersed
with a symbol.
Example: `severalInter ';' x`

matches `x ';' x ';' ... ';' x`

Creates one new rule.

:: (ToSym s x, ToSymT s x ~ a, ToSym s xs, ToSymT s xs ~ [a], Typeable a, Typeable s) | |

=> x | Symbol of type |

-> xs | Symbol of type |

-> Grammar s [a] |

Takes two symbols and combines them with `(:)`

.

Creates one new rule.

This can for example be used instead of using both `several`

and `several0`

on the same symbol, as that will create three new rules, whereas the
equivalent using `cons`

will only create two new rules. Example
transformation:

xs0 <- several0 x xs <- several x ==> xs0 <- several0 x xs <- x `cons` xs0