checkpoint

darcs-hash:20060720074716-5007d-b0c01eb3b8fe20d5d86314f3aeb94b43b8277ae9.gz

diff --git a/TODO b/TODO
index a6d3307..8c3fdf9 100644 (file)
--- a/TODO
+++ b/TODO
@@ -4,6 +4,7 @@ Immediately
   - needs/hates/follow API ugliness
 
   - Topology crap is kinda messed up
+      - Atom should be a topology, shouldn't it?
 
   - do Forest/Tree still need a Region?
   - reconsider the degree of genericization

diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index 0504a11..d4d5415 100644 (file)
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -82,11 +82,15 @@ public abstract class Parser<Tok, Result> {
             if (hs.contains(e)) return;
             hs.add(e);
             if (e instanceof Atom) return;
-            for(Sequence s : (Union)e) {
-                hs.add(s);
-                for(Position p = s.firstp(); p != null; p = p.next())
-                    walk(p.element(), hs);
-            }
+            for(Sequence s : (Union)e)
+                walk(s, hs);
+        }
+        private void walk(Sequence s, HashSet<Element> hs) {
+            hs.add(s);
+            for(Position p = s.firstp(); p != null; p = p.next())
+                walk(p.element(), hs);
+            for(Sequence ss : s.needs()) walk(ss, hs);
+            for(Sequence ss : s.hates()) walk(ss, hs);
         }
 
         /** the start state */
