import edu.berkeley.sbp.*;
import edu.berkeley.sbp.util.*;
import edu.berkeley.sbp.Parser.Table.*;
-import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.Sequence.Pos;
import java.io.*;
import java.util.*;
package edu.berkeley.sbp;
import edu.berkeley.sbp.util.*;
-import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
import java.io.*;
import java.util.*;
follow.put(seq, old);
if (eof) followEof.add(seq);
- for(Position p = seq.firstp().last().prev(); p!=null; p = p.prev()) {
+ for(Pos p = seq.firstp().last().prev(); p!=null; p = p.prev()) {
all.add(p.element());
if (p.element() instanceof Union)
for(Sequence s2 : ((Union)p.element())) {
Topology ret = seq.follow==null ? emptyTopology().complement() : seq.follow.getTokenTopology();
if (seen.contains(seq)) return ret;
seen.add(seq);
- for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
+ for(Pos p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
if (!(p.element() instanceof Union)) continue;
Topology t = emptyTopology();
for(Sequence s : ((Union)p.element()))
Sequence seq = (Sequence)e;
if (seen.contains(seq)) return emptyTopology();
seen.add(seq);
- for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
+ for(Pos p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
ret = ret.union(first(p.element(), seen));
if (!possiblyEpsilon(p.element())) break;
}
else if (e instanceof Sequence) {
ret = true;
Sequence s = (Sequence)e;
- for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next())
+ for(Pos p = s.firstp(); p!=null && !p.isLast(); p = p.next())
ret &= possiblyEpsilon(p.element(), hm);
}
hm.put(e, ret);
return ret;
}
- public boolean isRightNullable(Position p) {
+ public boolean isRightNullable(Pos p) {
if (p.isLast()) return true;
if (!possiblyEpsilon(p.element())) return false;
return isRightNullable(p.next());
private void gatherNulledSubsequences(Sequence seq, HashSet<Sequence> eq) {
if (eq.contains(seq)) return;
eq.add(seq);
- Position p = seq.firstp();
+ Pos p = seq.firstp();
for(; !p.isLast(); p = p.next()) {
if (!p.isLast() && isRightNullable(p.next()) && p.element() instanceof Union)
for(Sequence s : ((Union)p.element()))
}
}
- // Position Ordinality Comparisons //////////////////////////////////////////////////////////////////////////////
+ // Pos Ordinality Comparisons //////////////////////////////////////////////////////////////////////////////
- public boolean canKill(Position mep, Position himp) {
+ public boolean canKill(Pos mep, Pos himp) {
if (!isRightNullable(mep)) return false;
if (!isRightNullable(himp)) return false;
Sequence me = mep.owner();
return false;
}
- public boolean canNeed(Position mep, Position himp) {
+ public boolean canNeed(Pos mep, Pos himp) {
if (!isRightNullable(mep)) return false;
if (!isRightNullable(himp)) return false;
Sequence me = mep.owner();
return false;
}
- public int comparePositions(Position position, Position rposition) {
+ public int comparePositions(Pos position, Pos rposition) {
int ret = 0;
if (canKill(position, rposition) && canKill(rposition, position)) throw new Error();
if (canKill(position, rposition)) ret = -1;
import edu.berkeley.sbp.*;
import edu.berkeley.sbp.util.*;
import edu.berkeley.sbp.Parser.Table.*;
-import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.Sequence.Pos;
import java.io.*;
import java.util.*;
package edu.berkeley.sbp;
import edu.berkeley.sbp.*;
-import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.GSS.Phase;
import edu.berkeley.sbp.Node;
return ret.toString();
}
- private static boolean important(Position p) {
+ private static boolean important(Pos p) {
if (p.isLast()) return false;
if (p.element() == null) return false;
if (!(p.element() instanceof Union)) return false;
boolean go = false;
boolean force = false;
for(Pos pp : (Iterable<Pos>)parent.state().positions()) {
- Position p = (Position)pp;
+ Pos p = (Pos)pp;
if (skip) p = p.next();
int raise = 0;
done = false;
static <Tok> void complain(Node n, HashMap<String,HashSet<String>> errors, boolean force, int indent) {
if (touched.contains(n)) return;
touched.add(n);
- for(Position p : (Iterable<Position>)n.state()) {
+ for(Pos p : (Iterable<Pos>)n.state()) {
//if (!p.isLast() && !p.next().isLast()) continue;
if (((p.isFirst() || p.isLast()) && !force)/* || p.owner().name==null*/ ||
!important(p)) {
package edu.berkeley.sbp;
import edu.berkeley.sbp.util.*;
import edu.berkeley.sbp.Sequence.Position;
-import edu.berkeley.sbp.Sequence.Pos;
+import edu.berkeley.sbp.Sequence.Position;
import java.io.*;
import java.util.*;
private boolean accept = false;
private VisitableMap<Token,State<Token>> oshifts = null;
- private VisitableMap<Token,Pos> oreductions = null;
+ private VisitableMap<Token,Position> oreductions = null;
public final boolean doomed;
// Interface Methods //////////////////////////////////////////////////////////////////////////////
boolean canReduce(Token t) {
return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
void invokeEpsilonReductions(Token t, Node node) {
- if (t==null) for(Pos r : eofReductions) node.invoke(r, null);
+ if (t==null) for(Position r : eofReductions) node.invoke(r, null);
else oreductions.invoke(t, node, null);
}
void invokeReductions(Token t, Node node, Result b) {
- if (t==null) for(Pos r : eofReductions) node.invoke(r, b);
+ if (t==null) for(Position r : eofReductions) node.invoke(r, b);
else oreductions.invoke(t, node, b);
}
// Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
package edu.berkeley.sbp;
-import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.Sequence.Pos;
final class Reduction implements Comparable<Reduction> {
package edu.berkeley.sbp;
import edu.berkeley.sbp.util.*;
-import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.Sequence.Pos;
import java.util.*;
Iterable<Sequence> needs() { return needs; }
Iterable<Sequence> hates() { return hates; }
- Position firstp() { return firstp; }
- Position lastp() { return firstp().last(); }
+ Pos firstp() { return firstp; }
+ Pos lastp() { return firstp().last(); }
public Iterator<Element> iterator() { return new ArrayIterator<Element>(elements); }
protected Sequence(Element[] elements) {
for(int i=0; i<elements.length; i++)
if (elements[i]==null)
throw new RuntimeException("cannot have nulls in a sequence: " + this);
- this.firstp = new Position(0, null);
+ this.firstp = new Position(this, 0, null);
}
abstract Forest epsilonForm(Input.Region loc, Grammar cache);
- protected abstract <T> Forest<T> postReduce(Input.Region loc, Forest<T>[] args, Position p);
+ protected abstract <T> Forest<T> postReduce(Input.Region loc, Forest<T>[] args, Pos p);
// Position //////////////////////////////////////////////////////////////////////////////
static abstract class Pos implements IntegerMappable, Comparable<Pos>, Serializable {
+
+ public int ord = -1;
+ public int ord() { return ord; }
+
final Forest[] holder;
+
Pos(int len) { this.holder = new Forest[len]; }
public abstract int provides();
public abstract int[] hates();
public abstract boolean owner_needed_or_hated();
+ public abstract boolean isFirst();
+ public abstract boolean isLast();
+ public abstract Pos last();
+ public abstract Pos prev();
+ public abstract Pos next();
+
+ abstract Sequence owner();
+ abstract Element element();
+
public abstract int numPops();
public abstract <T> Forest<T> rewrite(Input.Region loc, Grammar cache);
}
/** the imaginary position before or after an element of a sequence; corresponds to an "LR item" */
- class Position extends Pos implements IntegerMappable {
+ private static class Position extends Pos implements IntegerMappable {
/*
public Pos getPos() {
return new DumbPos(elements.length, provides(), needs(), hates(), owner_needed_or_hated(), numPops(),
public int ord() { return ord; }
public int numPops() { return pos; }
- final int pos;
- private final Position next;
- private final Position prev;
+ final int pos;
+ private final Position next;
+ private final Position prev;
+ private transient Sequence owner;
public int provides() { return owner().sernum; }
public int[] needs() { return owner().needs_int(); }
public int[] hates() { return owner().hates_int(); }
public boolean owner_needed_or_hated() { return owner().needed_or_hated; }
- private Position(int pos, Position prev) {
- super(elements.length);
+ private Position(Sequence owner, int pos, Position prev) {
+ super(owner.elements.length);
+ this.owner = owner;
this.pos = pos;
- this.next = pos==elements.length ? null : new Position(pos+1, this);
+ this.next = pos==owner.elements.length ? null : new Position(owner, pos+1, this);
this.prev = prev;
}
return ord - ((Position)p).ord;
}
- boolean isFirst() { return pos==0; }
+ public boolean isFirst() { return pos==0; }
public int pos() { return pos; }
/** the element immediately after this Position, or null if this is the last Position */
- public Element element() { return pos>=elements.length ? null : elements[pos]; }
+ public Element element() { return pos>=owner().elements.length ? null : owner().elements[pos]; }
/** the element which produces the sequence to which this Position belongs */
- public Sequence owner() { return Sequence.this; }
+ public Sequence owner() { return owner; }
/** the next Position (the Position after <tt>this.element()</tt>) */
public Position next() { return next; }
public String toString() {
StringBuffer ret = new StringBuffer();
ret.append("<{");
- for(Position p = Sequence.this.firstp(); p != null; p = p.next()) {
+ for(Position p = (Position)owner().firstp(); p != null; p = p.next()) {
ret.append(' ');
if (p==this) ret.append(" | ");
if (p.element()!=null) ret.append(p.element());