Compiler API Reference
sun::parsing::DFA

sun::parsing::DFA

class · Source (opens in a new tab)

class sun::parsing::DFA

Lazily determinized NFA (subset construction with a transition cache)

A DFA state is a set of NFA states. Transitions are materialized the first time they are taken and then cached, so a scan costs one array load per input byte instead of a walk over the NFA's active set. The state count is bounded by the regex, not by the input.

Captures survive determinization because the NFA's capture bookkeeping only ever depended on which states are active, not on the path taken: a group's candidate start is written by any active enterGroup state and its end is committed by any active exitGroup state (both single global slots per group id). Those are properties of the state set, so they are precomputed per DFA state. This reproduces the NFA's semantics exactly, including its "last writer wins per group id" approximation. Path-accurate captures would need a tagged DFA with per-transition register copies; that is not built here.

The Lexer bypasses captures entirely and uses acceptKind()/step() directly.

Types

Public Functions

DFA

public · function · Source (opens in a new tab)

sun::parsing::DFA::DFA(NFA nfa)

Creates a deterministic matcher from a nondeterministic automaton.

Related: NFA

acceptKind

public · function · Source (opens in a new tab)

int32_t sun::parsing::DFA::acceptKind(int32_t s) const

Token kind of the alternative accepted in this state, or kNoAccept.

Related: Token

acceptingState

public · function · Source (opens in a new tab)

bool sun::parsing::DFA::acceptingState(int32_t s) const

Returns the acceptance information for a deterministic state.

bestCapture

public · function · Source (opens in a new tab)

const RegexCapture * sun::parsing::DFA::bestCapture() const

Winning capture of the current scan: longest match among NAMED groups, ties broken by lowest numeric group name (= token declaration order).

Related: RegexCapture

canReachAcceptingWithNonEmptyInput

public · function · Source (opens in a new tab)

bool sun::parsing::DFA::canReachAcceptingWithNonEmptyInput() const

Reports whether a nonempty continuation can reach an accepting state.

captureFor

public · function · Source (opens in a new tab)

const RegexCapture * sun::parsing::DFA::captureFor(int groupIdx) const

Capture recorded for a group in the current scan, or nullptr.

Related: RegexCapture, Capture

fullReset

public · function · Source (opens in a new tab)

void sun::parsing::DFA::fullReset()

Clears matching progress and restores the initial position.

isDead

public · function · static · Source (opens in a new tab)

static bool sun::parsing::DFA::isDead(int32_t s)

Reports whether a state cannot continue a match.

matches

public · function · Source (opens in a new tab)

bool sun::parsing::DFA::matches(const std::string &input)

Reports whether the automaton accepts the complete input string.

resetToPosition

public · function · Source (opens in a new tab)

void sun::parsing::DFA::resetToPosition(sun::support::Position pos)

Restarts matching at the supplied source position.

Related: sun::support::Position

simulate

public · function · Source (opens in a new tab)

void sun::parsing::DFA::simulate(const std::string &input)

Runs the automaton over the supplied input text.

startState

public · function · Source (opens in a new tab)

int32_t sun::parsing::DFA::startState() const

Returns the state from which matching begins.

stateCount

public · function · Source (opens in a new tab)

int sun::parsing::DFA::stateCount() const

Returns the number of deterministic states created so far.

step

step(int32_t s, unsigned char c)

public · function · Source (opens in a new tab)

int32_t sun::parsing::DFA::step(int32_t s, unsigned char c)

Consumes a character and advances to the corresponding automaton state.

step(char c)

public · function · Source (opens in a new tab)

bool sun::parsing::DFA::step(char c)

Consumes a character and advances to the corresponding automaton state.

transitionMisses

public · function · Source (opens in a new tab)

long long sun::parsing::DFA::transitionMisses() const

Returns the number of transitions requiring uncached computation.

Public Fields

isAccepting

public · variable · Source (opens in a new tab)

bool sun::parsing::DFA::isAccepting = false

No documentation comment.

kAlphabet

public · variable · static · Source (opens in a new tab)

int sun::parsing::DFA::kAlphabet = 256

No documentation comment.

kDead

public · variable · static · Source (opens in a new tab)

int32_t sun::parsing::DFA::kDead = 0

No documentation comment.

kNoAccept

public · variable · static · Source (opens in a new tab)

