Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solving the regex of madness, and snarky answers on StackOverflow (2019)

cargocultcode.com

Post reply on HN
Print view View original

71–80 of 136 posts

Re: Solving the regex of madness, and snarky answers on StackOverflow (2019)

#71

Post by Rapzid »

SavantIdiot wrote: post #61

Oh I've seen this many times in different forms. Especially with regexes. You know what this is a great example of? A case where hacking makes a mess, and thinking before coding solves the problem. The madness comes from using the wrong tool for the problem. Yes, you can hack a regex to parse XHTML this might be "good enough", but it is more robust, cleaner and easier to explain if you use a lexical tokenizer and a g…

Yeah, and you never actually end up solving the problem. You just end up solving every edge case that comes up :D

It's the same mentality that can lead to fixing but symptoms without making any real progress on the underlying issues.. Sometimes that's good enough I guess.

Re: Solving the regex of madness, and snarky answers on StackOverflow (2019)

#72

Post by jll29 »

> I think the flaw here is that HTML is a Chomsky Type 2 grammar (context free grammar) and a regular expression is a Chomsky Type 3 grammar (regular grammar).

Note that regarding formal language and complexity theory, while it is correct that in general, arbitrary nested structures require a context free grammar (type 2 in the Chomsky hierarchy) and are thus beyond regular (type 3) [1], this statement is NOT true _if_ you limit the nesting depth with a finite constant k.

For example, if you agree to an HTML tag maximum nesting depth of, say, 100, then it can be modeled with a regular (type 3) grammar, including correct required matching of opening and closing tags, and hence you can write a regular expression that matches it as well.

This debate is well-documented in the theoretical linguistics literature, where some say human languages are not regular because you can always embed yet another additional relative clause in any sentence in principle without adversely affecting grammaticality, whereas others say while you could you won't find natural examples in human-written text documents where extreme nesting depth is actually found. At that point psycholinguists and theoretical linguists usually start a fight about whether memory limits are important or "just performance as opposed to competence".

(Goes to show how practical solid theory is.)

[1] https://www.sciencedirect.com/science/article/pii/S001999585...

Re: Solving the regex of madness, and snarky answers on StackOverflow (2019)

#73

Post by DangitBobby »

inopinatus wrote: post #50
swiley wrote: post #48

Earlier quoted context omitted.

Here's the original text for reference: Locked. Comments on this question have been disabled, but it is still accepting new answers and other interactions. Learn more. I need to match all of these opening tags: But not these: I came up with this and wanted to make sure I've got it right. I am only capturing the a-z. I believe it says: Find a less-than, then Find (and capture) a-z one or more times, then Find zero or…

Not sure which revision that's pasted from, but it is not the original text, which can be found at https://stackoverflow.com/revisions/1732348/1 and I strongly advise against neglecting the title; doing so is how some folks blunder into misinterpretation, since the wording of that title is telegraphing a quite different underlying need to "please solve this regex puzzle".

Reading both, I see little to no difference. Is there an important change between the two revisions that I am missing? Also, my reading of the title does not, in fact, telegraph anything other than "help me with this regex puzzle."

Re: Solving the regex of madness, and snarky answers on StackOverflow (2019)

#74

Post by Akronymus »

nixpulvis wrote: post #19
NtrllyIntrstd wrote: post #11

