most of the crazy email regexes found here https://stackoverflow.com/questions/201323/how-to-validate-a... fail to validate in the input field
Only regular expressions[0] can compile to FST's; Perl-style regexes aren't regular.
Show HN: Regular expression compilation visualized
21–30 of 40 posts
Re: Show HN: Regular expression compilation visualized
#22This led me to look into sexpr based regular expressions, and indeed there are some. SRFI 115 seems pretty neat example: https://srfi.schemers.org/srfi-115/srfi-115.html
See also https://www.emacswiki.org/emacs/rx
Re: Show HN: Regular expression compilation visualized
#23What are the limitations of regular expressions compiled in this way, compared to things like Python’s `re` module? Is it just that they can’t support backreferences?
Re: Show HN: Regular expression compilation visualized
#24most of the crazy email regexes found here https://stackoverflow.com/questions/201323/how-to-validate-a... fail to validate in the input field
If you want crazy, you should look up RegEx match open tags except XHTML self-contained tags.
Re: Show HN: Regular expression compilation visualized
#25What are the limitations of regular expressions compiled in this way, compared to things like Python’s `re` module? Is it just that they can’t support backreferences?
Too many to enumerate, already the utter lack of Unicode is a killer. The tool supports only the academic interpretation of regular expressions that are strictly equivalent to some NFA/state machine, which is useless because in the last forty years we use programming languages and libraries with extended abilities to deal with real world problems.
Some programmers have adopted to vernacular "regular expression" for the former and "regex" for the latter for easier distinction, see quote in http://enwp.org/Regexen#Patterns_for_non-regular_languages
Re: Show HN: Regular expression compilation visualized
#26I wonder what the state of the art is in regex compilation? It feels to me like it shouldn’t be compilation to a program that processes one character at a time as you’ll be doing a lot of branches and so can’t process the data that fast. It feels like there ought to be a way to take advantage of ILP or SIMD operations. Maybe regex just doesn’t matter enough for that to be important.
> It feels to me like it shouldn’t be compilation to a program that processes one character at a time
High performance regex engines do use SIMD in various places. Others have mentioned Hyperscan, which is undoubtedly a showcase of the most sophisticated SIMD techniques when it comes to regex and substring searching. But even something like RE2 uses vectorized code in places, although indirectly.
But, in all instances I can think of, using SIMD is a matter of identifying some optimization opportunity in regex matching that doesn't generalize to handling all cases. At some point, to handle some cases, you'll need that "one character at a time" loop. (Whether it's backtracking or FSM based.) So visualizations like these are still rather helpful, and at the very least, give a basic conceptual understanding of what the most general kind of FSM-based regex might look like internally. (Although, most general purpose regex engines don't actually utilize all of the transformations presented in the OP.)
Re: Show HN: Regular expression compilation visualized
#27What are the limitations of regular expressions compiled in this way, compared to things like Python’s `re` module? Is it just that they can’t support backreferences?
Too many to enumerate, already the utter lack of Unicode is a killer. The tool supports only the academic interpretation of regular expressions that are strictly equivalent to some NFA/state machine, which is useless because in the last forty years we use programming languages and libraries with extended abilities to deal with real world problems. Some programmers have adopted to vernacular "regular expression" for t…
The tool could be extended to support Unicode, whereas AFAIK it would not be possible to extend it to support backreferences. Are there any other “regex” features that would be impossible to support?
Re: Show HN: Regular expression compilation visualized
#28What are the limitations of regular expressions compiled in this way, compared to things like Python’s `re` module? Is it just that they can’t support backreferences?
Too many to enumerate, already the utter lack of Unicode is a killer. The tool supports only the academic interpretation of regular expressions that are strictly equivalent to some NFA/state machine, which is useless because in the last forty years we use programming languages and libraries with extended abilities to deal with real world problems. Some programmers have adopted to vernacular "regular expression" for t…
Real regular expressions are hardly useless, I speculate that majority of real world uses of regexp are actually regular. Many of state of art regex engines (re2, hyperscan, rust regex) support only regular expressions
Re: Show HN: Regular expression compilation visualized
#29Earlier quoted context omitted.
Too many to enumerate, already the utter lack of Unicode is a killer. The tool supports only the academic interpretation of regular expressions that are strictly equivalent to some NFA/state machine, which is useless because in the last forty years we use programming languages and libraries with extended abilities to deal with real world problems. Some programmers have adopted to vernacular "regular expression" for t…
The tool could be extended to support Unicode, whereas AFAIK it would not be possible to extend it to support backreferences. Are there any other “regex” features that would be impossible to support?
>> Too many to enumerate
I take back my previous claim, this is a wrong exaggeration.
> The tool could be extended to support Unicode
Not an easy task. There are some things in the standard that do not map neatly to states, notably foldcasing of characters that change the count of characters and the treatment of the generic line boundary. Edit: after browsing UTS#18, I am almost certain that a conforming implementation cannot be mapped as exemplified in the tool. Maybe there's a neat work-around possible.
> features that would be impossible to support?
(?=, (?!, (?, (*asr:, (*SKIP)
Re: Show HN: Regular expression compilation visualized
#30Earlier quoted context omitted.
Too many to enumerate, already the utter lack of Unicode is a killer. The tool supports only the academic interpretation of regular expressions that are strictly equivalent to some NFA/state machine, which is useless because in the last forty years we use programming languages and libraries with extended abilities to deal with real world problems. Some programmers have adopted to vernacular "regular expression" for t…
Real regular expressions are hardly useless, I speculate that majority of real world uses of regexp are actually regular. Many of state of art regex engines (re2, hyperscan, rust regex) support only regular expressions
> I speculate that majority of real world uses of regexp are actually regular
I just surveyed a corpus of regexes with a crude static analysis tool and only 4% fit that restriction, I believe the result to be accurate within the order of magnitude. It makes sense: non-regular features are widely available, and thus people use them.
> state of art regex engines (re2, hyperscan, rust regex)
These are a clear regression from the actual state of art that's in use everywhere. (I know that re2's reason for being is precisely to have less features.) The advent of Perl (and related, libpcre) has utterly obliterated the competition at that time, and newcomers were not able to wrest their crown.