Irregular Expressions
tavianator.com
tavianator.com
It is notable for supporting lispy "SRE" syntax in addition to traditional PCRE syntax, standardized as SRFI 115: https://srfi.schemers.org/srfi-115/srfi-115.html
For readers unfamiliar with nom, it would be even more helpful if the author included reference links, because I was immediately confused about the sudden appearance of the "alt(..)" function scene, seemingly materialized out of thin air (presumably imports omitted for brevity).
If I'm understanding correctly, some Regex features may require implementing more than 21 rules for a thorough and complete implementation.
But for some reason it's customary in rust to stick to a lower number of autogenerated implementations. My first guess would be it might be a compile time issue?
Take, for example, the regex "a|(aa)+" (the set of even length strings of "a"'s or just one "a"). If you use the construction from the article, you get an NFA with basically two arms: one that recognizes "a" and one that recognizes "(aa)+". The initial state contains an epsilon arc to the start state of each of these arms. If you just flip the final/non-final states in each arm, the resulting language contains "a", since we are no longer accepting each even length "a" string, but now each odd length "a" string, of which "a" is a member. Thus the new language is not the proper complement of "a|(aa)+", which would not contain "a".
Perhaps something like “X|!Y” or similar might be impossible?
I suppose you generally accept in an NFA if there is an accepting state epsilon-reachable, so if you flip the accepting states, you could still have an accepting state epsilon-reachable, which is why this doesn't work. In an DFA, there is only one state that's (trivially) epsilon-reachable, so the construction works.
On the other hand, you can have an unambiguous [1] NFA (for example, a DFA, but you insert some dummy epsilon transitions between a split up state) where you can just flip the final/non-final states and complement the language.
So, in the end, complementing languages described by NFAs without determinizing them first is a bit of a tricky problem.
[1]: https://en.wikipedia.org/wiki/Unambiguous_finite_automaton --- a superset of DFAs, but they can have epsilon transitions
But you can't always complement the language easily for an UFA either, right? The path to an accepting state may be unambiguous, but there could at the same time be a path to a non-accepting state, so flipping the states may keep some words in the language. And make the automaton even ambiguous.
Interestingly neither re2 nor Rust regex perform capturing in DFAs. Rather, a DFA is used to locate the end of a match, the DFA is used again to determine the beginning of the match, and then an NDFA is used to match a third time, to extract the capture groups.
... but I haven't found them particularly accessible. And it's not clear it's a viable strategy in a general purpose regex engine. Namely, I'm not sure how much bigger it makes the DFA.
Also, AFAIK, these aren't DFAs. They are different theoretical structures with explicitly more power.
> and then an NDFA is used to match a third time, to extract the capture groups.
That's the PikeVM. It's an NFA simulation. Although it uses additional storage and is otherwise more computationally powerful than just a plain NFA.
That paper claims to be "the first practical submatch extraction and parsing algorithm based on DFA" and it came out only last year! It shows how new this theory is.
Firstly, the nice part about DFAs is that they're really simple to implement - in terms of capture groups bare in mind that the generation mechanism means that the nodes are probably super-positions, and the extracts across aspects of your language can intersect if you're not careful.
You can get into messy places really quickly - so I'd suggest not fucking with the machine directly.
However, there's one thing that you can do without compromising machine generation: add a processing mode that returns the trace of machine states for the matching string.
And then process that state trace.
Now bare in mind that some of the states that you went through might have been super-positions, so you don't quite know what they are.
But (now that you have a match) you can run the reverse of the match through the reverse of the network and intersect the reverse of its trace.
(I haven't actually done that, but it will clean up some trace ambiguity - where earlier branches were only later found not to have been taken.)
How did you know that your article was posted? Do you have a program to alert you of mentions?
I could point out the flaw and it would fix it, but introduce another.
However, I got enough out of it to rewrite it myself.