Re:Regex2fat: Turn your favorite regex into FAT32
by slondr on Wednesday April 15, 2020 @02:35PM
(#22881318)
RegExp and DFAs are the same computation class, so it's useful sometimes to model them as each other.
[ Parent
| on HN ]
Re:Regex2fat: Turn your favorite regex into FAT32
by Pmop on Wednesday April 15, 2020 @04:20PM
(#22882558)
No idea why you're being downvoted. Also, classical comp. sci technique of reducing your problem into another that's already been solved (with good enough time/mem bounds).
Re:Regex2fat: Turn your favorite regex into FAT32
by saagarjha on Thursday April 16, 2020 @06:07AM
(#22887813)
It’s frequently useful, as many regex engines construct DFAs under the hood :)
Re:Regex2fat: Turn your favorite regex into FAT32
by burntsushi on Thursday April 16, 2020 @07:59AM
(#22888497)
Not as frequent as you might expect! Most regex engines in common use don't use an automata based implementation, and instead use backtracking. This lets them implement additional non-regular features such as backreferences and recursion.
Even automata based regex engines don't usually build up a full DFA, since the size of the DFA may be exponential in the size of the regex. Instead, an NFA similation might be used, or a hybrid NFA/DFA that builds the DFA during match time, but typically doesn't build out the full DFA.