3 ms·
I created a similar regex web demo that shows how a regex is parsed -> NFA -> DFA -> minimal DFA, and finally outputs LLVMIR/Javascript/WebAssembly for from the
by JoelJacobson 3y ago
I created a similar regex web demo that shows how a regex is parsed -> NFA -> DFA -> minimal DFA, and finally outputs LLVMIR/Javascript/WebAssembly for from the minimal DFA:
http://compiler.org/reason-re-nfa/src/index.html http://compiler.org/reason-re-nfa/src/index.html
- eru 3y agoThough going from NFA to explicit DFA isn't always a good idea. Btw, you might also like looking into the Brzozowski derivative https://en.wikipedia.org/wiki/Brzozowski_derivative https://en.wikipedia.org/wiki/Brzozowski_derivative which can be used as an alternative way to match regular expressions.
- alphablended 3y agoI think it is also worth mentioning that the site linked at the top uses the antimirov extension to brzozovzki work on regex deivatives.
- lubutu 3y agoTo expand, Brzozowski introduced derivatives and Antimirov partial derivatives. Essentially the former correspond to DFAs and the latter to NFAs.
- mikhailfranco 3y agoYou could implement the NFA directly with concurrent exploration of all paths: https://github.com/mike-french/myrex https://github.com/mike-french/myrex