From 24112db237318c030b4d4f457d90c34fd69d652b Mon Sep 17 00:00:00 2001 From: adam Date: Thu, 20 Jul 2006 03:47:16 -0400 Subject: [PATCH 1/1] checkpoint darcs-hash:20060720074716-5007d-b0c01eb3b8fe20d5d86314f3aeb94b43b8277ae9.gz --- TODO | 1 + src/edu/berkeley/sbp/Parser.java | 21 ++++++++++++++------ src/edu/berkeley/sbp/Sequence.java | 3 +++ src/edu/berkeley/sbp/Union.java | 14 +++++-------- src/edu/berkeley/sbp/Walk.java | 7 ++++++- src/edu/berkeley/sbp/meta/MetaGrammarBindings.java | 14 ++++++------- 6 files changed, 37 insertions(+), 23 deletions(-) diff --git a/TODO b/TODO index a6d3307..8c3fdf9 100644 --- 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 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -82,11 +82,15 @@ public abstract class Parser { 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 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 { // Helpers ////////////////////////////////////////////////////////////////////////////// + private static void reachable(Sequence s, HashSet 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 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 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 --- 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 { 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 needs() { return needs; } + public Iterable hates() { return hates; } + protected final Element[] elements; final HashSet needed = new HashSet(); diff --git a/src/edu/berkeley/sbp/Union.java b/src/edu/berkeley/sbp/Union.java index ece239d..5932ac3 100644 --- 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 { private final String name; private final boolean synthetic; + private final List alternatives = new ArrayList(); - 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 { this.synthetic = synthetic; } - public Iterator iterator() { return alternatives.iterator(); } public boolean contains(Sequence s) { return alternatives.contains(s); } + public Iterator 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 { 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 --- a/src/edu/berkeley/sbp/Walk.java +++ b/src/edu/berkeley/sbp/Walk.java @@ -37,7 +37,12 @@ abstract class Walk { 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 --- 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 bad2 = new HashSet(); for(int i=0; i bad2 = new HashSet(); - 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