The author seems to be missing the point, in my opinion. While it is certainly true that often one can solve simple, seemingly innocent sub-problems within more general languages, the transitions from "I see I can solve this simple program with regex'es!" to "Then I can probably solve this other, almost identical problem as well!" and have the problem explode right into your face are subtle (almost imperceivable to a…

The regex is surely faster for the specific case. I can't say I've seen an XHTML parser off hand that allows me to stop parsing after just the start tag. Perhaps a lazy parser could start to compete, but I'm just guessing.

I believe you could build such a parser out of parsec. Altough, I am not sure if that is exactly what you are going for.

Re: Solving the regex of madness, and snarky answers on StackOverflow (2019)

#75

Post by shmageggy »

inopinatus wrote: post #58
jcelerier wrote: post #56

Earlier quoted context omitted.

> disengages any sense of purpose and practical utility and instead treats it like a badly worded test question. Who are you to know the purpose and utility better than the person who asked the question ?

Oh, are they here? It’d be fascinating to hear from them. Alternatively, perhap, that hostile tone is suggesting I’m personally unqualified to interpret loosely framed questions? I suppose, since I’ve only been doing it for a few decades, I’m definitely a novice by any standard, and my tendency to observe and follow up on anomalous, incomplete, subtly conflicting, or otherwise inexplicable requirements by investigati…

I have to ask, is this series of comments some kind of performance art or some sort of social experiment? Or is this unironically how you write/speak/act?

Re: Solving the regex of madness, and snarky answers on StackOverflow (2019)

#76

Post by User23 »

hansvm wrote: post #69
goto11 wrote: post #54

Earlier quoted context omitted.

So what do you use instead of regular expressions for such tasks?

IMO the biggest problem with regexes as seen in the wild is a lack of composability. If you need some kind of pattern like "[setA][setA+setB]{0,n}" then you'll copy-paste the definition of setA in both places. If you need to re-use that entire regex you'll copy-paste it again and construct a monstrous string with a really well-defined structure that isn't even slightly apparent without a reverse engineering session.…

Perl is great for this. It’s been a long time since I’ve written any, but with the right flags and use of qr// you can write extremely readable perlre.

Re: Solving the regex of madness, and snarky answers on StackOverflow (2019)

#77

Post by a1369209993 »

inopinatus wrote: post #39

> The question is about finding opening tags in XHTML using a regular expression Bzzzt, wrong, sorry! The question is about finding open tags in the presence of XHTML self-closing tags. That difference alone places these interpretations gulfs apart. But there’s more: it does not specify that the input document is even XHTML, only that XHTML-style self-closing elements may be present. In fact the original question was…

> For this task, the suggestion of "use a parser" is indeed sound advice.

Perhaps technically, but it's also useless advice because a parser does not exist for their particular flavor of malformed XHTML. XHTML parsers parse XHTML, which you yourself have said it wasn't:

> they were trying to fix a malformed document

So in the absence of a reference to a particular malformed-XHTML-recovering parser (which may or may not work on the specific input they have, but "try this thing" is at least actionable advice), "use a parser" amounts to "write a entire parser yourself, then use it".

> don't be a jerk about the precise semantics of a question, look at what the person needs

Pot, kettle.

Re: Solving the regex of madness, and snarky answers on StackOverflow (2019)

#78

Post by [deleted] »

wodenokoto wrote: post #36
NtrllyIntrstd wrote: post #11

The author seems to be missing the point, in my opinion. While it is certainly true that often one can solve simple, seemingly innocent sub-problems within more general languages, the transitions from "I see I can solve this simple program with regex'es!" to "Then I can probably solve this other, almost identical problem as well!" and have the problem explode right into your face are subtle (almost imperceivable to a…

The article goes as far as to say that a parser is not the right tool. > Not only can the task be solved with a regular expression - regular expressions are basically the only practical way to solve the problem. Which is why none of the clever answers actually suggest another way to solve the problem. So no, the author is not missing the point at all.

[deleted]

Re: Solving the regex of madness, and snarky answers on StackOverflow (2019)

#79

Post by a1369209993 »

chubot wrote: post #63

This conversation would be a lot clearer with a distinction between "regexes" and "regular languages". The former is what Perl/Python/etc. have, and the latter is a mathematical concept (and automata-based non-backtracking engines like RE2, re2c, and rust/regex are closer to this set-based definition). https://www.oilshell.org/blog/2020/07/eggex-theory.html With those definitions, this part of the snarky answer is wr…

> This conversation would be a lot clearer with a distinction between "regexes" and "regular languages".

Very much so.

> In this post, the example given IS a regex, but it IS NOT a regular language: ` # comment` The nongreedy match of .*? isn't a mathematical construct; it implies a backtracking engine.

Actually, that's [edit: "it IS NOT a regular language"] wrong, at least in principle. If you're limiting it to only the shortest match (which is how HTML (and most other) comments actually work), then (just like `(abc)+` is shorthand for `(abc)(abc)*`) `` is shorthand for (assuming I haven't made a mistake in the for-lack-of-a-better-word-arithmetic):

  ])* -->
That is, shortest-repetition-only can be implemented in a purely regular system.

On the other hand, if you want to allow longer matches when actually needed, then for purely-regular purposes (where it either matches or not) `` is just a wierd way of writing `` (which is quite obviously a regular language).

Re: Solving the regex of madness, and snarky answers on StackOverflow (2019)

#80

Post by [deleted] »

inopinatus wrote: post #58
jcelerier wrote: post #56

Earlier quoted context omitted.

> disengages any sense of purpose and practical utility and instead treats it like a badly worded test question. Who are you to know the purpose and utility better than the person who asked the question ?

Oh, are they here? It’d be fascinating to hear from them. Alternatively, perhap, that hostile tone is suggesting I’m personally unqualified to interpret loosely framed questions? I suppose, since I’ve only been doing it for a few decades, I’m definitely a novice by any standard, and my tendency to observe and follow up on anomalous, incomplete, subtly conflicting, or otherwise inexplicable requirements by investigati…

[deleted]
Post reply on HN