katydid- A haskell implementation of Katydid

Safe HaskellNone



This module is an efficient implementation of the derivative algorithm for trees.

It is intended to be used for production purposes.

This means that it gives up some readability for speed.

This module provides memoization of the nullable, calls and returns functions.



derive :: Tree t => Grammar -> [t] -> Either String Pattern Source #

derive is the classic derivative implementation for trees.

data Mem Source #

Mem is the object used to store memoized results of the nullable, calls and returns functions.

newMem :: Mem Source #

newMem creates a object used for memoization by the validate function. Each grammar should create its own memoize object.

validate :: Tree t => Grammar -> Pattern -> [t] -> State Mem Bool Source #

validate is the uses the derivative implementation for trees and return whether tree is valid, given the input grammar and start pattern.