katydid-0.1.1.0: A haskell implementation of Katydid

Safe HaskellNone
LanguageHaskell2010

MemDerive

Description

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.

Synopsis

Documentation

derive :: Tree t => Refs -> [t] -> Except 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.

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

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

validate :: Tree t => Refs -> 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.