Data.Parser.Grempa.Grammar

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 <@> symbol = An action function followed by a symbol

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

prod <#> symbol = A production followed by a symbol

prod <# symbol = A production followed by a symbol which will not be used when taking the semantic action of the production. The grammars have the type Grammar t a, which tells us that the grammar describes a language operating on [t] returning a.

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

Documentation

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

type Rule t a = [Prod t a]

data Prod t a where

A grammar production

Constructors

PSeq :: Prod t (b -> a) -> Symbol t b -> Prod t a

PSeqN :: Prod t a -> Symbol t b -> Prod t a

PFun :: Typeable a => a -> Prod t a

Instances

Typeable2 Prod

data Symbol t a where

A grammar symbol

Constructors

STerm :: t -> Symbol t t

SRule :: RId t a -> Symbol t a

Instances

ToSym t (Symbol t a)

data RId s a where

Rule ID

Constructors

RId :: (Typeable t, Typeable a) => RuleI -> Rule t a -> RId t a

Fields

rId :: RuleI

rIdRule :: Rule t a

Instances

Typeable2 RId

ToSym t (RId t a)

type GrammarState t = State (RuleIDs t)

rule :: (Typeable a, Typeable t) => Rule t a -> Grammar t a

Create a new rule in a grammar

evalGrammar :: GrammarState t a -> a

Get the result from a Grammar computation

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

Create an augmented grammar (with a new start symbol)

getFun :: Prod t a -> DynFun

Get the semantic action from a production

class ToSym t a where

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.

Associated Types

type ToSymT t a :: *

Methods

toSym :: a -> Symbol t (ToSymT t a)

Instances

ToSym t t

ToSym t (Symbol t a)

ToSym t (RId t a)

(<@>)

Arguments

:: (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.

(<@)

Arguments

:: (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 a

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 a

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 a

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 r

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)

A rule in a levels block

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

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]

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]

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]

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.

cons

Arguments

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

=> x

Symbol of type a

-> xs

Symbol of type [a]

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