From 142b31e063c97d2d6dc141a9e687d49b7f2ab826 Mon Sep 17 00:00:00 2001 From: adam Date: Sat, 11 Feb 2006 18:03:09 -0500 Subject: [PATCH] added GraphViz support darcs-hash:20060211230309-5007d-f17b922b820a79df9997ac551367f28d4ba212fa.gz --- src/edu/berkeley/sbp/Forest.java | 46 +++++++++-- src/edu/berkeley/sbp/tib/TibDoc.java | 55 ++++++++----- src/edu/berkeley/sbp/util/GraphViz.java | 123 +++++++++++++++++++++++++++++ src/edu/berkeley/sbp/util/StringUtil.java | 1 + tests/input.tibdoc | 2 +- tests/tibdoc.g | 2 +- 6 files changed, 199 insertions(+), 30 deletions(-) create mode 100644 src/edu/berkeley/sbp/util/GraphViz.java diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java index abc5874..b9c4fcc 100644 --- a/src/edu/berkeley/sbp/Forest.java +++ b/src/edu/berkeley/sbp/Forest.java @@ -7,7 +7,7 @@ import java.util.*; import java.lang.reflect.*; /** an efficient representation of a collection of trees (Tomita's shared packed parse forest) */ -public abstract class Forest /*extends PrintableTree>*/ implements Visitable>, IntegerMappable { +public abstract class Forest /*extends PrintableTree>*/ implements Visitable>, IntegerMappable, GraphViz.ToGraphViz { private static int master_idx = 0; private final int idx = master_idx++; @@ -24,7 +24,6 @@ public abstract class Forest /*extends PrintableTree>*/ impl /** expand this forest into a set of trees */ public HashSet> expand(boolean toss) { - //if (toss) scan(); final HashSetTreeConsumer ret = new HashSetTreeConsumer(); visit(new TreeMaker2(toss, ret), null, null); if (toss && ret.size() > 1) throw new InnerAmbiguous(this); @@ -50,19 +49,37 @@ public abstract class Forest /*extends PrintableTree>*/ impl return body; } static Forest leaf(Input.Location loc, T tag, Position p) { return create(loc, tag, null, false, false, p); } - public static Forest create(Input.Location loc, T tag, Forest[] tokens, boolean unwrap, boolean singleton, Position p) { return new MyBody(loc, tag, tokens, unwrap, singleton, p); } - // Body ////////////////////////////////////////////////////////////////////////////// - protected static interface Body { + protected static interface Body extends GraphViz.ToGraphViz { void expand(int i, TreeMaker h); } - + public abstract void edges(GraphViz.Node n); protected static class MyBody extends Forest implements Body /* extends PrintableTree> implements */ { + public boolean isTransparent() { return false; } + public boolean isHidden() { return false; } + public GraphViz.Node toGraphViz(GraphViz gv) { + if (gv.hasNode(this)) return gv.createNode(this); + GraphViz.Node n = gv.createNode(this); + n.label = headToString()==null?"":headToString(); + n.directed = true; + edges(n); + return n; + } + public void edges(GraphViz.Node n) { + for(int i=0; i void visit(Invokable,B,C> ivbc, B b, C c) { ivbc.invoke(this, b, c); } @@ -113,7 +130,7 @@ public abstract class Forest /*extends PrintableTree>*/ impl } } - protected String headToString() { return null; } + protected String headToString() { return tag==null?null:tag.toString(); } protected String headToJava() { return null; } protected String left() { return "{"; } protected String right() { return "}"; } @@ -136,6 +153,21 @@ public abstract class Forest /*extends PrintableTree>*/ impl return super.toInt(); } public void merge(Forest p) { if (p!=this) hp.add(p, true); } + + public boolean isTransparent() { return hp.size()==1; } + public boolean isHidden() { return hp.size()==0; } + public void edges(GraphViz.Node n) { for(Forest f : hp) f.edges(n); } + public GraphViz.Node toGraphViz(GraphViz gv) { + if (hp.size()==0) return null; + if (hp.size()==1) return hp.iterator().next().toGraphViz(gv); + if (gv.hasNode(this)) return gv.createNode(this); + GraphViz.Node n = gv.createNode(this); + n.label = "?"; + n.color = "red"; + for(Forest f : hp) n.edge(f); + return n; + } + public void visit(Invokable,B,C> ivbc, B b, C c) { if (hp==null) return; for(Forest f : hp) diff --git a/src/edu/berkeley/sbp/tib/TibDoc.java b/src/edu/berkeley/sbp/tib/TibDoc.java index 553397b..f3195ec 100644 --- a/src/edu/berkeley/sbp/tib/TibDoc.java +++ b/src/edu/berkeley/sbp/tib/TibDoc.java @@ -13,27 +13,40 @@ import java.io.*; public class TibDoc { public static void main(String[] s) throws Exception { - System.out.println("parsing " + s[0]); - Tree res = new CharParser(MetaGrammar.make()).parse(new FileInputStream(s[0])).expand1(); - MetaGrammar gram = (MetaGrammar)new Tib.Grammar().walk(res); - //System.out.println(gram); - Union mg = gram.done(); - - System.out.println("\nparsing " + s[1]); - Forest f = new CharParser(mg).parse(new Tib(new FileInputStream(s[1]))); - - System.out.println(); - System.out.println(f); - System.out.println(); - System.out.println(((Tree)new StringifyWalker().walk(f.expand1())).toPrettyString()); - - String st = new HTMLWalker().walk(f.expand1()).toString(); - System.out.println(st); - FileOutputStream fos = new FileOutputStream("out.html"); - PrintWriter p = new PrintWriter(new OutputStreamWriter(fos)); - p.println(st); - p.flush(); - p.close(); + try { + System.out.println("parsing " + s[0]); + Tree res = new CharParser(MetaGrammar.make()).parse(new FileInputStream(s[0])).expand1(); + MetaGrammar gram = (MetaGrammar)new Tib.Grammar().walk(res); + //System.out.println(gram); + Union mg = gram.done(); + + System.out.println("\nparsing " + s[1]); + Forest f = new CharParser(mg).parse(new Tib(new FileInputStream(s[1]))); + + System.out.println(); + System.out.println(f); + System.out.println(); + System.out.println(((Tree)new StringifyWalker().walk(f.expand1())).toPrettyString()); + + String st = new HTMLWalker().walk(f.expand1()).toString(); + System.out.println(st); + FileOutputStream fos = new FileOutputStream("out.html"); + PrintWriter p = new PrintWriter(new OutputStreamWriter(fos)); + p.println(st); + p.flush(); + p.close(); + } catch (Ambiguous a) { + FileOutputStream fos = new FileOutputStream("/Users/megacz/Desktop/out.dot"); + PrintWriter p = new PrintWriter(new OutputStreamWriter(fos)); + GraphViz gv = new GraphViz(); + a.ambiguity.toGraphViz(gv); + gv.dump(p); + p.flush(); + p.close(); + + } catch (Exception e) { + e.printStackTrace(); + } } public static class StringifyWalker extends ReflectiveWalker { diff --git a/src/edu/berkeley/sbp/util/GraphViz.java b/src/edu/berkeley/sbp/util/GraphViz.java new file mode 100644 index 0000000..a92e298 --- /dev/null +++ b/src/edu/berkeley/sbp/util/GraphViz.java @@ -0,0 +1,123 @@ +package edu.berkeley.sbp.util; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; + +public class GraphViz { + + IdentityHashMap ihm = new IdentityHashMap(); + HashMap groups = new HashMap(); + + public class Group { + public Group() { } + public void add(Node n) { groups.put(n, this); } + } + + private static int master_idx=0; + public class Node { + private final int idx = master_idx++; + public String label; + public boolean directed = false; + public String color="black"; + public ArrayList edges = new ArrayList(); + public ArrayList inbound = new ArrayList(); + public void edge(ToGraphViz o) { + Node n = o.toGraphViz(GraphViz.this); + if (n==null) return; + edges.add(n); + n.inbound.add(this); + } + public String name() { + if (inbound.size()==1 && inbound.get(0).simple()) + return inbound.get(0).name()+":node_"+idx; + return "node_"+idx; + } + public void edges(PrintWriter pw) { + if (simple()) return; + for(Node n : edges) + pw.println(" "+name()+" -> " + n.name()); + } + public int numEdges() { return edges.size(); } + public boolean simple() { + boolean simple = true; + if (label!=null && !label.equals("")) simple = false; + if (simple) + for(Node n : edges) + //if (n.numEdges()>0) { simple = false; break; } + if (n.inbound.size() > 1) { simple = false; break; } + return simple; + } + public void dump(PrintWriter pw) { + if (inbound.size() > 0) { + boolean good = false; + for(Node n : inbound) + if (!n.simple()) + { good = true; break; } + if (!good) return; + } + pw.print(" "+name()); + pw.print(" ["); + if (directed) pw.print("ordering=out"); + if (simple()) { + pw.print(" shape=record "); + pw.print(" label=\"{"); + boolean first = true; + for(Node n : edges) { + if (!first) pw.print("|"); + first = false; + pw.print("<"+n.name()+">"); + pw.print(StringUtil.escapify(n.label,"\\\"")); + } + pw.print("}\""); + } else { + pw.print(" label=\""); + pw.print(StringUtil.escapify(label,"\\\"")); + pw.print("\""); + } + pw.print("color="+color); + pw.print("];\n"); + } + } + + public boolean hasNode(ToGraphViz o) { + return ihm.get(o)!=null; + } + + public Node createNode(ToGraphViz o) { + Node n = ihm.get(o); + if (n!=null) return n; + n = new Node(); + ihm.put(o, n); + return n; + } + + public static interface ToGraphViz { + public Node toGraphViz(GraphViz gv); + public boolean isTransparent(); + public boolean isHidden(); + } + + public void dump(PrintWriter pw) { + IdentityHashMap done = new IdentityHashMap(); + pw.println("digraph G {\n"); + for(Group g : groups.values()) { + pw.println(" { rank=same;\n"); + for(Node n : groups.keySet()) + if (groups.get(n)==g) { + done.put(n,n); + n.dump(pw); + } + pw.println(" }\n"); + } + for(Node n : ihm.values()) { + if (done.get(n)!=null) continue; + n.dump(pw); + } + for(Node n : ihm.values()) n.edges(pw); + pw.println("}\n"); + } + +} diff --git a/src/edu/berkeley/sbp/util/StringUtil.java b/src/edu/berkeley/sbp/util/StringUtil.java index 41e67e9..8c046ee 100644 --- a/src/edu/berkeley/sbp/util/StringUtil.java +++ b/src/edu/berkeley/sbp/util/StringUtil.java @@ -55,6 +55,7 @@ public class StringUtil { */ public static String escapify(String s) { return escapify(s, "\\\n\r"); } public static String escapify(String s, String illegal) { + if (s==null) return null; StringBuffer sb = new StringBuffer(); for(int i=0; iadam@megacz.com with a !hyperlink to it! - The following demonstrates verbatim stuff [Knu68], as + The following demonstrates verbatim stuff [[Knu68]], as well as a footnote ((like)) because are coool in an O(n^^3) way. diff --git a/tests/tibdoc.g b/tests/tibdoc.g index 6287afa..4a57992 100644 --- a/tests/tibdoc.g +++ b/tests/tibdoc.g @@ -111,7 +111,7 @@ pre = verbatim:: "[verbatim]" { ~[]+ } /ws // FIXME doesn't work styled = underline:: "__" text "__" | footnote:: "((" text "))" | ( tt:: "[[" text "]]" - > citation:: "[" word "]" + | citation:: "[" text "]" ) | strikethrough:: "!!" text "!!" | superscript:: "^^" (word|block) -- 1.7.10.4