Text.GrammarCombinators.Transform.LeftCorner

Documentation

data LCBaseIx ix

Instances

DomainMap (LCDomain phi t) phi LCBaseIx

Show (r ix) => Show (LCValue r t (LCBaseIx ix))

data LCNTMinNTIx ix' ix

data LCNTMinTIx t ix

data LCDomain phi t ix where

LCDomain defines, for a base domain phi an extended domain containing the non-terminals used by the left- corner transform.

Constructors

LCBase :: phi ix -> LCDomain phi t (LCBaseIx ix)

LCNTMinNT :: phi ix' -> phi ix -> LCDomain phi t (LCNTMinNTIx ix' ix)

LCNTMinT :: t -> phi ix -> LCDomain phi t (LCNTMinTIx t ix)

Instances

(MemoFam phi, Token t) => MemoFam (LCDomain phi t)

(Token t, FoldFam phi) => FoldFam (LCDomain phi t)

(ShowFam phi, Show t) => ShowFam (LCDomain phi t)

(EqFam phi, Token t) => EqFam (LCDomain phi t)

(Domain phi, Token t) => Domain (LCDomain phi t)

DomainMap (LCDomain phi t) phi LCBaseIx

(ProductionRule p, EpsProductionRule p, RecProductionRule p (LCDomain phi t) (LCValue r t)) => EpsProductionRule (TransformLCRule p (LCDomain phi t) (LCValue r t) phi r t)

(ProductionRule p, EpsProductionRule p, RecProductionRule p (LCDomain phi t) (LCValue r t)) => LiftableProductionRule (TransformLCRule p (LCDomain phi t) (LCValue r t) phi r t)

(ProductionRule p, EpsProductionRule p, RecProductionRule p (LCDomain phi t) (LCValue r t)) => ProductionRule (TransformLCRule p (LCDomain phi t) (LCValue r t) phi r t)

(EqFam phi, EpsProductionRule p, LoopProductionRule p (LCDomain phi t) (LCValue r t)) => LoopProductionRule (TransformLCRule p (LCDomain phi t) (LCValue r t) phi r t) phi r

(ProductionRule p, EqFam phi, EpsProductionRule p, RecProductionRule p (LCDomain phi t) (LCValue r t)) => RecProductionRule (TransformLCRule p (LCDomain phi t) (LCValue r t) phi r t) phi r

data family LCValue r t ix

transformLeftCorner :: (Domain phi, Token t) => ProcessingContextFreeGrammar phi t r -> ProcessingContextFreeGrammar (LCDomain phi t) t (LCValue r t)

Apply the left-corner transform to a given grammar, removing direct and indirect left recursion.

Note that the new domain will contain O(n*t + n^2) non-terminals where n is the amount of non-terminals and t is the number of tokens, so when using this transformation, it can be beneficial to use a token type with a more limited amount of token values than Char, at least if you will use algorithms that fold over the full new grammar's domain (e.g. printGrammar does, printReachableGrammar doesn't).

transformLeftCornerE :: forall phi t r. (Domain phi, Token t) => ProcessingExtendedContextFreeGrammar phi t r -> ProcessingExtendedContextFreeGrammar (LCDomain phi t) t (LCValue r t)

Apply the left-corner transform to a given extended grammar, removing direct and indirect left recursion.