X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FParser.java;h=130ece9bfaeded7237c6f52a28a8a504565648d9;hp=a74ea5ea7459922106b6731373555a7d32183f0e;hb=21f5d362429cbbb7dafc7d307a2a1f6682e130f9;hpb=111166986ad83b54d0cae5c03c2304d23e332f29 diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index a74ea5e..130ece9 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -1,3 +1,5 @@ +// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license + package edu.berkeley.sbp; import edu.berkeley.sbp.*; import edu.berkeley.sbp.util.*; @@ -5,47 +7,49 @@ import edu.berkeley.sbp.Sequence.Position; import java.io.*; import java.util.*; -/** a parser which translates streams of Tokens of type T into a Forest */ -public abstract class Parser { +/** a parser which translates an Input<Token> into a Forest<NodeType> */ +public abstract class Parser { - protected final Table pt; + protected 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; } + public Parser(Union u, Topology top) { this.pt = new Table(u, top); } + Parser(Table pt) { this.pt = pt; } /** implement this method to create the output forest corresponding to a lone shifted input token */ - protected abstract Forest shiftToken(Tok t, Input.Location newloc); + public abstract Forest shiftToken(Token t, Input.Location newloc); boolean helpgc = true; public String toString() { return pt.toString(); } /** parse input, and return the shared packed parse forest (or throw an exception) */ - public Forest parse(Input input) throws IOException, ParseFailed { - GSS gss = new GSS(); + public Forest parse(Input input) throws IOException, ParseFailed { + GSS gss = new GSS(input); Input.Location loc = input.getLocation(); - GSS.Phase current = gss.new Phase(null, this, null, input.next(), loc, null); - current.newNode(null, Forest.create(null, null, null, false), pt.start, true); + Token tok = input.next(); + GSS.Phase current = gss.new Phase(null, null, tok, loc, input.getLocation(), null); + current.newNode(new Result(Forest.create(loc.createRegion(loc), null, null, false), null, null), pt.start, true); int count = 1; for(int idx=0;;idx++) { Input.Location oldloc = loc; - loc = input.getLocation(); current.reduce(); - Forest forest = current.token==null ? null : shiftToken((Tok)current.token, loc); - GSS.Phase next = gss.new Phase(current, this, current, input.next(), loc, forest); + Forest forest = current.token==null ? null : shiftToken((Token)current.token, loc); + loc = input.getLocation(); + Token nextToken = input.next(); + GSS.Phase next = gss.new Phase(current, current, nextToken, loc, input.getLocation(), forest); if (!helpgc) { FileOutputStream fos = new FileOutputStream("out-"+idx+".dot"); PrintWriter p = new PrintWriter(new OutputStreamWriter(fos)); GraphViz gv = new GraphViz(); for(Object n : next) - ((GSS.Phase.Node)n).toGraphViz(gv); + ((Node)n).toGraphViz(gv); gv.dump(p); p.flush(); p.close(); } count = next.size(); - if (current.isDone()) return (Forest)gss.finalResult; + if (current.isDone()) return (Forest)gss.finalResult; current = next; } } @@ -53,24 +57,26 @@ 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 String toString() { StringBuffer sb = new StringBuffer(); sb.append("parse table"); - for(State state : all_states.values()) { + for(State state : all_states.values()) { sb.append(" " + state + "\n"); - for(Topology t : state.shifts) { + for(Topology t : state.shifts) { sb.append(" shift \""+ new edu.berkeley.sbp.chr.CharTopology((IntegerTopology)t)+"\" => "); for(State st : state.shifts.getAll(t)) sb.append(st.idx+" "); sb.append("\n"); } - for(Topology t : state.reductions) + for(Topology t : state.reductions) sb.append(" reduce \""+ new edu.berkeley.sbp.chr.CharTopology((IntegerTopology)t)+"\" => " + state.reductions.getAll(t) + "\n"); + for(Sequence s : state.gotoSetNonTerminals.keySet()) + sb.append(" goto "+state.gotoSetNonTerminals.get(s)+" from " + s + "\n"); } return sb.toString(); } @@ -94,14 +100,15 @@ public abstract class Parser { } /** the start state */ - public final State start; + public final State start; /** the state from which no reductions can be done */ - private final State dead_state; + private final State dead_state; /** used to generate unique values for State.idx */ private int master_state_idx = 0; - HashMap,State> all_states = new HashMap,State>(); + HashMap,State> all_states = new HashMap,State>(); + HashSet all_elements = new HashSet(); /** construct a parse table for the given grammar */ public Table(Topology top) { this("s", top); } @@ -114,18 +121,19 @@ public abstract class Parser { cache.eof.put(start0, true); // construct the set of states - HashSet all_elements = new HashSet(); walk(start0, all_elements); for(SequenceOrElement e : all_elements) cache.ys.addAll(e, new Walk.YieldSet(e, cache).walk()); + for(SequenceOrElement e : all_elements) + cache.ys2.addAll(e, new Walk.YieldSet2(e, cache).walk()); HashSet hp = new HashSet(); reachable(start0, hp); - this.dead_state = new State(new HashSet(), all_states, all_elements); - this.start = new State(hp, all_states, all_elements); + this.dead_state = new State(new HashSet()); + this.start = new State(hp); // 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 @@ -135,8 +143,13 @@ public abstract class Parser { if (isRightNullable(p)) { Walk.Follow wf = new Walk.Follow(top.empty(), p.owner(), all_elements, cache); Topology follow = wf.walk(p.owner()); - for(Position p2 = p; p2 != null && p2.element() != null; p2 = p2.next()) + for(Position p2 = p; p2 != null && p2.element() != null; p2 = p2.next()) { + Atom set = new Walk.EpsilonFollowSet(new edu.berkeley.sbp.chr.CharAtom(top.empty().complement()), + new edu.berkeley.sbp.chr.CharAtom(top.empty()), + cache).walk(p2.element()); follow = follow.intersect(new Walk.Follow(top.empty(), p2.element(), all_elements, cache).walk(p2.element())); + if (set != null) follow = follow.intersect(set.getTokenTopology()); + } state.reductions.put(follow, p); if (wf.includesEof()) state.eofReductions.add(p); } @@ -147,7 +160,7 @@ public abstract class Parser { state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()).getTokenTopology())); } if (top instanceof IntegerTopology) - for(State state : all_states.values()) { + for(State state : all_states.values()) { state.oreductions = state.reductions.optimize(((IntegerTopology)top).functor()); state.oshifts = state.shifts.optimize(((IntegerTopology)top).functor()); } @@ -161,34 +174,35 @@ public abstract class Parser { /** a single state in the LR table and the transitions possible from it */ - class State implements Comparable>, IntegerMappable, Iterable { + class State implements IntegerMappable, Iterable { public final int idx = master_state_idx++; private final HashSet hs; + public HashSet> also = new HashSet>(); - 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(Tok t) { return oshifts!=null && oshifts.contains(t); } - void invokeShifts(Tok t, Invokable,B,C> irbc, B b, C c) { + boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); } + void invokeShifts(Token t, Invokable,B,C> irbc, B b, C c) { oshifts.invoke(t, irbc, b, c); } - boolean canReduce(Tok t) { return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); } - void invokeReductions(Tok t, Invokable irbc, B b, C c) { + boolean canReduce(Token t) { return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); } + void invokeReductions(Token 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); } @@ -198,7 +212,6 @@ public abstract class Parser { /** * create a new state consisting of all the Positions in hs * @param hs the set of Positions comprising this State - * @param all_states the set of states already constructed (to avoid recreating states) * @param all_elements the set of all elements (Atom instances need not be included) * * In principle these two steps could be merged, but they @@ -217,21 +230,38 @@ public abstract class Parser { * for non-Atom Elements. * */ - public State(HashSet hs, - HashMap,State> all_states, - HashSet all_elements) { + public State(HashSet hs) { this(hs, false); } + public boolean special; + public State(HashSet hs, boolean special) { this.hs = hs; + this.special = special; // 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); + ((HashMap)all_states).put(hs, this); + + for(Position p : hs) { + if (!p.isFirst()) continue; + for(Sequence s : p.owner().needs()) { + if (hs.contains(s.firstp())) continue; + HashSet h2 = new HashSet(); + reachable(s.firstp(), h2); + also.add((State)(all_states.get(h2) == null ? (State)new State(h2,true) : (State)all_states.get(h2))); + } + for(Sequence s : p.owner().hates()) { + if (hs.contains(s.firstp())) continue; + HashSet h2 = new HashSet(); + reachable(s, h2); + also.add((State)(all_states.get(h2) == null ? (State)new State(h2,true) : (State)all_states.get(h2))); + } + } // 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 // 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(); @@ -244,10 +274,11 @@ 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)); + ((TopologicalBag)gotoSetTerminals).put(r, all_states.get(h) == null + ? new State(h) : all_states.get(h)); } // Step 2: for every non-Atom element (ie every Element which has a corresponding reduction), @@ -262,7 +293,8 @@ public abstract class Parser { for(Position p : hs) { Element e = p.element(); if (e==null) continue; - for(SequenceOrElement y : cache.ys.getAll(e)) { + for(SequenceOrElement y : cache.ys2.getAll(e)) { + //System.out.println(e + " yields " + y); HashSet hp = new HashSet(); reachable(p.next(), hp); move.addAll(y, hp); @@ -270,7 +302,7 @@ public abstract class Parser { } OUTER: for(SequenceOrElement 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 ? (State)new State(h) : (State)all_states.get(h); // if a reduction is "lame", it should wind up in the dead_state after reducing if (y instanceof Sequence) { for(Position p : hs) { @@ -304,7 +336,7 @@ public abstract class Parser { return ret.toString(); } - public int compareTo(State s) { return idx==s.idx ? 0 : idx < s.idx ? -1 : 1; } + public Walk.Cache cache() { return cache; } public int toInt() { return idx; } } } @@ -313,8 +345,8 @@ public abstract class Parser { private static void reachable(Sequence s, HashSet h) { reachable(s.firstp(), h); - for(Sequence ss : s.needs()) reachable(ss, h); - for(Sequence ss : s.hates()) reachable(ss, h); + //for(Sequence ss : s.needs()) reachable(ss, h); + //for(Sequence ss : s.hates()) reachable(ss, h); } private static void reachable(Element e, HashSet h) { if (e instanceof Atom) return;