author adam Mon, 26 Feb 2007 01:31:00 +0000 (20:31 -0500) committer adam Mon, 26 Feb 2007 01:31:00 +0000 (20:31 -0500)
darcs-hash:20070226013100-5007d-abd1a29d67900dd808080e90efb0b87ccb36d600.gz

@@ -162,11 +162,29 @@ public abstract class Parser<Token, NodeType> {
if (p.element() != null && p.element() instanceof Atom)
}
+
if (top instanceof IntegerTopology)
for(State<Token> state : all_states) {
state.oreductions = state.reductions.optimize(((IntegerTopology)top).functor());
state.oshifts = state.shifts.optimize(((IntegerTopology)top).functor());
}
+
+            // crude algorithm to assing an ordinal ordering to every position
+            ArrayList<Sequence.Position> al = new ArrayList<Sequence.Position>();
+            for(State s : all_states) {
+                for(Object po : s) {
+                    Sequence.Position p = (Sequence.Position)po;
+                    if (al.contains(p)) continue;
+                    int i=0;
+                    for(; i<al.size(); i++) {
+                        if (p.compareTo(al.get(i), cache) > 0)
+                            break;
+                    }
+                }
+            }
+            for(int i=0; i<al.size(); i++)
+                al.get(i).ord = i;
}

private boolean isRightNullable(Position p) {
index a6d599f..684fbf8 100644 (file)
@@ -33,15 +33,8 @@ final class Reduction implements Comparable<Reduction> {

public int compareTo(Reduction r) {
int ret = compareTo0(r);
-        if (ret == 0) {
-            Walk.Cache cache = node.state().cache();
-            if (canKill(cache, position, r.position) && canKill(cache, r.position, position)) throw new Error();
-            if      (canKill(cache, position,   r.position)) ret =  1;
-            else if (canKill(cache, r.position, position)) ret = -1;
-            if      (canNeed(cache, position,   r.position)) ret =  1;
-            else if (canNeed(cache, r.position, position)) ret = -1;
-        }
-        return -1 * ret;
+        if (ret != 0) return -1 * ret;
+        return (position.ord - r.position.ord);
}

private static boolean isRightNullable(Walk.Cache c, Position p) {
@@ -55,10 +48,13 @@ final class Reduction implements Comparable<Reduction> {
if (!isRightNullable(cache, himp)) return false;
Sequence me  = mep.owner();
Sequence him = himp.owner();
+        Boolean b = me.canKill.get(him);
+        if (b!=null) return b;
for(Sequence killer : him.hates()) {
HashSet<Sequence> eq2 = new Walk.EquivalentTo(killer, cache).walk();
-            if (eq2.contains(me)) return true;
+            if (eq2.contains(me)) { me.canKill.put(him, true); return true; }
}
+        me.canKill.put(him, false);
return false;
}

@@ -82,10 +78,13 @@ final class Reduction implements Comparable<Reduction> {
if (!isRightNullable(cache, himp)) return false;
Sequence me  = mep.owner();
Sequence him = himp.owner();
+        Boolean b = me.canNeed.get(him);
+        if (b!=null) return b;
for(Sequence needer : him.needs()) {
HashSet<Sequence> eq2 = new Walk.EquivalentTo(needer, cache).walk();
-            if (eq2.contains(me)) return true;
+            if (eq2.contains(me)) { me.canNeed.put(him, true); return true; }
}
+        me.canNeed.put(him, false);
return false;
}
}
index d3d8d8a..a029274 100644 (file)
@@ -16,7 +16,10 @@ public abstract class Sequence implements Iterable<Element>, SequenceOrElement {

public boolean needed_or_hated = false;

-    final HashSet<Sequence> hated  = new HashSet<Sequence>();
+    public HashMap<Sequence,Boolean> canNeed = new HashMap<Sequence,Boolean>();
+    public HashMap<Sequence,Boolean> canKill = new HashMap<Sequence,Boolean>();
+
+    final HashSet<Sequence> hated   = new HashSet<Sequence>();

final HashSet<Sequence> needs  = new HashSet<Sequence>();
final HashSet<Sequence> hates  = new HashSet<Sequence>();
@@ -109,6 +112,20 @@ public abstract class Sequence implements Iterable<Element>, SequenceOrElement {
/** the imaginary position before or after an element of a sequence; corresponds to an "LR item" */
class Position implements IntegerMappable {

+        public int ord = -1;
+        public int compareTo(Position p, Walk.Cache cache) {
+            Position position = this;
+            Position rposition = p;
+            int ret = 0;
+            if (Reduction.canKill(cache, position, rposition) &&
+                Reduction.canKill(cache, rposition, position)) throw new Error();
+            if      (Reduction.canKill(cache, position,   rposition)) ret =  1;
+            else if (Reduction.canKill(cache, rposition, position)) ret = -1;
+            if      (Reduction.canNeed(cache, position,   rposition)) ret =  1;
+            else if (Reduction.canNeed(cache, rposition, position)) ret = -1;
+            return ret;
+        }
+
private Forest zero = null;
public Forest zero(Input.Region reg) {
if (zero != null) return zero;