int32_t sun::parsing::DFA::kNoAccept = -1

No documentation comment.

kUncomputed

public · variable · static · Source (opens in a new tab)

int32_t sun::parsing::DFA::kUncomputed = -1

No documentation comment.

Private Functions

addClosure

private · function · Source (opens in a new tab)

void sun::parsing::DFA::addClosure(int32_t id)

Adds a state and the states reachable through empty transitions.

intern

private · function · Source (opens in a new tab)

int32_t sun::parsing::DFA::intern(const std::vector< int32_t > &set)

Look up a sorted state set, creating the DFA state if it is new.

Related: DFA

materialize

private · function · Source (opens in a new tab)

int32_t sun::parsing::DFA::materialize(int32_t from, unsigned char c)

Compute and cache the transition out of from on byte c.

Private Fields

acceptKind_

private · variable · Source (opens in a new tab)

std::vector<int32_t> sun::parsing::DFA::acceptKind_

No documentation comment.

accepting_

private · variable · Source (opens in a new tab)

std::vector<uint8_t> sun::parsing::DFA::accepting_

No documentation comment.

canExtend_

private · variable · Source (opens in a new tab)

std::vector<uint8_t> sun::parsing::DFA::canExtend_

No documentation comment.

candidateGen_

private · variable · Source (opens in a new tab)

std::vector<uint32_t> sun::parsing::DFA::candidateGen_

No documentation comment.

candidateStart_

private · variable · Source (opens in a new tab)

std::vector<sun::support::Position> sun::parsing::DFA::candidateStart_

No documentation comment.

Related: sun::support::Position

captureGen_

private · variable · Source (opens in a new tab)

std::vector<uint32_t> sun::parsing::DFA::captureGen_

No documentation comment.

captureSlots_

private · variable · Source (opens in a new tab)

std::vector<RegexCapture> sun::parsing::DFA::captureSlots_

No documentation comment.

Related: RegexCapture

cur_

private · variable · Source (opens in a new tab)

int32_t sun::parsing::DFA::cur_ = kDead

No documentation comment.

Related: kDead

enterOff_

private · variable · Source (opens in a new tab)

std::vector<int32_t> sun::parsing::DFA::enterOff_

No documentation comment.

enterPool_

private · variable · Source (opens in a new tab)

std::vector<int32_t> sun::parsing::DFA::enterPool_

No documentation comment.

exitOff_

private · variable · Source (opens in a new tab)

std::vector<int32_t> sun::parsing::DFA::exitOff_

No documentation comment.

exitPool_

private · variable · Source (opens in a new tab)

std::vector<ExitInfo> sun::parsing::DFA::exitPool_

No documentation comment.

Related: ExitInfo

gen_

private · variable · Source (opens in a new tab)

uint32_t sun::parsing::DFA::gen_ = 0

No documentation comment.

interner_

private · variable · Source (opens in a new tab)

std::unordered_map<std::vector<int32_t>, int32_t, SetHash> sun::parsing::DFA::interner_

No documentation comment.

Related: SetHash

markGen_

private · variable · Source (opens in a new tab)

uint32_t sun::parsing::DFA::markGen_ = 0

No documentation comment.

mark_

private · variable · Source (opens in a new tab)

std::vector<uint32_t> sun::parsing::DFA::mark_

No documentation comment.

misses_

private · variable · Source (opens in a new tab)

long long sun::parsing::DFA::misses_ = 0

No documentation comment.

nfa_

private · variable · Source (opens in a new tab)

NFA sun::parsing::DFA::nfa_

No documentation comment.

Related: NFA

position_

private · variable · Source (opens in a new tab)

sun::support::Position sun::parsing::DFA::position_

No documentation comment.

Related: sun::support::Position

scratch_

private · variable · Source (opens in a new tab)

std::vector<int32_t> sun::parsing::DFA::scratch_

No documentation comment.

sets_

private · variable · Source (opens in a new tab)

std::vector<std::vector<int32_t> > sun::parsing::DFA::sets_

No documentation comment.

start_

private · variable · Source (opens in a new tab)

int32_t sun::parsing::DFA::start_ = kDead

No documentation comment.

Related: kDead

trans_

private · variable · Source (opens in a new tab)

std::vector<int32_t> sun::parsing::DFA::trans_

No documentation comment.

Compiler API Reference