#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< NFAState >	fStates

std::vector< int >	fStartStates

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.

                                         {
        std::vector<int> accept;
        // we reserve token 0 for END_OF_FILE, so this starts at 1
        accept.push_back(this->addState(NFAState(++fRegexCount)));
        std::vector<int> startStates = regex.createStates(this, accept);
        fStartStates.insert(fStartStates.end(), startStates.begin(), startStates.end());
        return fStartStates.size() - 1;
    }

◆ 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.

                             {
        fStates.push_back(std::move(s));
        return fStates.size() - 1;
    }

◆ 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.

                                {
    std::vector<int> states = fStartStates;
    for (size_t i = 0; i < s.size(); ++i) {
        std::vector<int> next;
        for (int id : states) {
            if (fStates[id].accept(s[i])) {
                for (int nextId : fStates[id].fNext) {
                    if (fStates[nextId].fKind != NFAState::kRemapped_Kind) {
                        next.push_back(nextId);
                    } else {
                        next.insert(next.end(), fStates[nextId].fData.begin(),
                                    fStates[nextId].fData.end());
                    }
                }
            }
        }
        if (!next.size()) {
            return INVALID;
        }
        states = next;
    }
    int accept = INVALID;
    for (int id : states) {
        if (fStates[id].fKind == NFAState::kAccept_Kind) {
            int result = fStates[id].fData[0];
            if (accept == INVALID || result < accept) {
                accept = result;
            }
        }
    }
    return accept;
}

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:

third_party/skia/src/sksl/lex/NFA.h
third_party/skia/src/sksl/lex/NFA.cpp

Public Member Functions

Public Attributes