Module Cf_dfa

module Cf_dfa: sig .. end

Overview

This module implements operators for functional composition of lazy deterministic finite automata (DFA). A lazy DFA is more efficient at recognizing regular grammars than a non-deterministic finite automaton, and the lazy evaluation amortizes the cost of compiling the state table so that it compares well to that of the NFA.

The interface defined here is used as the underlying algorithm for the Cf_lex module. It uses a functor that operates on a module defining the type of a symbol, the type of parser input tokens that contain such symbols, and a map of symbols to some polymorphic type. The result of the functor is a module that contains operator functions for composing expressions and rules for automata that operate on streams of the input symbol type.

Note: a DFA can be remarkably inefficient compared to an NFA for certain classes of unusual grammars and unusual input.

Module Types

module type Symbol_T = sig .. end

module type T = sig .. end

module Create: 
functor (S : Symbol_T) -> T  with module S = S