4 ms·

One fun project in this vein is to DIY something similar to this. To simplify things initially, you can use NFAs, along with an existing library to parse the re

One fun project in this vein is to DIY something similar to this. To simplify things initially, you can use NFAs, along with an existing library to parse the regex syntax yourself. The aha moment comes when you see how regex syntax compiles down to various configurations of automata. Couple that with the fact that automata are made to be composed together well, and the result is beautiful in a way that you rarely see in production code. Here's my stab at it in Rust: https://github.com/mattgreen/lexer/tree/master/src/nfa https://github.com/mattgreen/lexer/tree/master/src/nfa

mikhailfranco 3y ago
Concurrent parallel execution of NFA directly in Elixir: https://github.com/mike-french/myrex https://github.com/mike-french/myrex It is concurrent in all senses: a single match is split into many concurrent traversals of the network; multiple inputs can be matched concurrently within the same network; and string generators can also run concurrently in the network. That's possible because all state is in the traversal messages, not in the process nodes, and the whole thing runs asynch (non-blocking) in parallel, automatically using all cores in the machine. > you see how regex syntax compiles down to various configurations of automata That is Thompson's Construction [1]. The myrex README contains a long description of how regex structures map to small process networks, and how they glue together. The final process network is almost a direct 1-1 representation of the NFA. [1] Russ Cox has a nice explanation https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html