X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=bf58e6461ba0fd6aeb5566c21b3c7ecfb61f62ba;hp=ca8e1d505368093ab6d2f3598a6215291d9bda13;hb=33d7b8fa4974bad96108c11e5548b354cf10ecb8;hpb=dc9bb3a45ed306e2e35549076842b3e74efecb48 diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index ca8e1d5..bf58e64 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -1,10 +1,11 @@ -// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license +// Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license 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.Sequence.Pos; +import edu.berkeley.sbp.Sequence.Pos; import java.io.*; import java.util.*; import java.lang.reflect.*; @@ -26,7 +27,7 @@ class GSS { class Phase implements Invokable, IntegerMappable, GraphViz.ToGraphViz, Iterable { // FIXME: right now, these are the performance bottleneck - private HashMapBag performed = new HashMapBag(); + private HashMapBag performed = new HashMapBag(); public Forest.Many finalResult; private PriorityQueue reductionQueue = new PriorityQueue(); @@ -52,7 +53,6 @@ class GSS { private Phase prev; private Input.Location location; private Input.Location nextLocation; - private Input.Location prevLocation; private Forest forest; @@ -62,40 +62,36 @@ class GSS { newNode(primordealResult, startState, true); } public Phase(Phase prev, Forest forest) throws ParseFailed, IOException { - this.prevLocation = input.getLocation(); - this.token = (Tok)input.next(); this.location = input.getLocation(); + this.token = (Tok)input.next(); + this.nextLocation = input.getLocation(); this.prev = prev; this.forest = forest; this.pos = prev==null ? 0 : prev.pos+1; - this.nextLocation = input.getLocation(); if (prev != null) prev.shift(this, forest); numReductions = 0; int minPhasePos = Integer.MAX_VALUE; - int maxOrd = -1; Reduction best = null; //System.out.println("=============================================================================="); while(!reductionQueue.isEmpty()) { Reduction r = reductionQueue.poll(); //System.out.println("- " + r); - if (r.parentPhase() != null) - if (r.parentPhase().pos > minPhasePos) + if (r.predPhase() != null) + if (r.predPhase().pos > minPhasePos) throw new Error(); r.perform(); - if (r.parentPhase() != null) { - if (r.parentPhase().pos < minPhasePos) { - minPhasePos = r.parentPhase().pos; - maxOrd = r.reduction().ord; + if (r.predPhase() != null) { + if (r.predPhase().pos < minPhasePos) { + minPhasePos = r.predPhase().pos; best = r; - } else if (r.parentPhase().pos == minPhasePos) { + } else if (r.predPhase().pos == minPhasePos) { /* if (best != null && Parser.mastercache.comparePositions(r.reduction(), best.reduction()) < 0) throw new Error("\n"+r+"\n"+best+"\n"+ Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+ "\n"+(r.reduction().ord-best.reduction().ord)); */ - maxOrd = r.reduction().ord; best = r; } } @@ -107,26 +103,24 @@ class GSS { public boolean isDone() throws ParseFailed { if (token != null) return false; if (token==null && finalResult==null) - ParseFailed.error("unexpected end of file", this); + ParseFailed.error("unexpected end of file", this, null, + getLocation().createRegion(getLocation())); return true; } - public Input.Location getPrevLocation() { return prevLocation; } public Input.Location getLocation() { return location; } - public Input.Region getRegion() { return prevLocation.createRegion(location); } public Input.Location getNextLocation() { return nextLocation; } public boolean isFrontier() { return hash!=null; } /** perform all shift operations, adding promoted nodes to next */ - private void shift(Phase next, Forest result) throws ParseFailed { + private void shift(Phase next, Forest f) throws ParseFailed { this.next = next; // this massively improves GC performance if (prev != null) { IntPairMap h = prev.hash; prev.hash = null; prev.performed = null; - for(Node n : h) - n.check(); + for(Node n : h) n.check(); } numOldNodes = hash.size(); for(Node n : hash.values()) { @@ -136,28 +130,47 @@ class GSS { finalResult.merge(r.getForest()); } if (token == null) continue; - n.state().invokeShifts(token, this, new Result(result, n, null)); + Result result = new Result(f, n, null); + n.state().invokeShifts(token, this, result); } numNewNodes = next==null ? 0 : next.hash.size(); viewPos = this.pos; - if (!good && token!=null) ParseFailed.error("unexpected character", this); - if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this); + if (!good && token!=null) { + String toks = token+""; + if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.left) { + ParseFailed.error("unexpected increase in indentation", this, + token, getRegionFromThisToNext()); + } else if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.right) { + ParseFailed.error("unexpected decrease in indentation", this, + token, getRegionFromThisToNext()); + } else { + ParseFailed.error("unexpected character '"+ANSI.cyan(StringUtil.escapify(token+"", + "\\\'\r\n"))+"'", + this, token, getRegionFromThisToNext()); + } + } + if (token==null && finalResult==null) + ParseFailed.error("unexpected end of file", this, null, + getLocation().createRegion(getLocation())); for(Node n : hash) n.check(); } - void newNodeFromReduction(Result result, State state, Position reduction) { + Input.Region getRegionFromThisToNext() { + return getLocation().createRegion(getNextLocation()); + } + + void newNodeFromReduction(Result result, State state, Pos reduction) { int pos = result.phase().pos; - Sequence owner = reduction.owner(); - for(Sequence s : owner.hates()) + for(int s : reduction.hates()) if (performed.contains(pos, s)) return; - for(Sequence s : owner.needs()) + for(int s : reduction.needs()) if (!performed.contains(pos, s)) return; - if (owner.needed_or_hated && !performed.contains(pos, owner)) - performed.add(pos, owner); + if (reduction.owner_needed_or_hated() && !performed.contains(pos, reduction.provides())) + performed.add(pos, reduction.provides()); if (state!=null) - newNode(result, state, reduction.pos<=0); + newNode(result, state, reduction.numPops()<=0); } /** add a new node (merging with existing nodes if possible) @@ -169,7 +182,7 @@ class GSS { */ private boolean newNode(Result result, State state, boolean fromEmptyReduction) { Node p = hash.get(state, result.phase()); - if (p != null) { p.addResult(result); return true; } + if (p != null) { p.addResult(result); return !state.doomed(); } do { if (token != null && state.canShift(token)) break; if (state.isAccepting()) break; @@ -177,9 +190,10 @@ class GSS { if (!state.canReduce(token)) return false; } while(false); Node n = new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC + /** FIXME: this null-result can be used to notice bogus/dead states */ for(Object s : state.conjunctStates) newNode(new Result(null, n, null), (State)s, fromEmptyReduction); - return true; + return !n.state().doomed(); } public int toInt() { return pos+1; }