diff options
author | buraq <buraq@epfl.ch> | 2004-11-16 16:21:13 +0000 |
---|---|---|
committer | buraq <buraq@epfl.ch> | 2004-11-16 16:21:13 +0000 |
commit | 18b44350ef5670d58504462395dbdb6ca082f8bc (patch) | |
tree | 46a76199e11c40c2f18525b54dbbaaca17537a5e /sources | |
parent | 27410be7531a1f9e7642f5292c51672968ca5c0d (diff) | |
download | scala-18b44350ef5670d58504462395dbdb6ca082f8bc.tar.gz scala-18b44350ef5670d58504462395dbdb6ca082f8bc.tar.bz2 scala-18b44350ef5670d58504462395dbdb6ca082f8bc.zip |
fix
Diffstat (limited to 'sources')
-rw-r--r-- | sources/scala/runtime/matching/Matcher.scala | 214 | ||||
-rw-r--r-- | sources/scala/runtime/matching/PatternGrammar.scala | 185 | ||||
-rw-r--r-- | sources/scala/util/automata/NondetWordAutom.scala | 4 | ||||
-rw-r--r-- | sources/scala/util/automata/WordBerrySethi.scala | 34 | ||||
-rw-r--r-- | sources/scala/util/grammar/ImmutableTreeHedgeGrammar.scala | 28 | ||||
-rw-r--r-- | sources/scala/util/grammar/MutableTreeHedgeGrammar.scala | 65 | ||||
-rw-r--r-- | sources/scala/util/grammar/TreeHedgeGrammar.scala | 27 |
7 files changed, 32 insertions, 525 deletions
diff --git a/sources/scala/runtime/matching/Matcher.scala b/sources/scala/runtime/matching/Matcher.scala deleted file mode 100644 index 5482a78991..0000000000 --- a/sources/scala/runtime/matching/Matcher.scala +++ /dev/null @@ -1,214 +0,0 @@ -package scala.runtime.matching ; - -import scala.collection.Set; -import scala.collection.Map; -import scala.collection.mutable; -import scala.collection.immutable ; - -import scala.util.grammar.{ LabelledRHS, AnyTreeRHS, TreeRHS, ConsRHS, HedgeRHS }; -/** this class matches input against a grammar. A call to matchesT (matchesH) -** returns the list of initial tree (hedge) nonterminals that generate the -** input. -** @author Burak Emir -**/ -class Matcher( pgram:PatternGrammar ) { - - val treeTransitions = pgram.treeTransitions; - val hedgeTransitions = pgram.hedgeTransitions; - - /** convenience method */ - def singT( T:Int ) = immutable.ListSet.Empty[Int] + T; - - /** convenience method */ - def singH( H:Int ) = immutable.ListSet.Empty[Int] + H; - - /** top-level call - ** @todo remove sanity check - ** @return index of the first applicable nonterminal in initials - **/ - def matchesT( input:Any ):Iterator[Int] = - if( !pgram.isSequenceType ) - isApplicableTree( pgram.treeInitials.toSet(true), input ).elements; - else - error("trying to match hedge against tree grammar"); - - /** top-level call - ** @todo remove sanity check - ** @return index of the first applicable nonterminal in initials - **/ - def matchesH( h:Seq[Any] ):Iterator[Int] = - if( pgram.isSequenceType ) - isApplicableHedge( pgram.hedgeInitials.toSet(true), h.elements ).elements; - else - error("trying to match tree against hedge grammar"); - - /** top-level call - **/ - def isApplicableTree1( T:Int, t:Any ):boolean = - !isApplicableTree( singT( T ), t ).isEmpty; - - /** top-level call - **/ - def isApplicableHedge1( H:Int, h:Iterator[Any] ):boolean = - !isApplicableHedge( singH( H ), h ).isEmpty; - - - def getChildren( t:Any ):Iterator[Any] = t match { - //case n:scala.xml.Node => n.child; - case n:Seq[Any] => n.elements; - case n:CaseClass => Iterator.fromCaseClass( n ); - case _ => Iterator.empty[Any]; - } -// ------------------------------------------------------------------------ - - /** given set of tree nonterms initialNTs and input tree t, returns - ** { T | T in initialNTs, - ** T -> a<H> in rules, - ** isApplicable( H, t.children ) } - */ - protected def isApplicableTree( initialNTs:Set[Int/*TreeNT*/], - t:Any ):immutable.Set[Int/*TreeNT*/] = { - var hedgeNTs = immutable.ListSet.Empty[Int]; - var tmpNTs = immutable.ListSet.Empty[Int]; - var result = immutable.ListSet.Empty[Int]; - - //Console.println("isApplicableTree("+ initialNTs+","+t+")"); - for( val n <- initialNTs ) { - //Console.println("checking nt "+n); - for( val rule <- treeTransitions( n ) ) { - //Console.println("checking rule"+rule); - rule match { - - case AnyTreeRHS => - result = result + n; - - case LabelledRHS( AnyNode, newNT ) => - tmpNTs = tmpNTs + n; - hedgeNTs = hedgeNTs + newNT; - - case LabelledRHS( TestLabel(test), newNT ) - if pgram.test( test, t ) => - //Console.println("success for test "+test); - tmpNTs = tmpNTs + n; - hedgeNTs = hedgeNTs + newNT; - - - case _ => - //Console.println("no use"); - } - } - } - if( !hedgeNTs.isEmpty ) { - val applHedgeNTs = isApplicableHedge( hedgeNTs, getChildren( t ) ); - for( val tn <- tmpNTs ) { - for( val rule <- treeTransitions( tn )) { - rule match { - - case LabelledRHS( AnyNode, nt ) - if applHedgeNTs.contains( nt ) => - result = result + tn; - - case LabelledRHS( _ , nt ) /** type test in rule determined by ttn and nt */ - if applHedgeNTs.contains( nt ) => - result = result + tn; - - case _ => - } - } - } - } - //Console.println("RET isApplicableTree"+ initialNTs+","+t+") " + result); - result - } - - /** given set of hedge nonterms initialNTs and input hedge h, returns - ** { H | H in initialNTs, - ** T -> a<H> in rules, - ** isApplicable( H, t.children ) - */ - def isApplicableHedge( initialNTs:Set[Int/*HedgeNT*/], - it:Iterator[Any] ):immutable.Set[Int/*HedgeNT*/] = { - - //Console.println("isApplicableHedge("+initialNTs+",...)"); - - if( !it.hasNext ) { - var set = immutable.ListSet.Empty[Int]; - for( val h <- initialNTs ) { - //Console.println("isNullable("+h+")="+pgram.isNullable(h)); - if( pgram.isNullable( h )) { set = set + h; } - } - //Console.println("RET isApplicableHedge("+initialNTs+","+h+") " + set.toString()); - set /*+ EmptySeqNT */ - - } else { - val first = it.next; - var treeNTs = immutable.ListSet.Empty[Int]; - - for( val h <- initialNTs ) { - for( val rule <- hedgeTransitions( h ) ) { - /* all non-empty rules that start with some H in initialHedgeNTs */ - rule match { - case ConsRHS( treeNT , _ ) => { - treeNTs = treeNTs + treeNT - } - case _ => - } - } - } - val applTreeNTs = isApplicableTree( treeNTs, first ); - - var nextHedgeNTs = immutable.ListSet.Empty[Int/*HedgeNT*/]; - for( val h <- initialNTs; - val rule <- hedgeTransitions( h ) ) { - /* all non-empty rules that start with some H in initialHedgeNTs */ - rule match { - case ConsRHS( treeNT , nH ) - if( applTreeNTs.contains( treeNT )) => - nextHedgeNTs = nextHedgeNTs + nH - - case _ => - } - } - - val applNextHedgeNTs = isApplicableHedge( nextHedgeNTs, it ); - - var applHedgeNTs = immutable.ListSet.Empty[Int/*HedgeNT*/]; - - for( val nH <- applNextHedgeNTs; - val h <- initialNTs; - val rule <- hedgeTransitions( h ) ) { - /* all non-empty rules that start with some H in initialHedgeNTs */ - val H = nH; - rule match { - case ConsRHS( treeNT , H ) => { - applHedgeNTs = applHedgeNTs + h - } - case _ => - } - } -/* - - var applHNTs = immutable.ListSet.Empty[HedgeNT]; - - // go through all chain rules starting with initialNTs2's - for( val h <- initialNTs2, - val g <- applHedgeNTs ){ - // and check whether they can derive an applHedgeNT - if( followChainRules( immutable.ListSet.Empty[HedgeNT] + h, - hedgeRules ) - .contains( g ) ) { - applHNTs = applHNTs + h - } - } - } - */ - //Console.println("RET isApplicableHedge( " + initialNTs + ",...) " + applHedgeNTs); - /* applHNTs */ -applHedgeNTs /* no chain rules stuff needed */ - } - } - - - -} - diff --git a/sources/scala/runtime/matching/PatternGrammar.scala b/sources/scala/runtime/matching/PatternGrammar.scala deleted file mode 100644 index c98ac350cd..0000000000 --- a/sources/scala/runtime/matching/PatternGrammar.scala +++ /dev/null @@ -1,185 +0,0 @@ -package scala.runtime.matching ; -import scala.util.grammar._; -import scala.collection.{ immutable, mutable, Map, Set }; - -object PatternGrammar { - def encodeTreeRHS(x:TreeRHS):String = x match { - case LabelledRHS(TestLabel(test),hnt) => - val sb = new StringBuffer(); - sb.append(test); - sb.append('/'); - sb.append(hnt); - sb.toString(); - case AnyTreeRHS => "_" - } - def decodeTreeRHS(s:String):TreeRHS = s.charAt(0) match { - case '_' => AnyTreeRHS; - case _ => - val s2 = s.split("/"); - val test = Integer.parseInt(s2(0)); - val hnt = Integer.parseInt(s2(1)); - LabelledRHS(TestLabel(test),hnt); - } - def encodeHedgeRHS(x:HedgeRHS):String = x match { - case ConsRHS(tnt, hnt) => - val sb = new StringBuffer(); - sb.append(tnt); - sb.append('/'); - sb.append(hnt); - sb.toString(); - case AnyHedgeRHS => "A" - } - def decodeHedgeRHS(s:String):HedgeRHS = s.charAt(0) match { - case 'A' => AnyHedgeRHS; - case _ => - val s2 = s.split("/"); - val tnt = Integer.parseInt(s2(0)); - val hnt = Integer.parseInt(s2(1)); - ConsRHS(tnt,hnt); - } - def decode(str: String, tests: PatternTests): PatternGrammar = { - val sq:Seq[String] = str.split("#"); - //Console.println("sq.length"+sq.length); - val it = sq.elements; - - def readIntArray(length: Int): Array[Int] = { - val arr = new Array[Int](length); - var i = 0; - while(i < length) { - arr(i) = Integer.parseInt(it.next); - i = i + 1; - } - arr - } - def readBitSet(n: Int): immutable.BitSet = { - val len = (n >>> 5) + (if( (n & 0x1F)!= 0 ) 1 else 0); - new immutable.BitSet(n,readIntArray(len),false); - } - def readTransitionsT: immutable.Set[TreeRHS] = { - val trans = it.next; - //Console.println("T trans = "+trans); - var r = new immutable.ListSet[TreeRHS]; - if(trans.length() == 0) - return r; - val s:Array[String] = trans.split(","); - var i = 1; - while( i < s.length) { - r = r + PatternGrammar.decodeTreeRHS(s(i)); - i = i + 1; - } - r - } - def readTransitionsH: immutable.Set[HedgeRHS] = { - val trans = it.next; - //Console.println("H trans = "+trans); - val s:Array[String] = trans.split(","); - var r = new immutable.ListSet[HedgeRHS]; - if(trans.length() == 0) - return r; - var i = 1; - while(i < s.length) { - r = r + PatternGrammar.decodeHedgeRHS(s(i)); - i = i + 1; - } - r - } - - val _nTreeNT = Integer.parseInt( it.next ); - //Console.println("read _nTreeNT:"+_nTreeNT); - val _nHedgeNT = Integer.parseInt( it.next ); - //Console.println("read _nHedge:"+_nHedgeNT); - val _treeInitials = readBitSet( _nTreeNT ); - //Console.println("read treeInitials:" + _treeInitials.toArray); - val _hedgeInitials = readBitSet( _nHedgeNT ); - //Console.println("read hedgeInitials:" + _hedgeInitials.toArray); - val _isNullable = readBitSet( _nHedgeNT ); - //Console.println("read isNullable:" + _isNullable.toArray); - var i = 0; - val _treeTransitions = new Array[immutable.Set[TreeRHS]](_nTreeNT); - while(i < _nTreeNT) { - _treeTransitions(i) = readTransitionsT; - i = i + 1; - } - i = 0; - val _hedgeTransitions = new Array[immutable.Set[HedgeRHS]](_nHedgeNT); - while(i < _nHedgeNT) { - _hedgeTransitions(i) = readTransitionsH; - i = i + 1; - } - new PatternGrammar { - val nTreeNT = _nTreeNT; - val nHedgeNT = _nHedgeNT; - val treeInitials = _treeInitials; - val hedgeInitials = _hedgeInitials; - val isNullable = _isNullable; - val treeTransitions = _treeTransitions; - val hedgeTransitions = _hedgeTransitions; - val vars = new Array[Int](0); // @todo - final def test(i:Int, inp:Any) = tests(i,inp); - } - } -} - -/** runtime representation of patterns. This class augments - * scala.util.grammar.TreeHedgeGrammar, with an abstract representation - * of variable bindings. Variables are simply consecutive integers, - * following pre-order of occurrence in pattern - * @caseVars an array, field i holding the number of variables in case i - */ -abstract class PatternGrammar extends scala.util.grammar.ImmutableTreeHedgeGrammar { - - val vars:Array[Int]; - - def test(test:Int, inp:Any): Boolean; - - def isSequenceType: Boolean = { treeInitials.toSet(true).isEmpty }; - - def encode: String = { - val sb = new StringBuffer(); - def writeInt(i: Int) = { - sb.append(i); - sb.append('#'); - } - def writeIntArray(arr:Array[Int]) = { - var i = 0; - while(i < arr.length) { - sb.append(arr(i)); - sb.append('#'); - i = i + 1; - } - } - - writeInt( nTreeNT ); // nTreeNT - writeInt( nHedgeNT ); // nHedgeNT - writeIntArray(treeInitials.toArray); // treeInitials - writeIntArray(hedgeInitials.toArray); // hedgeInitials - writeIntArray(isNullable.toArray); // isNullable - // treeTransitions - var i = 0; - while(i < nTreeNT) { - val set = treeTransitions(i).elements; - sb.append('n'); - while( set.hasNext ) { - sb.append(','); - sb.append(PatternGrammar.encodeTreeRHS(set.next)); - } - sb.append('#'); - i = i + 1; - } - // hedgeTransitions - i = 0; - while(i < nHedgeNT) { - val set = hedgeTransitions(i).elements; - sb.append('n'); - while( set.hasNext ) { - sb.append(','); - sb.append(PatternGrammar.encodeHedgeRHS(set.next)); - } - sb.append('#'); - i = i + 1; - } - sb.toString(); - } - - -} diff --git a/sources/scala/util/automata/NondetWordAutom.scala b/sources/scala/util/automata/NondetWordAutom.scala index 36b36db84a..be4347459e 100644 --- a/sources/scala/util/automata/NondetWordAutom.scala +++ b/sources/scala/util/automata/NondetWordAutom.scala @@ -14,12 +14,12 @@ abstract class NondetWordAutom { type T_label; val nstates: Int; - val finals: Array[Option[Int]] ; + val finals: Array[Int] ; // -1 means not final val delta: Array[Map[T_label,List[Int]]]; val default: Array[List[Int]]; /** returns true if the state is final */ - final def isFinal(state: Int) = !finals( state ).isEmpty; + final def isFinal(state: Int) = finals( state ) > -1; /** returns tag of final state */ final def finalTag(state: Int) = finals( state ); diff --git a/sources/scala/util/automata/WordBerrySethi.scala b/sources/scala/util/automata/WordBerrySethi.scala index dd37bf47d6..49203c08c2 100644 --- a/sources/scala/util/automata/WordBerrySethi.scala +++ b/sources/scala/util/automata/WordBerrySethi.scala @@ -169,14 +169,40 @@ abstract class WordBerrySethi extends BaseBerrySethi { delta1 = delta1.update( i, deltaq( i )); i = i + 1; } + val finalsArr = new Array[Int](pos); + { + var k = 0; while(k < pos) { + finalsArr(k) = finals.get(k).match { + case Some(z) => z; + case None => -1; + }; + k = k + 1; + } + } + + val initialsArr = new Array[Int](initials.size); + val it = initials.elements; + { + var k = 0; while(k < initials.size) { + initialsArr(k) = it.next; + k = k + 1; + } + } + val deltaArr = new Array[Map[T_label,List[Int]]](pos); + { + var k = 0; while(k < pos) { + deltaArr(k) = delta1(k); + k = k + 1; + } + } new NondetWordAutom { type T_label = WordBerrySethi.this.T_label; val nstates = pos; - val labels = WordBerrySethi.this.labels; - val initials = WordBerrySethi.this.initials; - val finals = WordBerrySethi.this.finals; - val delta = delta1; + //val labels = WordBerrySethi.this.labels; + val initials = initialsArr; + val finals = finalsArr; + val delta = deltaArr; val default = defaultq; } case _ => error("expected Sequ"); diff --git a/sources/scala/util/grammar/ImmutableTreeHedgeGrammar.scala b/sources/scala/util/grammar/ImmutableTreeHedgeGrammar.scala deleted file mode 100644 index 388b18ede5..0000000000 --- a/sources/scala/util/grammar/ImmutableTreeHedgeGrammar.scala +++ /dev/null @@ -1,28 +0,0 @@ -package scala.util.grammar; - -import scala.collection.immutable ; - -/** a mutable representation of hedge grammars. A hedge grammar over an - * alphabet consists of tree and hedge nonterminals (consecutive integers), - * and tree and hedge productions that relate them. Hedge nonterminals that - * can derive the empty hedge are called "nullable". initials tree - * or hedge nonterminals. - */ -abstract class ImmutableTreeHedgeGrammar extends TreeHedgeGrammar { - - /** number of tree nonterminals*/ - val nTreeNT: Int; - /** number of hedge nonterminals*/ - val nHedgeNT: Int; - /** inv: treeInitials.length == nTreeNT */ - val treeInitials: immutable.BitSet; - /** inv: hedgeInitials.length == nHedgeNT */ - val hedgeInitials: immutable.BitSet; - /** inv: isNullable.length == nHedgeNT */ - val isNullable: immutable.BitSet; - /** inv: treeTransitions.length == nTreeNT */ - val treeTransitions: Array[immutable.Set[TreeRHS]]; - /** inv: hedgeTransitions.length == nHedgeNT */ - val hedgeTransitions: Array[immutable.Set[HedgeRHS]]; - -} diff --git a/sources/scala/util/grammar/MutableTreeHedgeGrammar.scala b/sources/scala/util/grammar/MutableTreeHedgeGrammar.scala deleted file mode 100644 index 3798e2e631..0000000000 --- a/sources/scala/util/grammar/MutableTreeHedgeGrammar.scala +++ /dev/null @@ -1,65 +0,0 @@ -package scala.util.grammar; - -import scala.collection.mutable ; - -/** a mutable representation of hedge grammars. A hedge grammar over an - * alphabet consists of tree and hedge nonterminals (consecutive integers), - * and tree and hedge productions that relate them. Hedge nonterminals that - * can derive the empty hedge are called "nullable". initials tree - * or hedge nonterminals. - */ -class MutableTreeHedgeGrammar[ A ] { - - /** number of tree nonterminals*/ - var nTreeNT: Int = 0; - /** number of hedge nonterminals*/ - var nHedgeNT: Int = 0; - /** inv: treeInitials.length == nTreeNT */ - val treeInitials = new mutable.BitSet(); - /** inv: hedgeInitials.length == nHedgeNT */ - val hedgeInitials = new mutable.BitSet(); - /** inv: hedgeIsNullable.length == nHedgeNT */ - val isNullable = new mutable.BitSet();; - val treeTransitions: mutable.Map[Int, mutable.Set[TreeRHS]] = - new mutable.HashMap[Int, mutable.Set[TreeRHS]]; - val hedgeTransitions: mutable.Map[Int, mutable.Set[HedgeRHS]] = - new mutable.HashMap[Int, mutable.Set[HedgeRHS]]; - - def makeTreeNT = { - val r = nTreeNT; - nTreeNT = nTreeNT + 1; - treeInitials.ensureSize( nTreeNT ); - treeTransitions.update(r, new mutable.HashSet[TreeRHS]()); - r - } - - def makeHedgeNT = { - val r = nTreeNT; - nHedgeNT = nHedgeNT + 1; - hedgeInitials.ensureSize( nHedgeNT ); - hedgeTransitions.update(r, new mutable.HashSet[HedgeRHS]()); - r - } - - def addConsRule(hnt1: Int,tnt: Int,hnt2: Int): Unit = - addHedgeRule(hnt1, ConsRHS(tnt, hnt2)); - - def addAnyHedgeRule(hnt: Int): Unit = - addHedgeRule(hnt, AnyHedgeRHS); - - def addEmptyHedgeRule(hnt: Int): Unit = - addHedgeRule(hnt, EmptyHedgeRHS); - - def addHedgeRule(hnt: Int, rhs: HedgeRHS): Unit = - hedgeTransitions( hnt ) += rhs; - - def addTreeRule(tnt: Int, label: A, hnt: Int): Unit = - addTreeRule(tnt, LabelledRHS( label, hnt )); - - def addAnyTreeRule(tnt: Int): Unit = - addTreeRule(tnt, AnyTreeRHS); - - def addTreeRule(tnt: Int,rhs: TreeRHS): Unit = - treeTransitions( tnt ) += rhs; - -} diff --git a/sources/scala/util/grammar/TreeHedgeGrammar.scala b/sources/scala/util/grammar/TreeHedgeGrammar.scala deleted file mode 100644 index 2cfef1c105..0000000000 --- a/sources/scala/util/grammar/TreeHedgeGrammar.scala +++ /dev/null @@ -1,27 +0,0 @@ -package scala.util.grammar; - -import scala.collection.{ BitSet, Set, mutable } ; - -/** a mutable representation of hedge grammars. A hedge grammar over an - * alphabet consists of tree and hedge nonterminals (consecutive integers), - * and tree and hedge productions that relate them. Hedge nonterminals that - * can derive the empty hedge are called "nullable". initials tree - * or hedge nonterminals. - */ -abstract class TreeHedgeGrammar { - - /** number of tree nonterminals*/ - def nTreeNT: Int; - /** number of hedge nonterminals*/ - def nHedgeNT: Int; - /** inv: treeInitials.size == nTreeNT */ - def treeInitials: BitSet; - /** inv: hedgeInitials.size == nHedgeNT */ - def hedgeInitials: BitSet; - /** inv: isNullable.size == nHedgeNT */ - def isNullable: BitSet; - - def treeTransitions: Array[Set[TreeRHS]] ; - def hedgeTransitions: Array[Set[HedgeRHS]] ; - -} |