91–100 of 224 posts
> Is there a regular expression to detect a valid regular expression? No, there is not. For example, parentheses in a regex must be balanced, and (famously) there is no regex to detect balanced parentheses.
So, given the much discussed limitations of reg-exps and the desire to parse context-free grammars. My question is, why are we still using regular expressions. Or rather, why isn't there something as easy to use as regular expressions that can processes context-free grammars?
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.
sentence --> noun_phrase, verb_phrase.
noun_phrase --> det, noun.
verb_phrase --> verb, noun_phrase.
det --> [the].
det --> [a].
noun --> [cat].
noun --> [bat].
verb --> [eats].
It's directly executable as a logic program (it's Prolog syntactic sugar).
Earlier quoted context omitted.
If you were looking for the reason why a regex cannot parse HTML, it is because HTML has matching nested tags and regex parsers are finite state machines (FSM). What this means is that a regex parser is like a goldfish. It only knows about the state it is currently in (what it just read) and which possible states it may transition to (what is legally allowed to come next). The fish never remembers where it was before…
The question is about identifying end-tags in XHTML. This is indeed possible with a regex.
Earlier quoted context omitted.
Not sure if you are trolling, but here we go... In the case at hand, correctness of the validator expression V clearly means "V determines well-formedness of any regular expressions" which is clearly not implied by "V is well-formed" (a much weaker statement because ".*" is well-formed but matches everything). Therefore, when applying V to itself, we only learn if a weak requirement for V's correctness holds. Similar…
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.
Earlier quoted context omitted.
More precisely, it is arbitrarily deep nested clauses that cannot be parsed, on account of true REs not being able to either use recursion or keep count of how deep they are. https://blogs.msdn.microsoft.com/jaredpar/2008/10/15/regular...
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?
Adding the rest of the regex machinery makes this a bit more complex, but in general, if the computer can store the string, it can check whether it's regular.
Earlier quoted context omitted.
Your mistake appears to be - ignoring the alternative hypothesis. You are mistaken, not me. The consequences of Godel's incompleteness theorem are such that a mathematical system (such as a compiler) cannot prove its own correctness. It can only prove that it is free from known errors. Once you define what an "error" is.
Godel incompleteness only applies to sufficiently powerful formal systems.
https://en.wikipedia.org/wiki/Chomsky_hierarchy#Type-0_gramm...
In this type of grammar Godel's incompleteness theorem is equivalent to the Halting problem.
> Is there a regular expression to detect a valid regular expression? No, there is not. For example, parentheses in a regex must be balanced, and (famously) there is no regex to detect balanced parentheses.
This is true if you want to handle arbitrarily deep nested parents. But any given string you are asked to validate to see if it is a regex will be a finite length, and contain a finite number of opening paren characters. So it’s maximum possible nesting depth is known. And you can construct, fairly trivially, a regex that can validate paren nesting up to a fixed depth. So, in practice, you could use a regular express…
> What I suspect you might not be able to validate is that in a regex, while [a-z] is valid, [z-a] is not.
It's fairly trivial to validate things like a-z being valid in a character class while z-a isn't. There are only finitely many legal ranges. You can just list them all, like \[(a-a|a-b|a-c|...|z-z)\].
Earlier quoted context omitted.
Godel incompleteness only applies to sufficiently powerful formal systems.
Indeed. Type 0 Grammars are the most powerful grammars we have. https://en.wikipedia.org/wiki/Chomsky_hierarchy#Type-0_gramm... In this type of grammar Godel's incompleteness theorem is equivalent to the Halting problem.
> Is there a regular expression to detect a valid regular expression? No, there is not. For example, parentheses in a regex must be balanced, and (famously) there is no regex to detect balanced parentheses.
This is true if you want to handle arbitrarily deep nested parents. But any given string you are asked to validate to see if it is a regex will be a finite length, and contain a finite number of opening paren characters. So it’s maximum possible nesting depth is known. And you can construct, fairly trivially, a regex that can validate paren nesting up to a fixed depth. So, in practice, you could use a regular express…
It's not an interesting property.