191–200 of 224 posts
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…
)))((()(()
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…
This only works if you have a single type of parenthesis. Is that applicable to regex expressions in general that only ()’s can nest?
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
It can process arbitrary deep nestings? I'm not familiar with it, but I had a look and I can't see anything in there that would allow it to do it. Can you point to syntax that allows it?
In general regex's that run in linear time are based on DFA's (as opposed to NFA's - which is what most use).
A DFA is part of the Chomsky hierarchy of languages that has DFA's at the bottom (aka regex's, least powerful - can't handle recursive structures), a DFA coupled with an infinite stack for memory (aka LR parsers, can't handle context sensitive grammars, also runs in very close to linear time), and finally a DFA coupled with an infinite tape (aka Turing Machine, can do any sort of computation).
In each of these cases the DFA (regex) is essentially a computer program and all they are doing is allowing it to store stuff on various kinds of memory (none, stack, tape with arbitrary movements). An interesting corollary of this is any computer program can be expressed as a DFA.
Earlier quoted context omitted.
It’s a famous post on StackOverflow, but I don’t find it particularly helpful.
I 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…
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/
Earlier quoted context omitted.
A parser. Specifically, an XHTML parser.
How do you think an XHTML parser is written? In particular, how does an XHTML parser identify tokens like start and end tags?
Earlier quoted context omitted.
It depends on the representation. If the representation is in the FSA format (state, character, state), it becomes nearly trivial.
An analogous problem for this representation would be detecting transitions to undefined states, or ambiguous (duplicate) transitions.
TL;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.
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).
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.
You can make a DCG rule as specific or as general as you like. As a for instance, this is a vim regex I retrieved from my recent history:
\[13\/13,15\/12,24-24]
s --> ['[',13,'/',13,,,15,'/',12,,,24,-,24,']'].
DCGs are Turing-complete, so you can go all the way from programs to finite automata when you write a pattern to match.
They're not really a regex competitor. They were invented in the '70s as a formalism for context-free grammars to be used in representing natural language. They fit right into the logic programming language Prolog that was created soon after (and by some of the same people).
Earlier quoted context omitted.
Here is the answer to the question: https://www.cargocultcode.com/solving-the-zalgo-regex/ tl;dr: It can indeed be solved relatively easily with a regex.
It doesn't work for me with regex101. "The preceding token is not quantifiable" on this part: |