@@ -287,10 +291,15 @@ public abstract class Parser<Tok, Result> {
 
     // Helpers //////////////////////////////////////////////////////////////////////////////
     
+    private static void reachable(Sequence s, HashSet<Position> h) {
+        reachable(s.firstp(), h);
+        for(Sequence ss : s.needs()) reachable(ss, h);
+        for(Sequence ss : s.hates()) reachable(ss, h);
+    }
     private static void reachable(Element e, HashSet<Position> h) {
         if (e instanceof Atom) return;
         for(Sequence s : ((Union)e))
-            reachable(s.firstp(), h);
+            reachable(s, h);
     }
     private static void reachable(Position p, HashSet<Position> h) {
         if (h.contains(p)) return;

diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java
index 31d8f29..28f6564 100644 (file)
--- a/src/edu/berkeley/sbp/Sequence.java
+++ b/src/edu/berkeley/sbp/Sequence.java
@@ -56,6 +56,9 @@ public abstract class Sequence extends Element implements Iterable<Element> {
     public Sequence and(Sequence s) { Sequence ret = dup(); ret.needs.add(s); s.needed.add(ret); return ret; }
     public Sequence not(Sequence s) { Sequence ret = dup(); ret.hates.add(s); s.hated.add(ret); return ret; }
 
+    public Iterable<Sequence> needs() { return needs; }
+    public Iterable<Sequence> hates() { return hates; }
+
     protected final Element[] elements;
 
     final HashSet<Sequence> needed = new HashSet<Sequence>();

diff --git a/src/edu/berkeley/sbp/Union.java b/src/edu/berkeley/sbp/Union.java
index ece239d..5932ac3 100644 (file)
--- a/src/edu/berkeley/sbp/Union.java
+++ b/src/edu/berkeley/sbp/Union.java
@@ -12,18 +12,18 @@ public class Union extends Element implements Iterable<Sequence> {
 
     private final String name;
     private final boolean synthetic;
+
     private final List<Sequence> alternatives = new ArrayList<Sequence>();
 
-    public Union() { this(null, false); }
     public Union(String name) { this(name, false); }
 
     /**
      *  Since every cycle in a non-degenerate grammar contains at
      *  least one Union, every instance of this class must be able to
      *  display itself in both "long form" (list of the long forms of
-     *  its alternatives) and "short form" (some abbreviation).
+     *  its alternatives) and "short form" (some name).
      *
-     *  @param shortForm the "short form" display; usually 
+     *  @param shortForm the "short form" display; for display purposes only
      *  @param synthetic if true, this Union's "long form" is "obvious" and should not be displayed when printing the grammar
      */
     public Union(String name, boolean synthetic) {
@@ -31,16 +31,13 @@ public class Union extends Element implements Iterable<Sequence> {
         this.synthetic = synthetic;
     }
 
-    public Iterator<Sequence> iterator() { return alternatives.iterator(); }
     public boolean contains(Sequence s) { return alternatives.contains(s); }
+    public Iterator<Sequence> iterator() { return alternatives.iterator(); }
 
     /** adds an alternative */
     public void add(Sequence s) {
+        if (alternatives.contains(s)) return;
         alternatives.add(s);
-
-        // FIXME: does this make sense?
-        for(Sequence n : s.needs) add(n);
-        for(Sequence n : s.hates) add(n);
     }
 
 
@@ -92,7 +89,6 @@ public class Union extends Element implements Iterable<Sequence> {
     private void bodyToString(StringBuffer sb, String before, String between) {
         boolean first = true;
         for(Sequence s : this) {
-            if (s.lame) continue;
             // FIXME: what to do here about printing out negated sequences?
             sb.append(first ? before : between);
             first = false;

diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java
index cd991e8..496edd6 100644 (file)
--- a/src/edu/berkeley/sbp/Walk.java
+++ b/src/edu/berkeley/sbp/Walk.java
@@ -37,7 +37,12 @@ abstract class Walk<T> {
         else if (e instanceof Sequence) return sequence((Sequence)e);
         else if (e instanceof Union) {
             T ret = bottom(e);
-            for(Sequence s : (Union)e) ret = union((Union)e, ret, walk(s));
+            for(Sequence s : (Union)e) {
+                ret = union((Union)e, ret, walk(s));
+                // FIXME
+                for(Sequence ss : s.needs()) ret = union((Union)e, ret, walk(ss));
+                for(Sequence ss : s.hates()) ret = union((Union)e, ret, walk(ss));
+            }
             return ret;
         } else {
             throw new Error("unknown element of class " + e.getClass().getName() + ": " + e);

diff --git a/src/edu/berkeley/sbp/meta/MetaGrammarBindings.java b/src/edu/berkeley/sbp/meta/MetaGrammarBindings.java
index 835d79e..196394a 100644 (file)
--- a/src/edu/berkeley/sbp/meta/MetaGrammarBindings.java
+++ b/src/edu/berkeley/sbp/meta/MetaGrammarBindings.java
@@ -75,7 +75,7 @@ public class MetaGrammarBindings extends AnnotationGrammarBindings {
             HashSet<Sequence> bad2 = new HashSet<Sequence>();
             for(int i=0; i<sequences.length; i++) {
                 Seq[] group = sequences[i];
-                Union u2 = new Union();
+                Union u2 = new Union(null, false);
                 if (sequences.length==1) u2 = u;
                 for(int j=0; j<group.length; j++) {
                     group[j].build(cx, u2, false, cnt);
@@ -130,7 +130,7 @@ public class MetaGrammarBindings extends AnnotationGrammarBindings {
             if (!rep) { super.build(cx, u, this); return; }
             HashSet<Sequence> bad2 = new HashSet<Sequence>();
 
-            Union urep = new Union();
+            Union urep = new Union(null, false);
             urep.add(Sequence.empty);
             if (sep != null)
                 urep.add(Sequence.singleton(new Element[] { cx.get(sep), u }, 1));
@@ -139,10 +139,10 @@ public class MetaGrammarBindings extends AnnotationGrammarBindings {
 
             for(int i=0; i<sequences.length; i++) {
                 Seq[] group = sequences[i];
-                Union u2 = new Union();
+                Union u2 = new Union(null, false);
                 if (sequences.length==1) u2 = u;
                 for(int j=0; j<group.length; j++) {
-                    Union u3 = new Union();
+                    Union u3 = new Union(null, false);
                     group[j].build(cx, u3, false, this);
                     Sequence s = Sequence.unwrap(new Element[] { u3, urep },
                                                  cx.rm.repeatTag(),
@@ -171,7 +171,7 @@ public class MetaGrammarBindings extends AnnotationGrammarBindings {
             this.sequences = sequences;
         }
         public Element build(Context cx, NonTerminalNode cnt) {
-            Union ret = new Union();
+            Union ret = new Union(null, false);
             build(cx, ret, cnt);
             return ret;
         }
@@ -336,9 +336,9 @@ public class MetaGrammarBindings extends AnnotationGrammarBindings {
     public static @bind.as("{")           class XTree                 extends ElementNode {
         public @bind.arg Seq body;
         public Element build(Context cx, NonTerminalNode cnt) {
-            Union u = new Union();
+            Union u = new Union(null, false);
             Sequence s = body.build(cx, u, false, null);
-            Union u2 = new Union();
+            Union u2 = new Union(null, false);
             u2.add(Sequence.singleton(new Element[] {
                 CharAtom.leftBrace,
                 cx.get("ws"),