tttardigrado/hsderiv

Haskell implementation of Brzozowski derivatives for regular expressions.

HsDeriv

Haskell implementation of Brzozowski derivatives for regular expressions.

Technologies

• Haskell
• Parsec
• Haskeline

References

Papers

• Derivatives of Regular Expressions by Brzozowski
• Regular-expression derivatives reexamined by Owens, Reppy and Turon

Blog Posts

• A regular expression matcher in Scheme by Mathew Might
• Derivatives of regular expressions explained using pac-man by Walter Schulze
• Derivatives of Regular Expressions by Harrison Goldstein

Implementations

• In gleam by Julian Schurhammer
• In elm by Hazim Avdal
• In idris by Mathias Pedersen

hsderiv's Issues

Add more resources

• Papers
• Blog posts
• Implementations

Add char classes

Add [x-y] syntax

[a-e] => a|b|c|d|e

Add tests

Fix `&` precedence

& has higher precedence than |

Add smart constructors

Use smart constructors to simplify the tree while building and deriving expressions

ex:

seq Eps a = a
seq a Eps = a
seq Nil _ = Nil
seq _ Nil = Nil
seq a b   = Seq a b

Add regex matching repl

:r sets the new regex

:r regex

:q quits the repl

:p prints the parsed version of the current regex

any other input just matches to the current regex (printing either accepted or rejected)