X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FParser.java;h=bfc022dd43bb68e86fcaba97d1f4a3bd01c56de2;hp=5f6e2526d80d4aeffe7daa5890225a92ce2be1d6;hb=HEAD;hpb=61566402d83d5c06d57fb850e60ca0f82c27b9a2

diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index 5f6e252..bfc022d 100644
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -8,7 +8,7 @@ import java.io.*;
 import java.util.*;
 
 /** a parser which translates an Input<Token> into a Forest<NodeType> */
-public abstract class Parser<Token, NodeType> {
+public abstract class Parser<Token, NodeType> implements Serializable {
 
     final Table pt;
 
@@ -24,22 +24,79 @@ public abstract class Parser<Token, NodeType> {
 
     /** parse <tt>input</tt>, and return the shared packed parse forest (or throw an exception) */
     public Forest<NodeType> parse(Input<Token> input) throws IOException, ParseFailed {
+        long start = System.currentTimeMillis();
         verbose = System.getProperty("sbp.verbose", null) != null;
         spinpos = 0;
         GSS gss = new GSS(input, this);
+        int idmax = 0;
+        int[][] count = new int[1024*1024][];
+        HashMap<Pos,Integer> ids = new HashMap<Pos,Integer>();
         try {
             for(GSS.Phase current = gss.new Phase<Token>(pt.start); ;) {
                 if (verbose) debug(current.token, gss, input);
                 if (current.isDone()) return (Forest<NodeType>)current.finalResult;
                 Input.Region region = current.getLocation().createRegion(current.getNextLocation());
                 Forest forest = shiftToken((Token)current.token, region);
+                /*
+                int maxid = 0;
+                for(Reduction r : gss.finishedReductions)
+                    if (ids.get(r.reduction())==null)
+                        ids.put(r.reduction(), idmax++);
+                count[current.pos] = new int[idmax];
+                for(Reduction r : gss.finishedReductions)
+                    count[current.pos][ids.get(r.reduction())]++;
+                */
                 current = gss.new Phase<Token>(current, forest);
             }
         } finally {
             if (verbose) {
-                System.err.print("\r"+ANSI.clreol());
+                long time = System.currentTimeMillis() - start;
+                System.err.println("\r parse time: " + time +"ms "+ ANSI.clreol());
                 debug(null, gss, input);
             }
+            /*
+            PrintWriter pw = new PrintWriter(new OutputStreamWriter(new FileOutputStream("out.plot")));
+            boolean[] use = new boolean[idmax];
+            for(int i=0; i<count.length; i++)
+                if (count[i]!=null)
+                for(int j=0; j<count[i].length; j++)
+                    if (count[i][j]>20)
+                        use[j] = true;
+            for(int i=0; i<count.length; i++)
+                if (count[i]!=null) {
+                    int row = 0;
+                    for(int j=0; j<use.length; j++)
+                        if (use[j]) {
+                            row++;
+                            pw.println(i+", "+row+", "+(j>=count[i].length ? 0 : count[i][j]));
+                        }
+                    pw.println();
+                }
+            pw.close();
+            pw = new PrintWriter(new OutputStreamWriter(new FileOutputStream("test.plot")));
+            pw.println("set terminal postscript enhanced color");
+            pw.println("set output \"out.ps\"");
+            pw.println("set pm3d map");
+            pw.println("set autoscale");
+            pw.println("set view 0,0");
+            pw.println("set ytics (\\");
+            int q = -1;
+            for(int j=0; j<use.length; j++)
+                if (use[j]) {
+                    q++;
+                    for(Pos p : ids.keySet())
+                        if (ids.get(p) == j) {
+                            String title = p.toString();
+                            System.out.println(q + " " + title);
+                            pw.println("\""+q+"\"  "+(((double)q)+0.5)+",\\");
+                            break;
+                        }
+                }
+            pw.println("\".\"  "+(q+1)+")");
+            pw.println("set size square");
+            pw.println("splot \"out.plot\"");
+            pw.close();
+            */
         }
     }
 
@@ -106,7 +163,7 @@ public abstract class Parser<Token, NodeType> {
     // Table //////////////////////////////////////////////////////////////////////////////
 
     /** an SLR(1) parse table which may contain conflicts */
-    class Table extends Grammar<Token> implements Serializable {
+    class Table implements Serializable {
 
         /** the start state */
         final State<Token>   start;
@@ -239,7 +296,7 @@ public abstract class Parser<Token, NodeType> {
          *  possible from it
          *
          *  A state corresponds to a set of Sequence.Pos's.  Each
-         *  Node in the GSS has a State; the Node represents a set of
+         *  StateNode in the GSS has a State; the StateNode represents a set of
          *  possible parses, one for each Pos in the State.
          *
          *  Every state is either "doomed" or "normal".  If a Pos
@@ -254,10 +311,10 @@ public abstract class Parser<Token, NodeType> {
          *  Nodes with non-doomed states represent nodes which
          *  contribute to actual valid parses.  Nodes with doomed
          *  States exist for no other purpose than to enable/disable
-         *  some future reduction from a non-doomed Node.  Because of
+         *  some future reduction from a non-doomed StateNode.  Because of
          *  this, we "garbage-collect" Nodes with doomed states if
          *  there are no more non-doomed Nodes which they could
-         *  affect (see Result, Reduction, and Node for details).
+         *  affect (see ResultNode, Reduction, and StateNode for details).
          *
          *  Without this optimization, many seemingly-innocuous uses
          *  of positive and negative conjuncts can trigger O(n^2)
@@ -273,8 +330,8 @@ public abstract class Parser<Token, NodeType> {
             HashMap<Pos,State<Token>>      gotoSetNonTerminals = new HashMap<Pos,State<Token>>();
             private transient TopologicalBag<Token,State<Token>>  gotoSetTerminals    = new TopologicalBag<Token,State<Token>>();
 
-            private           TopologicalBag<Token,Pos>      reductions          = new TopologicalBag<Token,Pos>();
-            private           HashSet<Pos>                   eofReductions       = new HashSet<Pos>();
+                       TopologicalBag<Token,Pos>      reductions          = new TopologicalBag<Token,Pos>();
+                       HashSet<Pos>                   eofReductions       = new HashSet<Pos>();
             private           TopologicalBag<Token,State<Token>>  shifts              = new TopologicalBag<Token,State<Token>>();
             private           boolean                             accept              = false;
 
@@ -290,16 +347,16 @@ public abstract class Parser<Token, NodeType> {
             Iterable<Pos>  positions()             { return hs; }
 
             boolean                    canShift(Token t)       { return oshifts!=null && oshifts.contains(t); }
-            void                       invokeShifts(Token t, GSS.Phase phase, Result r) { oshifts.invoke(t, phase, r); }
+            void                       invokeShifts(Token t, GSS.Phase phase, StateNode pred, Forest f) { oshifts.invoke(t, phase, pred, f); }
             boolean                    canReduce(Token t)        {
                 return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
-            void          invokeEpsilonReductions(Token t, Node node) {
-                if (t==null) for(Pos r : eofReductions) node.invoke(r, null);
-                else         oreductions.invoke(t, node, null);
+            void          invokeEpsilonReductions(Token t, StateNode node) {
+                if (t==null) for(Pos r : eofReductions) node.invoke(r, null, null);
+                else         oreductions.invoke(t, node, null, null);
             }
-            void          invokeReductions(Token t, Node node, Result b) {
-                if (t==null) for(Pos r : eofReductions) node.invoke(r, b);
-                else         oreductions.invoke(t, node, b);
+            void          invokeReductions(Token t, StateNode node, ResultNode only) {
+                if (t==null) for(Pos r : eofReductions) node.invoke(r, only, null);
+                else         oreductions.invoke(t, node, only, null);
             }
 
             // Constructor //////////////////////////////////////////////////////////////////////////////