1 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
3 package edu.berkeley.sbp;
4 import edu.berkeley.sbp.*;
5 import edu.berkeley.sbp.util.*;
6 import edu.berkeley.sbp.Parser.Table.*;
7 import edu.berkeley.sbp.Sequence.Position;
10 import java.lang.reflect.*;
12 /** implements Tomita's Graph Structured Stack */
16 public GSS(Input input) { this.input = input; }
17 public Input getInput() { return input; }
19 // FIXME: right now, these are the performance bottleneck
20 HashMapBag<Integer,Sequence> performed = new HashMapBag<Integer,Sequence>();
23 Forest.Many finalResult;
25 /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
26 class Phase<Tok> implements Invokable<State, Result, Object>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
28 public ArrayList<Reduction> reductionQueue = new ArrayList<Reduction>();
30 public void invoke(State st, Result result, Object o) {
32 good |= next.newNode(result, st, false);
35 /** the token immediately after this phase */
39 public IntPairMap<Node> hash; /* ALLOC */
41 private Phase next = null;
43 private Input.Location location;
44 private Input.Location nextLocation;
45 private Input.Location prevLocation;
47 private Forest forest;
49 public Phase(Phase prev, Phase previous, Tok token, Input.Location location,
50 Input.Location nextLocation, Forest forest) throws ParseFailed {
51 this.prevLocation = prev==null ? location : prev.getLocation();
54 this.pos = previous==null ? 0 : previous.pos+1;
56 this.location = location;
57 this.nextLocation = nextLocation;
59 hash = new IntPairMap<Node>();
62 if (prev != null) prev.shift(this, forest);
65 public boolean isFrontier() { return next==null; }
66 public boolean isDone() throws ParseFailed {
67 if (token != null) return false;
68 if (token==null && finalResult==null)
69 ParseFailed.error("unexpected end of file", this);
73 public Input.Location getPrevLocation() { return prevLocation; }
74 public Input.Location getLocation() { return location; }
75 public Input.Region getRegion() { return getPrevLocation().createRegion(getLocation()); }
76 public Input.Location getNextLocation() { return nextLocation; }
78 /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
79 public void shift(Phase next, Forest result) throws ParseFailed {
80 // this massively improves GC performance
81 if (prev!=null) prev.hash = null;
83 for(Node n : hash.values()) {
84 if (token == null && n.state().isAccepting()) {
85 if (finalResult==null) finalResult = new Forest.Many();
87 finalResult.merge(r.getForest());
89 if (token == null) continue;
90 n.state().invokeShifts(token, this, new Result(result, n, null), null);
92 if (!good && token!=null) ParseFailed.error("unexpected character", this);
93 if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this);
96 /** perform all reduction operations */
97 public void reduce() throws ParseFailed {
98 Reduction last = null;
99 while(!reductionQueue.isEmpty()) {
103 OUTER: for(int i=0; i<reductionQueue.size(); i++) {
104 for(int j=0; j<reductionQueue.size(); j++) {
106 if (reductionQueue.get(i).compareTo(reductionQueue.get(j)) > 0)
109 r = reductionQueue.get(i);
110 reductionQueue.remove(r);
115 if (last == null) last = r;
116 else if (r.compareTo(last) > 0) last = r;
117 else if (r.compareTo(last) < 0) {
118 if (r.targetPhase() != null)
119 System.out.println("err " + last.compareTo(r) + " " + last.targetPhase().pos() +
120 " " + r.targetPhase().pos() + " " + pos);
128 public void newNodeFromReduction(Result result, State state, boolean fromEmptyReduction, Position reduction) {
129 int pos = result.phase().pos;
130 Sequence owner = reduction.owner();
131 for(Sequence s : owner.hates)
132 if (performed.contains(pos, s))
134 for(Sequence s : owner.needs)
135 if (!performed.contains(pos, s))
137 if (owner.needed_or_hated && !performed.contains(pos, owner))
138 performed.add(pos, owner);
140 newNode(result, state, fromEmptyReduction);
143 /** add a new node (merging with existing nodes if possible)
144 * @param parent the parent of the new node
145 * @param result the SPPF result corresponding to the new node
146 * @param state the state that the new node is in
147 * @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
148 * @param start the earliest part of the input contributing to this node (used to make merging decisions)
150 public boolean newNode(Result result, State state, boolean fromEmptyReduction) {
151 Node p = hash.get(state, result.phase());
152 if (p != null) { p.merge(result); return true; }
154 if (token != null && state.canShift(token)) break;
155 if (state.isAccepting()) break;
156 if (token==null) break;
157 if (!state.canReduce(token)) return false;
159 new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC
163 public int toInt() { return pos+1; }
164 public int size() { return hash==null ? 0 : hash.size(); }
165 public int pos() { return pos; }
166 public Tok getToken() { return token; }
167 public Iterator<Node> iterator() { return hash.iterator(); }
168 public GSS getGSS() { return GSS.this; }
170 // GraphViz //////////////////////////////////////////////////////////////////////////////
172 public GraphViz.Node toGraphViz(GraphViz gv) {
173 if (gv.hasNode(this)) return gv.createNode(this);
174 GraphViz.Group g = gv.createGroup(this);
175 g.label = "Phase " + pos;
180 public boolean isTransparent() { return false; }
181 public boolean isHidden() { return false; }