Simplifying Regular Expressions Further

We describe a cumulative series of transformations to simplify regular expressions, and investigate their effectiveness and cost. Transformations depending on increasingly powerful comparisons of expressions give results clearly superior to commonly used algebraic simplifications. Early in the series, efficient transformations enabled by language-invariant attributes are surprisingly effective. Later in the series, transformations depending on comparisons of expressed languages are made feasible by bounding the size of subexpressions to which they are applied. We set out the principles of our transformations, address some key implementation issues, and evaluate the results of systematic test measurements.