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.
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.
1
3
Show replies