search

mioalter / pardus

A compiler for the Tiger programming language written in Scala.
0 stars 0 forks source link

Regex and Kleene-* algebras #2

Open mioalter opened 3 years ago

mioalter commented 3 years ago

First, make a lexer directly using fastparse.

For fun, define a Kleene- algebra trait, make a regex data type (with constructors for alternation, concatenation, and star), make a language data type (maybe?), and make a k instance for each. Maybe we do not need language.

We'll either have to define an equiv for regex or else always normalize inputs when we construct (like reducing fractions).

Then of course we'll want to define NFA and DFA data types and implement matching and transformation algorithms.

mioalter commented 2 years ago

Chapter 2 files https://www.cs.princeton.edu/~appel/modern/ml/chap2/