Text.ANTLR.LL1

Documentation

recognize :: (Eq nts, Ref t, Eq (Sym t), HasEOF (Sym t), Ord nts, Ord t, Ord (Sym t), Ord (StripEOF (Sym t)), Prettify nts, Prettify t, Prettify (Sym t), Prettify (StripEOF (Sym t)), Hashable (Sym t), Hashable nts, Hashable (StripEOF (Sym t))) => Grammar () nts (StripEOF (Sym t)) -> [t] -> Bool

Language recognizer using predictiveParse.

first :: forall sts nts. (Eq nts, Eq sts, Ord nts, Ord sts, Hashable nts, Hashable sts) => Grammar () nts sts -> [ProdElem nts sts] -> Set (Icon sts)

First set of a grammar.

follow :: forall nts sts. (Eq nts, Eq sts, Ord nts, Ord sts, Hashable nts, Hashable sts) => Grammar () nts sts -> nts -> Set (Icon sts)

Follow set of a grammar.

foldWhileEpsilon :: (Eq ts, Hashable ts) => (HashSet (Icon ts) -> HashSet a -> HashSet a) -> HashSet a -> [HashSet (Icon ts)] -> HashSet a

Fold over a set of ProdElems (symbols) while all the previous sets of symbols contains an epsilon.

isLL1 :: (Eq nts, Eq sts, Ord nts, Ord sts, Hashable nts, Hashable sts) => Grammar () nts sts -> Bool

Is the given grammar in LL(1)?

  A -> α | β for all distinct ordered pairs of α and β,
       first(α) intersection first(β) == empty
  and if epsilon is in α, then
       first(α) intersection follow(A) == empty

parseTable :: forall nts sts. (Eq nts, Eq sts, Ord nts, Ord sts, Hashable sts, Hashable nts) => Grammar () nts sts -> ParseTable nts sts

The algorithm for computing an LL parse table from a grammar.

predictiveParse :: forall nts t ast. (Prettify nts, Prettify t, Prettify (Sym t), Prettify (StripEOF (Sym t)), Prettify ast, Eq nts, Eq (Sym t), HasEOF (Sym t), Ord (Sym t), Ord nts, Ord t, Ord (StripEOF (Sym t)), Hashable (Sym t), Hashable nts, Hashable (StripEOF (Sym t)), Ref t) => Grammar () nts (StripEOF (Sym t)) -> Action ast nts t -> [t] -> Maybe ast

Top-down predictive parsing algorithm.

removeEpsilons :: forall s nts t. (Eq t, Eq nts, Prettify t, Prettify nts, Prettify s, Ord t, Ord nts, Hashable t, Hashable nts) => Grammar s nts t -> Grammar s nts t

Remove all epsilon productions, i.e. productions of the form "A -> eps", without affecting the language accepted.

removeEpsilons' :: forall s nts t. (Eq t, Eq nts, Prettify t, Prettify nts, Prettify s, Ord t, Ord nts, Hashable t, Hashable nts) => [Production s nts t] -> [Production s nts t]

Remove all epsilon productions, i.e. productions of the form "A -> eps", without affecting the language accepted.

leftFactor :: forall s nts t. (Eq t, Eq nts, Prettify t, Prettify nts, Ord t, Ord nts, Hashable nts) => Grammar s nts t -> Grammar s (Prime nts) t

Left-factor a grammar to make it LL(1). This is experimental and mostly untested. This adds Primes to the nonterminal symbols in cases where we need to break up a production rule in order to left factor it.

newtype Prime nts

Add primes to nonterminal symbols.

Constructors

Prime (nts, Int)

Instances

Eq nts => Eq (Prime nts)

Defined in Text.ANTLR.LL1

Methods

(==) :: Prime nts -> Prime nts -> Bool

(/=) :: Prime nts -> Prime nts -> Bool

Ord nts => Ord (Prime nts)

Defined in Text.ANTLR.LL1

Methods

compare :: Prime nts -> Prime nts -> Ordering

(<) :: Prime nts -> Prime nts -> Bool

(<=) :: Prime nts -> Prime nts -> Bool

(>) :: Prime nts -> Prime nts -> Bool

(>=) :: Prime nts -> Prime nts -> Bool

max :: Prime nts -> Prime nts -> Prime nts

min :: Prime nts -> Prime nts -> Prime nts

Show nts => Show (Prime nts)

Defined in Text.ANTLR.LL1

Methods

showsPrec :: Int -> Prime nts -> ShowS

show :: Prime nts -> String

showList :: [Prime nts] -> ShowS

Generic (Prime nts)

Defined in Text.ANTLR.LL1

Associated Types

type Rep (Prime nts) :: Type -> Type

Methods

from :: Prime nts -> Rep (Prime nts) x

to :: Rep (Prime nts) x -> Prime nts

Hashable nts => Hashable (Prime nts)

Defined in Text.ANTLR.LL1

Methods

hashWithSalt :: Int -> Prime nts -> Int

hash :: Prime nts -> Int

Prettify nts => Prettify (Prime nts)

Defined in Text.ANTLR.LL1

Methods

prettify :: Prime nts -> Pretty

prettifyList :: [Prime nts] -> Pretty

type Rep (Prime nts)

Defined in Text.ANTLR.LL1

type Rep (Prime nts) = D1 (MetaData "Prime" "Text.ANTLR.LL1" "antlr-haskell-0.1.0.0-I1YLZdM1Y3a3syLrgVdT7Y" True) (C1 (MetaCons "Prime" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (nts, Int))))

type ParseTable nts sts = Map (PTKey nts sts) (PTValue nts sts)

M[A,s] = α for each symbol s member FIRST(α)

type PTKey nts sts = (nts, Icon sts)

Keys in the LL1 parse table.

type PTValue nts sts = Set (ProdElems nts sts)

All possible productions we could reduce. Empty implies parse error, singleton implies unambiguous entry, multiple implies ambiguous: