From cf349fcf2f460e53ad5f9dd0397eb382c4aa92b2 Mon Sep 17 00:00:00 2001 From: adam Date: Wed, 11 Jan 2006 03:12:05 -0500 Subject: [PATCH] checkpoint harmony darcs-hash:20060111081205-5007d-b481bd9f6b56924bd3db420d6bc5c6d574aa2bc5.gz --- src/edu/berkeley/sbp/GSS.java | 28 ++++++------- src/edu/berkeley/sbp/ParseFailed.java | 4 +- src/edu/berkeley/sbp/Parser.java | 66 +++++++++++++++--------------- src/edu/berkeley/sbp/Token.java | 4 +- src/edu/berkeley/sbp/misc/CharToken.java | 2 +- 5 files changed, 52 insertions(+), 52 deletions(-) diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index becea95..5bfbd52 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -1,8 +1,8 @@ package edu.berkeley.sbp; 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.Parser.Table.State; import java.io.*; import java.util.*; import java.lang.reflect.*; @@ -24,10 +24,14 @@ class GSS { public Forest.Ref finalResult; /** corresponds to a positions between tokens the input stream; same as Tomita's U_i's */ - public class Phase implements Invokable, IntegerMappable { + public class Phase implements Invokable.Node>, IntegerMappable { + + public void invoke(State st, Forest result, Node n) { + good |= next.newNode(n, result, st, false); + } /** the token immediately after this phase */ - final Token token; + final Tok token; private final int pos; @@ -42,7 +46,7 @@ class GSS { private Forest forest; - public Phase(Phase prev, Parser parser, Phase previous, Token token, Token.Location location, Forest forest) { + public Phase(Phase prev, Parser parser, Phase previous, Tok token, Token.Location location, Forest forest) { this.prev = prev; this.forest = forest; this.parser = parser; @@ -198,10 +202,6 @@ class GSS { class Reset extends RuntimeException { } - public void invoke(State st, Forest result, Node n) { - good |= next.newNode(n, result, st, false); - } - /** perform all shift operations, adding promoted nodes to next */ public void shift(Phase next, Forest result) throws ParseFailed { // this massively improves GC performance @@ -257,7 +257,7 @@ class GSS { private boolean allqueued = false; /** what state this node is in */ - public final State state; + public final Parser.Table.State state; /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */ public Phase phase() { return Phase.this; } @@ -303,22 +303,22 @@ class GSS { } } - public void reduce(Position r, int pos, GSS.Phase target, Forest[] holder) { + public void reduce(Position r, int pos, Phase target, Forest[] holder) { Forest old = holder[pos]; holder[pos] = this.pending(); if (pos==0) { System.arraycopy(holder, 0, r.holder, 0, holder.length); for(int i=0; i target, Forest[] holder) { + Parser.Table.State state0 = state.gotoSetNonTerminals.get(r.owner()); if (result==null) throw new Error(); if (state0!=null) target.newNode(this, result, state0, r.pos<=0, r); diff --git a/src/edu/berkeley/sbp/ParseFailed.java b/src/edu/berkeley/sbp/ParseFailed.java index e5041d6..9c0a3ad 100644 --- a/src/edu/berkeley/sbp/ParseFailed.java +++ b/src/edu/berkeley/sbp/ParseFailed.java @@ -16,7 +16,7 @@ public class ParseFailed extends RuntimeException { public Token.Location getLocation() { return location; } public String toString() { return message/* + (location==null ? "" : (" at " + location))*/; } - public static void complain(Node n, HashMap> errors, boolean force) { + public static void complain(GSS.Phase.Node n, HashMap> errors, boolean force) { //if (n.touched) return; //n.touched = true; for(Position p : n.state) { @@ -44,7 +44,7 @@ public class ParseFailed extends RuntimeException { } return ANSI.purple(ret.toString()); } - public static String error(String message, Token token, Iterable nodes) { + public static String error(String message, Object token, Iterable nodes) { String lookAhead = token==null ? "" : token.toString(); StringBuffer ret = new StringBuffer(); ret.append("\n "); diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index d04c49f..3bafbfe 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -6,31 +6,31 @@ import java.io.*; import java.util.*; /** a parser which translates streams of Tokens of type T into a Forest */ -public abstract class Parser { +public abstract class Parser { private final Table pt; /** create a parser to parse the grammar with start symbol u */ - protected Parser(Union u, Topology top) { this.pt = new Table(u, top); } - protected Parser(Table pt) { this.pt = pt; } + protected Parser(Union u, Topology top) { this.pt = new Table(u, top); } + protected Parser(Table pt) { this.pt = pt; } /** implement this method to create the output forest corresponding to a lone shifted input token */ - public abstract Forest shiftedToken(T t, Token.Location loc); + public abstract Forest shiftToken(Tok t, Token.Location loc); /** parse input, using the table pt to drive the parser */ - public Forest parse(Token.Stream input) throws IOException, ParseFailed { + public Forest parse(Token.Stream input) throws IOException, ParseFailed { GSS gss = new GSS(); Token.Location loc = input.getLocation(); - GSS.Phase current = gss.new Phase(null, this, null, input.next(1, 0, 0), loc, null); + GSS.Phase current = gss.new Phase(null, this, null, input.next(1, 0, 0), loc, null); current.newNode(null, Forest.leaf(null, null), pt.start, true); int count = 1; for(;;) { loc = input.getLocation(); current.reduce(); - Forest forest = current.token==null ? null : shiftedToken((T)current.token, loc); - GSS.Phase next = gss.new Phase(current, this, current, input.next(count, gss.resets, gss.waits), loc, forest); + Forest forest = current.token==null ? null : shiftToken((Tok)current.token, loc); + GSS.Phase next = gss.new Phase(current, this, current, input.next(count, gss.resets, gss.waits), loc, forest); count = next.size(); - if (current.isDone()) return (Forest)gss.finalResult; + if (current.isDone()) return (Forest)gss.finalResult; current = next; } } @@ -38,7 +38,7 @@ public abstract class Parser { // Table ////////////////////////////////////////////////////////////////////////////// /** an SLR(1) parse table which may contain conflicts */ - static class Table extends Walk.Cache { + static class Table extends Walk.Cache { public final Walk.Cache cache = this; @@ -55,7 +55,7 @@ public abstract class Parser { } /** the start state */ - public final State start; + public final State start; /** used to generate unique values for State.idx */ private int master_state_idx = 0; @@ -71,17 +71,17 @@ public abstract class Parser { cache.eof.put(start0, true); // construct the set of states - HashMap,State> all_states = new HashMap,State>(); - HashSet all_elements = new HashSet(); + HashMap,State> all_states = new HashMap,State>(); + HashSet all_elements = new HashSet(); walk(start0, all_elements); for(Element e : all_elements) cache.ys.addAll(e, new Walk.YieldSet(e, cache).walk()); HashSet hp = new HashSet(); reachable(start0, hp); - this.start = new State(hp, all_states, all_elements); + this.start = new State(hp, all_states, all_elements); // for each state, fill in the corresponding "row" of the parse table - for(State state : all_states.values()) + for(State state : all_states.values()) for(Position p : state.hs) { // the Grammar's designated "last position" is the only accepting state @@ -102,7 +102,7 @@ public abstract class Parser { if (p.element() != null && p.element() instanceof Atom) state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()))); } - for(State state : all_states.values()) { + for(State state : all_states.values()) { state.oreductions = state.reductions.optimize(); state.oshifts = state.shifts.optimize(); } @@ -116,34 +116,34 @@ public abstract class Parser { /** a single state in the LR table and the transitions possible from it */ - public class State implements Comparable, IntegerMappable, Iterable { + public class State implements Comparable>, IntegerMappable, Iterable { public final int idx = master_state_idx++; private final HashSet hs; - public transient HashMap gotoSetNonTerminals = new HashMap(); - private transient TopologicalBag gotoSetTerminals = new TopologicalBag(); + public transient HashMap> gotoSetNonTerminals = new HashMap>(); + private transient TopologicalBag> gotoSetTerminals = new TopologicalBag>(); - private TopologicalBag reductions = new TopologicalBag(); + private TopologicalBag reductions = new TopologicalBag(); private HashSet eofReductions = new HashSet(); - private TopologicalBag shifts = new TopologicalBag(); + private TopologicalBag> shifts = new TopologicalBag>(); private boolean accept = false; - private VisitableMap oshifts = null; - private VisitableMap oreductions = null; + private VisitableMap> oshifts = null; + private VisitableMap oreductions = null; // Interface Methods ////////////////////////////////////////////////////////////////////////////// boolean isAccepting() { return accept; } public Iterator iterator() { return hs.iterator(); } - boolean canShift(Token t) { return oshifts.contains(t); } - void invokeShifts(Token t, Invokable irbc, B b, C c) { + boolean canShift(Tok t) { return oshifts.contains(t); } + void invokeShifts(Tok t, Invokable,B,C> irbc, B b, C c) { oshifts.invoke(t, irbc, b, c); } - boolean canReduce(Token t) { return t==null ? eofReductions.size()>0 : oreductions.contains(t); } - void invokeReductions(Token t, Invokable irbc, B b, C c) { + boolean canReduce(Tok t) { return t==null ? eofReductions.size()>0 : oreductions.contains(t); } + void invokeReductions(Tok t, Invokable irbc, B b, C c) { if (t==null) for(Position r : eofReductions) irbc.invoke(r, b, c); else oreductions.invoke(t, irbc, b, c); } @@ -173,7 +173,7 @@ public abstract class Parser { * */ public State(HashSet hs, - HashMap,State> all_states, + HashMap,State> all_states, HashSet all_elements) { this.hs = hs; @@ -186,7 +186,7 @@ public abstract class Parser { // of _new_ positions (positions after shifting). These mappings are // collectively known as the _closure_ - TopologicalBag bag0 = new TopologicalBag(); + TopologicalBag bag0 = new TopologicalBag(); for(Position position : hs) { if (position.isLast() || !(position.element() instanceof Atom)) continue; Atom a = (Atom)position.element(); @@ -199,10 +199,10 @@ public abstract class Parser { // set, add that character set to the goto table (with the State corresponding to the // computed next-position set). - for(Topology r : bag0) { + for(Topology r : bag0) { HashSet h = new HashSet(); for(Position p : bag0.getAll(r)) h.add(p); - gotoSetTerminals.put(r, all_states.get(h) == null ? new State(h, all_states, all_elements) : all_states.get(h)); + gotoSetTerminals.put(r, all_states.get(h) == null ? new State(h, all_states, all_elements) : all_states.get(h)); } // Step 2: for every non-Atom element (ie every Element which has a corresponding reduction), @@ -224,7 +224,7 @@ public abstract class Parser { } for(Element 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); + State s = all_states.get(h) == null ? new State(h, all_states, all_elements) : all_states.get(h); gotoSetNonTerminals.put(y, s); } } @@ -236,7 +236,7 @@ public abstract class Parser { return ret.toString(); } - public int compareTo(Table.State s) { return idx==s.idx ? 0 : idx < s.idx ? -1 : 1; } + public int compareTo(State s) { return idx==s.idx ? 0 : idx < s.idx ? -1 : 1; } public int toInt() { return idx; } } } diff --git a/src/edu/berkeley/sbp/Token.java b/src/edu/berkeley/sbp/Token.java index 1014a55..10ab90f 100644 --- a/src/edu/berkeley/sbp/Token.java +++ b/src/edu/berkeley/sbp/Token.java @@ -14,8 +14,8 @@ public interface Token { public abstract String toString(); /** a sequence of input tokens; returns null when EOF is reached */ - public static interface Stream { - public T next(int numstates, int resets, int waits) throws IOException; + public static interface Stream { + public Tok next(int numstates, int resets, int waits) throws IOException; public abstract Location getLocation(); } diff --git a/src/edu/berkeley/sbp/misc/CharToken.java b/src/edu/berkeley/sbp/misc/CharToken.java index 87be340..2042145 100644 --- a/src/edu/berkeley/sbp/misc/CharToken.java +++ b/src/edu/berkeley/sbp/misc/CharToken.java @@ -15,7 +15,7 @@ public class CharToken implements Token, IntegerMappable { public static class CharToStringParser extends Parser { public CharToStringParser(Union u) { super(u, new IntegerTopology()); } - public Forest shiftedToken(CharToken ct, Token.Location loc) { + public Forest shiftToken(CharToken ct, Token.Location loc) { return Forest.create(loc, ct.result(), null, false, false); } } -- 1.7.10.4