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.1.tar.gz
sha256=f64814687276bad56483b2b8dfaaf70d0d6485f67fe5d44bff34bfa47af1896e
md5=3a15a377800cf988a310b4082406c685

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.