What's the purpose of the Scala package scala.util.automata?

Question

I saw the scala.util.automata package quite some time ago and just fell over it recently when reading a bit of ScalaDoc.

Does anyone have seen this package in usage anywhere yet and for which purpose?

I wonder if those classes have some connection to the parser combinators or if they are used standalone?

The classes have names like

class BaseBerrySethi
class DetWordAutom[T <: AnyRef]
trait Inclusion[A <: AnyRef]
class NondetWordAutom[T <: AnyRef]
class SubsetConstruction[T <: AnyRef]
class WordBerrySethi extends BaseBerrySethi 

and a not very helpful description.

It seems like they will be shipped with Scala 2.9.

Answer 1

It's the implementation of a regular expression to a finite automaton conversion. http://www2.in.tum.de/hp/file?fid=571 [PDF] An example of one way to create an NDFA can be found at http://www.scala-lang.org/api/current/scala/util/regexp/WordExp.html, although that doesn't show how to use the resulting automaton. It appears the automaton would be used by calling "next" repeatedly, threading the state set in the form of a BitSet through and checking each time with containsFinal to see if the automaton had reached a final state. What I don't see is what the initial states should be represented as, but it would seem likely that the initial state would be an empty BitSet.

Answer 2

It was one of the first things I came upon when I started learning Scala. Found some bugs in it, too. It isn't particularly useful, and there was even some discussion about deprecating it.

It does implement a fairly flexible algorithm to convert regular expressions all the way to DFAs, but the DFA itself isn't particularly flexible, iirc.