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.2.tar.gz
sha256=bb2af4d8b376b2d60fa996bd4d3b90d9f3559455672540f6d7c3598af81d483b
md5=f7bfa83013801b42fcdba607af2f012b

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.