X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FParser.java;h=9db0bf95b61e642415f48595e0ca8f39807433ba;hp=4aa65151106cb01ece84878d9b80a5c7110b92db;hb=3ee451bce342d4bb61ad6235ba57bdf817bfdd1a;hpb=b8a597c8d1a29afc24f9b89f726d5b1a9b9aeec1

diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index 4aa6515..9db0bf9 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,35 +7,37 @@ 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<R> */
-public abstract class Parser<Tok, Result> {
+/** a parser which translates an Input&lt;Token&gt; into a Forest&lt;NodeType&gt; */
+public abstract class Parser<Token, NodeType> {
 
-    protected final Table<Tok> pt;
+    protected final Table<Token> pt;
 
     /** create a parser to parse the grammar with start symbol <tt>u</tt> */
-    protected Parser(Union u, Topology<Tok> top)  { this.pt = new Table<Tok>(u, top); }
-    protected Parser(Table<Tok> pt)               { this.pt = pt; }
+    public Parser(Union u, Topology<Token> top)  { this.pt = new Table<Token>(u, top); }
+    Parser(Table<Token> pt)               { this.pt = pt; }
 
     /** implement this method to create the output forest corresponding to a lone shifted input token */
-    protected abstract Forest<Result> shiftToken(Tok t, Input.Location newloc);
+    public abstract Forest<NodeType> shiftToken(Token t, Input.Location newloc);
 
     boolean helpgc = true;
 
     public String toString() { return pt.toString(); }
 
     /** parse <tt>input</tt>, and return the shared packed parse forest (or throw an exception) */
-    public Forest<Result> parse(Input<Tok> input) throws IOException, ParseFailed {
+    public Forest<NodeType> parse(Input<Token> input) throws IOException, ParseFailed {
         GSS gss = new GSS();
         Input.Location loc = input.getLocation();
-        GSS.Phase current = gss.new Phase<Tok>(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<Token>(null, this, null, tok, loc, input.getLocation(), null);
+        current.newNode(null, Forest.create(loc.createRegion(loc), null, null, false), 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<Tok>(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<Token>(current, this, current, nextToken, loc, input.getLocation(), forest);
             if (!helpgc) {
                 FileOutputStream fos = new FileOutputStream("out-"+idx+".dot");
                 PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
@@ -45,7 +49,7 @@ public abstract class Parser<Tok, Result> {
                 p.close();
             }
             count = next.size();
-            if (current.isDone()) return (Forest<Result>)gss.finalResult;
+            if (current.isDone()) return (Forest<NodeType>)gss.finalResult;
             current = next;
         }
     }
@@ -53,21 +57,21 @@ public abstract class Parser<Tok, Result> {
     // Table //////////////////////////////////////////////////////////////////////////////
 
     /** an SLR(1) parse table which may contain conflicts */
-    static class Table<Tok> extends Walk.Cache {
+    static class Table<Token> extends Walk.Cache {
 
         public String toString() {
             StringBuffer sb = new StringBuffer();
             sb.append("parse table");
-            for(State<Tok> state : all_states.values()) {
+            for(State<Token> state : all_states.values()) {
                 sb.append("  " + state + "\n");
-                for(Topology<Tok> t : state.shifts) {
+                for(Topology<Token> t : state.shifts) {
                     sb.append("      shift  \""+
                               new edu.berkeley.sbp.chr.CharTopology((IntegerTopology<Character>)t)+"\" => ");
                     for(State st : state.shifts.getAll(t))
                         sb.append(st.idx+"  ");
                     sb.append("\n");
                 }
-                for(Topology<Tok> t : state.reductions)
+                for(Topology<Token> t : state.reductions)
                     sb.append("      reduce \""+
                               new edu.berkeley.sbp.chr.CharTopology((IntegerTopology<Character>)t)+"\" => " +
                               state.reductions.getAll(t) + "\n");
@@ -77,7 +81,7 @@ public abstract class Parser<Tok, Result> {
 
         public final Walk.Cache cache = this;
 
-        private void walk(Element e, HashSet<Element> hs) {
+        private void walk(Element e, HashSet<SequenceOrElement> hs) {
             if (e==null) return;
             if (hs.contains(e)) return;
             hs.add(e);
@@ -85,7 +89,7 @@ public abstract class Parser<Tok, Result> {
             for(Sequence s : (Union)e)
                 walk(s, hs);
         }
-        private void walk(Sequence s, HashSet<Element> hs) {
+        private void walk(Sequence s, HashSet<SequenceOrElement> hs) {
             hs.add(s);
             for(Position p = s.firstp(); p != null; p = p.next())
                 walk(p.element(), hs);
@@ -94,14 +98,14 @@ public abstract class Parser<Tok, Result> {
         }
 
         /** the start state */
-        public  final State<Tok>   start;
+        public  final State<Token>   start;
 
         /** the state from which no reductions can be done */
-        private final State<Tok>   dead_state;
+        private final State<Token>   dead_state;
 
         /** used to generate unique values for State.idx */
         private int master_state_idx = 0;
-        HashMap<HashSet<Position>,State<Tok>>   all_states    = new HashMap<HashSet<Position>,State<Tok>>();
+        HashMap<HashSet<Position>,State<Token>>   all_states    = new HashMap<HashSet<Position>,State<Token>>();
 
         /** construct a parse table for the given grammar */
         public Table(Topology top) { this("s", top); }
@@ -114,18 +118,18 @@ public abstract class Parser<Tok, Result> {
             cache.eof.put(start0, true);
 
             // construct the set of states
-            HashSet<Element>                        all_elements  = new HashSet<Element>();
+            HashSet<SequenceOrElement>                        all_elements  = new HashSet<SequenceOrElement>();
             walk(start0, all_elements);
-            for(Element e : all_elements)
+            for(SequenceOrElement e : all_elements)
                 cache.ys.addAll(e, new Walk.YieldSet(e, cache).walk());
             HashSet<Position> hp = new HashSet<Position>();
             reachable(start0, hp);
 
-            this.dead_state = new State<Tok>(new HashSet<Position>(), all_states, all_elements);
-            this.start = new State<Tok>(hp, all_states, all_elements);
+            this.dead_state = new State<Token>(new HashSet<Position>(), all_states, all_elements);
+            this.start = new State<Token>(hp, all_states, all_elements);
 
             // for each state, fill in the corresponding "row" of the parse table
-            for(State<Tok> state : all_states.values())
+            for(State<Token> state : all_states.values())
                 for(Position p : state.hs) {
 
                     // the Grammar's designated "last position" is the only accepting state
@@ -147,7 +151,7 @@ public abstract class Parser<Tok, Result> {
                         state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()).getTokenTopology()));
                 }
             if (top instanceof IntegerTopology)
-                for(State<Tok> state : all_states.values()) {
+                for(State<Token> state : all_states.values()) {
                     state.oreductions = state.reductions.optimize(((IntegerTopology)top).functor());
                     state.oshifts = state.shifts.optimize(((IntegerTopology)top).functor());
                 }
@@ -161,34 +165,34 @@ public abstract class Parser<Tok, Result> {
 
         /** a single state in the LR table and the transitions possible from it */
 
-        class State<Tok> implements Comparable<State<Tok>>, IntegerMappable, Iterable<Position> {
+        class State<Token> implements Comparable<State<Token>>, IntegerMappable, Iterable<Position> {
         
             public  final     int               idx    = master_state_idx++;
             private final     HashSet<Position> hs;
 
-            public transient HashMap<Element,State<Tok>>          gotoSetNonTerminals = new HashMap<Element,State<Tok>>();
-            private transient TopologicalBag<Tok,State<Tok>>     gotoSetTerminals    = new TopologicalBag<Tok,State<Tok>>();
+            public transient HashMap<Sequence,State<Token>>         gotoSetNonTerminals = new HashMap<Sequence,State<Token>>();
+            private transient TopologicalBag<Token,State<Token>>     gotoSetTerminals    = new TopologicalBag<Token,State<Token>>();
 
-            private           TopologicalBag<Tok,Position> reductions          = new TopologicalBag<Tok,Position>();
+            private           TopologicalBag<Token,Position> reductions          = new TopologicalBag<Token,Position>();
             private           HashSet<Position>              eofReductions       = new HashSet<Position>();
-            private           TopologicalBag<Tok,State<Tok>>     shifts              = new TopologicalBag<Tok,State<Tok>>();
+            private           TopologicalBag<Token,State<Token>>     shifts              = new TopologicalBag<Token,State<Token>>();
             private           boolean                         accept              = false;
 
-            private VisitableMap<Tok,State<Tok>> oshifts = null;
-            private VisitableMap<Tok,Position> oreductions = null;
+            private VisitableMap<Token,State<Token>> oshifts = null;
+            private VisitableMap<Token,Position> oreductions = null;
 
             // Interface Methods //////////////////////////////////////////////////////////////////////////////
 
             boolean             isAccepting()           { return accept; }
             public Iterator<Position>  iterator()       { return hs.iterator(); }
 
-            boolean             canShift(Tok t)         { return oshifts!=null && oshifts.contains(t); }
-            <B,C> void          invokeShifts(Tok t, Invokable<State<Tok>,B,C> irbc, B b, C c) {
+            boolean             canShift(Token t)         { return oshifts!=null && oshifts.contains(t); }
+            <B,C> void          invokeShifts(Token t, Invokable<State<Token>,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)); }
-            <B,C> void          invokeReductions(Tok t, Invokable<Position,B,C> irbc, B b, C c) {
+            boolean             canReduce(Token t)        { return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
+            <B,C> void          invokeReductions(Token t, Invokable<Position,B,C> irbc, B b, C c) {
                 if (t==null) for(Position r : eofReductions) irbc.invoke(r, b, c);
                 else         oreductions.invoke(t, irbc, b, c);
             }
@@ -218,8 +222,8 @@ public abstract class Parser<Tok, Result> {
              *  </ul>
              */
             public State(HashSet<Position> hs,
-                         HashMap<HashSet<Position>,State<Tok>> all_states,
-                         HashSet<Element> all_elements) {
+                         HashMap<HashSet<Position>,State<Token>> all_states,
+                         HashSet<SequenceOrElement> all_elements) {
                 this.hs = hs;
 
                 // register ourselves in the all_states hash so that no
@@ -231,7 +235,7 @@ public abstract class Parser<Tok, Result> {
                 //          of _new_ positions (positions after shifting).  These mappings are
                 //          collectively known as the _closure_
 
-                TopologicalBag<Tok,Position> bag0 = new TopologicalBag<Tok,Position>();
+                TopologicalBag<Token,Position> bag0 = new TopologicalBag<Token,Position>();
                 for(Position position : hs) {
                     if (position.isLast() || !(position.element() instanceof Atom)) continue;
                     Atom a = (Atom)position.element();
@@ -244,10 +248,10 @@ public abstract class Parser<Tok, Result> {
                 //          set, add that character set to the goto table (with the State corresponding to the
                 //          computed next-position set).
 
-                for(Topology<Tok> r : bag0) {
+                for(Topology<Token> r : bag0) {
                     HashSet<Position> h = new HashSet<Position>();
                     for(Position p : bag0.getAll(r)) h.add(p);
-                    gotoSetTerminals.put(r, all_states.get(h) == null ? new State<Tok>(h, all_states, all_elements) : all_states.get(h));
+                    gotoSetTerminals.put(r, all_states.get(h) == null ? new State<Token>(h, all_states, all_elements) : all_states.get(h));
                 }
 
                 // Step 2: for every non-Atom element (ie every Element which has a corresponding reduction),
@@ -258,19 +262,19 @@ public abstract class Parser<Tok, Result> {
                 //         to avoid having to iteratively construct our set of States as shown in most
                 //         expositions of the algorithm (ie "keep doing XYZ until things stop changing").
 
-                HashMapBag<Element,Position> move = new HashMapBag<Element,Position>();
+                HashMapBag<SequenceOrElement,Position> move = new HashMapBag<SequenceOrElement,Position>();
                 for(Position p : hs) {
                     Element e = p.element();
                     if (e==null) continue;
-                    for(Element y : cache.ys.getAll(e)) {
+                    for(SequenceOrElement y : cache.ys.getAll(e)) {
                         HashSet<Position> hp = new HashSet<Position>();
                         reachable(p.next(), hp);
                         move.addAll(y, hp);
                     }
                 }
-                OUTER: for(Element y : move) {
+                OUTER: for(SequenceOrElement y : move) {
                     HashSet<Position> h = move.getAll(y);
-                    State<Tok> s = all_states.get(h) == null ? new State<Tok>(h, all_states, all_elements) : all_states.get(h);
+                    State<Token> s = all_states.get(h) == null ? new State<Token>(h, all_states, all_elements) : 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) {
@@ -279,13 +283,13 @@ public abstract class Parser<Tok, Result> {
                                 for(Sequence seq : u)
                                     if (seq.needs.contains((Sequence)y) || seq.hates.contains((Sequence)y)) {
                                         // FIXME: what if there are two "routes" to get to the sequence?
-                                        ((HashMap)gotoSetNonTerminals).put(y, dead_state);
+                                        ((HashMap)gotoSetNonTerminals).put((Sequence)y, dead_state);
                                         continue OUTER;
                                     }
                             }
                         }
+                        gotoSetNonTerminals.put((Sequence)y, s);
                     }
-                    gotoSetNonTerminals.put(y, s);
                 }
             }
 
@@ -304,7 +308,7 @@ public abstract class Parser<Tok, Result> {
                 return ret.toString();
             }
 
-            public int compareTo(State<Tok> s) { return idx==s.idx ? 0 : idx < s.idx ? -1 : 1; }
+            public int compareTo(State<Token> s) { return idx==s.idx ? 0 : idx < s.idx ? -1 : 1; }
             public int toInt() { return idx; }
         }
     }