convered maximal to use character lookahead

darcs-hash:20060102034924-5007d-d76e881205902ded81ca8826b94b9e865e1e232c.gz

diff --git a/src/edu/berkeley/sbp/Element.java b/src/edu/berkeley/sbp/Element.java
index 5f55be6..b440257 100644 (file)
--- a/src/edu/berkeley/sbp/Element.java
+++ b/src/edu/berkeley/sbp/Element.java
@@ -14,6 +14,7 @@ public abstract class Element {
     abstract void reachable(HashSet<Sequence.Position> rp);
 
     abstract Topology toAtom();
+    public Topology noFollow() { return null; }
     Forest epsilonForm() { throw new Error("no epsilon form: " + this); }
     final boolean possiblyEpsilon(Walk.Cache cache)   {
         Boolean ret = cache==null ? null : cache.possiblyEpsilon.get(this);

diff --git a/src/edu/berkeley/sbp/Repeat.java b/src/edu/berkeley/sbp/Repeat.java
index 48ac386..bc6626a 100644 (file)
--- a/src/edu/berkeley/sbp/Repeat.java
+++ b/src/edu/berkeley/sbp/Repeat.java
@@ -20,48 +20,47 @@ public class Repeat extends Union {
     public  static Repeat many1(Element e)              { return new Repeat(e, false, true); }
     /** repeat one or more times, separated by <tt>sep</tt> */
     public  static Repeat many1(Element e, Element sep) { return new Repeat(e, false, true, sep); }
-    public  static Maximal maximal(Element e)           { return new Maximal(e); }
+    /** repeat zero or more times, matching a maximal sequence of atoms */
+    public  static Repeat maximal0(Element e)              { return new Repeat(e, true, true, null, true); }
+    /** repeat one or more times, matching a maximal sequence of atoms */
+    public  static Repeat maximal1(Element e)              { return new Repeat(e, false, true, null, true); }
+    /** repeat one or more times, separated by <tt>sep</tt>, matching a maximal sequence of atoms */
+    public  static Repeat maximal1(Element e, Element sep) { return new Repeat(e, false, true, sep, true); }
 
     // Instance //////////////////////////////////////////////////////////////////////////////
     
     final boolean zeroOkay, manyOkay;
     final Element e;
     final Element separator;
+    final boolean maximal;
 
     Repeat(final Element e, boolean zeroOkay, boolean manyOkay) { this(e, zeroOkay, manyOkay, null); }
-    Repeat(final Element e, boolean zeroOkay, boolean manyOkay, Element separator) {
+    Repeat(final Element e, boolean zeroOkay, boolean manyOkay, Element separator) { this(e, zeroOkay, manyOkay, separator, false); }
+    Repeat(final Element e, boolean zeroOkay, boolean manyOkay, final Element separator, boolean maximal) {
         super(e+(!manyOkay ? "?" : (zeroOkay ? "*" : "+"))+(separator==null?"":("/"+separator.toString())), true);
         this.e = e;
+        this.maximal = maximal;
         this.zeroOkay = zeroOkay;
         this.manyOkay = manyOkay;
         this.separator = separator;
+        Union who = this;
+        if (maximal) {
+            who = new Union(this+"++");
+            add(new Sequence.Singleton(who, null, null) {
+                    public Topology noFollow() { return separator==null ? e.toAtom() : separator.toAtom(); }
+                });
+        }
         if (zeroOkay) {
-            add(new Sequence.Constant.Empty());
-            if (manyOkay) add(new Sequence.Singleton(many1(e, separator), null, null));
-            else          add(new Sequence.Singleton(e, null, null));
+            who.add(new Sequence.Constant.Empty());
+            if (manyOkay) who.add(new Sequence.Singleton(many1(e, separator), null, null));
+            else          who.add(new Sequence.Singleton(e, null, null));
         } else {
-            add(new Sequence.RewritingSequence(null, new Element[] { e }, null, null));
+            who.add(new Sequence.RewritingSequence(null, new Element[] { e }, null, null));
             if (this.separator==null) {
-                add(new Sequence.Unwrap(new Element[] { e,                 Repeat.this }, null, null));
+                who.add(new Sequence.Unwrap(new Element[] { e,                 Repeat.this }, null, null));
             } else {
-                add(new Sequence.Unwrap(new Element[] { e, this.separator, Repeat.this }, new boolean[] { false, true, false }, null, null));
+                who.add(new Sequence.Unwrap(new Element[] { e, this.separator, Repeat.this }, new boolean[] { false, true, false }, null, null));
             }
         }
     }
-
-    static class MaximalSequence extends Sequence.Singleton {
-        private final Element e;
-        public String toString() { return e+"@"; }
-        public Topology noFollow() { return e.toAtom(); }
-        public MaximalSequence(Element e) {
-            super(e, null, null);
-            this.e = e;
-        }
-    }
-    static class Maximal extends Union {
-        public Maximal(final Element e) {
-            super(e+"+", true);
-            add(new MaximalSequence(e));
-        }
-    }
 }

diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java
index a5149f2..d252604 100644 (file)
--- a/src/edu/berkeley/sbp/Sequence.java
+++ b/src/edu/berkeley/sbp/Sequence.java
@@ -38,8 +38,7 @@ public abstract class Sequence extends Element implements Iterable<Element> {
     public Topology noFollow() { return null; }
 
     Topology toAtom() {
-        if (elements.length>1) throw new RuntimeException("cannot invoke toAtom() on a Sequence with " + elements.length + " elements: " + this);
-        if (elements.length==0) return null;
+        if (elements.length!=1) throw new RuntimeException("cannot invoke toAtom() on a Sequence with " + elements.length + " elements: " + this);
         return elements[0].toAtom();
     }
 

diff --git a/src/edu/berkeley/sbp/Union.java b/src/edu/berkeley/sbp/Union.java
index a7a7630..db0db7d 100644 (file)
--- a/src/edu/berkeley/sbp/Union.java
+++ b/src/edu/berkeley/sbp/Union.java
@@ -23,10 +23,10 @@ public class Union extends Element implements Iterable<Sequence> {
         Topology ret = null;
         for(Sequence s : this) {
             Topology a = s.toAtom();
-            if (a==null) continue;
             if (ret==null) ret = a.dup();
-            else           ret.add(a.dup());
+            else           ret = ret.union(a.dup());
         }
+        if (ret==null) throw new RuntimeException("confusion on " + this);
         return ret;
     }
 

diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java
index cfd9c31..8b6eae6 100644 (file)
--- a/src/edu/berkeley/sbp/Walk.java
+++ b/src/edu/berkeley/sbp/Walk.java
@@ -164,14 +164,11 @@ abstract class Walk<T> {
                 if (matched) walk(a);
             }
 
-            if (e instanceof Repeat.MaximalSequence || e instanceof Repeat.Maximal)
-                cs.remove(new Last<Tok>(cs.fresh(), c).walk(e));
-            /*
             if (e instanceof Sequence) {
                 Sequence s = (Sequence)e;
-                if (s.noFollow() != null) cs.remove(s.noFollow());
+                if (s.noFollow() != null) cs.remove(s.noFollow().dup());
             }
-            */
+
             if (c != null && e==me) {
                 c.follow.put(e, cs.dup());
                 c.eof.put(e, eof);

diff --git a/src/edu/berkeley/sbp/misc/MetaGrammar.java b/src/edu/berkeley/sbp/misc/MetaGrammar.java
index 861b5a9..85b17ee 100644 (file)
--- a/src/edu/berkeley/sbp/misc/MetaGrammar.java
+++ b/src/edu/berkeley/sbp/misc/MetaGrammar.java
@@ -96,8 +96,8 @@ public class MetaGrammar extends StringWalker {
         else if ("+".equals(head))  return Repeat.many1((Element)walk(tree.child(0)));
         else if ("+/".equals(head)) return Repeat.many1((Element)walk(tree.child(0)), (Element)walk(tree.child(1)));
         else if ("*/".equals(head)) return Repeat.many0((Element)walk(tree.child(0)), (Element)walk(tree.child(1)));
-        else if ("**".equals(head)) return Repeat.maximal(Repeat.many0((Element)walk(tree.child(0))));
-        else if ("++".equals(head)) return Repeat.maximal(Repeat.many1((Element)walk(tree.child(0))));
+        else if ("**".equals(head)) return Repeat.maximal0((Element)walk(tree.child(0)));
+        else if ("++".equals(head)) return Repeat.maximal1((Element)walk(tree.child(0)));
         else if ("?".equals(head))  return Repeat.maybe((Element)walk(tree.child(0)));
         else if ("&".equals(head))
             return ((PreSequence)walk(tree,0)).and(new PreSequence((Element[])Reflection.lub((Object[])walk(tree, 1)), null).buildSequence(null, true, false));
@@ -300,6 +300,9 @@ public class MetaGrammar extends StringWalker {
 
 
 
+
+
+
         // DO NOT EDIT STUFF BELOW: IT IS AUTOMATICALLY GENERATED
 new Tree(null, "gram", new Tree[] { new Tree(null, null, new Tree[] { }),
         new Tree(null, "grammar", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "::=", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "s", new Tree[] { })}),
@@ -746,9 +749,9 @@ new Tree(null, "gram", new Tree[] { new Tree(null, null, new Tree[] { }),
         new Tree(null, "nonTerminal", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { }),
         new Tree(null, "s", new Tree[] { })})})})})})}),
         new Tree(null, "!::=", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { })}),
