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

Is there a regular expression to detect a valid regular expression?

stackoverflow.com

Post reply on HN
Print view View original

201–210 of 224 posts

Re: Is there a regular expression to detect a valid regular expression?

#201

Post by YeGoblynQueenne »

carapace wrote: post #120
YeGoblynQueenne wrote: post #92

Earlier quoted context omitted.

How about this for ease-of-use? sentence --> noun_phrase, verb_phrase. noun_phrase --> det, noun. verb_phrase --> verb, noun_phrase. det --> [the]. det --> [a]. noun --> [cat]. noun --> [bat]. verb --> [eats]. Reads -and behaves- as BNF. Strings in []'s are terminals, the rest are nonterminals. It's directly executable as a logic program (it's Prolog syntactic sugar).

And this can be used to generate sentences as well as parse them. ;-)

Indeed. I tend to forget how counter-intuitive this is.

With DCGs you get your recognisers for nothing and your generators for free. As I like to say.

Re: Is there a regular expression to detect a valid regular expression?

#202

Post by unlinkr »

LoSboccacc wrote: post #105
hk__2 wrote: post #17

Earlier quoted context omitted.

It’s a famous post on StackOverflow, but I don’t find it particularly helpful.

it's sad that today the stack overflow majority shares your mindset and an answer like that would drown in downvotes or killed by moderation. some people like to act super serious all the time like they're playing a sitcom version of what they think adulthood is in a quest to be the most boring person on earth like if that's the goal of human interaction

The problem is it is funny and wrong. Apparently it have given a lot of people really confused ideas about what is possible and what is not possible with regular expressions.

If it had been funny and right I would not have a problem with it.

Re: Is there a regular expression to detect a valid regular expression?

#203

Post by unlinkr »

shakna wrote: post #196
unlinkr wrote: post #71

Earlier quoted context omitted.

How do you think an XHTML parser is written? In particular, how does an XHTML parser identify tokens like start and end tags?

If I were writing a limited parser, in answer to the narrow question being asked, I wouldn't be using regex at all. It's not suited to this particular problem. (For example it would get caught on things like "> which may well be valid input.)

So how would you tokenize without the use of regular expressions? What more appropriate technique would you use instead?

The example you provide in not XHTML so not really relevant for the discussion. But in any case, a regular expression have no problem recognizing a quoted string.

Re: Is there a regular expression to detect a valid regular expression?

#204

Post by hk__2 »

unlinkr wrote: post #194
hk__2 wrote: post #160

Earlier quoted context omitted.

What about this --> -->?

Yes you can tokenize this with a regular expression and extract the valid start and end tags. If comments in XHTML could nest you would have a problem. But this is not the case.

> Yes you can tokenize this with a regular expression and extract the valid start and end tags.

So you need more than a regular expression, hence your premise is incorrect.

Re: Is there a regular expression to detect a valid regular expression?

#205

Post by unlinkr »

majewsky wrote: post #162
lol768 wrote: post #70

Earlier quoted context omitted.

It doesn't work for me with regex101. "The preceding token is not quantifiable" on this part: |

You want (?:, not (? Without the colon, the parser appears to be interpreting (? as "one or more instances of (", but ( is no a full expression by itself and therefore cannot be modified with a quantifier.

I actually meant (? in order to create a named capture.

Re: Is there a regular expression to detect a valid regular expression?

#206

Post by taejo »

jessaustin wrote: post #95
benj111 wrote: post #77

Earlier quoted context omitted.

Can regex engines actually process arbitrarily deep nestings themselves though? It seems to me it would start getting computationally expensive very quickly to search for those kinds of regexes, so is 'arbitrarily deep' a practical concern for todays hardware?

Just considering the language of balanced parentheses, the only memory needed is a single integer to track depth. If we see a "(", increment. If we see a ")", decrement. If we never go negative and end up with zero, that's a balanced parentheses expression. (To be clear, the parser I've described is not a regex parser.) Adding the rest of the regex machinery makes this a bit more complex, but in general, if the compu…

As you say, this is not a regex parser, but some readers may not know the theorem that the regular languages are exactly those which can be parsed by a Turing machine with constant memory, and parenthesis count can have log n bits.

In fact, any Turing machine using o(log log n) space recognizes a regular language (so there is an equivalent machine using O(1) space).

Re: Is there a regular expression to detect a valid regular expression?

#207

Post by shakna »

unlinkr wrote: post #203
shakna wrote: post #196

Earlier quoted context omitted.

If I were writing a limited parser, in answer to the narrow question being asked, I wouldn't be using regex at all. It's not suited to this particular problem. (For example it would get caught on things like "> which may well be valid input.)

So how would you tokenize without the use of regular expressions? What more appropriate technique would you use instead? The example you provide in not XHTML so not really relevant for the discussion. But in any case, a regular expression have no problem recognizing a quoted string.

> So how would you tokenize without the use of regular expressions?

Since this need doesn't appear to be an everyday one, with clearly defined targets, a simple hand-written lexer isn't hard to write, and will make less mistakes than a regex. Just use a scanning approach. As a bonus, you'll still be able to read in 12 months time.

Re: Is there a regular expression to detect a valid regular expression?

#208

Post by unlinkr »

shakna wrote: post #207
unlinkr wrote: post #203

Earlier quoted context omitted.

So how would you tokenize without the use of regular expressions? What more appropriate technique would you use instead? The example you provide in not XHTML so not really relevant for the discussion. But in any case, a regular expression have no problem recognizing a quoted string.

> So how would you tokenize without the use of regular expressions? Since this need doesn't appear to be an everyday one, with clearly defined targets, a simple hand-written lexer isn't hard to write, and will make less mistakes than a regex. Just use a scanning approach. As a bonus, you'll still be able to read in 12 months time.

Why would a hand-written lexer have fewer mistakes than a regular expression using an off-the-shelf regex engine? They would need to encode the same lexical grammar, so at that level there is the same amount of complexity.

Writing a lexer by hand is just trading ten lines of regex (a widely known declarative DSL) with hundreds of lines of custom code. I don't see how that would be more maintainable in the long run.

Re: Is there a regular expression to detect a valid regular expression?

#209

Post by unlinkr »

hk__2 wrote: post #204
unlinkr wrote: post #194

Earlier quoted context omitted.

Yes you can tokenize this with a regular expression and extract the valid start and end tags. If comments in XHTML could nest you would have a problem. But this is not the case.

> Yes you can tokenize this with a regular expression and extract the valid start and end tags. So you need more than a regular expression, hence your premise is incorrect.

No, you don't need more than a regular expression. If you want to extract elements, i.e. match start tags to the corresponding end tags, then you need a stack-based parser. But just to extract the start tags (which is the question) a regular expression is sufficient.

The original question is a question about tokenization, not parsing, which is why a regular expression is sufficient.

Re: Is there a regular expression to detect a valid regular expression?

#210

Post by unlinkr »

nurettin wrote: post #139
unlinkr wrote: post #127

Earlier quoted context omitted.

That is a valid XHTML tag (if I remember correctly) and can be matched perfectly fine by a regex.

Perhaps something like "([^"]*)" could skip what is inside the string literal. Unless there is "<input" in the string literal, then where you start parsing becomes very important.

That pattern would indeed match a quoted string. I don't see how it would matter if the quoted string contains something like "<input". It can contain anything except a quote character.
Post reply on HN