dfa.hpp File Reference

real::dfa — a maximal-munch DFA over a set of patterns (opt-in). More...

#include "real/version.hpp"
#include <array>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <optional>
#include <span>
#include <stdexcept>
#include <string>
#include <string_view>
#include <vector>
#include "real/core/config.hpp"
#include "real/real.hpp"

Include dependency graph for dfa.hpp:

Go to the source code of this file.

Classes
class	real::dfa_error
	Thrown when a pattern cannot be represented as a DFA. More...
struct	real::dfa_match
	The outcome of dfa::match — which rule won, and how many bytes it spans. More...
struct	real::detail::dfa_instr
	A flattened NFA instruction (global PCs, global class index). More...
struct	real::detail::dfa_nfa
	The union NFA over all the patterns, flattened into one address space. More...
struct	real::detail::dfa_byte_classes
	Computes byte-equivalence classes: two bytes are equivalent iff they satisfy the same consuming predicates (every klass test and every byte literal). Reduces the alphabet so the DFA is built over classes, not 256. More...
struct	real::detail::dfa_tables
	The baked DFA tables produced by dfa_build. More...
class	real::dfa
	A maximal-munch DFA over an ordered set of patterns. More...

Namespaces
namespace	real
namespace	real::detail

Typedefs
using	real::detail::dfa_set = std::vector< std::uint64_t >
	A set of NFA PCs as a bitset (one per DFA state during construction).

Functions
dfa_nfa	real::detail::dfa_flatten (std::span< const program_view > programs)
	Flattens programs into one union NFA, auditing DFA-ability.
void	real::detail::dfa_set_bit (dfa_set &s, std::size_t i)
bool	real::detail::dfa_test_bit (const dfa_set &s, std::size_t i)
dfa_set	real::detail::dfa_closure (const dfa_nfa &nfa, const std::vector< std::uint32_t > &seeds, bool at_start)
	The epsilon-closure of seeds (a PC list), as a canonical PC bitset. at_start follows a text_start assertion (true only at offset 0).
dfa_set	real::detail::dfa_move (const dfa_nfa &nfa, const dfa_set &set, std::uint8_t rep)
	The move on the byte rep: ε-closure of the successors of every PC in set that consumes rep.
std::int64_t	real::detail::dfa_accept_of (const dfa_nfa &nfa, const dfa_set &set)
	The accepting rule of a state set: the SMALLEST rule index among its match PCs (the order tie-break), or -1 if none accept.
dfa_byte_classes	real::detail::dfa_compute_classes (const dfa_nfa &nfa)
dfa_tables	real::detail::dfa_build (std::span< const program_view > programs, std::size_t state_cap=max_dfa_states)
	Subset construction over byte-classes, then Moore minimization (initial partition by accept tag, so distinct rule tags never merge).

Variables
constexpr std::uint32_t	real::detail::dfa_no_rule {std::numeric_limits<std::uint32_t>::max()}

Detailed Description

real::dfa — a maximal-munch DFA over a set of patterns (opt-in).

A lexer matches many rules at every position; running each rule's Pike VM in turn is linear but re-scans the input once per candidate rule. real::dfa fuses a set of patterns into one deterministic automaton that recognizes the winning rule in a single left-to-right pass — the same maximal-munch decision (longest match; ties to the earliest rule), reached far faster when many rules share leading bytes. It is built from the patterns' compiled programs, runs at run time (the tables are heap-allocated once and then immutable), and is the accelerated rule-dispatch path SciLex opts into.

Note

NOT the internal real::detail::lazy_dfa (automata/lazy_dfa.hpp): that one is a private, priority-preserving forward DFA that finds a single pattern's match boundary for the Pike route. This real::dfa is a public, capture-free maximal-munch recognizer over a whole rule set.

Scope: a pattern is DFA-able iff its program holds no zero-width assertion other than a leading \A/^ (a no-op under anchored scanning). A pattern with any other assertion ($, \b, multiline ^/$, …) is not representable as a pure DFA; the constructor throws real::dfa_error rather than silently mis-recognizing — the caller keeps such rules on the Pike VM. Lazy/greedy makes no difference to a DFA: it recognizes the pattern's language and takes the longest match, which is the lexer's munch for greedy rules but not for lazy ones (whose match() is the shortest) — so the caller must only feed DFA-faithful (greedy, assertion-free) rules. Include this header explicitly; real.hpp does not.

Definition in file dfa.hpp.