-        new Tree(null, null, new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "qprod", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, " ", new Tree[] { })})}),
-        new Tree(null, "qprod", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\n", new Tree[] { })})}),
-        new Tree(null, "qprod", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\r", new Tree[] { })})})})})}),
+        new Tree(null, null, new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "ps", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "[", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "range", new Tree[] { new Tree(null, " ", new Tree[] { })}),
+        new Tree(null, "range", new Tree[] { new Tree(null, "\r", new Tree[] { })}),
+        new Tree(null, "range", new Tree[] { new Tree(null, "\n", new Tree[] { })})})})})})})})}),
         new Tree(null, "::=", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { }),
         new Tree(null, "o", new Tree[] { }),
         new Tree(null, "r", new Tree[] { }),
@@ -846,3 +849,6 @@ new Tree(null, "gram", new Tree[] { new Tree(null, null, new Tree[] { }),
 
 
 
+
+
+

diff --git a/src/edu/berkeley/sbp/tib/Tib.java b/src/edu/berkeley/sbp/tib/Tib.java
index 9b4b974..39f6071 100644 (file)
--- a/src/edu/berkeley/sbp/tib/Tib.java
+++ b/src/edu/berkeley/sbp/tib/Tib.java
@@ -289,10 +289,8 @@ public class Tib implements Token.Stream<CharToken> {
 
     public static class Grammar extends MetaGrammar {
         private int anon = 0;
-        private final Element ws = Repeat.maximal(Repeat.many0(nonTerminal("w")));
-        public Grammar() {
-            dropAll.add(ws);
-        }
+        private final Element ws = Repeat.maximal0(nonTerminal("w"));
+        public Grammar() { dropAll.add(ws); }
         public Object walk(Tree<String> tree) {
             String head = tree.head();
             if (tree.numChildren()==0) return super.walk(tree);

diff --git a/src/edu/berkeley/sbp/util/TopologicalBag.java b/src/edu/berkeley/sbp/util/TopologicalBag.java
index 7812a51..2a1bb53 100644 (file)
--- a/src/edu/berkeley/sbp/util/TopologicalBag.java
+++ b/src/edu/berkeley/sbp/util/TopologicalBag.java
@@ -27,7 +27,7 @@ public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
     public void add(Topology<K> t, V v) { put(t, v); }
     public void addAll(Topology<K> k, Iterable<V> vi) { putAll(k, vi); }
 
-    public void putAll(Topology<K> k, Iterable<V> vi) { for(V v : vi) put(k, v); }
+    public void putAll(Topology<K> k, Iterable<V> vi) { if (vi!=null) for(V v : vi) put(k, v); }
     public void put(Topology<K> t, V v) {
         for(Topology<K> ht : h.keySet()) {
             if (t.disjoint(ht)) continue;
@@ -59,7 +59,9 @@ public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
         TopologicalBag<K,V> ret = new TopologicalBag<K,V>();
         for(Topology<K> ht : h.keySet()) {
             if (ht.disjoint(t)) continue;
-            ret.putAll(ht.intersect(t), h.get(ht));
+            Iterable<V> it = h.get(ht);
+            Topology<K> tk = ht.intersect(t);
+            ret.putAll(tk, it);
         }
         return ret;
     }