#include <NFAtoDFA.h>

Public Member Functions
	NFAtoDFA (NFA *nfa)

DFA	convert ()

Static Public Attributes
static constexpr char	START_CHAR = 9

static constexpr char	END_CHAR = 126

Detailed Description

Converts a nondeterministic finite automaton to a deterministic finite automaton. Since NFAs and DFAs differ only in that an NFA allows multiple states at the same time, we can find each possible combination of simultaneous NFA states and give this combination a label. These labelled nodes are our DFA nodes, since we can only be in one such unique set of NFA states at a time.

As an NFA can end up in multiple accept states at the same time (for instance, the token "while" is valid for both WHILE and IDENTIFIER), we disambiguate by preferring the first matching regex (in terms of the order in which they were added to the NFA).

Definition at line 32 of file NFAtoDFA.h.

Constructor & Destructor Documentation

◆ NFAtoDFA()

NFAtoDFA::NFAtoDFA ( NFA * nfa )

inline

Definition at line 37 of file NFAtoDFA.h.

38 : fNFA(*nfa) {}

Member Function Documentation

◆ convert()

DFA NFAtoDFA::convert ( )

inline

Returns a DFA created from the NFA.

Definition at line 43 of file NFAtoDFA.h.

                  {
        // create state 0, the "reject" state
        getState(DFAState::Label({}));
        // create a state representing being in all of the NFA's start states at once
        std::vector<int> startStates = fNFA.fStartStates;
        std::sort(startStates.begin(), startStates.end());
        // this becomes state 1, our start state
        DFAState* start = getState(DFAState::Label(startStates));
        this->scanState(start);
 
        this->computeMappings();
 
        int stateCount = 0;
        for (const auto& row : fTransitions) {
            stateCount = std::max(stateCount, (int) row.size());
        }
        return DFA(fCharMappings, fTransitions, fAccepts);
    }

Member Data Documentation

◆ END_CHAR

constexpr char NFAtoDFA::END_CHAR = 126

inlinestaticconstexpr

Definition at line 35 of file NFAtoDFA.h.

◆ START_CHAR

constexpr char NFAtoDFA::START_CHAR = 9

inlinestaticconstexpr

Definition at line 34 of file NFAtoDFA.h.

The documentation for this class was generated from the following file:

third_party/skia/src/sksl/lex/NFAtoDFA.h

Public Member Functions

Static Public Attributes