2 Automata: Compiling State Machines
This package provides macros and functions for writing state machines over racket/match patterns (as opposed to concrete characters.)
2.1 Machines
Each of the subsequent macros compile to instances of the machines provided by this module. This is a documented feature of the modules, so these functions should be used to, for example, determine if the machine is currently accepting.
An applicable structure for machines. When the structure is applied, the next field is used as the procedure.
A sub-structure of
machine that is accepting.
Returns #t if m ends in an accepting state after consuming every element of i.
Returns #t if m stays in an accepting state during the consumption of every element of i.
A machine that is never accepting.
A machine that is initially accepting and never accepting afterwards.
A machine that is always accepting.
A machine that inverts the acception criteria of m.
A machine that simulates the Kleene star of m. m may be invoked many times.
A machine that simulates the union of m0 and m1.
A machine that simulates the intersection of m0 and m1.
A machine that simulates the sequencing of m0 and m1. m1 may be invoked many times.
A machine that simulates the sequencing of m0 and (make-m1).
(make-m1) may be invoked many times.
2.2 Deterministic Finite Automata
This module provides a macro for deterministic finite automata.
| (dfa start | | (end ...) | | [state ([evt next-state] | | ...)] | | ...) |
|
| |
|
A
machine that starts in state
start where each state behaves as specified in the rules. If a
state is in
(end ...), then it is constructed with
machine-accepting.
next-state need not be a state from this DFA.
2.3 Non-Deterministic Finite Automata
This module provides a macro for non-deterministic finite automata.
| (nfa (start:id ...) | | (end:id ...) | | [state:id ([evt:expr (next-state:id ...)] | | ...)] | | ...) |
|
| |
|
A
machine that starts in state
(set start ...) where each state behaves as specified in the rules. If a state is in
(end ...), then the machine is accepting.
next-state must be a state from this NFA.
These machines are efficiently compiled to use the smallest possible bit-string as a set representation and unsafe numeric operations where appropriate for inspection and adjusting the sets.
2.4 Non-Deterministic Finite Automata (with epsilon transitions)
This module provides a macro for non-deterministic finite automata with epsilon transitions.
A binding for use in epsilon transitions.
| (nfa/ep (start:id ...) | | (end:id ...) | | [state:id ([epsilon (epsilon-state:id ...)] | | ... | | [evt:expr (next-state:id ...)] | | ...)] | | ...) |
|
| |
|
Extends
nfa with epsilon transitions, which must be listed first for each state.
2.5 Regular Expressions
This module provides a macro for regular expression compilation.
Compiles a regular expression over match patterns to a
machine.
The interpretation of the pattern language is mostly intuitive. The pattern language may be extended
with define-re-transformer. dseq allows bindings of the match pattern to be
used in the rest of the regular expression. (Thus, they are not really regular expressions.)
unquote escapes to Racket to evaluate an expression that evaluates to a regular expression (this happens
once, at compile time.) rec binds a Racket identifier to a delayed version of the inner expression; even
if the expression is initially accepting, this delayed version is never accepting.
The compiler will use an NFA, provided complement and dseq are not used. Otherwise,
many NFAs connected with the machine simulation functions from unstable/automata/machine are used.
Binds
id as an regular expression transformer used by the
re macro. The expression should evaluate to a function that accepts a syntax object and returns a syntax object that uses the regular expression pattern language.
2.5.1 Extensions
This module provides a few transformers that extend the syntax of regular expression patterns.
Optionally matches re-pat.
Matches one or more re-pat in sequence.
Matches re-pat in sequence num times, where num must be syntactically a number.
Matches everything that re-pat_0 does, except what re-pat_1 matches.
Matches the intersection of re-pat_0 and re-pat_1.
Matches the prefix closure of the sequence
(seq re-pat ...).
2.5.2 Examples
Examples: |
| | Success: '() => #t | Failure: '(0) => #f |
| | Failure: '() => #f | Failure: '(1) => #f |
| | Success: '("A") => #t | Failure: '() => #f | Failure: '("B") => #f |
| | Success: '() => #t | Success: '("B") => #t | Success: '("A" "A") => #t | Failure: '("A") => #f |
| | Success: '(1) => #t | Success: '(0) => #t | Failure: '() => #f | Failure: '(0 1) => #f | Failure: '(0 1 1) => #f |
| | Success: '(0 1) => #t | Failure: '() => #f | Failure: '(0) => #f | Failure: '(0 1 1) => #f |
| | Success: '() => #t | Success: '(0) => #t | Success: '(0 0) => #t | Failure: '(1) => #f |
| | Success: '() => #t | Success: '("A") => #t | Failure: '("B") => #f |
| | | Success: '() => #t | Success: '("A") => #t | Failure: '("B") => #f |
| | Success: '("A") => #t | Success: '("A" "A") => #t | Failure: '() => #f |
| | Success: '("A" "A" "A") => #t | Failure: '() => #f | Failure: '("A") => #f | Failure: '("A" "A") => #f |
| | Success: '(4) => #t | Success: '(6) => #t | Failure: '(3) => #f | Failure: '(2) => #f |
| | Success: '(2) => #t | Failure: '(1) => #f | Failure: '(4) => #f |
| | Success: '("A" "B" "C") => #t | Failure: '("A") => #f | Failure: '("A" "B") => #f |
| | Success: '(1) => #t | Failure: '(0) => #f | Failure: '() => #f |
| | Success: '(1) => #t | Failure: '(0) => #f | Failure: '() => #f |
| | Success: '(1 0 1 0 1) => #t | Success: '(0 1 0 1 0) => #t | Success: '(1 0 1 1 0 1) => #t | Success: '(0 1 0 0 1 0) => #t | Success: '() => #t | Failure: '(1 0) => #f |
| | Success: '(0 2 3 4) => #t | Success: '() => #t | Success: '(2) => #t | Success: '(234 5 9 1 9 0) => #t | Success: '(1 0) => #t | Success: '(0 1) => #t | Failure: '(1) => #f |
| | Success: '(0 0) => #t | Success: '(1 1) => #t | Failure: '() => #f | Failure: '(1) => #f | Failure: '(1 0) => #f |
|
|