1 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
3 package edu.berkeley.sbp.meta;
4 import edu.berkeley.sbp.util.*;
5 import edu.berkeley.sbp.*;
6 import edu.berkeley.sbp.chr.*;
7 import edu.berkeley.sbp.misc.*;
9 import java.lang.annotation.*;
10 import java.lang.reflect.*;
14 * The inner classes of this class represent nodes in the Abstract
15 * Syntax Tree of a grammar.
17 public class GrammarAST {
20 * Create a grammar from a parse tree and binding resolver
22 * @param t a tree produced by parsing a grammar using the metagrammar
23 * @param s the name of the "start symbol"
24 * @param gbr a GrammarBindingResolver that resolves grammatical reductions into tree-node-heads
26 public static Union buildFromAST(Tree grammarAST, String startingNonterminal, File[] includes) {
27 return new GrammarAST(includes, "").buildGrammar(grammarAST, startingNonterminal);
30 public static Object illegalTag = ""; // this is the tag that should never appear in the non-dropped output FIXME
32 private final String prefix;
33 private final File[] includes;
35 public GrammarAST(File[] includes, String prefix) {
37 this.includes = includes;
40 // Methods //////////////////////////////////////////////////////////////////////////////
42 private Union buildGrammar(Tree t, String rootNonTerminal) {
43 return ((GrammarAST.GrammarNode)walk(t)).build(rootNonTerminal);
46 public Object[] walkChildren(Tree t) {
47 Object[] ret = new Object[t.size()];
48 for(int i=0; i<ret.length; i++) {
49 ret[i] = walk(t.child(i));
50 if (ret[i] instanceof Object[])
51 ret[i] = Reflection.lub((Object[])ret[i]);
53 return Reflection.lub(ret);
55 public String stringifyChildren(Tree t) {
56 StringBuffer sb = new StringBuffer();
57 for(int i=0; i<t.size(); i++) {
58 sb.append(t.child(i).head());
59 sb.append(stringifyChildren(t.child(i)));
63 public String unescape(Tree t) {
64 StringBuffer sb = new StringBuffer();
65 for(int i=0; i<t.size(); i++)
66 sb.append(t.child(i).head()+stringifyChildren(t.child(i)));
70 public Object walk(Tree t) {
71 String head = (String)t.head();
72 while(head.indexOf('.') > 0)
73 head = head.substring(head.indexOf('.')+1);
74 if (head==null) throw new RuntimeException("head is null: " + t);
75 if (head.equals("|")) return walkChildren(t);
76 if (head.equals("RHS")) return walkChildren(t);
77 if (head.equals("Grammar")) return new GrammarNode(walkChildren(t));
78 if (head.equals("(")) return new UnionNode((Seq[][])walkChildren(t.child(0)));
79 if (head.equals("Word")) return stringifyChildren(t);
80 if (head.equals("Elements")) return seq2((ElementNode[])Reflection.rebuild(walkChildren(t), ElementNode[].class));
81 if (head.equals("NonTerminalReference")) return new ReferenceNode(stringifyChildren(t.child(0)));
82 //if (head.equals(")")) return new ReferenceNode(stringifyChildren(t.child(0)));
83 if (head.equals("{")) return new XTree((Seq)walk(t.child(0)));
84 if (head.equals("::")) return tag((String)walk(t.child(0)), (Seq)walk(t.child(1)));
85 if (head.equals("++")) return plusmax((ElementNode)walk(t.child(0)));
86 if (head.equals("...")) return star(new TildeNode(new AtomNode()));
87 if (head.equals("+")) return plus((ElementNode)walk(t.child(0)));
88 if (head.equals("++/")) return plusmaxfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1)));
89 if (head.equals("+/")) return plusfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1)));
90 if (head.equals("**")) return starmax((ElementNode)walk(t.child(0)));
91 if (head.equals("*")) return star((ElementNode)walk(t.child(0)));
92 if (head.equals("**/")) return starmaxfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1)));
93 if (head.equals("*/")) return starfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1)));
94 if (head.equals("?")) return question((ElementNode)walk(t.child(0)));
95 if (head.equals("!")) return new DropNode((ElementNode)walk(t.child(0)));
96 if (head.equals("^")) return new LiteralNode((String)walk(t.child(0)), true);
97 if (head.equals("`")) {
98 ElementNode ret = (ElementNode)walk(t.child(0));
102 if (head.equals("Quoted")) return stringifyChildren(t);
103 if (head.equals("Literal")) return new LiteralNode(walkString(t.child(0)));
104 if (head.equals("->")) return walkSeq(t.child(0)).follow(walkElement(t.child(1)));
105 if (head.equals("DropNT")) return new NonTerminalNode(walkString(t.child(0)), (Seq[][])walkChildren(t.child(1)), false, null, true);
106 if (head.equals("=")) return new NonTerminalNode(walkString(t.child(0)), (Seq[][])walk(t.child(2)),
107 true, t.size()==2 ? null : walkString(t.child(1)), false);
108 if (head.equals("&")) return and2(walkSeq(t.child(0)), walkSeq(t.child(1)));
109 if (head.equals("&~")) return andnot2(walkSeq(t.child(0)), walkSeq(t.child(1)));
110 if (head.equals("/")) return (walkSeq(t.child(0))).separate(walkElement(t.child(1)));
111 if (head.equals("()")) return new LiteralNode("");
112 if (head.equals("[")) return new AtomNode((char[][])Reflection.rebuild(walkChildren(t), char[][].class));
113 if (head.equals("\\{")) return new DropNode(new AtomNode(new char[] { CharAtom.left, CharAtom.left }));
114 if (head.equals("\\}")) return new DropNode(new AtomNode(new char[] { CharAtom.right, CharAtom.right }));
115 if (head.equals(">>")) return new DropNode(new AtomNode(new char[] { CharAtom.left, CharAtom.left }));
116 if (head.equals("<<")) return new DropNode(new AtomNode(new char[] { CharAtom.right, CharAtom.right }));
117 if (head.equals("~")) return new TildeNode(walkElement(t.child(0)));
118 if (head.equals("~~")) return new Seq(new RepeatNode(new TildeNode(new AtomNode()), null, true, true, false)).andnot(walkSeq(t.child(0)));
119 if (head.equals("Range") && t.size()==2 && ">".equals(t.child(0).head()))
120 return new char[] { CharAtom.left, CharAtom.left };
121 if (head.equals("Range") && t.size()==2 && "<".equals(t.child(0).head()))
122 return new char[] { CharAtom.right, CharAtom.right };
123 if (head.equals("Range") && t.size()==1) return new char[] { unescape(t).charAt(0), unescape(t).charAt(0) };
124 if (head.equals("Range")) return new char[] { unescape(t).charAt(0), unescape(t).charAt(1) };
125 if (head.equals("\"\"")) return "";
126 if (head.equals("\n")) return "\n";
127 if (head.equals("\r")) return "\r";
128 if (head.equals("grammar.Grammar")) return walkChildren(t);
129 if (head.equals("SubGrammar")) return GrammarBuilder.buildFromAST(t.child(0), "s", includes);
130 if (head.equals("NonTerminal"))
131 return new NonTerminalNode((String)walk(t.child(0)),
132 (Seq[][])walkChildren(t.child(1)), false, null, false);
133 if (head.equals("Colons")) {
134 String tag = (String)walk(t.child(0));
135 Seq[][] seqs = (Seq[][])walk(t.child(1));
136 for(Seq[] seq : seqs)
137 for(int i=0; i<seq.length; i++)
138 seq[i] = tag(tag, seq[i]);
139 return new NonTerminalNode(tag, seqs, false, null, false);
141 if (head.equals("TestCase"))
142 return new RegressionTests.TestCase(walkString(t.child(0)),
143 walkString(t.child(1)),
144 (String[])Reflection.coerce(walkChildren(t.child(2)), String[].class),
145 (Union)walk(t.child(3)),
148 if (head.equals("#import")) {
149 String fileName = (String)stringifyChildren(t.child(0));
150 for(File f : includes) {
151 File file = new File(f.getAbsolutePath()+File.separatorChar+fileName);
152 if (!file.exists()) continue;
154 String newPrefix = t.size()<2 ? "" : ((String)walk(t.child(1))+".");
155 FileInputStream fis = new FileInputStream(file);
156 Tree tr = new CharParser(MetaGrammar.newInstance()).parse(fis).expand1();
157 return (GrammarNode)new GrammarBuilder(includes, newPrefix).walk(tr);
158 } catch (Exception e) {
159 throw new RuntimeException("while parsing " + file, e);
162 throw new RuntimeException("unable to find #include file \""+fileName+"\"");
164 throw new RuntimeException("unknown head: \"" + head + "\" => " + (head.equals("...")));
167 // Nodes //////////////////////////////////////////////////////////////////////////////
169 /** Root node of a grammar's AST; a set of named nonterminals */
170 private class GrammarNode extends HashMap<String,NonTerminalNode> {
171 public GrammarNode(NonTerminalNode[] nonterminals) {
172 for(NonTerminalNode nt : nonterminals) {
173 if (nt==null) continue;
174 if (this.get(nt.name)!=null)
175 throw new RuntimeException("duplicate definition of nonterminal \""+nt.name+"\"");
176 this.put(nt.name, nt);
179 public GrammarNode(Object[] nt) { add(nt); }
180 private void add(Object o) {
182 else if (o instanceof Object[]) for(Object o2 : (Object[])o) add(o2);
183 else if (o instanceof NonTerminalNode) {
184 NonTerminalNode nt = (NonTerminalNode)o;
185 if (this.get(nt.name)!=null)
186 throw new RuntimeException("duplicate definition of nonterminal \""+nt.name+"\"");
187 this.put(nt.name, nt);
189 else if (o instanceof GrammarNode)
190 for(NonTerminalNode n : ((GrammarNode)o).values())
193 public String toString() {
195 for(NonTerminalNode nt : values()) ret += nt + ", ";
198 public Union build(String rootNonterminal) {
199 Context cx = new Context(this);
201 for(GrammarBuilder.NonTerminalNode nt : values())
202 if (nt.name.equals(rootNonterminal))
203 return (Union)cx.get(nt.name);
208 public class UnionNode extends ElementNode {
209 public Seq[][] sequences;
210 public String sep = null;
212 public UnionNode(Seq[][] sequences) { this(sequences, false, null); }
213 public UnionNode(Seq[][] sequences, boolean rep, String sep) {
214 this.sequences = sequences;
218 public Atom toAtom(Context cx) {
220 for(Seq[] ss : sequences)
222 ret = ret==null ? s.toAtom(cx) : (Atom)ret.union(s.toAtom(cx));
225 public Element build(Context cx, NonTerminalNode cnt, boolean dropall) {
226 return buildIntoPreallocatedUnion(cx, cnt, dropall, new Union(null, false)); }
227 public Element buildIntoPreallocatedUnion(Context cx, NonTerminalNode cnt, boolean dropall, Union u) {
230 urep = new Union(null, false);
231 urep.add(Sequence.create(new Element[0], cnt.name));
233 ? Sequence.create(new Element[] { u }, 0)
234 : Sequence.create(new Element[] { cx.get(sep), u }, 1));
236 HashSet<Sequence> bad2 = new HashSet<Sequence>();
237 for(int i=0; i<sequences.length; i++) {
238 Seq[] group = sequences[i];
239 Union u2 = new Union(null, false);
240 if (sequences.length==1) u2 = u;
241 for(int j=0; j<group.length; j++)
243 group[j].build(cx, u2, cnt, dropall);
245 Union u3 = new Union(null, false);
246 group[j].build(cx, u3, cnt, dropall);
247 Sequence s = Sequence.create(cnt.name,
248 new Element[] { u3, urep },
249 new boolean[] { false, false },
253 if (sequences.length==1) break;
254 Sequence seq = Sequence.create(u2);
255 for(Sequence s : bad2) seq = seq.andnot(s);
257 bad2.add(Sequence.create(u2));
263 public class NonTerminalNode extends UnionNode {
264 public boolean alwaysDrop;
265 public String name = null;
266 public boolean drop(Context cx) { return alwaysDrop; }
267 public NonTerminalNode(String name, Seq[][] sequences, boolean rep, String sep, boolean alwaysDrop) {
268 super(sequences, rep, sep==null?null:(prefix + sep));
269 this.name = prefix + name;
270 this.alwaysDrop = alwaysDrop;
272 public Element build(Context cx, NonTerminalNode cnt, boolean dropall) { return cx.get(name); }
276 public boolean alwaysDrop = false;
277 public boolean drop(Context cx) { return alwaysDrop; }
278 HashSet<Seq> and = new HashSet<Seq>();
279 HashSet<Seq> not = new HashSet<Seq>();
280 ElementNode[] elements;
283 public Seq(ElementNode e) { this(new ElementNode[] { e }); }
284 public Seq(ElementNode[] elements) {
285 this.elements = elements;
286 for(int i=0; i<elements.length; i++)
287 if (elements[i]==null)
288 throw new RuntimeException();
290 public Atom toAtom(Context cx) {
291 if (elements.length != 1)
292 throw new Error("you attempted to use ->, **, ++, or a similar character-class"+
293 " operator on a [potentially] multicharacter production");
294 return elements[0].toAtom(cx);
296 public Seq tag(String tag) { this.tag = tag; return this; }
297 public Seq follow(ElementNode follow) { this.follow = follow; return this; }
298 public Seq and(Seq s) { and.add(s); return this; }
299 public Seq andnot(Seq s) { not.add(s); return this; }
301 Seq ret = new Seq(elements);
308 public Seq separate(ElementNode sep) {
309 ElementNode[] elements = new ElementNode[this.elements.length * 2 - 1];
310 for(int i=0; i<this.elements.length; i++) {
311 elements[i*2] = this.elements[i];
312 if (i<this.elements.length-1)
313 elements[i*2+1] = new DropNode(sep);
315 this.elements = elements;
318 public Sequence build(Context cx, Union u, NonTerminalNode cnt, boolean dropall) {
319 Sequence ret = build0(cx, cnt, dropall);
320 for(Seq s : and) ret = ret.and(s.build(cx, null, cnt, true));
321 for(Seq s : not) ret = ret.andnot(s.build(cx, null, cnt, true));
322 if (u!=null) u.add(ret);
325 public Sequence build0(Context cx, NonTerminalNode cnt, boolean dropall) {
326 boolean[] drops = new boolean[elements.length];
327 Element[] els = new Element[elements.length];
329 for(int i=0; i<elements.length; i++) {
330 if (dropall) drops[i] = true;
331 else drops[i] = elements[i].drop(cx);
332 if (elements[i].getOwnerTag() != null)
333 tag = elements[i].getOwnerTag();
337 boolean multiNonDrop = false;
338 for(int i=0; i<drops.length; i++)
340 if (idx==-1) idx = i;
341 else multiNonDrop = true;
342 for(int i=0; i<elements.length; i++) {
343 if (!multiNonDrop && i==idx && tag!=null && elements[i] instanceof RepeatNode) {
344 els[i] = ((RepeatNode)elements[i]).build(cx, cnt, dropall, tag);
347 els[i] = elements[i].build(cx, cnt, dropall);
349 if (tag==null && multiNonDrop)
350 throw new RuntimeException("multiple non-dropped elements in sequence: " + Sequence.create(els, ""));
351 boolean lift = false;
352 if (elements.length > 0 && elements[0].lifted)
357 ? Sequence.create(els, illegalTag)
358 : Sequence.createLeft(tag, els, drops, lift);
359 else if (tag==null) ret = Sequence.create(els, idx);
360 else ret = Sequence.createLeft(tag, els, drops, lift);
363 ret = Sequence.createLeft(tag, els, drops, lift);
364 if (this.follow != null)
365 ret = ret.followedBy(this.follow.toAtom(cx));
370 public class ReferenceNode extends ElementNode {
371 public String nonTerminal;
372 public ReferenceNode() { }
373 public NonTerminalNode resolve(Context cx) {
374 NonTerminalNode ret = cx.grammar.get(nonTerminal);
375 if (ret==null) throw new RuntimeException("undefined nonterminal: " + nonTerminal);
378 public ReferenceNode(String nonTerminal) { this.nonTerminal = prefix + nonTerminal; }
379 public Atom toAtom(Context cx) { return cx.grammar.get(nonTerminal).toAtom(cx); }
380 public boolean drop(Context cx) { return resolve(cx).drop(cx); }
381 public Element build(Context cx, NonTerminalNode cnt, boolean dropall) {
382 if (!this.nonTerminal.startsWith(prefix)) nonTerminal = prefix + nonTerminal;
383 Element ret = cx.get(nonTerminal);
384 if (ret == null) throw new RuntimeException("unknown nonterminal \""+nonTerminal+"\"");
389 public class LiteralNode extends ElementNode {
390 private String string;
391 private final String thePrefix = prefix;
392 private boolean caret;
393 public LiteralNode(String string) { this(string, false); }
394 public LiteralNode(String string, boolean caret) {
395 this.string = string;
398 public String getOwnerTag() { return caret ? thePrefix+string : super.getOwnerTag(); }
399 public String toString() { return "\""+string+"\""; }
400 public boolean drop(Context cx) { return true; }
401 public Atom toAtom(Context cx) {
402 if (string.length()!=1) return super.toAtom(cx);
403 edu.berkeley.sbp.util.Range.Set set = new edu.berkeley.sbp.util.Range.Set();
404 set.add(string.charAt(0), string.charAt(0));
405 return CharAtom.set(set);
407 public Element build(Context cx, NonTerminalNode cnt, boolean dropall) { return CharAtom.string(string); }
410 public class AtomNode extends ElementNode {
411 AtomNodeRange[] ranges;
412 public AtomNode() { this(new AtomNodeRange[0]); }
413 public AtomNode(AtomNodeRange[] ranges) { this.ranges = ranges; }
414 public AtomNode(AtomNodeRange range) { this.ranges = new AtomNodeRange[] { range }; }
415 public Element build(Context cx, NonTerminalNode cnt, boolean dropall) { return toAtom(cx); }
416 public Atom toAtom(Context cx) {
417 edu.berkeley.sbp.util.Range.Set set = new edu.berkeley.sbp.util.Range.Set();
418 for(AtomNodeRange r : ranges) set.add(r.first, r.last);
419 return CharAtom.set(set);
422 public class AtomNodeRange {
425 public AtomNodeRange(char only) { first = only; last = only; }
426 public AtomNodeRange(char first, char last) { this.first = first; this.last = last; }
429 public class RepeatNode extends ElementNode {
430 public ElementNode e, sep;
431 public final boolean zero, many, max;
432 public RepeatNode(ElementNode e, ElementNode sep, boolean zero, boolean many, boolean max) {
433 this.e = e; this.sep = sep; this.zero = zero; this.many = many; this.max = max;
435 public Atom toAtom(Context cx) { return sep==null ? e.toAtom(cx) : super.toAtom(cx); }
436 public boolean drop(Context cx) { return e.drop(cx); }
437 public Element build(Context cx, NonTerminalNode cnt, boolean dropall) {
438 Element ret = build(cx, cnt, dropall, illegalTag);
439 String must = "must be tagged unless they appear within a dropped expression or their contents are dropped: ";
440 if (!dropall && !drop(cx) && !e.drop(cx))
441 if (!many) throw new RuntimeException("options (?) " + must + ret);
442 else if (zero) throw new RuntimeException("zero-or-more repetitions (*) " + must + ret);
443 else throw new RuntimeException("one-or-more repetitions (+) " + must + ret);
446 public Element build(Context cx, NonTerminalNode cnt, boolean dropall, Object repeatTag) {
448 ? Repeat.repeat(e.build(cx, null, dropall), zero, many, sep==null ? null : sep.build(cx, null, dropall), repeatTag)
450 ? Repeat.repeatMaximal(e.toAtom(cx), zero, many, repeatTag)
451 : Repeat.repeatMaximal(e.build(cx, null, dropall), zero, many, sep.toAtom(cx), repeatTag);
455 public abstract class ElementNode {
456 public boolean lifted = false;
457 public String getOwnerTag() { return null; }
458 public boolean drop(Context cx) { return false; }
459 public Atom toAtom(Context cx) { throw new Error("can't convert a " + this.getClass().getName() + " to an atom: " + this); }
460 public abstract Element build(Context cx, NonTerminalNode cnt, boolean dropall);
463 public abstract class ElementNodeWrapper extends ElementNode {
464 protected ElementNode _e;
465 public ElementNodeWrapper(ElementNode e) { this._e = e; }
466 public String getOwnerTag() { return _e.getOwnerTag(); }
467 public boolean drop(Context cx) { return _e.drop(cx); }
468 public Atom toAtom(Context cx) { return _e.toAtom(cx); }
469 public Element build(Context cx, NonTerminalNode cnt, boolean dropall) { return _e.build(cx, cnt, dropall); }
472 public class TildeNode extends ElementNodeWrapper {
473 public TildeNode(ElementNode e) { super(e); }
474 public Atom toAtom(Context cx) { return (Atom)((Topology<Character>)_e.toAtom(cx).complement()); }
475 public Element build(Context cx, NonTerminalNode cnt, boolean dropall) { return toAtom(cx); }
478 public class DropNode extends ElementNodeWrapper {
479 public DropNode(ElementNode e) { super(e); }
480 public boolean drop(Context cx) { return true; }
483 public Seq and2(Seq s, Seq a) { a.alwaysDrop = true; return s.and(a); }
484 public Seq andnot2(Seq s, Seq a) { a.alwaysDrop = true; return s.andnot(a); }
485 public Seq arrow(Seq s, ElementNode e) { return s.follow(e); }
486 public Seq tag(String tagname, Seq s) { return s.tag(tagname); }
487 public Seq seq(ElementNode[] elements) { return new Seq(elements); }
488 public Seq seq2(ElementNode[] elements) { return new Seq(elements); }
489 public ElementNode plusmax(final ElementNode e) { return new RepeatNode(e, null, false, true, true); }
490 public ElementNode plus(final ElementNode e) { return new RepeatNode(e, null, false, true, false); }
491 public ElementNode plusmaxfollow(final ElementNode e, final ElementNode sep) { return new RepeatNode(e, sep, false, true, true); }
492 public ElementNode plusfollow(final ElementNode e, final ElementNode sep) { return new RepeatNode(e, sep, false, true, false); }
493 public ElementNode starmax(final ElementNode e) { return new RepeatNode(e, null, true, true, true); }
494 public ElementNode star(final ElementNode e) { return new RepeatNode(e, null, true, true, false); }
495 public ElementNode starmaxfollow(final ElementNode e, final ElementNode sep) { return new RepeatNode(e, sep, true, true, true); }
496 public ElementNode starfollow(final ElementNode e, final ElementNode sep) { return new RepeatNode(e, sep, true, true, false); }
497 public ElementNode question(final ElementNode e) { return new RepeatNode(e, null, true, false, false); }
499 //////////////////////////////////////////////////////////////////////////////
501 public class Context {
502 public HashMap<String,Union> map = new HashMap<String,Union>();
503 public GrammarNode grammar;
504 public Context(Tree t) { }
505 public Context(GrammarNode g) { this.grammar = g; }
506 public Union build() {
508 for(NonTerminalNode nt : grammar.values()) {
509 Union u = get(nt.name);
510 if ("s".equals(nt.name))
515 public Union peek(String name) { return map.get(name); }
516 public void put(String name, Union u) { map.put(name, u); }
517 public Union get(String name) {
518 Union ret = map.get(name);
519 if (ret != null) return ret;
520 NonTerminalNode nt = grammar.get(name);
522 throw new Error("warning could not find " + name);
524 ret = new Union(name, false);
526 nt.buildIntoPreallocatedUnion(this, nt, nt.drop(this), ret);