15 ms·
Is there a regular expression to detect a valid regular expression?
- gamache 7y agoI believe Zalgo has the answer to this, via an equivalent question. https://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags https://stackoverflow.com/questions/1732348/regex-match-open...
- abraCadabstrax 7y agoPerhaps the most epic reply I have ever seen on SO.
- hk__2 7y agoIt’s a famous post on StackOverflow, but I don’t find it particularly helpful.
- joppy 7y agoI don't think that answer was written with the intent of being particularly helpful, I think it was written with a different goal in mind.
- jacobush 7y agoIt is helpful in that almost koan way though.
- swasheck 7y agoIt is helpful. It may not provide the answer the OP wanted, but it provides the answer they needed.
- wool_gather 7y agoThe author said at one point that it was written in a bit of a huff of frustration, and if I remember correctly, also after a pint or two. It's not the best answer answer by any means, but it is one of those small gems of the web, I think.
- snazz 7y agoHad it not gotten extremely lucky, it would have a very negative score. Anything intended to be funny on StackOverflow doesn’t go over well very often.
- ChrisSD 7y agoThe answer was made in '09. StackOverflow was more accepting of some humour at the time. And it is making a valid point: regex isn't the right tool for this job.
- unlinkr 7y agoThe question is about how to identify start and end-tags in XHTML. What would be an appropriate tool for that job?
- shakna 7y agoA parser. Specifically, an XHTML parser.
- unlinkr 7y agoHow do you think an XHTML parser is written? In particular, how does an XHTML parser identify tokens like start and end tags?
- saagarjha 7y agoIt keeps track of state that a regular expression cannot?
- unlinkr 7y agoYou don't need to keep track of state to match tokens like XHTML start or end tags.
- journalctl 7y ago
- stfwn 7y agoIf 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; there is no option to have the legality of a transition depend on what it read _before_ the current state. But this memory function is a requirement to recursively match opening tags to their closing tags - you need to keep a stack of opening stacks somewhere in order to then cross off their closing tags in reverse order. So regex cannot parse HTML.
- unlinkr 7y agoThe question is about identifying end-tags in XHTML. This is indeed possible with a regex.
- bryanrasmussen 7y agotheoretically I believe an end tag really requires a valid start tag. anyway you can probably answer any number of simple questions about a bit of HTML using regex but as code wants to grow to handle more use cases there will come a time when the solution will break down and the code that wrote to handle all the previous uses will need to be rewritten using something other than regex.
- unlinkr 7y agoAn element requires a start and end tag, or a self-closing start tag.
- unlinkr 7y agoYou have to distinguish between the different levels of parsing. Regexes are appropriate for tokenization, which is the task of recognizing lexical units like start tags, end tags, comments and so on. The SO question is about selecting such tokens, so this can be solved with a regex. If you have more complex use cases like matching start tags to end tags, you might need a proper parser on top. But you still need tokenization as a stage in that parser! I don't see what you would gain by using something other than regexes for tokenization? I guess in some extreme cases a hand written lexer could be more performant, but in the typical case a regex engine would probably be a lot faster than the alternatives and certainly more maintainable. I know it is possible to write a parser without a clear tokenization/parsing separation - but it is not clear to me this would be beneficial in any way.
- kortex 7y agoI found it extremely helpful. The sheer emphasis of the reply made me very curious why the idea of using regex on xml is so bonkers. - I will never forget that regex can't parse XHTML - the reason being, regex is insufficiently powerful - when I first saw this post, I knew little about regex under the hood, this sent me down a wiki hole of FSMs, pushdown automata and turing machines - this misconception is apparently common enough to be madness-inducing to those that know better - use a hecking xml parser instead It almost reminds me of a Bill Nye sketch. Teaching through a bit of non-sequitur and absurdism.
- unlinkr 7y agoThe problem with the answer is it is wrong. The question is about identifying start-tags in XHTML. This is a question of tokenization and can be solved with a regular expression. Indeed, most parsers use regular expressions for the tokenization stage. It is exactly the right tool for the job! Furthermore, the asker specifically needs to distinguish between start tags and self-closing start tags. This is a token-level difference which is typically not exposed by XHTML parsers. So saying "use a parser" is less than helpful. I have elaborated a bit in blog post: https://www.cargocultcode.com/solving-the-zalgo-regex/ https://www.cargocultcode.com/solving-the-zalgo-regex/
- LoSboccacc 7y agoit'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
- hk__2 7y agoYou can be funny and helpful at the same time.
- LoSboccacc 7y agowhich is exactly what that so answer was
- unlinkr 7y agoThe 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.
- LoSboccacc 7y agoStack overflow is not a homework help group, the "Regex are the wrong tool for the job" answer is more correct than the answer with the working Regex.
- unlinkr 7y agoThe job (the question asked) is about recognizing start and end tags in XHTML. These are lexical tokens and therefore regular expressions are a perfectly fine tool for this. Indeed many parsers use regular expressions to perform the lexical analysis (https://en.wikipedia.org/wiki/Lexical_analysis https://en.wikipedia.org/wiki/Lexical_analysis) aka tokeniziation. Quoting from wikipedia: The specification of a programming language often includes a set of rules, the lexical grammar, which defines the lexical syntax. The lexical syntax is usually a regular language, with the grammar rules consisting of regular expressions; If you disagree that regular expressions are an appropriate tool for lexical analysis, can you articulate why? And what technique do you propose instead?
- hammerbrostime 7y agoWow it looks like It was designed by David Carson.
- nolok 7y agoIn SO's hall of fame of regular members being feed up of a common yet stupid question always coming back up it's up there alongside the thread about making addition with jQuery
- lolinder 7y agoMy favorite part of it is the moderators' note at the end: > Moderator's Note > This post is locked to prevent inappropriate edits to its content. The post looks exactly as it is supposed to look - there are no problems with its content. Please do not flag it for our attention.
- gnud 7y agoThe big problem with the content is suggesting to use an XML parser to parse HTML. That might often work, and several XML parsers have some sort of HTML "mode", but in general, no, not really. HTML documents are frequently invalid XML. HTML documents lack an XML declaration, they don't close all tags, etc. They might even lack a root element. Someone mentioned this in a comment on SO, but it was (as far as I could see) not really addressed or answered. HTML 5 has it's own parsing rules, specified at [1]. However, I don't know of any implementation of these outside of browsers. I normally use Beatuiful Soup [2] (for Python) or HTML Agility Pack [3] (for .NET), and while I don't think these implement the exact standard, they're easier than struggling with a XML parser for HTML "in the wild". 1: https://html.spec.whatwg.org/multipage/parsing.html https://html.spec.whatwg.org/multipage/parsing.html 2: https://www.crummy.com/software/BeautifulSoup/ https://www.crummy.com/software/BeautifulSoup/ 3: https://html-agility-pack.net/ https://html-agility-pack.net/
- kortex 7y agoThe question title implies he's parsing XHTML text. > XHTML is an XML-based HTML. It serves the same function as HTML, but with the same rules as XML documents. https://stackoverflow.com/q/1429065 https://stackoverflow.com/q/1429065
- ChrisSD 7y agoThe question title is ambiguous but the question tags include both HTML and XHTML. Self-closing `<element />` is an XML-ism which in HTML is treated the same as `<element>` but it was still fashionable to use them in HTML when XHTML was at its height.
- unlinkr 7y agoHere is the answer to the question: https://www.cargocultcode.com/solving-the-zalgo-regex/ https://www.cargocultcode.com/solving-the-zalgo-regex/ tl;dr: It can indeed be solved relatively easily with a regex.
- kortex 7y agoThis is a bit out of my wheelhouse, but this feels wrong, or at least naively capable. Like it feels like this sort of reasoning leads to the kind of bugs (depending on what you use the result of the rexex for) that allow for code injection, a la the Equifax hack. Maybe another HN poster can back me up, or explain why in fact Zalgo is mistaken and CargoCode is correct. Either way, this sort of complexity is one reason I avoid XML like the plague and keep HTML at arm's length.
- lonelappde 7y agoCargoCode is correct. Zalgo simply misread the question because he was so sick of similar subtly different questions.
- unlinkr 7y agoThis is what I really hate about the Zalgo answer. It is instilling people some vague sense that regular expressions are somehow bad, wrong and dangerous. But without any real arguments or contexts which would allow you to evaluate if the feeling is justified.
- lol768 7y agoIt doesn't work for me with regex101. "The preceding token is not quantifiable" on this part: | < (? \w+ )
- kortex 7y agoSee, this is kinda what I mean. Maybe you can detect tags with regex, but maybe you shouldn't, given the widespread but subtle differences in regex engines. Perhaps the entire approach of "why are you trying to parse X?" Needs to be traced and re-evaluated.
- tzs 7y agoFrom that answer: "You can't parse [X]HTML with regex". I've always wondered how that came about. How come very early in the development of the web no one important enough for people to pay attention to them said, "Hey...wait a second. If this thing becomes popular, people are going to really want to processes web documents with their usual text file processing tools and techniques. We really outta make this thing reasonably easy to process with grep and sed and awk and Perl and such"?
- tom_mellior 7y agoThe problem isn't with the surface syntax of HTML. Anything else, like S-expressions or JSON or whatever would have the same problem. The problem is arbitrary nesting of elements. No language with nesting can be parsed with regex (modulo various copouts mentioned elsethread). But such nesting is useful and necessary for a document language like HTML. This goal is important; "we must be able to use awk" isn't.
- deleted 7y ago[deleted]
- ChrisSD 7y agoWhy would you want a regular expression to detect a valid regular expression?
- afiori 7y agoProbably to check if a regular expression is valid
- xfitm3 7y agoCouldn't you just compile it and check for return value?
- ChrisSD 7y agoYes, checking to see if a regular expression is valid is useful but that wasn't what I was asking. Why specifically would you want to use a regular expression for this job?
- Lordarminius 7y agoMaybe because you can :/
- afiori 7y agoThe simplest explanation is because you already have a lot of functionality implemented this way. Still probably the library you are using exposes a validation function...
- braythwayt 7y agoA regular expression is a domain-specific language that defines a language consisting of all the strings it matches. In principle, this serves as executable documentation. A regular expression that matches valid regular expressions could be viewed as a human-readable documentation of valid regular expression syntax that has the valuable side-effect of being executable. If, instead, we detect whether a string is a regular expression by compiling it, we may find it very difficult to read the compiler source code. It is much more work to make an optimized regular expression engine that is also self-documenting than a regular expression.
- ac42 7y agoIIRC, regex can be implemented by an NFA which can't solve balanced parentheses that are part of regex syntax.
- ac42 7y agohttps://en.m.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.m.wikipedia.org/wiki/Nondeterministic_finite_auto...
- mikejb 7y agoCorrect, though there are multiple interpretations of what a "regex" is. In the theoretical sense you're correct, though some (most programmers, I'd say) mean "PCRE" when they say regex. And PCREs are pretty powerful, see [1] for example [1] https://news.ycombinator.com/item?id=9748736 https://news.ycombinator.com/item?id=9748736
- nabla9 7y agoRegex has two different meaning depending on the context. One is CS definition of regular expression matcher for regular languages. The other is extension of that into non-regular languages, typically PCRE compatible.
- z3c0 7y agoThe answer is as horrifying as you'd expect, but impressive nonetheless. Recursive regex is really fun and powerful, when it works. I once made a recursive regex for matching a full name, complete with checking for suffixes, prefixes, an undefined amount of middle names, hyphenated last names, and Scotch-Irish names (Mc-, O'-, etc). Still simpler than this monstrosity.
- tyingq 7y agoI did enjoy the comment with the Xhibit/Pimp my Ride reference.
- tannhaeuser 7y agoBasic classical regular expression syntax without grouping parentheses is trivially regular. With parentheses, the maximum nesting level must be bounded to remain regular because "regexpes can't count".
- mkagenius 7y agoIt may be noted that regular languages (as in compiler design) do not have such recursive constructs.
- ukj 7y agoThis immediately triggers the Liar's paradox [1]. Can a regular expression check its own validity? How can you tell if it's lying? Beware of bugs in the above code; I have only proved it correct, not tried it --Donald Knuth [1] https://en.wikipedia.org/wiki/Liar_paradox https://en.wikipedia.org/wiki/Liar_paradox
- zwkrt 7y agoA self-hosted compiler is definitely not a case of the liars paradox, so I don’t think this applies. In fact, it doesn’t matter what the parser is written in, at some point you do have to trust that it actually follows the spec, probably through testing.
- ukj 7y agoSo what you have to trust is that the spec doesn't produce lies ? ;) FYI. I am just having some philosophical fun with GIGO. Ultimately, computers are just instruments which amplify human intention, it's not the computers's job to be ultimate moral arbiter of our words. Gödel's incompleteness theorem already tells us that a system cannot prove its own correctness.
- Iv 7y agoThat does not really apply. A compiler can compile itself, it can check if its own code is valid.
- ukj 7y agoYou are necessarily claiming that a compiler is incapable of false negatives. e.g incorrectly validating its own code. Beware of bugs in the above code; I have only proved it correct, not tried it --Donald Knuth
- mannykannot 7y agoThe fact that someone might make a mistake in doing something does not show it cannot be done. More generally, You seem to be mistaking validating a program's source with the question of whether it performs its intended purpose. These are different things, and attempting to conflate them will only lead to confusion.
- noobiemcfoob 7y ago"Evaluate it in a try..catch or whatever your language provides." "That's not very enterprisey of you" Oooh, I'm laughing so hard it hurts. It's been a particularly 'enterprisey' week at work.
- nolok 7y ago"We could do it in a easy two liners that make sense, but, and hear me out here, what if we instead built an entire 10k LOC system that would barely work half of the time, using dozens of man hours for it ? And then never re-use it nor train anyone about it so that it becomes a mythical black box after your contract expires ?" "Well, I gave you my recommendation but hey at the end of the day you're the customer and I'm paid by the hour, so whatever you say boss" I now consider myself very lucky to be successful enough to not have to deal with projects like that, but back when I wasn't I paid quite a few things I wanted with those sort of stupid decisions.
- murukesh_s 7y agoActually that is how enterprise works afaik. But few well funded startups on the other hand...
- braythwayt 7y agoThat answer feels entirely wrong to me. As pointed out, it may be an XY answer: It presumes the person posing the question wants to validate regular expressions. But with something so blatantly self-referential, it actually feels unlikely to me that what they want to do is validate regular expressions. My guess is that they are generally curious about whether Regexen (PCRE or strict regular expressions) are powerful enough to validate Regexen (again whether PCRE or strict). XY answers are good for avoiding a lot of unnecessary yak-shaving/accidental complexity of a bad solution. But the conversation around whether we are talking about recognizing strict Regexen or PCRE Regexen, and in turn whether we are using strict Regexen or PCRE Regexen to recognize them is not accidental complexity or yak-shaving, it is intrinsic to understanding the nature of the problem and solution spaces. I too find the answer humorous for the "enterprisey" reference, but I think it would be a very bad answer if we are judging it strictly on the basis of its value.
- timeattack 7y agoThis is perfect example of a insight which leads to a rabbit hole of intertwined complexity of our concepts when you try to understand why regexp for validating regexp is actually much simpler than regexp for validating email address.
- ChrisSD 7y agoIt depends what you mean by "validating email addresses". A regex that tests if a string looks like a valid email address is simple. Forget the ancient RFCs, a real world email address is in the form of `mailbox@domainname`. Which is not so difficult to test for with a bit of care. However, testing if the email address is a valid mailbox is harder and indeed impossible using regex alone. The domain name can be validated using standard domain tools but in practice the mailbox can be anything that the server will route to a valid mailbox. The only way to validate it is to send an email.
- dillonmckay 7y agoEven then, there is no way to determine if there is a ‘catch-all’ address configured, or some email tarpit. I have a domain w/ a .tech TLD, and quite a few frontend JS validators do not accept my email as a valid address (government sites, some banks).
- kyberias 7y agoI hate it how the accepted answer is incorrect and does not teach the fundamental property of regular expressions.
- unlinkr 7y agoIt only works in practice, not in theory.
- yifanl 7y agoIt doesnt work in practice, PCRE does not validate all valid PCRE expressions.
- PeterisP 7y agoThe fundamental property of regular expressions is that the programming/software engineering concept of "regex" or "regular expression" is fundamentally different from the mathematical concept of "regular language". If you see "regex" without any special context and start thinking about what it can/can't do, then the first association should be with something like PCRE and its capabilities, not something that's bound by the pumping lemma.
- tobinfricke 7y ago> 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.
- jameshart 7y agoThis 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 expression to validate the paren nesting of any given string - if you were allowed to prepare the regex based on the string length, or on running another regex over the string first. What I suspect you might not be able to validate is that in a regex, while [a-z] is valid, [z-a] is not.
- daveFNbuck 7y agoIf you allow generating a regular expression based on string length, you can validate any computable language with a regular expression. It's trivial to just run a solver on all strings of that length and or the accepted ones together. > 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)\].
- repsilat 7y agoFor a fixed input length all languages are decidable by regular expressions. Trivially, the union of all valid input strings of that length, like "(abc|def|...)". It's not an interesting property.
- raldi 7y agoSure there is. Read the linked answer, or just google it. Example: https://regular-expressions.mobi/recurse.html?wlr=1 https://regular-expressions.mobi/recurse.html?wlr=1
- GuB-42 7y agoAn interesting question would be "which regex variant can be parsed by itself, and how?". Parsing simple regex with PCRE is cheating. If you are using PCRE, you should be parsing PCRE. The simplest case would be DOS style globs with just * and ?, and it can parse itself: just use "*".
- cbarrick 7y ago"Regular Expression Matching Can Be Simple And Fast" [1] is worth a read (by Russ Cox of Bell Labs and Go fame). [1]: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
- papito 7y agoThere isn't even a regular expression to detect a valid email, bruh.
- deleted 7y ago[deleted]
- rocqua 7y agoSo, 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?
- andrewflnr 7y agoI 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.
- YeGoblynQueenne 7y agoHow 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).
- carapace 7y agoAnd this can be used to generate sentences as well as parse them. ;-)
- YeGoblynQueenne 7y agoIndeed. 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.
- andrewflnr 7y agoThat 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.
- anewguy9000 7y agoit would become conscious
- andrewflnr 7y agoI've always been mildly amused by the fact that while regular expressions are a context-free language, context-free grammars are a regular language.
- sswaterproofing 7y agoI concur that utilizing Spanish, English, and Spanglish in a similar code is definitely not an upbeat practice. The issue is I'm accustomed to coding in English, however, there were a few rules to pursue, (for example, remarking in Spanish or utilizing certain names for tokens) in the undertaking. Anyway, the fact of the matter was simply to give a thought on the calculation, not to give some full reference code. https://www.sswaterproofing.in https://www.sswaterproofing.in
- deleted 7y ago[deleted]
- Piskvorrr 7y agoTL;DR: No. But there exist languages built on top of regular expressions (notably PCRE) that can. They can't validate themselves, though - turtles all the way down to Gödel.
- tom_mellior 7y agoPlenty of parser formalisms can define their own syntax in their own syntax. As mentioned elsewhere, C compilers can parse their own source code. Gödel has nothing to do with it.
- fortran77 7y agoWe see good examples of "the problem with StackOverflow" here. The second highest-rated answer is "Evaluate it in a try..catch or whatever your language provides." and it's justified because "Surely the real question is 'how do I validate a regular expression'." This is a fascinating computer science question and I'm pretty sure the questioner wasn't asking "how do I validate a regular expression" because he would have asked that.
- sosborn 7y agoPersonally, I think this is a strength of StackOverflow. I think most people read through all of the answers, and this particular one keeps people who know nothing about regex from trying to evaluate regex with regex. And for those with a deeper understanding, they have an answer that provides the intellectual stimulation they are looking for.
- jogjayr 7y ago> I think most people read through all of the answers You're vastly overestimating what most SO users come to the site for. They (and I include myself) just want something that'll work and isn't horrible. Even "not horrible" is something I care about but I know that many devs don't.
- perl4ever 7y agoIf somebody doesn't know the answer to their question in advance, which by definition they don't, it's by no means guaranteed they will know a horrible answer when they see it.
- thereare5lights 7y ago> I'm pretty sure the questioner wasn't asking "how do I validate a regular expression" because he would have asked that. In my experience, people sometimes ask for how to solve the more immediate detail they’re working on rather than the broader problem.
- 7y ago
- notyourday 7y agoDon't use a regex to do it. Most of languages have a way to catch runtime errors. Stick regex to a variable, create a dummy input and run that block with a catcher around it. If catcher throws a runtime error, you have a bad regex. If it does not, you have a valid regex.
- a3n 7y agoAnother way to phrase the question: Are regexes self hosting?
- kmstout 7y agoNo. I wrote about this awhile back (https://reindeereffect.github.io/2018/06/24/regex/#the-limits-of-regular-expressions https://reindeereffect.github.io/2018/06/24/regex/#the-limit...). From that post: [M]atching parentheses requires our recognition device to remember how many unmatched open parentheses there are. Since the only way for a DFA to remember anything is to be in one of a set of states corresponding to it, and since the unmatched open parentheses could easily outnumber the available states, we can see that the fundamental limitation of a DFA is that it can store only a finite amount of information (remember the ‘F’ in DFA?). This limitation applies to any string matching task that involves recursive structures or algebraic relationships between substrings. It is why “HTML and regex go together like love, marriage, and ritual infanticide.”
- jraph 7y agoMy 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 https://youtu.be/5PmHRSeA2c8?t=110
- gpm 7y ago> 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=3265&product_id=0&version_id=0&page=1&hasexp=0&opdos=1&opec=0&opov=0&opcsrf=0&opgpriv=0&opsqli=0&opxss=0&opdirt=0&opmemc=0&ophttprs=0&opbyp=0&opfileinc=0&opginf=0&cvssscoremin=0&cvssscoremax=0&year=0&cweid=0&order=1&trc=38&sha=3be670e89a2d45bd0df8736dd00d2179b59636da https://www.cvedetails.com/vulnerability-list.php?vendor_id=...
- seanmcdirmid 7y agoA regular language for writing regular language recognizers is an interesting thought exercise.
- proverbialbunny 7y agoMaybe I'm taking this a step too far but doesn't Gödel's Incompleteness Theorems (https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...) state that a language can not define itself? You need a meta language to be able to define and specify a language in its entirety. In other words, regex can not parse regex in its entirety. It's impossible.
- wool_gather 7y agoNo, not really. This is probably closer to Chomsky's area than Gödel's. Gödel's theorem is about semantics, not syntax. As a nice counter-example to what you said, you can define the Backus-Naur notation using Backus-Naur notation: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form#Further_examples https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form#Furth...
- wahern 7y agoCan a C program parse C source code? A Java program parse Java source code? Yes, they can, so such a general limitation couldn't be the reason regular expressions can't parse themselves. Perhaps you had in mind the Halting Problem: https://en.wikipedia.org/wiki/Halting_problem#G%C3%B6del's_incompleteness_theorems https://en.wikipedia.org/wiki/Halting_problem#G%C3%B6del's_i...