package orsetto

  1. Overview
  2. Docs
package orsetto
Legend:
Library
Module
Module type
Parameter
Class
Class type

Functional composition of lazy deterministic finite automata.

Overview

This module implements operators for functional composition of lazy deterministic finite automata (DFA). A DFA is computationally more efficient at recognizing regular grammars than a non-deterministic finite automaton, at the cost of requiring exponentially more space for states. Lazy computation and memorization of DFA states usually requires space comparable with direct NFA elaboration, at the cost of some additional computation required when new DFA states are encountered.

Interface
module type Dispatch = sig ... end

This signature provides the abstraction necessary to represent an event dispatch, which is part of the DFA state record. It creates a dispatch for each new DFA state computed. It conceptually represents a lazily-evaluated map of events to state transitions.

module type Basis = sig ... end

This signature is a the basis for creating a DFA module.

module Aux : sig ... end

This module contains some pre-defined dispatch modules.

module type Regular = sig ... end

The signature of the core functions of the DFA engine.

module type Machine = sig ... end
module Core (B : Basis) : sig ... end

Use Core(B) to make a DFA with basis B.

module type Affix = sig ... end

The signature of additional affix operators for composing terms.

module Mk_affix (R : Regular) : Affix with type event := R.event and type term := R.term and type 'r fin := 'r R.fin

Use Mk_affix(R) to make the optional affix operators for R.

module type Profile = sig ... end

The DFA signature including the affix operators.

module Create (B : Basis) : Profile with type event := B.Event.t

Use Create(B) to make the DFA module for B including its optional affix operators.