Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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



Though 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 which can be used as an alternative way to match regular expressions.


I think it is also worth mentioning that the site linked at the top uses the antimirov extension to brzozovzki work on regex deivatives.


To expand, Brzozowski introduced derivatives and Antimirov partial derivatives. Essentially the former correspond to DFAs and the latter to NFAs.


You could implement the NFA directly with concurrent exploration of all paths:

https://github.com/mike-french/myrex




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: