2 ms·
I don't know if this is relevant to what Chubot's doing but Brzozowski’s Derivatives of Regular Expressions are pretty mathy. (Disclosure, I wrote this) http:/
by carapace 7y ago
I don't know if this is relevant to what Chubot's doing but Brzozowski’s Derivatives of Regular Expressions are pretty mathy. (Disclosure, I wrote this) http://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expressions.html http://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expres...
- chubot 7y agoThat's cool -- I have a big page of notes on derivatives and have thought about replacing my usage of re2c with them (re2c being automata-based). One benefit of that is aesthetic -- re2c is a 30K line piece of C code itself. The other benefit is practical -- it would be nice to "hoist" it up to the Oil language level, so shell users can use efficiently compiled regexes. And I filed this issue to try derivatives awhile ago: https://github.com/oilshell/oil/issues/197 https://github.com/oilshell/oil/issues/197 There is a possible performance win, but I'm not sure if it makes sense. If you see anything interesting there I'd love to chat about it! (contact info in profile) ----- What I mean by "math" is either automata-based methods or derivatives. In contrast, Perl-style backtracking engines aren't math. To me, the "magic" of "regular languages" is that they give you non-determinism for free. The equivalence between NFAs and DFAs isn't obvious, and it's useful in practice. I've taken advantage of this free nondeterminism in my huge shell lexer. (See my other reply for details)
- carapace 7y agoI'm enamored of dRE (as I call it) but pragmatically it seems to me you could stick with re2c. I think it's interesting to generalize dRE to general control-flow (not just parsing.) Are you aware of Abstract State Machines? https://en.wikipedia.org/wiki/Abstract_state_machine https://en.wikipedia.org/wiki/Abstract_state_machine