Hacker News Reader

Comment by Rokid | Hacker News Reader

What is this? I'm so curious but nothing of this rings a bell with me. I mean I know what a regular expression is, and I've formatted several USBs to FAT32, but DFAs and everything in between have me Googling like crazy, still in the dark though.

View on HN

It converts your regexp into a virtual filesystem and then you can test if a string matches the regexp by converting the string into a path and testing if that path is contained in the filesystem.

Presumably this is useful if you can place files into (or modify a file at) the location for a particular regexp.

That wouldn’t work. This works by hard linking a lot of directories to each other, so if you were to write a file there, it ends up in multiple locations (possibly all ‘directories’ in the file system)

The file system could work around that by creating new unique directories whenever you write any file to an empty directory, but that would require it to keep the regular expression it represents around, and would fill up the file system quite rapidly.

I wouldn't necessarily call this useful for anything in particular. It's more of a silly trick to show off than anything. (And a reminder of how regexes work behind the scenes.)

RegExp and DFAs are the same computation class, so it's useful sometimes to model them as each other.

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).

It’s frequently useful, as many regex engines construct DFAs under the hood :)

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.

This was what made it all make sense for me:

https://perl.plover.com/Regex/article.html

Reply on news.ycombinator.com