Flutter Engine
The Flutter Engine
Public Member Functions | Public Attributes | List of all members
NFA Struct Reference

#include <NFA.h>

Public Member Functions

int addRegex (const RegexNode &regex)
 
int addState (NFAState s)
 
int match (std::string s) const
 

Public Attributes

int fRegexCount = 0
 
std::vector< NFAStatefStates
 
std::vector< intfStartStates
 

Detailed Description

A nondeterministic finite automaton for matching regular expressions. The NFA is initialized with a number of regular expressions, and then matches a string against all of them simultaneously.

Definition at line 22 of file NFA.h.

Member Function Documentation

◆ addRegex()

int NFA::addRegex ( const RegexNode regex)
inline

Adds a new regular expression to the set of expressions matched by this automaton, returning its index.

Definition at line 27 of file NFA.h.

27 {
28 std::vector<int> accept;
29 // we reserve token 0 for END_OF_FILE, so this starts at 1
30 accept.push_back(this->addState(NFAState(++fRegexCount)));
31 std::vector<int> startStates = regex.createStates(this, accept);
32 fStartStates.insert(fStartStates.end(), startStates.begin(), startStates.end());
33 return fStartStates.size() - 1;
34 }
std::vector< int > fStartStates
Definition: NFA.h:55
int addState(NFAState s)
Definition: NFA.h:39
int fRegexCount
Definition: NFA.h:51

◆ addState()

int NFA::addState ( NFAState  s)
inline

Adds a new state to the NFA, returning its index.

Definition at line 39 of file NFA.h.

39 {
40 fStates.push_back(std::move(s));
41 return fStates.size() - 1;
42 }
struct MyStruct s
std::vector< NFAState > fStates
Definition: NFA.h:53

◆ match()

int NFA::match ( std::string  s) const

Matches a string against all of the regexes added to this NFA. Returns the index of the first (in addRegex order) matching expression, or -1 if no match. This is relatively slow and used only for debugging purposes; the NFA should be converted to a DFA before actual use.

Definition at line 13 of file NFA.cpp.

13 {
14 std::vector<int> states = fStartStates;
15 for (size_t i = 0; i < s.size(); ++i) {
16 std::vector<int> next;
17 for (int id : states) {
18 if (fStates[id].accept(s[i])) {
19 for (int nextId : fStates[id].fNext) {
20 if (fStates[nextId].fKind != NFAState::kRemapped_Kind) {
21 next.push_back(nextId);
22 } else {
23 next.insert(next.end(), fStates[nextId].fData.begin(),
24 fStates[nextId].fData.end());
25 }
26 }
27 }
28 }
29 if (!next.size()) {
30 return INVALID;
31 }
32 states = next;
33 }
34 int accept = INVALID;
35 for (int id : states) {
36 if (fStates[id].fKind == NFAState::kAccept_Kind) {
37 int result = fStates[id].fData[0];
38 if (accept == INVALID || result < accept) {
39 accept = result;
40 }
41 }
42 }
43 return accept;
44}
Instance * fNext
#define INVALID
Definition: LexUtil.h:13
static float next(float f)
GAsyncResult * result
@ kRemapped_Kind
Definition: NFAState.h:27
@ kAccept_Kind
Definition: NFAState.h:20
const uintptr_t id

Member Data Documentation

◆ fRegexCount

int NFA::fRegexCount = 0

Definition at line 51 of file NFA.h.

◆ fStartStates

std::vector<int> NFA::fStartStates

Definition at line 55 of file NFA.h.

◆ fStates

std::vector<NFAState> NFA::fStates

Definition at line 53 of file NFA.h.


The documentation for this struct was generated from the following files: