nfe - Non-deterministic finite automata expression

Module Description

The nfe module implements an expression in a non-deterministic finite automata. An expression is a concatenation, repeation or alteration of non-deterministic finite automata states [nfs]. An not yet fully built expression consists of two cells on the stack: a list with the non resolved out states and a list of [nfs] states.
The code is based on the Thompson NFA algorithm published by Russ Cox.

Module Words

Expression structure

nfe% ( -- n )
Get the required space for a nfe expression

Expression creation, initialisation and cleanup

nfe-init ( nfe -- )
Initialise the expression

nfe+free-expression ( nfe -- )
Free all states in the [sub]expression [recursive]

nfe-(free) ( nfe -- )
Free the internal, private variables from the heap

nfe-create ( "<spaces>name" -- ; -- nfe )
Create a named expression in the dictionary

nfe-new ( -- nfe )
Create a new expression on the heap

nfe-free ( nfe -- )
Free the expression from the heap

Member words

nfe-visit++ ( nfe -- n )
Increment the visit number in the expression, return the visit number

nfe-level+@ ( nfe -- n )
Increment and return the paren level

nfe-visit@ ( nfe -- n )
Get the current visit number

nfe-expression@ ( nfe -- a-addr )
Get the list of states in the expression or nil

nfe-states@ ( nfe -- n )
Get the number of states in the expression

nfe-parens@ ( nfe -- n )
Get the number of parens in the expression

Expression building words

nfe-clear ( nfe -- )
Clear the expression

nfe-single ( x n nfe -- nfs1 nfs2 )
Start an expression, nfs2 nfs1, with a single new state nfs1 with data x and type n

nfe-concat ( nfs1 nfs2 nfs3 nfs4 nfe -- nfs5 nfs6 )
Concat the two expressions, return the outs nfs5 and start nfs6

nfe-paren ( nfs1 nfs2 n nfe -- nfs3 nfs4 )
Paren the expression with level n, return the new outs nf3 and start nfs4

nfe-alternation ( nfs1 nfs2 nfs3 nfs4 nfe -- nfs5 nfs6 )
Make an alternation [|] of two expressions, return the new outs nfs5 and start nfs6

nfe-zero-or-one ( nfs1 nfs2 nfe -- nfs3 nfs4 )
Repeat the expression one or zero [?] times, return the new start outs nfs3 and start nfs4

nfe-zero-or-more ( nfs1 nfs2 nfe -- nfs3 nfs4 )
Repeat the expression zero or more [*] times, return the new outs nfs3 and start nfs4

nfe-one-or-more ( nfs1 nfs2 nfe -- nfs3 nfs4 )
Repeat the expression one or more [+] times, return the new outs nfs3 and start nfs4

nfe-close ( nfs1 nfs2 nfe -- nfs3 )
Close the expression by adding the match state, return the start nfs3

Matching words

nfe-match? ( c-addr u flag nfe -- flag )
Match a string c-addr u, with the flag indicating case insensitive match, return the match result

nfe-search ( c-addr u flag nfe -- n )
Search in the string c-addr u for a match, with the flag indicating case insensitive match, return the first offset for a match, or -1 for no match

nfe-result ( n1 nfe -- n2 n3 )
Get the match result of the n1th grouping, return match start n3 and end n2

Inspection

nfe-dump ( nfe -- )
Dump the expression

generated 10-Apr-2008 by ofcfrth-0.5.0