- data LCBaseIx ix
- data LCNTMinNTIx ix' ix
- data LCNTMinTIx t ix
- data LCDomain phi t ix where
- 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)
- data family LCValue r t ix
- transformLeftCorner :: (Domain phi, Token t) => ProcessingContextFreeGrammar phi t r -> ProcessingContextFreeGrammar (LCDomain phi t) t (LCValue r t)
- transformLeftCornerE :: forall phi t r. (Domain phi, Token t) => ProcessingExtendedContextFreeGrammar phi t r -> ProcessingExtendedContextFreeGrammar (LCDomain phi t) t (LCValue r t)
Documentation
data LCNTMinNTIx ix' ix Source
data LCNTMinTIx t ix Source
data LCDomain phi t ix whereSource
LCDomain
defines, for a base domain phi an extended
domain containing the non-terminals used by the left-
corner transform.
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) |
transformLeftCorner :: (Domain phi, Token t) => ProcessingContextFreeGrammar phi t r -> ProcessingContextFreeGrammar (LCDomain phi t) t (LCValue r t)Source
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)Source
Apply the left-corner transform to a given extended grammar, removing direct and indirect left recursion.