package orsetto

  1. Overview
  2. Docs
A library of assorted structured data interchange languages

Install 

dune-project
 Dependency

bitbucket.org Edit opam file Versions (8)

Authors

  1. J
    james woodyatt <jhw@conjury.org>

Maintainers

  1. J
    james woodyatt <jhw@conjury.org>

Sources

r1.0.3.tar.gz
sha256=151ca6df499bd3de7aa89a4e1627411fbee24c4dea6e0e71ce21f06f181ee654
md5=00393728b481c2bf15919a8202732335

doc/orsetto.cf/Cf_dfa/index.html

Module Cf_dfa

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.