diff options
author | buraq <buraq@epfl.ch> | 2004-07-08 17:08:24 +0000 |
---|---|---|
committer | buraq <buraq@epfl.ch> | 2004-07-08 17:08:24 +0000 |
commit | 9b4accd2265d3046d1198cae67561257c077d563 (patch) | |
tree | 6fa2bdc275ffc30e4c972cc7ddd152c49fcf5132 | |
parent | 9686e20774b3da3efe87e24d913aefef1805041a (diff) | |
download | scala-9b4accd2265d3046d1198cae67561257c077d563.tar.gz scala-9b4accd2265d3046d1198cae67561257c077d563.tar.bz2 scala-9b4accd2265d3046d1198cae67561257c077d563.zip |
algos
-rw-r--r-- | sources/scala/util/automata/NondetWordAutom.scala | 33 | ||||
-rw-r--r-- | sources/scala/util/automata/WordBerrySethi.scala | 209 |
2 files changed, 242 insertions, 0 deletions
diff --git a/sources/scala/util/automata/NondetWordAutom.scala b/sources/scala/util/automata/NondetWordAutom.scala new file mode 100644 index 0000000000..548d4f68e1 --- /dev/null +++ b/sources/scala/util/automata/NondetWordAutom.scala @@ -0,0 +1,33 @@ +package scala.util.automata ; + +import scala.util.alphabet.Alphabet ; +import scala.collection.{ Set, Map, mutable }; + +/** 0 is always the only initial state */ +abstract class NondetWordAutom[ A <: Alphabet ] { + + val nstates: Int; + val labels: Set[A] ; + val finals: Map[Int,Int] ; + val delta: Map[Int,Map[A,List[Int]]]; + val default: Array[List[Int]]; + + /** returns true if the state is final */ + final def isFinal(state: Int) = finals.contains( state ); + + /** returns tag of final state */ + final def finalTag(state: Int) = finals( state ); + + /** returns true if the set of states contains at least one final state */ + final def containsFinal(Q: Set[Int]):Boolean = { + val it = Q.elements; + while( it.hasNext ) + if( isFinal( it.next )) + return true; + return false; + } + + /** returns true if there are no finite states */ + final def isEmpty = finals.isEmpty; + +} diff --git a/sources/scala/util/automata/WordBerrySethi.scala b/sources/scala/util/automata/WordBerrySethi.scala new file mode 100644 index 0000000000..890c8cae1d --- /dev/null +++ b/sources/scala/util/automata/WordBerrySethi.scala @@ -0,0 +1,209 @@ +package scala.util.automata ; + +import scala.util.alphabet.Alphabet ; +import scala.util.regexp.WordExp ; + +import scala.collection.{ mutable, Map } ; +import scala.collection.immutable ; + +/** this turns a regexp over A into a NondetWordAutom over A using the + * celebrated position automata construction (also called Berry-Sethi or + * Glushkov) + */ +abstract class WordBerrySethi[ A <: Alphabet ] extends BaseBerrySethi { + + override val lang: WordExp[ A ]; + import lang.{Alt,Eps,Letter,Meta,RegExp,Sequ,Star} ; + + + protected var labels:mutable.HashSet[A] = _ ; + // don't let this fool you, only labelAt is a real, surjective mapping + protected var labelAt: immutable.TreeMap[int, A] = _; // new alphabet "gamma" + + protected var deltaq: Array[mutable.HashMap[A,List[Int]]] = _; // delta + + protected var defaultq: Array[List[Int]] = _; // default transitions + + protected var initials:immutable.Set[Int] = _ ; + //NondetWordAutom revNfa ; + + /** computes first( r ) where the word regexp r */ + protected override def compFirst(r: RegExp): immutable.Set[Int] = r match { + case x:Letter => emptySet + posMap(x); // singleton set + case _ => super.compFirst(r); + } + + /** computes last( r ) where the word regexp r */ + protected override def compLast(r: RegExp): immutable.Set[Int] = r match { + case x:Letter => emptySet + posMap(x) // singleton set + case _ => super.compLast(r) + } + + /** returns the first set of an expression, setting the follow set along + * the way + */ + protected override def compFollow1( fol1:immutable.Set[Int], r:RegExp ): immutable.Set[Int] = + r match { + + case x:Letter => + val i = posMap( x ); + this.follow.update( i, fol1 ); + emptySet + i; + + case _ => super.compFollow1(fol1, r) + + } + + /** returns "Sethi-length" of a pattern, creating the set of position + * along the way + */ + + + /** called at the leaves of the regexp */ + protected def seenLabel( r:RegExp, i:Int, label: A ): Unit = { + this.posMap.update( r, i ); + this.labelAt.update( i, label ); + //@ifdef if( label != Wildcard ) { + this.labels += label ; + //@ifdef } + } + + // overriden in BindingBerrySethi + protected def seenLabel( r: RegExp, label: A ): Unit = { + pos = pos + 1; + seenLabel( r, pos, label ); + } + + + // todo: replace global variable pos with acc + override def traverse(r: RegExp): Unit = r match { + case Letter( label ) => seenLabel( r, label ) ; + case _ => super.traverse(r) + } + + + protected def makeTransition(src: Int, dest:Int, label: A ):Unit = { + //@ifdef compiler if( label == Wildcard ) + //@ifdef compiler defaultq.update(src, dest::defaultq( src )) + //@ifdef compiler else + val q = deltaq( src ); + q.update(label, dest::(q.get(label) match { + case Some(x) => x + case _ => Nil + })); + } + + protected def initialize(subexpr: Seq[RegExp]): Unit = { + this.posMap = new mutable.HashMap[RegExp,Int](); + this.labelAt = new immutable.TreeMap[Int,A](); + this.follow = new mutable.HashMap[Int,immutable.Set[Int]](); + this.labels = new mutable.HashSet[A](); + + this.pos = 0; + + // determine "Sethi-length" of the regexp + //activeBinders = new Vector(); + var it = subexpr.elements; + while( it.hasNext ) + traverse( it.next ); + + //assert ( activeBinders.isEmpty() ); + this.initials = emptySet + 0; + } + + protected def initializeAutom(): Unit = { + + finals = immutable.TreeMap.Empty[Int,Int]; // final states + deltaq = new Array[mutable.HashMap[A,List[Int]]]( pos ); // delta + defaultq = new Array[List[Int]]( pos ); // default transitions + + var j = 0; + while( j < pos ) { + deltaq( j ) = new mutable.HashMap[A,List[Int]](); + defaultq( j ) = Nil; + j = j + 1 + } + } + + protected def collectTransitions(): Unit = { // make transitions + var j = 0; + while( j < pos ) { + val fol = this.follow( j ); + val it = fol.elements; + while( it.hasNext ) { + val k = it.next; + if( pos == k ) + finals.update( k, finalTag ) + else + makeTransition( j, k, labelAt( k )) + } + j = j + 1; + } + } + + def automatonFrom(pat: RegExp, finalTag: Int): NondetWordAutom[ A ] = { + this.finalTag = finalTag; + + pat match { + case x:Sequ => + // (1,2) compute follow + first + initialize( x.rs ); + pos = pos + 1; + globalFirst = compFollow( x.rs ); + + //System.out.print("someFirst:");debugPrint(someFirst); + // (3) make automaton from follow sets + initializeAutom(); + collectTransitions(); + + if( x.isNullable ) // initial state is final + finals.update( 0, finalTag ); + + var delta1: immutable.TreeMap[Int,Map[A,List[Int]]] = + new immutable.TreeMap[Int,Map[A,List[Int]]]; + + var i = 0; + while( i < deltaq.length ) { + delta1 = delta1.update( i, deltaq( i )); + i = i + 1; + } + + new NondetWordAutom[ A ] { + val nstates = pos; + val labels = WordBerrySethi.this.labels; + val initials = WordBerrySethi.this.initials; + val finals = WordBerrySethi.this.finals; + val delta = delta1; + val default = defaultq; + } + case _ => error("expected Sequ"); + } + } + + /* + void print1() { + System.out.println("after sethi-style processing"); + System.out.println("#positions:" + pos); + System.out.println("posMap:"); + + for( Iterator it = this.posMap.keySet().iterator(); + it.hasNext(); ) { + Tree t = (Tree) it.next(); + switch(t) { + case Literal( _ ): + System.out.print( "(" + t.toString() + " -> "); + String s2 = ((Integer) posMap.get(t)).toString(); + System.out.print( s2 +") "); + } + } + System.out.println("\nfollow: "); + for( int j = 1; j < pos; j++ ) { + TreeSet fol = (TreeSet) this.follow.get(new Integer(j)); + System.out.print("("+j+" -> "+fol.toString()+") "); + //debugPrint( fol ); + System.out.println(); + } + + } + */ +} |