Classes | Defines | Typedefs | Enumerations
rexdfa.h File Reference

Definition of DFA interface. More...

Go to the source code of this file.

Classes

struct  rexdfss_s
struct  rexdft_s
struct  rexdfs_s
struct  rexdfa_s

Defines

#define REX_DFA_DEADSTATE   (0)
#define REX_DFA_STARTSTATE   (1)
#define REX_DFA_STATE(__dfa__, __nstate__)   (&(__dfa__)->states[__nstate__])
#define REX_DFA_TRANSITION(__dfa__, __nstate__, __ntrans__)   (&(__dfa__)->trans[(REX_DFA_STATE(__dfa__, __nstate__)->trans) + (__ntrans__)])
#define REX_DFA_SUBSTATE(__dfa__, __nstate__, __nsubstate__)   ((__dfa__)->substates ? &(__dfa__)->substates[REX_DFA_STATE(__dfa__, __nstate__)->substates + (__nsubstate__)] : ((rexdfss_t*)0))
#define REX_DFA_ACCSUBSTATE(__dfa__, __nstate__, __naccsubstate__)   ((__dfa__)->accsubstates ? &(__dfa__)->accsubstates[REX_DFA_STATE(__dfa__, __nstate__)->accsubstates + (__naccsubstate__)] : ((rexdfss_t*)0))
#define REX_DFA_NEXT(__dfa__, __nstate__, __input__, __nextptr__)

Typedefs

typedef struct rexdfss_s rexdfss_t
typedef struct rexdft_s rexdft_t
typedef struct rexdfs_s rexdfs_t
typedef struct rexdfa_s rexdfa_t

Enumerations

enum  rex_statetype_t { REX_STATETYPE_NONE = 0, REX_STATETYPE_START = 1, REX_STATETYPE_ACCEPT = 2, REX_STATETYPE_DEAD = 3 }

Detailed Description

Definition of DFA interface.

Synopsis

This file defines the data structures and the macros for the DFA implementation.


Define Documentation

#define REX_DFA_ACCSUBSTATE (   __dfa__,
  __nstate__,
  __naccsubstate__ 
)    ((__dfa__)->accsubstates ? &(__dfa__)->accsubstates[REX_DFA_STATE(__dfa__, __nstate__)->accsubstates + (__naccsubstate__)] : ((rexdfss_t*)0))

Get a pointer to rexdfss_t accepting sub-state.

Parameters:
__dfa__Pointer to rexdfa_t object
__nstate__State ID returned from REX_DFA_NEXT or REX_DFA_STARTSTATE
__naccsubstate__Sub-state offset in the array of accepting sub-states for the specified state. This parameter must be from 0 to rexdfs_t::naccsubstates - 1.
Returns:
Pointer to rexdfss_t accepting substate.
Examples:
js-tokenizer.c.
#define REX_DFA_DEADSTATE   (0)

DFA Dead State ID, In rexdfa_t object the state at offset 0 is always the dead state

Examples:
js-tokenizer.c.
#define REX_DFA_NEXT (   __dfa__,
  __nstate__,
  __input__,
  __nextptr__ 
)
Value:
do { \
                        rexdft_t *t; \
                        rexuint_t mid, min = 0, max = REX_DFA_STATE(__dfa__, __nstate__)->ntrans; \
                        while (max > min) { \
                                mid = (min + max)/2; \
                                t = REX_DFA_TRANSITION(__dfa__, __nstate__, mid); \
                                if ((__input__) >= t->lowin) { \
                                        min = mid + 1; \
                                } else { \
                                        max = mid; \
                                } \
                        } \
                        t = REX_DFA_TRANSITION(__dfa__, __nstate__, min-1); \
                        *(__nextptr__) = t->state; \
                } while (0)

Get the next state ID in the DFA for the specified input. The macro will search through the transitions of the current state to find the next state of the DFA for the specified input. The next state will be assigned to *(__nextptr__).

Parameters:
__dfa__Pointer to rexdfa_t object
__nstate__Current state of the DFA.
__input__Current input
__nextptr__Output the next state in here
Returns:
The next state of the DFA for the specified input is written in __nextptr__
Examples:
js-tokenizer.c.
#define REX_DFA_STARTSTATE   (1)

DFA Start State ID, In rexdfa_t object the start state is always at offset 1

Examples:
js-tokenizer.c.
#define REX_DFA_STATE (   __dfa__,
  __nstate__ 
)    (&(__dfa__)->states[__nstate__])

Get a pointer to rexdfa_t state.

Parameters:
__dfa__Pointer to rexdfa_t object
__nstate__State ID returned from REX_DFA_NEXT or REX_DFA_DEADSTATE, REX_DFA_STARTSTATE
Returns:
Pointer to rexdfa_t
Examples:
js-tokenizer.c.
#define REX_DFA_SUBSTATE (   __dfa__,
  __nstate__,
  __nsubstate__ 
)    ((__dfa__)->substates ? &(__dfa__)->substates[REX_DFA_STATE(__dfa__, __nstate__)->substates + (__nsubstate__)] : ((rexdfss_t*)0))

Get a pointer to rexdfss_t sub-state. This macro would only work if the DFA is generated with its NFA sub-states.

Parameters:
__dfa__Pointer to rexdfa_t object
__nstate__State ID returned from REX_DFA_NEXT or REX_DFA_STARTSTATE
__nsubstate__Sub-state offset in the array of sub-states for the specified state. This parameter must from 0 to rexdfs_t::nsubstates - 1.
Returns:
Pointer to rexdfss_t substate.
#define REX_DFA_TRANSITION (   __dfa__,
  __nstate__,
  __ntrans__ 
)    (&(__dfa__)->trans[(REX_DFA_STATE(__dfa__, __nstate__)->trans) + (__ntrans__)])

Get a pointer to rexdft_t transition. This macro is used internally to find a transition to the next state.

Parameters:
__dfa__Pointer to rexdfa_t object
__nstate__State ID returned from REX_DFA_NEXT or REX_DFA_DEADSTATE, REX_DFA_STARTSTATE
__ntrans__Transition offset in the array of transitions for the specified state. This parameter must be from 0 to rexdfs_t::ntrans - 1.
Returns:
Pointer to rexdft_t transition

Typedef Documentation

typedef struct rexdfa_s rexdfa_t

Define DFA.

typedef struct rexdfs_s rexdfs_t

State definition

typedef struct rexdfss_s rexdfss_t

Define DFA sub-state.

typedef struct rexdft_s rexdft_t

Define DFA transition.


Enumeration Type Documentation

Definition of state types.

Enumerator:
REX_STATETYPE_NONE 

There is nothing interesting about this state

REX_STATETYPE_START 

This state is marked as starting point for the automaton

REX_STATETYPE_ACCEPT 

This type indicates that one or more regular expressions compiled in the automaton matched.

REX_STATETYPE_DEAD 

The automaton is in the dead state(all transitions lead back to the same state)