From 111166986ad83b54d0cae5c03c2304d23e332f29 Mon Sep 17 00:00:00 2001 From: adam Date: Sat, 22 Jul 2006 19:44:56 -0400 Subject: [PATCH] checkpoint darcs-hash:20060722234456-5007d-9cd269e491f7a78f8580acec36b15d568f90e4da.gz --- src/edu/berkeley/sbp/Element.java | 2 +- src/edu/berkeley/sbp/Parser.java | 22 +++++----- src/edu/berkeley/sbp/Sequence.java | 2 +- src/edu/berkeley/sbp/SequenceOrElement.java | 11 +++++ src/edu/berkeley/sbp/Walk.java | 60 +++++++++++++-------------- 5 files changed, 54 insertions(+), 43 deletions(-) create mode 100644 src/edu/berkeley/sbp/SequenceOrElement.java diff --git a/src/edu/berkeley/sbp/Element.java b/src/edu/berkeley/sbp/Element.java index 4ccde61..16ae2f0 100644 --- a/src/edu/berkeley/sbp/Element.java +++ b/src/edu/berkeley/sbp/Element.java @@ -8,7 +8,7 @@ import java.lang.reflect.*; import java.lang.ref.*; /** the root superclass for all components of the grammar (terminals, nonterminals, literals, etc) */ -public abstract class Element { +public abstract class Element implements SequenceOrElement { /** sorry, you can't make up new, custom elements */ Element() { } diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 4aa6515..a74ea5e 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -77,7 +77,7 @@ public abstract class Parser { public final Walk.Cache cache = this; - private void walk(Element e, HashSet hs) { + private void walk(Element e, HashSet hs) { if (e==null) return; if (hs.contains(e)) return; hs.add(e); @@ -85,7 +85,7 @@ public abstract class Parser { for(Sequence s : (Union)e) walk(s, hs); } - private void walk(Sequence s, HashSet hs) { + private void walk(Sequence s, HashSet hs) { hs.add(s); for(Position p = s.firstp(); p != null; p = p.next()) walk(p.element(), hs); @@ -114,9 +114,9 @@ public abstract class Parser { cache.eof.put(start0, true); // construct the set of states - HashSet all_elements = new HashSet(); + HashSet all_elements = new HashSet(); walk(start0, all_elements); - for(Element e : all_elements) + for(SequenceOrElement e : all_elements) cache.ys.addAll(e, new Walk.YieldSet(e, cache).walk()); HashSet hp = new HashSet(); reachable(start0, hp); @@ -166,7 +166,7 @@ public abstract class Parser { public final int idx = master_state_idx++; private final HashSet hs; - public transient HashMap> gotoSetNonTerminals = new HashMap>(); + public transient HashMap> gotoSetNonTerminals = new HashMap>(); private transient TopologicalBag> gotoSetTerminals = new TopologicalBag>(); private TopologicalBag reductions = new TopologicalBag(); @@ -219,7 +219,7 @@ public abstract class Parser { */ public State(HashSet hs, HashMap,State> all_states, - HashSet all_elements) { + HashSet all_elements) { this.hs = hs; // register ourselves in the all_states hash so that no @@ -258,17 +258,17 @@ public abstract class Parser { // to avoid having to iteratively construct our set of States as shown in most // expositions of the algorithm (ie "keep doing XYZ until things stop changing"). - HashMapBag move = new HashMapBag(); + HashMapBag move = new HashMapBag(); for(Position p : hs) { Element e = p.element(); if (e==null) continue; - for(Element y : cache.ys.getAll(e)) { + for(SequenceOrElement y : cache.ys.getAll(e)) { HashSet hp = new HashSet(); reachable(p.next(), hp); move.addAll(y, hp); } } - OUTER: for(Element y : move) { + OUTER: for(SequenceOrElement y : move) { HashSet h = move.getAll(y); State s = all_states.get(h) == null ? new State(h, all_states, all_elements) : all_states.get(h); // if a reduction is "lame", it should wind up in the dead_state after reducing @@ -279,13 +279,13 @@ public abstract class Parser { for(Sequence seq : u) if (seq.needs.contains((Sequence)y) || seq.hates.contains((Sequence)y)) { // FIXME: what if there are two "routes" to get to the sequence? - ((HashMap)gotoSetNonTerminals).put(y, dead_state); + ((HashMap)gotoSetNonTerminals).put((Sequence)y, dead_state); continue OUTER; } } } + gotoSetNonTerminals.put((Sequence)y, s); } - gotoSetNonTerminals.put(y, s); } } diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java index f431518..b67f8a7 100644 --- a/src/edu/berkeley/sbp/Sequence.java +++ b/src/edu/berkeley/sbp/Sequence.java @@ -8,7 +8,7 @@ import java.lang.reflect.*; import java.lang.ref.*; /** juxtaposition; zero or more adjacent Elements; can specify a rewriting */ -public abstract class Sequence extends Element implements Iterable { +public abstract class Sequence /*extends Element*/ implements Iterable, SequenceOrElement { protected final Element[] elements; diff --git a/src/edu/berkeley/sbp/SequenceOrElement.java b/src/edu/berkeley/sbp/SequenceOrElement.java new file mode 100644 index 0000000..c67173f --- /dev/null +++ b/src/edu/berkeley/sbp/SequenceOrElement.java @@ -0,0 +1,11 @@ +package edu.berkeley.sbp; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; + +interface SequenceOrElement { +} diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java index a82cf52..3d23469 100644 --- a/src/edu/berkeley/sbp/Walk.java +++ b/src/edu/berkeley/sbp/Walk.java @@ -7,10 +7,10 @@ import java.util.*; import java.lang.reflect.*; import java.lang.ref.*; -/** a traversal of the grammar performed by mapping from Elements to a lattice and computing the resulting LUB */ +/** a traversal of the grammar performed by mapping from SequenceOrElements to a lattice and computing the resulting LUB */ abstract class Walk { - protected HashSet acc = new HashSet(); - protected abstract T bottom(Element e); + protected HashSet acc = new HashSet(); + protected abstract T bottom(SequenceOrElement e); protected final Cache c; public Walk() { this(null); } @@ -26,13 +26,13 @@ abstract class Walk { public T walkAtom(Atom r) { return walk(r); } public T union(Union u, T a, T b) { return bottom(u); } public T sequence(Sequence s, T a, T b) { return bottom(s); } - protected T walk(Element e) { + protected T walk(SequenceOrElement e) { if (acc.contains(e)) return bottom(e); acc.add(e); return walk2(e); } - protected T walk2(Element e) { + protected T walk2(SequenceOrElement e) { if (e instanceof Atom) return walkAtom((Atom)e); else if (e instanceof Sequence) return sequence((Sequence)e); else if (e instanceof Union) { @@ -50,13 +50,13 @@ abstract class Walk { } } - static class YieldSet extends Walk> { - private final Element e; - public final HashSet walk() { return walk(e); } - public YieldSet(Element e, Cache c) { super(c); this.e = e; } - public HashSet bottom(Element e) { return acc; } - public HashSet sequence(Sequence seq) { return bottom(seq); } - public HashSet walkAtom(Atom r) { + static class YieldSet extends Walk> { + private final SequenceOrElement e; + public final HashSet walk() { return walk(e); } + public YieldSet(SequenceOrElement e, Cache c) { super(c); this.e = e; } + public HashSet bottom(SequenceOrElement e) { return acc; } + public HashSet sequence(Sequence seq) { return bottom(seq); } + public HashSet walkAtom(Atom r) { c.atoms.put(e, c.atoms.get(e)==null ? r : c.atoms.get(e).union(r)); return super.walkAtom(r); } @@ -69,9 +69,9 @@ abstract class Walk { public Boolean walkAtom(Atom r) { return false; } public Boolean sequence(Sequence s, Boolean a, Boolean b) { return new Boolean(a && b); } public Boolean union(Union u, Boolean a, Boolean b) { return new Boolean(a || b); } - public Boolean bottom(Element e) { return (e instanceof Union) ? false : true; } - private HashMap hm = new HashMap(); - protected Boolean walk(Element e) { + public Boolean bottom(SequenceOrElement e) { return (e instanceof Union) ? false : true; } + private HashMap hm = new HashMap(); + protected Boolean walk(SequenceOrElement e) { if (hm.get(e) != null) return hm.get(e); hm.put(e, false); Boolean ret = walk2(e); @@ -87,7 +87,7 @@ abstract class Walk { public Topology cs; public WalkTokenSet(Topology cs) { this.cs = cs; } public WalkTokenSet(Topology cs, Cache c) { super(c); this.cs = cs; } - public Topology bottom(Element e) { return cs; } + public Topology bottom(SequenceOrElement e) { return cs; } public Topology walkAtom(Atom r) { cs = cs.union(r.getTokenTopology()); return cs; } } @@ -103,15 +103,15 @@ abstract class Walk { } static class Follow extends WalkTokenSet { - private final Element me; - private final HashSet all; + private final SequenceOrElement me; + private final HashSet all; private boolean eof = false; public boolean includesEof() { return eof; } - public Follow(Topology cs, Element me, HashSet all, Cache c) { super(cs, c); this.me = me; this.all = all; } - public Topology bottom(Element e) { return cs; } + public Follow(Topology cs, SequenceOrElement me, HashSet all, Cache c) { super(cs, c); this.me = me; this.all = all; } + public Topology bottom(SequenceOrElement e) { return cs; } public Topology sequence(Sequence seq) { return cs; } - public Topology walkAtom(Atom r) { return walk((Element)r); } - public Topology walk(Element e) { + public Topology walkAtom(Atom r) { return walk((SequenceOrElement)r); } + public Topology walk(SequenceOrElement e) { if (acc.contains(e)) return bottom(e); acc.add(e); @@ -129,7 +129,7 @@ abstract class Walk { eof = c.eof.get(e) != null && c.eof.get(e).booleanValue(); cs = cso.empty(); - for(Element x : all) { + for(SequenceOrElement x : all) { boolean matched = false; if (!(x instanceof Sequence)) continue; Sequence a = (Sequence)x; @@ -173,15 +173,15 @@ abstract class Walk { } static class Cache { - public final HashMap possiblyEpsilon = new HashMap(); - public HashMap eof = new HashMap(); - public HashMap follow = new HashMap(); - public HashMapBag ys = new HashMapBag(); - public HashMap atoms = new HashMap(); - public Topology first(Element e, Topology empty) { + public final HashMap possiblyEpsilon = new HashMap(); + public HashMap eof = new HashMap(); + public HashMap follow = new HashMap(); + public HashMapBag ys = new HashMapBag(); + public HashMap atoms = new HashMap(); + public Topology first(SequenceOrElement e, Topology empty) { return new Walk.First(empty, this).walk(e); } - final boolean possiblyEpsilon(Element e) { + final boolean possiblyEpsilon(SequenceOrElement e) { Walk.Cache cache = this; Boolean ret = possiblyEpsilon.get(e); if (ret != null) return ret.booleanValue(); -- 1.7.10.4