Is there a regular expression to detect a valid regular expression? • Hacker News Board

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

#171

Post by dang » Sun, Sep 08, 2019, 9:27 PM UTC

ukj wrote: post #152

mannykannot wrote: post #141

Earlier quoted context omitted.

It is a general rule that those who avoid answering a question do not have an answer, and this is no exception. Here, You completely misunderstand Chomsky’s hierarchy: By your inverted-hierarchy argument, the simplest regular language would be complex enough that incompleteness would be an issue in its validation.

Well, this looks like abuse of Cunningham's law, but I'll bite. It is a general rule that general rules have exceptions. And you have (incorrectly) asserted that this is not an exception. Q.E.D Even the most powerful languages (Type 0 in the hierarchy) cannot solve the halting problem. Which is equivalent to Godel's incompleteness theorem. https://www.scottaaronson.com/blog/?p=710 If a Type 3 grammar can recursively…

Please stop.

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

#172

Post by dang » Sun, Sep 08, 2019, 9:27 PM UTC

mannykannot wrote: post #165

ukj wrote: post #152

Earlier quoted context omitted.

Well, this looks like abuse of Cunningham's law, but I'll bite. It is a general rule that general rules have exceptions. And you have (incorrectly) asserted that this is not an exception. Q.E.D Even the most powerful languages (Type 0 in the hierarchy) cannot solve the halting problem. Which is equivalent to Godel's incompleteness theorem. https://www.scottaaronson.com/blog/?p=710 If a Type 3 grammar can recursively…

Your second paragraph is just a direct begging-of-the-question. More significantly, verifying that sentences are well-formed in some language is not the same as proving the language’s correctness. As a response to you argument, consider this regular language: A

Please also stop.

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

#173

Post by ukj » Sun, Sep 08, 2019, 9:35 PM UTC

mannykannot wrote: post #165

ukj wrote: post #152

Earlier quoted context omitted.

Well, this looks like abuse of Cunningham's law, but I'll bite. It is a general rule that general rules have exceptions. And you have (incorrectly) asserted that this is not an exception. Q.E.D Even the most powerful languages (Type 0 in the hierarchy) cannot solve the halting problem. Which is equivalent to Godel's incompleteness theorem. https://www.scottaaronson.com/blog/?p=710 If a Type 3 grammar can recursively…

Your second paragraph is just a direct begging-of-the-question. More significantly, verifying that sentences are well-formed in some language is not the same as proving the language’s correctness. As a response to you argument, consider this regular language: A

Curry-Howard isomorphism.

Proving that a sentences are “well-formed” is the same as implementing an algorithm which takes a string and returns a Boolean.

You can call this function “is_well_formed?”

I await your proof in the regular language you have specified above.

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

#174

Post by ukj » Sun, Sep 08, 2019, 9:43 PM UTC

malisper wrote: post #169

ukj wrote: post #88

Earlier quoted context omitted.

You are axiomatically assuming that the proposition "V determines well-formedness of any regular expressions" to be true. I am asking you to prove that. Constructively.

It's not possible to do this for regular expressions, but it is possible to do it for context free grammars. You can write a context-free grammar in Backus-Naur form that recognizes all context-free grammars in Backus-Naur form: ::= | ::= " ">" "::=" ::= " " | "" ::= | "|" ::= | ::= | ::= | " ">" ::= '"' '"' | "'" "'" ::= "" | ::= '' | ::= | | ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L"…

Sure. Total functional programming (provably terminating code) comes at the cost of Turing-completeness.

The choice exists.

https://en.wikipedia.org/wiki/Total_functional_programming

Observe though that BNF is just a notation. Parsers for BNF are not implemented in BNF. Bison. Yacc.

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

#175

Post by ridiculous_fish » Sun, Sep 08, 2019, 9:44 PM UTC

gpm wrote: post #107

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?

Yes, regex engines that are designed to do so run in linear time on the size of the regex (as well as linear time with respect to the length of the input). One such engine is rust's https://github.com/rust-lang/regex

Does "linear wrt A and linear wrt B" mean O(A*B) or O(A+B)?

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

#176

Post by jraph » Sun, Sep 08, 2019, 9:51 PM UTC

My first thought seeing this title: "Why, no. Next!"

My second thought: the voice of Linus Torvalds at DebConf 14 saying "Hum… No! Hum… that was quick." [1]

Though this is only speaking about a recursively defined regular expression language which is infinite, which strictly handles regular languages, as defined in computer science lessons in university.

And then, "Why not just try and see if it breaks the provided regex parser since you have one?", and it's actually one of the answers in the link… awesome. I wonder it is has security implications though (are forged regexes exploiting flawed regex parsers a thing?)

[1] https://youtu.be/5PmHRSeA2c8?t=110

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

#177

Post by gpm » Sun, Sep 08, 2019, 9:53 PM UTC

ridiculous_fish wrote: post #175

gpm wrote: post #107

Earlier quoted context omitted.

Yes, regex engines that are designed to do so run in linear time on the size of the regex (as well as linear time with respect to the length of the input). One such engine is rust's https://github.com/rust-lang/regex

Does "linear wrt A and linear wrt B" mean O(A*B) or O(A+B)?

It means O(AB), but is carefully worded to not say (or suggest) it's not possible to do O(A+B) which is a subset of O(AB) ;)

I'm not sure if it's possible to match regex with that time complexity, it looks like the implementation I referenced is O(AB). https://docs.rs/regex/1.3.1/regex/#untrusted-input.

(star symbol removed because hn decided to turn them into a block of italics)

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

#178

Post by gerdesj » Sun, Sep 08, 2019, 9:59 PM UTC

nightfly wrote: post #140

jessaustin wrote: post #95

Earlier quoted context omitted.

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…

)))((()(()

When I check brackets by hand or manually I do actually get my hands out and when I say open I uncurl a finger, and when I say close, I furl a finger. "Open, open, open, close, open, close, close, close". Provided I have no fingers on display at the end, then the brackets are balanced. They might not be in the right place but at least they are balanced. If I find myself starting with close then I close the lid and go and do something else.

I'm sure some sort of rather cheap algorithm falls out of the above. It wont guarantee correctness in what the balanced brackets actually contain but they will at least be balanced.

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

#179

Post by gpm » Sun, Sep 08, 2019, 10:05 PM UTC

jraph wrote: post #176

My first thought seeing this title: "Why, no. Next!" My second thought: the voice of Linus Torvalds at DebConf 14 saying "Hum… No! Hum… that was quick." [1] Though this is only speaking about a recursively defined regular expression language which is infinite, which strictly handles regular languages, as defined in computer science lessons in university. And then, "Why not just try and see if it breaks the provided r…

> are forged regexes exploiting flawed regex parsers a thing?

Looks like yes, depending on the engine.

PCRE for instance has a long list of security vulnerabilities including some with arbitrary code execution: https://www.cvedetails.com/vulnerability-list.php?vendor_id=...

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

#180

Post by andrewflnr » Sun, Sep 08, 2019, 10:06 PM UTC

YeGoblynQueenne wrote: post #92

andrewflnr wrote: post #84

Earlier quoted context omitted.

I don't know if it's possible to do the "string describing a set strings" thing that regex does with more powerful parsing while maintaining the ease of use. CFGs make heavy use of named sub-languages (productions). A regex-style parser would at least have to have some kind of recursion-inducing metacharacter.

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).

That looks great, but it's hard to position it as a regex competitor. I should be more explicit about what I mean by "regex-style": The cool thing about regex that makes them so approachable is that they kind of look like the thing they're describing/matching. Your thing here mostly does not.