more representation changes

9 files changed, 311 insertions, 95 deletions

diff --git a/sources/scala/runtime/matching/Grammar.scala b/sources/scala/runtime/matching/Grammar.scala
index 89fdc0c12a..4bd2489f59 100644
--- a/sources/scala/runtime/matching/Grammar.scala
+++ b/sources/scala/runtime/matching/Grammar.scala
@@ -5,25 +5,164 @@ import scala.collection.Map ;
 import scala.collection.immutable;
 import scala.collection.mutable;
 
-//val ruleOrder = new Order( rule_smaller, rule_eq );
 /** runtime representation of patterns. This class treats all variable
  *  indices as sequence variables
  *  @caseVars an array, field i holding the number of variables in case i
  */
-abstract class Grammar( theTreeTransitions:Map[Int,Set[TRule]],
-                        theHedgeTransitions:Map[Int,Set[HRule]],
-                        theVars:Array[Int] ) {
+class Grammar {
 
-  final val treeTransitions = theTreeTransitions ;
-  final val hedgeTransitions = theHedgeTransitions ;
+  var treeTransitions:  Array[immutable.Set[TRule]] = _; /*i:(i,test,hnt) */
+  var hedgeTransitions: Array[immutable.Set[HRule]] = _; /*i:(i,tnt,hnt)*/
   /** for cases 1..n, holds max. variable index */
-  final val vars = theVars;
+  var vars:Array[Int] = _;
+  //val vsetTree:Array[Set[Int]] ;
+  //val vsetHedge:Array[Set[Int]] ;
 
-  val treeInitials:Set[TreeNT] ;
-  val hedgeInitials:Set[HedgeNT] ;
+  var treeInitials:Set[TreeNT]  = _;
+  var hedgeInitials:Set[HedgeNT] = _;
 
-  def test( test:int, inp:Any ):boolean ;
+  def test(test:int, inp:Any):boolean = false;
 
   final def isSequenceType = treeInitials.isEmpty;
 
+  /*
+  protected def allTreeNT: Array[TreeNT] = {
+    val ar = new Array[TreeNT]( treeTransitions.length );
+    for( val tr <- treeTransitions ) {
+      tr.elements.next match {
+        case TreeRule(n,_,_)  =>
+        case AnyTreeRule(n)   =>
+        case AnyNodeRule(n,_) =>
+      }
+    }
+  }
+  */
+  //val hedgeNT:          Array[HedgeNT];
+
+  final def encode:Array[Byte] = {
+    val bos = new java.io.ByteArrayOutputStream();
+    val obos = new java.io.ObjectOutputStream(bos);
+    obos.writeObject(this);
+    bos.toByteArray();
+  }
+  /*
+  var i = 0;
+    val sb = new StringBuffer();
+    sb.append( treeTransitions.length.toString() )
+    sb.append('#')
+    while( i < treeTransitions.length ) {
+      sb.append( Grammar.encodeTRuleSet( treeTransitions( i )));
+      sb.append('#')
+      i = i + 1;
+    }
+    sb.append( hedgeTransitions.length.toString() )
+    sb.append('#')
+    i = 0;
+    while( i < hedgeTransitions.length ) {
+      sb.append( Grammar.encodeHRuleSet( hedgeTransitions( i )));
+      i = i + 1;
+    }
+    sb.append('#')
+  }
+  */
+
 }
+
+
+/*
+object Grammar {
+
+    new Grammar  {
+      override val treeTransitions  = theTreeTransitions;
+      override val hedgeTransitions = theHedgeTransitions;
+      override val vars             = theVars;
+      override val treeInitials     = null;//theTreeInitials;
+      override val hedgeInitials    = null;//theHedgeInitials;
+      // @todo
+      //def test( test:int, inp:Any ):boolean = { false; };
+    }
+  }
+
+
+  final def decodeTRuleSet(trules: String): immutable.Set[TRule]= {
+    new immutable.ListSet[TRule]();
+  }
+
+  final def decodeHRuleSet(trules: String): immutable.Set[HRule]= {
+    new immutable.ListSet[HRule]();
+  }
+
+  final def encodeTRuleSet(trules: immutable.Set[TRule]):String = {
+    "";
+  }
+
+  final def encodeHRuleSet(trules: immutable.Set[TRule]):String = {
+    "";
+  }
+
+}
+*/
+
+
+  /*
+  object & {
+    final def x (s:String): Int = Integer.parseInt(s, 16);
+  }
+  def decode(s: String): Grammar = {
+    val z:Array[String] = s.split("#");
+    var i = 0;
+    val tlength = & x z(0) ;
+    var j = 1;
+    var theTreeTransitions = new Array[immutable.Set[TRule]]( tlength );
+    while( i < tlength ) {
+      theTreeTransitions.update( i, Grammar.decodeTRuleSet(z( j )));
+      i = i + 1;
+      j = j + 1;
+    }
+    val hlength = & x z(j);
+    j = j + 1;
+    var theHedgeTransitions = new Array[immutable.Set[HRule]]( hlength );
+    i = 0;
+    j = j + 1;
+    while( i < hlength ) {
+      theHedgeTransitions.update( i, Grammar.decodeHRuleSet(z( j )));
+      i = i + 1;
+      j = j + 1;
+    }
+    val vlength = & x z(j);
+    j = j + 1;
+    var theVars = new Array[Int]( vlength );
+    i = 0;
+    while( i < vlength ) {
+      theVars.update( i, Integer.parseInt(z( j ),16));
+      i = i + 1;
+      j = j + 1;
+    }
+
+    val tilength = & x z(j) ;
+    j = j + 1;
+    var theTreeInitials = new Array[TreeNT]( tilength );
+    i = 0;
+    while( i < vlength ) {
+      theTreeInitials.update( i, new TreeNT( & x z( j )));
+      i = i + 1;
+      j = j + 1;
+    }
+
+
+    val hilength = & x z(j) ;
+    j = j + 1;
+    var theHedgeInitials = new Array[HedgeNT]( hilength );
+    i = 0;
+    while( i < hilength ) {
+      val hi = & x z( j );
+      theHedgeInitials.update( i, {
+        if( hi < 0 )
+          new HedgeNT(-hi, true);
+        else
+          new HedgeNT(hi, false);
+      });
+      i = i + 1;
+      j = j + 1;
+    }
+  */
diff --git a/sources/scala/tools/scalac/transformer/matching/FullRegularTranslator.scala b/sources/scala/tools/scalac/transformer/matching/FullRegularTranslator.scala
index 486bb4b2d4..e30b7baa7f 100644
--- a/sources/scala/tools/scalac/transformer/matching/FullRegularTranslator.scala
+++ b/sources/scala/tools/scalac/transformer/matching/FullRegularTranslator.scala
@@ -1,4 +1,3 @@
-
 import scala.runtime.matching._ ;
 
 import scala.collection.Set;
@@ -11,14 +10,8 @@ import scalac.{Global => scalac_Global}
 import scalac.symtab._;
 import scalac.util.Names ;
 
-
-
 package scala.tools.scalac.transformer.matching {
 
-
-  import PatternInfo.minimalWidth;
-  import TreeInfo.isSequenceValued;
-
 /** generates from a pattern (with variable names v_1,..,v_k)
  *  a set of regular hedge grammar rules,
  *  together with an variable index mapping 1,..,k
@@ -26,6 +19,9 @@ package scala.tools.scalac.transformer.matching {
  */
 class FullRegularTranslator(global: scalac_Global) {
 
+  val pe  = new matching.PatternExp( global.definitions );
+  import pe._ ;
+
   /* --- real variables --- */
 
   /** the grammar that we build up incrementally */
@@ -71,10 +67,10 @@ class FullRegularTranslator(global: scalac_Global) {
       }
 
   /** returns a test index for this variable
-  */
     def newTest( test:Tree ):Int = {
       0 // bogus
     }
+  */
 
 
 
@@ -85,20 +81,19 @@ class FullRegularTranslator(global: scalac_Global) {
     var k = 0;
     cur = InitialGrammar.make;
     while( it.hasNext )
-      translate( it.next.pat, { k = k + 1; k } );
+      translate( pe.fromTree(it.next.pat), { k = k + 1; k } );
     cur.toGrammar;
   }
 
   /** p must be a pattern
   */
-  protected def translate( p:Tree, k:Int ):unit = {
+  protected def translate( p:RegExp, k:Int ):unit = {
 
     this.varCounter = 0;
-    if( isSequenceValued( p ) ) {
-      this.isSequenceType = true;
+    this.isSequenceType = isSequenceValued( p );
+    if( this.isSequenceType ) {
       MakeHedgeRule( cur.make.initialHedgeNT, EMPTYHEDGE, emptyVars, p );
     } else {
-      this.isSequenceType = false;
       val in = cur.make.initialTreeNT;
       try {
         MakeTreeRule( in, emptyVars, p );
@@ -203,14 +198,14 @@ Afterwards: Chain rules need not be applied anymore. They only exist with
     }
       */
 
-    def sortByWidth( xs:Iterator[Tree] ):List[Tree] = {
+    def sortByWidth( xs:Iterator[RegExp] ):List[RegExp] = {
 
 
-      def view( x:Pair[Tree,int] ):Ordered[Pair[Tree,int]] =
-        new Ordered[Pair[Tree,int]] with Proxy( x ) {
-          def compareTo [b >: Pair[Tree,int] <% Ordered[b]](that: b): int =
+      def view( x:Pair[RegExp,int] ):Ordered[Pair[RegExp,int]] =
+        new Ordered[Pair[RegExp,int]] with Proxy( x ) {
+          def compareTo [b >: Pair[RegExp,int] <% Ordered[b]](that: b): int =
             that match {
-            case Pair(p:Tree,i:int) =>
+            case Pair(p:RegExp,i:int) =>
               if( minimalWidth( x._1 ) == minimalWidth( p ) ) {
                 if( x._2 < i ) -1 else
                   if( x._2 == i ) 0 else 1
@@ -223,7 +218,7 @@ Afterwards: Chain rules need not be applied anymore. They only exist with
           }
         };
 
-      var mySet = new immutable.TreeSet[Pair[Tree,int]]();
+      var mySet = new immutable.TreeSet[Pair[RegExp,int]]();
       var j = 1;
       for( val p <- xs ) {
         mySet = mySet + Pair(p,j);
@@ -238,7 +233,7 @@ Afterwards: Chain rules need not be applied anymore. They only exist with
     def MakeHedgeRule( in:HedgeNT,
                        out:HedgeNT,
                        vset: immutable.Set[Int],
-                       it:Iterator[Tree] ):unit = {
+                       it:Iterator[RegExp] ):unit = {
       DEBUGPRINT("MakeHedgeRule("+in+","+out+","+vset+","+it+")");
       var i = in;
       if( !it.hasNext ) {
@@ -255,23 +250,23 @@ Afterwards: Chain rules need not be applied anymore. They only exist with
 
   /*
   */
-  def MakeHedgeRule( in:HedgeNT, nt:HedgeNT, vset:immutable.Set[Int], pat:Tree):unit =
+  def MakeHedgeRule( in:HedgeNT, nt:HedgeNT, vset:immutable.Set[Int], pat:RegExp):unit =
     pat match {
       /*
       case Point() =>
 	cur.hedgeRules += new HedgeChainRule(in, iteration);
       cur.hedgeRules += new HedgeChainRule(in, iterationEnd);
       */
-      case Tree$Sequence( xs ) =>
-	MakeHedgeRule( in, nt, vset, Iterator.fromArray( xs ) );
+      case x:Sequ =>
+	MakeHedgeRule( in, nt, vset, x.rs.elements );
 
-      case Tree$Alternative( xs  ) =>
-	for( val z <- sortByWidth( Iterator.fromArray( xs ) ) ) {
+      case x:Alt =>
+	for( val z <- sortByWidth( x.rs.elements ) ) {
 	  MakeHedgeRule( in, nt, vset, z );
 	}
 
-      // Star( p )
-      case Tree$Bind(n, p) if TreeInfo.isNameOfStarPattern( n ) =>
+      case Star( p ) =>
+      //case Tree$Bind(n, p) if TreeInfo.isNameOfStarPattern( n ) =>
 	MakeHedgeRule( in, in, vset, p );
       cur.hedgeRules += new HedgeChainRule( in, nt );
 
@@ -301,9 +296,10 @@ Afterwards: Chain rules need not be applied anymore. They only exist with
       iteration = null;
       iterationEnd = null;
       */
-      case Tree$Bind( vble, p:Tree ) =>
-        if( isSequenceValued( p ) ) {
-	  MakeHedgeRule( in, nt, vset + newVar( pat.symbol() ), p );
+      case Binding( vble, p ) =>
+      //case Tree$Bind( vble, p:Tree ) =>
+        if (isSequenceValued( p )) {
+	  MakeHedgeRule( in, nt, vset + newVar( vble ), p );
         } else {
           try {
  	    val trNT = cur.make.TreeNT( vset );
@@ -327,35 +323,38 @@ Afterwards: Chain rules need not be applied anymore. They only exist with
     }
 
 
-  def MakeTreeRule( in:TreeNT, vset: immutable.Set[Int], pat:Tree):unit = {
+  def MakeTreeRule( in:TreeNT, vset: immutable.Set[Int], pat:RegExp):unit = {
     DEBUGPRINT("MakeTreeRule("+in+","+vset+","+pat+")");
     pat match {
+      case Wildcard =>
       // WildcardTree()
-      case Tree$Ident( Names.PATTERN_WILDCARD ) =>
+      // case Tree$Ident( Names.PATTERN_WILDCARD ) =>
         if( vset.isEmpty )
           throw new WildcardException(); // OPTIMIZATION to collapse _ rules
         else
           cur.treeRules += new AnyTreeRule( in );
       // WildcardNode( x @ _* )
-      case Tree$Apply( Tree$Ident( Names.PATTERN_WILDCARD ), xs ) =>
+      case Node(WildcardTest, sequ) =>
+      //case Tree$Apply( Tree$Ident( Names.PATTERN_WILDCARD ), xs ) =>
 	{
 	  val Children = cur.make.HedgeNT;
           cur.treeRules += new AnyNodeRule( in, Children );
-	  MakeHedgeRule( Children, EMPTYHEDGE, emptyVars, Iterator.fromArray( xs ));
+	  MakeHedgeRule( Children, EMPTYHEDGE, emptyVars, sequ);
 	}
       // Node( label:String, x @ _* ) => //p.type
-      case Tree$Apply( theTest, xs ) =>
+      case Node( theTest, sequ ) =>
+      //case Tree$Apply( theTest, xs ) =>
         val test = newTest( theTest ); //p.type
         val childrenNT = cur.make.HedgeNT; // make a new NT
         cur.treeRules += new TreeRule(in, test, childrenNT );
-        MakeHedgeRule( childrenNT, EMPTYHEDGE, emptyVars, Iterator.fromArray( xs ));
+        MakeHedgeRule( childrenNT, EMPTYHEDGE, emptyVars, sequ);
 
-      case Tree$Alternative( xs ) => // is tree valued
-        for(val pat<-Iterator.fromArray( xs ))
+      case x:Alt => // is tree valued
+        for(val pat <- x.rs.elements )
           MakeTreeRule( in, vset, pat );
 
-      case Tree$Bind( _, p:Tree ) =>
-        in.vset = in.vset + newVar( pat.symbol() );
+      case Binding( vble, p ) =>
+        in.vset = in.vset + newVar( vble );
         MakeTreeRule( in, in.vset, p );
 
       case _ => //DEBUGPRINT("error, we found "+p.getClass());
diff --git a/sources/scala/tools/scalac/transformer/matching/MutableGrammar.scala b/sources/scala/tools/scalac/transformer/matching/MutableGrammar.scala
index 56d4554751..145914d281 100644
--- a/sources/scala/tools/scalac/transformer/matching/MutableGrammar.scala
+++ b/sources/scala/tools/scalac/transformer/matching/MutableGrammar.scala
@@ -4,6 +4,9 @@ import scala.collection.mutable;
 import scala.runtime.matching._;
 import scalac.symtab._;
 
+import scala.util.alphabet.{ IntLabel, IntAlphabet };
+import scala.util.grammar.{ AnyTreeRHS, LabelledTreeRHS, TreeRHS, ConsRHS, HedgeRHS };
+
 package scala.tools.scalac.transformer.matching {
 
 
@@ -83,44 +86,92 @@ case class MutableGrammar( treeRules:mutable.Set[TRule],
       case None => immutable.ListSet.Empty[A] + r;
     });
 
+  /** converts this grammar in a pattern grammar (an ImmutableTreeHedgeGrammar with variable info)
+  */
+  def toGrammar:PatternGrammar = {
+    val rbsNullable = new mutable.ResizableBitSet();
+    val _treeTransitions:Array[immutable.Set[TreeRHS]] = {
+      val theTreeTransitionsMap: immutable.TreeMap[Int,immutable.Set[TreeRHS]] = {
+        var tmp =
+          immutable.TreeMap.Empty[Int,immutable.Set[TreeRHS]];
+        treeRules.foreach { treeRule => treeRule match {
+          case AnyTreeRule( t ) => tmp = add( t.i, AnyTreeRHS, tmp );
+          //case AnyNodeRule( t, _ ) => tmp = add( t.i, treeRule, tmp ) // ??!!!!!!!!!!!!!!!!!!!!!!
+          case TreeRule( t, i, h ) => tmp = add( t.i, LabelledTreeRHS(IntLabel(i),h.i), tmp )
+        }};
+        tmp
+      };
+      val arr = new Array[immutable.Set[TreeRHS]]( theTreeTransitionsMap.size );
+      val it = theTreeTransitionsMap.keys;
+      while( it.hasNext ) {
+        val k = it.next;
+        arr.update( k, theTreeTransitionsMap( k ));
+      }
+      arr
+    }
+    val _nTreeNT        = _treeTransitions.length;
+
+    val _hedgeTransitions: Array[immutable.Set[HedgeRHS]] = {
+      val theHedgeTransitionsMap: immutable.TreeMap[Int,immutable.Set[HedgeRHS]] = {
+        var tmp =
+          immutable.TreeMap.Empty[Int,immutable.Set[HedgeRHS]];
+        hedgeRules.foreach { hedgeRule => hedgeRule match {
+          case HedgeRule( h, t, h2 ) =>
+            rbsNullable.ensureSize( h2.i );
+            rbsNullable.set( h2.i, h2.nullable );
+            tmp = add( h.i, ConsRHS(t.i,h2.i), tmp );
+          case HedgeChainRule( h, _ ) => throw new RuntimeException();
+          //tmp = add( h.i, hedgeRule, tmp );
+        }};
+        // to maintain assumption that every hedge nt is present
+        tmp.update( 0, immutable.ListSet.Empty[HedgeRHS] );
+      };
+      val arr = new Array[immutable.Set[HedgeRHS]]( theHedgeTransitionsMap.size );
+      val it = theHedgeTransitionsMap.keys;
+      while( it.hasNext ) {
+        val k = it.next;
+        arr.update( k, theHedgeTransitionsMap( k ));
+      }
+      arr
+    }
+    val _nHedgeNT       = _hedgeTransitions.length ;
 
+    val _vars = new Array[Int]( caseVars.size );
+    val it = caseVars.keys;
+    while( it.hasNext ) {
+      val k = it.next;
+      _vars.update( k, caseVars( k ));
+    }
 
-  /** converts this grammar in a immutable grammar
-  */
-  def toGrammar:Grammar = {
-    val treeTransitions:immutable.TreeMap[Int,immutable.Set[TRule]] = {
-      var tmp =
-        immutable.TreeMap.Empty[Int,immutable.Set[TRule]];
-      treeRules.foreach { treeRule => treeRule match {
-        case AnyTreeRule( t ) => tmp = add( t.i, treeRule, tmp );
-        case AnyNodeRule( t, _ ) => tmp = add( t.i, treeRule, tmp )
-        case TreeRule( t, _, _ ) => tmp = add( t.i, treeRule, tmp )
-      }};
-      tmp
-    };
-    val hedgeTransitions:immutable.TreeMap[Int,immutable.Set[HRule]] = {
-      var tmp =
-        immutable.TreeMap.Empty[Int,immutable.Set[HRule]];
-      hedgeRules.foreach { hedgeRule => hedgeRule match {
-        case HedgeRule( h, _, _ ) => tmp = add( h.i, hedgeRule, tmp );
-        case HedgeChainRule( h, _ ) => tmp = add( h.i, hedgeRule, tmp );
-      }};
-      // to maintain assumption that every hedge nt is present
-      tmp.update( 0, immutable.ListSet.Empty[HRule] );
-    };
-    val theCaseVars = new Array[Int]( caseVars.size );
-    var i = 0;
-    for( val k <- caseVars.keys ) {
-      theCaseVars( i ) = caseVars( k );
-      i = i + 1
+    val _treeInitials = {
+      val rbs = new mutable.ResizableBitSet( _nTreeNT );
+      for( val k <- make.treeInitials ) {
+        rbs.set( k.i )
+      }
+      new immutable.BitSet(rbs)
     }
-    new Grammar( treeTransitions, hedgeTransitions, theCaseVars ) {
-      val treeInitials = make.treeInitials;
-      val hedgeInitials = make.hedgeInitials;
+
+    val _hedgeInitials = {
+      val rbs = new mutable.ResizableBitSet( _nHedgeNT );
+      for( val k <- make.hedgeInitials ) {
+        rbsNullable.ensureSize( k.i );
+        rbsNullable.set( k.i, k.nullable );
+        rbs.set( k.i )
+      }
+      new immutable.BitSet(rbs)
+    }
+    val _isNullable = new immutable.BitSet( rbsNullable );
+    new PatternGrammar {
+      val nTreeNT          = _nTreeNT;
+      val nHedgeNT         = _nHedgeNT;
+      val treeTransitions  = _treeTransitions;
+      val hedgeTransitions = _hedgeTransitions;
+      val vars             = _vars;
+      val treeInitials     = _treeInitials;
+      val hedgeInitials    = _hedgeInitials;
+      val isNullable       = _isNullable;
       // @todo
-      def test( test:int, inp:Any ):boolean = {
-        false;
-      };
+      def test( test:int, inp:Any ):boolean = { false; };
     }
   }
 
diff --git a/sources/scala/util/automata/NondetWordAutom.scala b/sources/scala/util/automata/NondetWordAutom.scala
index 548d4f68e1..95290d22c1 100644
--- a/sources/scala/util/automata/NondetWordAutom.scala
+++ b/sources/scala/util/automata/NondetWordAutom.scala
@@ -9,7 +9,7 @@ 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 delta:    Function1[Int,Map[A,List[Int]]];
   val default:  Array[List[Int]];
 
   /** returns true if the state is final */
diff --git a/sources/scala/util/grammar/HedgeRHS.scala b/sources/scala/util/grammar/HedgeRHS.scala
new file mode 100644
index 0000000000..e435909eb9
--- /dev/null
+++ b/sources/scala/util/grammar/HedgeRHS.scala
@@ -0,0 +1,12 @@
+package scala.util.grammar;
+
+abstract class HedgeRHS;
+
+/** right hand side of a hedge production, deriving a single tree */
+case class  ConsRHS(tnt: Int, hnt: Int) extends HedgeRHS;
+
+/** right hand side of a hedge production, deriving any hedge */
+case object AnyHedgeRHS extends HedgeRHS;
+
+/** right hand side of a hedge production, deriving the empty hedge */
+case object EmptyHedgeRHS extends HedgeRHS;
diff --git a/sources/scala/util/grammar/ImmutableTreeHedgeGrammar.scala b/sources/scala/util/grammar/ImmutableTreeHedgeGrammar.scala
index b758631121..62132a2aef 100644
--- a/sources/scala/util/grammar/ImmutableTreeHedgeGrammar.scala
+++ b/sources/scala/util/grammar/ImmutableTreeHedgeGrammar.scala
@@ -21,7 +21,7 @@ abstract class ImmutableTreeHedgeGrammar[ A <: Alphabet ] extends TreeHedgeGramm
   val hedgeInitials: immutable.BitSet;
   /** inv: isNullable.length == nHedgeNT */
   val isNullable: immutable.BitSet;
-  var treeTransitions:  Array[immutable.Set[TreeRHS]];
-  var hedgeTransitions: Array[immutable.Set[HedgeRHS]];
+  val treeTransitions:  Array[immutable.Set[TreeRHS]];
+  val hedgeTransitions: Array[immutable.Set[HedgeRHS]];
 
 }
diff --git a/sources/scala/util/grammar/MutableTreeHedgeGrammar.scala b/sources/scala/util/grammar/MutableTreeHedgeGrammar.scala
index 518ee1a6b3..59eabc50fe 100644
--- a/sources/scala/util/grammar/MutableTreeHedgeGrammar.scala
+++ b/sources/scala/util/grammar/MutableTreeHedgeGrammar.scala
@@ -42,14 +42,23 @@ class MutableTreeHedgeGrammar[ A <: Alphabet ] extends TreeHedgeGrammar[ A ] {
     r
   }
 
-  def addHedgeRule(hnt1: Int,tnt: Int,hnt2: Int): Unit =
-    addHedgeRule(hnt1, HedgeRHS(tnt, hnt2));
+  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, TreeRHS( label, hnt ));
+    addTreeRule(tnt, LabelledTreeRHS( 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
index 8837a1ba52..06af102869 100644
--- a/sources/scala/util/grammar/TreeHedgeGrammar.scala
+++ b/sources/scala/util/grammar/TreeHedgeGrammar.scala
@@ -11,11 +11,6 @@ import scala.collection.{ BitSet, Set, mutable } ;
  */
 abstract class TreeHedgeGrammar[ A <: Alphabet ] {
 
-  /** right hand side of a tree production */
-  case class TreeRHS(label: A, hnt: Int);
-  /** right hand side of a hedge production */
-  case class HedgeRHS(tnt: Int, hnt: Int);
-
   /** number of tree nonterminals*/
   def nTreeNT: Int;
   /** number of hedge nonterminals*/
diff --git a/sources/scala/util/grammar/TreeRHS.scala b/sources/scala/util/grammar/TreeRHS.scala
new file mode 100644
index 0000000000..6e365a5bf6
--- /dev/null
+++ b/sources/scala/util/grammar/TreeRHS.scala
@@ -0,0 +1,11 @@
+package scala.util.grammar;
+
+import scala.util.alphabet.Alphabet ;
+
+/** right hand side of a tree production */
+abstract class TreeRHS;
+
+/** right hand side of a tree production, labelled with a letter from an alphabet */
+case class  LabelledTreeRHS[A <: Alphabet](label: A, hnt: Int) extends TreeRHS;
+
+case object AnyTreeRHS extends TreeRHS;