MemDerive

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.

Documentation

derive :: Tree t => Refs -> [t] -> Except String Pattern

derive is the classic derivative implementation for trees.

data Mem

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

newMem :: Mem

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

nullable :: Refs -> Pattern -> State Mem Bool

nullable returns whether a pattern is nullable and memoizes the results.

validate :: Tree t => Refs -> Pattern -> [t] -> State Mem Bool

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