4 ms·

The only part I agree in this writing is that you don't need to be snarky to be correct. (I'd like to introduce the XY problem of the second kind, where the ans

The only part I agree in this writing is that you don't need to be snarky to be correct. (I'd like to introduce the XY problem of the second kind, where the answerer is so confident that it is the answerer who have missed the actual question.) Some regexes can recognize a language beyond the regular language. They are typically available in two flavors: recursive references (Perl, Ruby, PCRE) and stackable captures (.NET). They are obscure enough that I would not recommend them, but it is patently false that regular expressions (EDIT: of the practical interest) cannot be recursive. It is possible to match individual HTML tags with regexes, but it is difficult. It cannot use a bare `\w` or `\s` because both XML/XHTML and HTML5 parsers have peculiar definitions for tag name characters and space characters. For example your `\s` will typically match various Unicode space characters, while only ASCII whitespaces are recognized in tags. There are also several notable exceptions to the parser (and external states termed the "tree construction"), so missing any of them would result in an immediate XSS. If you think you can write a correct regex for HTML tags, my quizzes [1] should make you concerned. Limiting the question to XHTML does alleviate some but not all concerns. The distinction between recognition and parsing is correct, but parsing doesn't necessarily mean the reconstruction of parse tree. Parsing means the access to constituent nonterminals, which can be used to reconstruct parse tree but also directly used as their own (e.g. calculators). Indeed in most regex implementations you can't extract two or more strings out of each capture (Raku is a notable exception), so you can match against e.g. `(\w+)(?:,(\w+))*` but can't extract a list of comma-separated words with it. Practically speaking this means you can't extract a list of attributes with a single regex, making it unsuitable for HTML parsing anyway. [1] https://news.ycombinator.com/item?id=26355451 https://news.ycombinator.com/item?id=26355451

dataflow 6y ago
> it is patently false that regular expressions cannot be recursive. No, it's more like the term "regular expression" has gotten hijacked and nowadays gets abused to colloquially include, shall we say, irregular expressions. i.e. people basically say "regex" when they mean "some succinct pattern language with syntax similarities to (classical) regular expressions".
- lifthrasiir 6y ago
  Regular expressions in the formal language theory do not have captures anyway. The name collision is unfortunate, but we have already established that regexes in practice means a pattern language largely modelled after theoretical regular expressions and not the theoretical regular expressions themselves. At the very least the writing could have mentioned this discrepancy.
  - dataflow 6y ago
    Captures are a red herring here. They don't fundamentally alter the nature of what a regex does, which is to recognize regular languages. Pointing to them as if they're some kind of justification is like calling pilots "drivers" because drivers originally drove wagons, and wagons didn't have rubber tires like cars and planes anyway. It's completely missing that the point of the distinction between a plane and a wagon has always been the land vs. air travel, not modern features like tires or the infotainment systems or what have you. But yes I guess it'd have been better for the writing to mention the discrepancy in any case.
    - nixpulvis 6y ago
      On a related note, lookaheads (and behinds) do somewhat change the fundamental expressive power I believe.
    - lifthrasiir 6y ago
      > They don't fundamentally alter the nature of what a regex does, which is to recognize regular languages. It's a bit subjective but captures are harder than recognition. Russ Cox has once noted [1] that the extraction has to be run as a separate step after the recognition and a fast DFA can't always be used for that, suggesting they are related but different problems. [1] https://swtch.com/~rsc/regexp/regexp3.html https://swtch.com/~rsc/regexp/regexp3.html
      - mannykannot 6y ago
        Well, if you allow an arbitrary depth of capture-group nesting, then that may be so, but it seems beside the point here. It is not clear to me that this article makes any point about extraction that is relevant to this discussion.

dataflow 6y ago

> it is patently false that regular expressions cannot be recursive. No, it's more like the term "regular expression" has gotten hijacked and nowadays gets abused to colloquially include, shall we say, irregular expressions. i.e. people basically say "regex" when they mean "some succinct pattern language with syntax similarities to (classical) regular expressions".

lifthrasiir 6y ago
Regular expressions in the formal language theory do not have captures anyway. The name collision is unfortunate, but we have already established that regexes in practice means a pattern language largely modelled after theoretical regular expressions and not the theoretical regular expressions themselves. At the very least the writing could have mentioned this discrepancy.
- dataflow 6y ago
  Captures are a red herring here. They don't fundamentally alter the nature of what a regex does, which is to recognize regular languages. Pointing to them as if they're some kind of justification is like calling pilots "drivers" because drivers originally drove wagons, and wagons didn't have rubber tires like cars and planes anyway. It's completely missing that the point of the distinction between a plane and a wagon has always been the land vs. air travel, not modern features like tires or the infotainment systems or what have you. But yes I guess it'd have been better for the writing to mention the discrepancy in any case.
  - nixpulvis 6y ago
    On a related note, lookaheads (and behinds) do somewhat change the fundamental expressive power I believe.
  - lifthrasiir 6y ago
    > They don't fundamentally alter the nature of what a regex does, which is to recognize regular languages. It's a bit subjective but captures are harder than recognition. Russ Cox has once noted [1] that the extraction has to be run as a separate step after the recognition and a fast DFA can't always be used for that, suggesting they are related but different problems. [1] https://swtch.com/~rsc/regexp/regexp3.html https://swtch.com/~rsc/regexp/regexp3.html
    - mannykannot 6y ago
      Well, if you allow an arbitrary depth of capture-group nesting, then that may be so, but it seems beside the point here. It is not clear to me that this article makes any point about extraction that is relevant to this discussion.