X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FParser.java;h=db08afcd22c0afadd2671761384d5a29efcce848;hp=fac14b0e78e251ff76b6f12254eb9b17cae4fce4;hb=a22c5074e705e3ffcf03e9f9d174aed8ef79fc91;hpb=9ded11559a1b6f817e99355b1c9e2c88042e91d4 diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index fac14b0..db08afc 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -1,12 +1,9 @@ package edu.berkeley.sbp; import edu.berkeley.sbp.*; import edu.berkeley.sbp.util.*; -import edu.berkeley.sbp.*; import edu.berkeley.sbp.Sequence.Position; -import edu.berkeley.sbp.*; import java.io.*; import java.util.*; -import java.lang.reflect.*; /** a parser which translates streams of Tokens of type T into a Forest */ public abstract class Parser { @@ -15,14 +12,16 @@ public abstract class Parser { /** create a parser to parse the grammar with start symbol u */ protected Parser(Union u) { this.pt = new Table(u, top()); } - protected Parser(Table pt) { this.pt = pt; } + //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 Topology top(); + /** this method must return an empty topology of the input token type */ + public abstract Topology top(); - /** parse input for a exactly one unique result, throwing Ambiguous if not unique or Failed if none */ - public Tree parse1(Token.Stream input) throws IOException, Failed, Ambiguous { + /** parse input for a exactly one unique result, throwing Ambiguous if not unique or ParseFailed if none */ + public Tree parse1(Token.Stream input) throws IOException, ParseFailed, Ambiguous { Forest ret = parse(input); try { return ret.expand1(); } catch (Ambiguous a) { @@ -33,19 +32,19 @@ public abstract class Parser { } /** parse input, using the table pt to drive the parser */ - public Forest parse(Token.Stream input) throws IOException, Failed { + 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, input.next(), loc); - current.newNode(null, null, pt.start, true); + 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(); - GSS.Phase next = gss.new Phase(current, input.next(), loc); current.reduce(); Forest forest = current.token==null ? null : shiftedToken((T)current.token, loc); - current.shift(next, forest); + GSS.Phase next = gss.new Phase(current, this, current, input.next(count, gss.resets, gss.waits), loc, forest); + count = next.hash.size(); if (current.isDone()) return (Forest)current.finalResult; - current.checkFailure(); current = next; } } @@ -53,27 +52,6 @@ public abstract class Parser { // Exceptions ////////////////////////////////////////////////////////////////////////////// - public static class Failed extends Exception { - private final Token.Location location; - private final String message; - public Failed() { this("", null); } - public Failed(String message, Token.Location loc) { this.location = loc; this.message = message; } - public Token.Location getLocation() { return location; } - public String toString() { return message + (location==null ? "" : (" at " + location)); } - } - - public static class Ambiguous extends RuntimeException { - public final Forest ambiguity; - public Ambiguous(Forest ambiguity) { this.ambiguity = ambiguity; } - public String toString() { - StringBuffer sb = new StringBuffer(); - sb.append("unresolved ambiguity "/*"at " + ambiguity.getLocation() + ":"*/); - for(Object result : ambiguity.expand(false)) - sb.append("\n " + result); - return sb.toString(); - } - } - // Table ////////////////////////////////////////////////////////////////////////////// @@ -81,6 +59,8 @@ public abstract class Parser { static class Table extends Walk.Cache { public final Walk.Cache cache = this; + + public HashMapBag byPosition = new HashMapBag(); private void walk(Element e, HashSet hs) { if (e==null) return; @@ -159,8 +139,18 @@ public abstract class Parser { } /** a single state in the LR table and the transitions possible from it */ - public class State implements Comparable, Iterable { + + public class State implements Comparable, IntegerMappable, Iterable { + public int toInt() { return idx; } + + public boolean lame() { + for(Position p : this) + for(Position p2 = p; p2!=null; p2=p2.next()) + if (p2.isLast() && !p2.owner().lame) + return false; + return true; + } /* public boolean isResolvable(Token t) { boolean found = false; @@ -245,6 +235,7 @@ public abstract class Parser { // register ourselves in the all_states hash so that no // two states are ever created with an identical position set all_states.put(hs, this); + for(Position p : hs) byPosition.add(p,this); // Step 1a: examine all Position's in this state and compute the mappings from // sets of follow tokens (tokens which could follow this position) to sets @@ -307,7 +298,13 @@ public abstract class Parser { } } - public String toString() { return "state["+idx+"]"; } + public String toString() { + //return "state["+idx+"]"; + StringBuffer ret = new StringBuffer(); + ret.append("state["+idx+"]: "); + for(Position p : this) ret.append("{"+p+"} "); + return ret.toString(); + } public int compareTo(Table.State s) { return idx==s.idx ? 0 : idx < s.idx ? -1 : 1; } } @@ -378,8 +375,9 @@ public abstract class Parser { } private void finish(GSS.Phase.Node parent, Forest result, GSS.Phase target) { State state = parent.state.gotoSetNonTerminals.get(position.owner()); + if (result==null) throw new Error(); if (state!=null) - target.newNode(parent, result, state, numPop<=0); + target.newNode(parent, result, state, numPop<=0, this); } } }