17struct Regex2NfaConverter {
19 : nfa_(std::make_unique<automaton::NFA>()) {}
21 void add_range_transitions(automaton::NFANode* from, automaton::NFANode* to, std::uint16_t lb, std::uint16_t ub) {
22 for (
auto i = lb; i <= ub; ++i)
26 void add_range_transitions(automaton::NFANode* from, automaton::NFANode* to,
const Def* lit0,
const Def* lit1) {
27 auto lb = lit0->as<
Lit>()->
get();
28 auto ub = lit1->as<
Lit>()->
get();
29 add_range_transitions(from, to, lb, ub);
33 convert(
const Def* regex, automaton::NFANode* start, automaton::NFANode* end, automaton::NFANode*
error =
nullptr) {
35 auto middle = nfa_->add_state();
39 add_range_transitions(start, end, 0_u16, 255);
41 add_range_transitions(start, end,
range->arg(0),
range->arg(1));
42 if (
error) add_range_transitions(start,
error, 0, 255);
44 auto first = nfa_->add_state();
45 auto error = nfa_->add_state();
48 auto args = detail::flatten_in_arg<regex::disj>(
not_->arg());
49 std::vector<std::pair<std::uint8_t, std::uint8_t>> ranges;
50 for (
auto& arg : args) {
52 &&
"as per normalizer, if we're in a 'not_' argument, we must only have disjs and ranges!");
57 std::sort(ranges.begin(), ranges.end());
59 for (
auto rng : ranges) {
60 if (rng.first > last) add_range_transitions(first, end, last, rng.first - 1);
61 add_range_transitions(first,
error, rng.first, rng.second);
62 last = std::min(rng.second + 1_u16, 255);
64 if (last < 255) add_range_transitions(first, end, last, 255);
66 auto first = nfa_->add_state();
67 auto error = nfa_->add_state();
68 error->set_erroring(
true);
79 convert(opt->arg(), start, end);
81 auto m1 = nfa_->add_state();
82 auto m2 = nfa_->add_state();
89 auto m0 = nfa_->add_state();
90 auto m1 = nfa_->add_state();
91 auto m2 = nfa_->add_state();
103 void convert(
const Def* regex) {
104 auto start = nfa_->add_state();
105 nfa_->set_start(start);
106 auto end = nfa_->add_state();
111 std::unique_ptr<automaton::NFA> nfa() {
return std::move(nfa_); }
114 std::unique_ptr<automaton::NFA> nfa_;
120 Regex2NfaConverter converter;
121 converter.convert(
regex);
122 return converter.nfa();
void set_accepting(bool accepting)
void add_transition(const NFANode *to, std::uint16_t c)
static auto isa(const Def *def)
static T as(const Def *def)
const Sigma * convert(const TBound< up > *b)
std::unique_ptr< automaton::NFA > regex2nfa(const Def *regex)
void error(Loc loc, const char *f, Args &&... args)
constexpr decltype(auto) get(Span< T, N > span) noexcept
automaton::NFA * regex2nfa(const Def *regex)
You can dl::get this function.