X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2Fmeta%2FGrammarBuilder.java;h=121f4808fe972c7a081844652d6450201f3f214e;hp=d9b04c23dd0d63327530a12fd0b750b3d5b779b5;hb=1d5f76f8144b739719737bfe75f321caf67cfa19;hpb=7dd51387ce4308d3784a1291604203aaf677ba16 diff --git a/src/edu/berkeley/sbp/meta/GrammarBuilder.java b/src/edu/berkeley/sbp/meta/GrammarBuilder.java index d9b04c2..121f480 100644 --- a/src/edu/berkeley/sbp/meta/GrammarBuilder.java +++ b/src/edu/berkeley/sbp/meta/GrammarBuilder.java @@ -31,15 +31,26 @@ import java.io.*; /** The java classes typically used to represent a parsed grammar AST; each inner class is a type of AST node. */ public class GrammarBuilder { + /** + * Create a grammar from a parse tree and binding resolver + * + * @param t a tree produced by parsing a grammar using the metagrammar + * @param s the name of the "start symbol" + * @param gbr a GrammarBindingResolver that resolves grammatical reductions into tree-node-heads + */ + public static Union buildFromAST(Tree grammarAST, String startingNonterminal, File[] includes) { + return new GrammarBuilder(includes, "").buildGrammar(grammarAST, startingNonterminal); + } + public static Object illegalTag = ""; // this is the tag that should never appear in the non-dropped output FIXME private final String prefix; - private final String path; + private final File[] includes; //public GrammarBuilder(String path) { this(path, ""); } - public GrammarBuilder(String path, String prefix) { + public GrammarBuilder(File[] includes, String prefix) { this.prefix = prefix; - this.path = path; + this.includes = includes; } public Union buildGrammar(Tree t, String rootNonTerminal) { @@ -74,7 +85,8 @@ public class GrammarBuilder { public Object walk(Tree t) { String head = (String)t.head(); - while(head.indexOf('.') != -1) head = head.substring(head.indexOf('.')+1); + while(head.indexOf('.') > 0) + head = head.substring(head.indexOf('.')+1); if (head==null) throw new RuntimeException("head is null: " + t); if (head.equals("|")) return walkChildren(t); if (head.equals("RHS")) return walkChildren(t); @@ -84,8 +96,10 @@ public class GrammarBuilder { if (head.equals("Elements")) return seq2((ElementNode[])Reflection.rebuild(walkChildren(t), ElementNode[].class)); if (head.equals("NonTerminalReference")) return new ReferenceNode(stringifyChildren(t.child(0))); //if (head.equals(")")) return new ReferenceNode(stringifyChildren(t.child(0))); + if (head.equals("{")) return new XTree((Seq)walk(t.child(0))); if (head.equals("::")) return tag((String)walk(t.child(0)), (Seq)walk(t.child(1))); if (head.equals("++")) return plusmax((ElementNode)walk(t.child(0))); + if (head.equals("...")) return star(new TildeNode(new AtomNode())); if (head.equals("+")) return plus((ElementNode)walk(t.child(0))); if (head.equals("++/")) return plusmaxfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1))); if (head.equals("+/")) return plusfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1))); @@ -96,10 +110,15 @@ public class GrammarBuilder { if (head.equals("?")) return question((ElementNode)walk(t.child(0))); if (head.equals("!")) return new DropNode((ElementNode)walk(t.child(0))); if (head.equals("^")) return new LiteralNode((String)walk(t.child(0)), true); + if (head.equals("`")) { + ElementNode ret = (ElementNode)walk(t.child(0)); + ret.lifted = true; + return ret; + } if (head.equals("Quoted")) return stringifyChildren(t); if (head.equals("Literal")) return new LiteralNode((String)walk(t.child(0))); if (head.equals("->")) return arrow((Seq)walk(t.child(0)), (ElementNode)walk(t.child(1))); - if (head.equals("DropNT")) return new NonTerminalNode((String)walk(t.child(0)), (Seq[][])walk(t.child(1)), true, null, true); + if (head.equals("DropNT")) return new NonTerminalNode((String)walk(t.child(0)), (Seq[][])walkChildren(t.child(1)), false, null, true); if (head.equals("=") && t.size()==2) return new NonTerminalNode((String)walk(t.child(0)), (Seq[][])walk(t.child(1)), true, null, false); if (head.equals("=")) return new NonTerminalNode((String)walk(t.child(0)), (Seq[][])walk(t.child(2)), true, (String)walk(t.child(1)), false); if (head.equals("&")) return and2((Seq)walk(t.child(0)), (Seq)walk(t.child(1))); @@ -110,13 +129,17 @@ public class GrammarBuilder { if (head.equals("\\{")) return new DropNode(new AtomNode(new AtomNodeRange(CharAtom.left, CharAtom.left))); if (head.equals("\\}")) return new DropNode(new AtomNode(new AtomNodeRange(CharAtom.right, CharAtom.right))); if (head.equals("~")) return new TildeNode((ElementNode)walk(t.child(0))); + if (head.equals("~~")) { + Seq seq = new Seq(star(new TildeNode(new AtomNode()))); + return seq.andnot((Seq)walk(t.child(0))); + } if (head.equals("Range") && t.size()==1) return new AtomNodeRange(unescape(t).charAt(0)); if (head.equals("Range")) return new AtomNodeRange(unescape(t).charAt(0), unescape(t).charAt(1)); if (head.equals("\"\"")) return ""; if (head.equals("\n")) return "\n"; if (head.equals("\r")) return "\r"; if (head.equals("grammar.Grammar")) return walkChildren(t); - if (head.equals("SubGrammar")) return Grammar.create(t.child(0), "s"); + if (head.equals("SubGrammar")) return GrammarBuilder.buildFromAST(t.child(0), "s", includes); if (head.equals("NonTerminal")) return new NonTerminalNode((String)walk(t.child(0)), (Seq[][])walkChildren(t.child(1)), false, null, false); @@ -136,18 +159,22 @@ public class GrammarBuilder { false, false); if (head.equals("#import")) { - String fileName = path+(String)stringifyChildren(t.child(0)); - try { - String newPrefix = (String)walk(t.child(1)); - if (newPrefix.length() > 0) newPrefix += "."; - FileInputStream fis = new FileInputStream(fileName); - Tree tr = new CharParser(MetaGrammar.newInstance()).parse(fis).expand1(); - return (GrammarNode)new GrammarBuilder(path, newPrefix).walk(tr); - } catch (Exception e) { - throw new RuntimeException("while parsing " + fileName, e); + String fileName = (String)stringifyChildren(t.child(0)); + for(File f : includes) { + File file = new File(f.getAbsolutePath()+File.separatorChar+fileName); + if (!file.exists()) continue; + try { + String newPrefix = t.size()<2 ? "" : ((String)walk(t.child(1))+"."); + FileInputStream fis = new FileInputStream(file); + Tree tr = new CharParser(MetaGrammar.newInstance()).parse(fis).expand1(); + return (GrammarNode)new GrammarBuilder(includes, newPrefix).walk(tr); + } catch (Exception e) { + throw new RuntimeException("while parsing " + file, e); + } } + throw new RuntimeException("unable to find #include file \""+fileName+"\""); } - throw new RuntimeException("unknown head: " + head + "\n"+t); + throw new RuntimeException("unknown head: \"" + head + "\" => " + (head.equals("..."))); } /** A grammar (a set of nonterminals) */ @@ -247,7 +274,7 @@ public class GrammarBuilder { public class NonTerminalNode extends UnionNode { public boolean alwaysDrop; public String name = null; - public boolean drop() { return alwaysDrop; } + public boolean drop(Context cx) { return alwaysDrop; } public NonTerminalNode(String name, Seq[][] sequences, boolean rep, String sep, boolean alwaysDrop) { super(sequences, rep, sep==null?null:(prefix + sep)); this.name = prefix + name; @@ -258,7 +285,7 @@ public class GrammarBuilder { public class Seq { public boolean alwaysDrop = false; - public boolean drop() { return alwaysDrop; } + public boolean drop(Context cx) { return alwaysDrop; } HashSet and = new HashSet(); HashSet not = new HashSet(); ElementNode[] elements; @@ -309,13 +336,10 @@ public class GrammarBuilder { public Sequence build0(Context cx, NonTerminalNode cnt, boolean dropall) { boolean[] drops = new boolean[elements.length]; Element[] els = new Element[elements.length]; - dropall |= drop(); + dropall |= drop(cx); for(int i=0; i 0 && elements[0].lifted) + lift = true; if (!multiNonDrop) { if (idx == -1) ret = tag==null ? Sequence.create(els, illegalTag) - : Sequence.create(tag, els, drops, false); + : Sequence.createLeft(tag, els, drops, lift); else if (tag==null) ret = Sequence.create(els, idx); - else ret = Sequence.create(tag, els, drops, false); + else ret = Sequence.createLeft(tag, els, drops, lift); } if (multiNonDrop) - ret = Sequence.create(tag, els, drops, false); + ret = Sequence.createLeft(tag, els, drops, lift); if (this.follow != null) ret = ret.followedBy(this.follow.toAtom(cx)); return ret; @@ -354,9 +381,14 @@ public class GrammarBuilder { public class ReferenceNode extends ElementNode { public String nonTerminal; public ReferenceNode() { } - public NonTerminalNode resolve(Context cx) { return cx.grammar.get(nonTerminal); } + public NonTerminalNode resolve(Context cx) { + NonTerminalNode ret = cx.grammar.get(nonTerminal); + if (ret==null) throw new RuntimeException("undefined nonterminal: " + nonTerminal); + return ret; + } public ReferenceNode(String nonTerminal) { this.nonTerminal = prefix + nonTerminal; } public Atom toAtom(Context cx) { return cx.grammar.get(nonTerminal).toAtom(cx); } + public boolean drop(Context cx) { return resolve(cx).drop(cx); } public Element build(Context cx, NonTerminalNode cnt, boolean dropall) { if (!this.nonTerminal.startsWith(prefix)) nonTerminal = prefix + nonTerminal; Element ret = cx.get(nonTerminal); @@ -376,7 +408,7 @@ public class GrammarBuilder { } public String getOwnerTag() { return caret ? thePrefix+string : super.getOwnerTag(); } public String toString() { return "\""+string+"\""; } - public boolean drop() { return true; } + public boolean drop(Context cx) { return true; } public Atom toAtom(Context cx) { if (string.length()!=1) return super.toAtom(cx); edu.berkeley.sbp.util.Range.Set set = new edu.berkeley.sbp.util.Range.Set(); @@ -388,6 +420,7 @@ public class GrammarBuilder { public class AtomNode extends ElementNode { AtomNodeRange[] ranges; + public AtomNode() { this(new AtomNodeRange[0]); } public AtomNode(AtomNodeRange[] ranges) { this.ranges = ranges; } public AtomNode(AtomNodeRange range) { this.ranges = new AtomNodeRange[] { range }; } public Element build(Context cx, NonTerminalNode cnt, boolean dropall) { return toAtom(cx); } @@ -406,14 +439,20 @@ public class GrammarBuilder { public class RepeatNode extends ElementNode { public ElementNode e, sep; - public boolean zero, many, max; + public final boolean zero, many, max; public RepeatNode(ElementNode e, ElementNode sep, boolean zero, boolean many, boolean max) { - this.e = e; this.sep = sep; this.zero = zero; this.many = many; this.max = max;} + this.e = e; this.sep = sep; this.zero = zero; this.many = many; this.max = max; + } public Atom toAtom(Context cx) { return sep==null ? e.toAtom(cx) : super.toAtom(cx); } + public boolean drop(Context cx) { return e.drop(cx); } public Element build(Context cx, NonTerminalNode cnt, boolean dropall) { - if (!dropall && !drop() && !e.drop()) - throw new Error("you need a tag on this repetition: " + build(cx, cnt, dropall, "")); - return build(cx, cnt, dropall, illegalTag); + Element ret = build(cx, cnt, dropall, illegalTag); + String must = "must be tagged unless they appear within a dropped expression or their contents are dropped: "; + if (!dropall && !drop(cx) && !e.drop(cx)) + if (!many) throw new RuntimeException("options (?) " + must + ret); + else if (zero) throw new RuntimeException("zero-or-more repetitions (*) " + must + ret); + else throw new RuntimeException("one-or-more repetitions (+) " + must + ret); + return ret; } public Element build(Context cx, NonTerminalNode cnt, boolean dropall, Object repeatTag) { return (!max) @@ -425,8 +464,9 @@ public class GrammarBuilder { } public abstract class ElementNode { + public boolean lifted = false; public String getOwnerTag() { return null; } - public boolean drop() { return false; } + public boolean drop(Context cx) { return false; } public Atom toAtom(Context cx) { throw new Error("can't convert a " + this.getClass().getName() + " to an atom: " + this); } public abstract Element build(Context cx, NonTerminalNode cnt, boolean dropall); } @@ -435,7 +475,7 @@ public class GrammarBuilder { protected ElementNode _e; public ElementNodeWrapper(ElementNode e) { this._e = e; } public String getOwnerTag() { return _e.getOwnerTag(); } - public boolean drop() { return _e.drop(); } + public boolean drop(Context cx) { return _e.drop(cx); } public Atom toAtom(Context cx) { return _e.toAtom(cx); } public Element build(Context cx, NonTerminalNode cnt, boolean dropall) { return _e.build(cx, cnt, dropall); } } @@ -448,7 +488,7 @@ public class GrammarBuilder { public class DropNode extends ElementNodeWrapper { public DropNode(ElementNode e) { super(e); } - public boolean drop() { return true; } + public boolean drop(Context cx) { return true; } } public Seq and2(Seq s, Seq a) { a.alwaysDrop = true; return s.and(a); } @@ -465,7 +505,7 @@ public class GrammarBuilder { public ElementNode star(final ElementNode e) { return new RepeatNode(e, null, true, true, false); } public ElementNode starmaxfollow(final ElementNode e, final ElementNode sep) { return new RepeatNode(e, sep, true, true, true); } public ElementNode starfollow(final ElementNode e, final ElementNode sep) { return new RepeatNode(e, sep, true, true, false); } - public ElementNode question(final ElementNode e) { return new RepeatNode(e, null, true, true, false); } + public ElementNode question(final ElementNode e) { return new RepeatNode(e, null, true, false, false); } ////////////////////////////////////////////////////////////////////////////// @@ -494,29 +534,26 @@ public class GrammarBuilder { } else { ret = new Union(name, false); map.put(name, ret); - nt.buildIntoPreallocatedUnion(this, nt, nt.drop(), ret); + nt.buildIntoPreallocatedUnion(this, nt, nt.drop(this), ret); } return ret; } } - /* - public class XTree extends ElementNode { - public Seq body; + public class XTree extends ElementNode { + public Seq body; + public XTree(Seq seq) { this.body = seq; } public Element build(Context cx, NonTerminalNode cnt, boolean dropall) { Union u = new Union(null, false); Sequence s = body.build(cx, u, null, dropall); Union u2 = new Union(null, false); u2.add(Sequence.create(new Element[] { CharAtom.leftBrace, - cx.get("ws"), u, - cx.get("ws"), CharAtom.rightBrace - }, 2)); + }, 1)); return u2; } } - */ }