# Module Cf_dfa

    module Cf_dfa: sig .. end

Functional composition of lazy deterministic finite automata.

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

The type of the input module for `Create(S: Symbol_T)` functor defined below.

    module type T = sig .. end

The output of the `Create(S: Symbol_T)` functor, which is a module that can be used to compose deterministic finite automata which operate on symbols of the type specified.

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

The functor that creates a DFA module.