5 ms·

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 strictl

by bmn__ 6y ago

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 http://enwp.org/Regexen#Patterns_for_non-regular_languages

pansa2 6y ago
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?
- bmn__ 6y ago
  >> 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)
  - abecedarius 6y ago
    Intersection and complement are both expressible in regular expressions (in the CS sense). Is that not what you mean by impossible to support? (I'm too lazy to look up what the other listed notations mean.)
    - bmn__ 6y ago
      > Is that not what you mean no, I mean generic line boundary
  - allanrbo 6y ago
    Some of these are in fact possible, though with some restrictions. I wrote a blog post on how to support some negative lookbehinds: http://allanrbo.blogspot.com/2020/01/alternative-to-negative-lookbehinds-in.html http://allanrbo.blogspot.com/2020/01/alternative-to-negative...
zokier 6y ago
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
- bmn__ 6y ago
  > 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.
  - zokier 6y ago
    PCRE is hardly used "everywhere". Vim switched from backtracking engine to dfa one. Emacs has it's own non-backtracking engine. As does GNU grep. Ripgrep notoriously is built around rust-regex. VSCode uses ripgrep for searches. Google obviously uses its own re2 in its products. Hyperscan has some case studies of its use: https://www.hyperscan.io/2016/01/21/rspamd-1-1-released-hyperscan-support-regex-matching/ https://www.hyperscan.io/2016/01/21/rspamd-1-1-released-hype... https://www.hyperscan.io/2020/09/28/optimize-azure-cloud-security-with-intel-hyperscan/ https://www.hyperscan.io/2020/09/28/optimize-azure-cloud-sec... https://www.hyperscan.io/2018/10/19/hyperscan-adopted-by-github/ https://www.hyperscan.io/2018/10/19/hyperscan-adopted-by-git... Even PCRE itself has a dfa mode. Because people want and use that. It's not just some academic navelgazing. I'm not saying that non-regular engines, pcre in the forefront, are not popular. They are. But at the same time they are not be-all end-all for regex, regular engines still see lot of use especially in performance sensitive applications.
    - bmn__ 6y ago

by bmn__ 6y ago

pansa2 6y ago

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?

bmn__ 6y ago
>> 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)
- abecedarius 6y ago
  Intersection and complement are both expressible in regular expressions (in the CS sense). Is that not what you mean by impossible to support? (I'm too lazy to look up what the other listed notations mean.)
  - bmn__ 6y ago
    > Is that not what you mean no, I mean generic line boundary
- allanrbo 6y ago
  Some of these are in fact possible, though with some restrictions. I wrote a blog post on how to support some negative lookbehinds: http://allanrbo.blogspot.com/2020/01/alternative-to-negative-lookbehinds-in.html http://allanrbo.blogspot.com/2020/01/alternative-to-negative...

zokier 6y ago

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

bmn__ 6y ago
> 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.
- zokier 6y ago
  PCRE is hardly used "everywhere". Vim switched from backtracking engine to dfa one. Emacs has it's own non-backtracking engine. As does GNU grep. Ripgrep notoriously is built around rust-regex. VSCode uses ripgrep for searches. Google obviously uses its own re2 in its products. Hyperscan has some case studies of its use: https://www.hyperscan.io/2016/01/21/rspamd-1-1-released-hyperscan-support-regex-matching/ https://www.hyperscan.io/2016/01/21/rspamd-1-1-released-hype... https://www.hyperscan.io/2020/09/28/optimize-azure-cloud-security-with-intel-hyperscan/ https://www.hyperscan.io/2020/09/28/optimize-azure-cloud-sec... https://www.hyperscan.io/2018/10/19/hyperscan-adopted-by-github/ https://www.hyperscan.io/2018/10/19/hyperscan-adopted-by-git... Even PCRE itself has a dfa mode. Because people want and use that. It's not just some academic navelgazing. I'm not saying that non-regular engines, pcre in the forefront, are not popular. They are. But at the same time they are not be-all end-all for regex, regular engines still see lot of use especially in performance sensitive applications.
  - bmn__ 6y ago