3 ms·
This is absurd. I did not realize you could do nearly this much computation in regex.
by devanshp 5mo ago
This is absurd. I did not realize you could do nearly this much computation in regex.
- karlgkk 5mo agoIt’s turing complete so you could compile almost any language to regex. You might have to build a vm for some languages, also in regex. The point is, it’s regex all the way down.
- Patryk27 5mo agoRegular expressions are not Turing-complete.
- 0xffany 5mo agoTrue in the CS Theory space, but most modern regex engines implement a few niceties which make their "regex" turing complete. https://blog.poisson.chat/posts/2024-06-18-turing-regex.html https://blog.poisson.chat/posts/2024-06-18-turing-regex.html
- benchloftbrunch 5mo agoJavascript/PCRE/etc regexes have additional features (like backreferences) that give them strictly more computational power than a regular DFA/NFA. (Still not Turing complete though without external control flow to support arbitrary iteration/recursion, like is done here)
- tgv 5mo agoIt's not just regex. The regular expressions are used to select and perform an action. There's a loop around it with controls the stack. That has more power than the regex.
- casey2 5mo agoThis is an odd comment because it's a famously (imo) over known fact due to cs textbooks and how academia organizes knowledge, optimizing for pushing papers over genuine discovery.