Conversation
You’re unable to view this Tweet because this account owner limits who can view their Tweets. Learn more
An actual regular expression is a grammar for a regular language:
brilliant.org/wiki/regular-l
Most implementations (Perl-style, etc.) are cursed and support a lot more via state machine hacks (backreferences, etc.).
re2, Go regexp and Rust regex are actually always regular.
2
10
You’re unable to view this Tweet because this account owner limits who can view their Tweets. Learn more
It's about whether you can express it with a FSM (brilliant.org/wiki/finite-st). You have the right idea already.
swtch.com/~rsc/regexp/re is a really good read explaining it.
twitter.com/happyautomata/
Perl's take on it is a total hack with workarounds to make it handle common cases.
Quote Tweet
read image description
ALT
1
3
Irregular doesn't really mean you can express anything, just that you can express more than a FSM.
They're a subset of brilliant.org/wiki/context-f.
It's defined in terms of what kind of parsers you need to parse the grammars. Simpler grammar types allow simpler/faster algorithms.
1
3
You’re unable to view this Tweet because this account owner limits who can view their Tweets. Learn more
The next step up from would be posting CFGs.
It's not a path that leads anywhere good because eventually you end up with a Twitter bot that posts a twenty thousand tweet thread describing an eldritch horror like C++ which cannot be parsed to an AST with a grammar.
C++ doesn't even fit in the 'recursively enumerable' circle on that page. It's beyond human understanding. I think if you wanted to actually write a real grammar you would need to produce many ASTs and then figure out which one (if any? hopefully not multiple?) is valid later on.
3