osa1 / lexgen

A fully-featured lexer generator, implemented as a proc macro
MIT License
63 stars 7 forks source link

Implement DFA minimization #38

Open osa1 opened 2 years ago

osa1 commented 2 years ago

For the algorithm, in addition to dragon book, there's a paper "Fast brief practical DFA minimization" which is paywalled but available on sci-hub. (doi:10.1016/j.ipl.2011.12.004) (edit: also available here https://www.cs.cmu.edu/~cdm/papers/Valmari12.pdf)

A real-world example of how much difference DFA minimization makes: https://twitter.com/cfbolz/status/1461300039398088707