public String toString() { return a.toString(); }
}
- public static Union make() throws Exception {
- Meta.MetaGrammarFile mgf = new MetaGrammar.Meta.MetaGrammarFile(meta);
+ public static Union make(Tree<String> tree, String nt) throws Exception {
+ Meta.MetaGrammarFile mgf = new MetaGrammar.Meta.MetaGrammarFile(tree);
BuildContext bc = new BuildContext(mgf);
- return mgf.get("s").build(bc);
+ return mgf.get(nt).build(bc);
+ }
+ public static Union make() throws Exception {
+ return make(meta, "s");
}
+ /*
public String toString() {
StringBuffer ret = new StringBuffer();
for(Union u : nt.values()) u.toString(ret);
return ret.toString();
}
-
+ */
public /*private*/ static HashSet<Element> dropAll = new HashSet<Element>();
public /*private*/ static HashMap<Element,String> carets = new HashMap<Element,String>();
////////////////////////////////////////////////////////////////////////////////
- private Union g;
- private HashMap<String,Union> nt;
- private int anon = 0;
- private String startSymbol;
private static boolean strings;
private static Element set(Range.Set r) { if (strings) throw new Error(); return CharRange.set(r); }
private static Atom leftBrace() { return strings ? StringInput.leftBrace : CharRange.leftBrace; }
private static Atom rightBrace() { return strings ? StringInput.rightBrace : CharRange.rightBrace; }
- public MetaGrammar() { this("s", false); }
- public MetaGrammar(String s) { this(s, false); }
- public MetaGrammar(String s, boolean strings) { this.strings = strings; done(s); throw new Error(); }
- public Union done() { return done("s"); }
- public Union done(String str) {
- Union ret = g;
- g = new Union(str);
- startSymbol = str;
- nt = new HashMap<String,Union>();
- dropAll = new HashSet<Element>();
- dropAll.add(leftBrace());
- dropAll.add(rightBrace());
- nt.put(str, g);
- return ret;
- }
-
-
- // MetaGrammar //////////////////////////////////////////////////////////////////////////////
-
- public Union getNonTerminal(String str) { return nonTerminal(str, null, false, false); }
- private Union nonTerminal(String str) { return nonTerminal(str, null, false, false); }
- public Union anonymousNonTerminal(Sequence[][] s) {
- return nonTerminal("anon"+(anon++), s, false, false);
- }
- private Union nonTerminal(String str, Sequence[][] s, boolean synthetic, boolean dropAll) {
- Union n = str.equals(startSymbol) ? g : nt.get(str);
- if (n == null) nt.put(str, n = new Union(str, synthetic));
- if (dropAll) this.dropAll.add(n);
- if (s==null) return n;
- HashSet<Sequence> seqs = new HashSet<Sequence>();
- for(int i=0; i<s.length; i++) {
- if (s[i]==null) continue;
- HashSet<Sequence> temp = new HashSet<Sequence>();
- for(Sequence pre : s[i]) {
- for(Sequence sn : seqs) pre = pre.not(sn);
- temp.add(pre);
- n.add(pre);
- }
- seqs.addAll(temp);
- }
- //StringBuffer sb = new StringBuffer();
- //n.toString(sb);
- //System.out.println(sb);
- return n;
- }
+ private MetaGrammar() { }
public static String string(Iterable<Tree<String>> children) {
String ret = "";
return ret;
}
- // hack, this doens't really work if you're nesting
- HashSet<Element> keep = new HashSet<Element>();
-
- public Sequence sequence(Object o, boolean lame) {
- return new PreSequence((Element[])Reflection.lub((Object[])o), null).buildSequence(null, lame, false);
- }
-
public static class BuildContext extends HashMap<String,Union> {
private final Meta.MetaGrammarFile mgf;
public BuildContext(Meta.MetaGrammarFile mgf) { this.mgf = mgf; }
public String name;
public MetaUnion rhs;
public MetaNonterminal(Tree<String> tree) {
- System.err.println("MetaNonterminal("+tree+")");
name = string(tree.child(0));
rhs = rhs(tree.child(1));
}
return u;
}
public MetaUnion(Tree<String> t, boolean prioritized) {
- System.err.println("MetaUnion("+t+")");
//System.err.println("metaunion: " + t);
this.prioritized = prioritized;
int i = 0;
}
public static MetaSequence makeMetaSequence(Tree<String> t) {
- System.err.println("MetaSequence("+t+")");
+ //System.err.println("MetaSequence("+t+")");
if ("psx".equals(t.head())) return MetaConjunct.make(t.child(0));
if (t.head().equals("&")) return new MetaAnd(makeMetaSequence(t.child(0)), MetaConjunct.make(t.child(1)), false);
if (t.head().equals("&~")) return new MetaAnd(makeMetaSequence(t.child(0)), MetaConjunct.make(t.child(1)), true);
return ret;
}
private MetaConjunct(Tree<String> t) {
- System.err.println("MetaConjunct("+t+")");
+ //System.err.println("MetaConjunct("+t+")");
elements = new MetaClause[t.numChildren()];
int i = 0; for(Tree<String> tt : t)
elements[i++] = MetaClause.make(tt, this);
return ret;
}
public static MetaConjunct make(Tree<String> t) {
- System.err.println("MetaConjunct.make("+t+")");
+ //System.err.println("MetaConjunct.make("+t+")");
if ("/".equals(t.head())) {
MetaConjunct ret = make(t.child(0));
ret.separator = MetaClause.make(t.child(1), ret);
public boolean lift = false;
public abstract Element build(BuildContext bc);
public static MetaClause make(Tree<String> t, MetaConjunct c) {
- System.err.println("MetaClause.make("+t+")");
+ //System.err.println("MetaClause.make("+t+")");
if (t.head().equals("{")) throw new Error("metatree: " + t);
if (t.head().equals("*")) return new MetaRepeat(make(t.child(0), c), false, null, true, true);
if (t.head().equals("+")) return new MetaRepeat(make(t.child(0), c), false, null, false, true);
}
- public Object walk(Tree<String> tree) {
- String head = tree.head();
- if (tree.numChildren()==0) return super.walk(tree);
- if ("\\n".equals(head)) return new Character('\n');
- else if ("\\r".equals(head)) return new Character('\r');
- else if ("grammar".equals(head)) { for(Tree<String> t : tree.children()) walk(t); return this; }
- else if ("*".equals(head)) return Sequence.many0((Element)walk(tree.child(0)), repeatTag());
- else if ("+".equals(head)) return Sequence.many1((Element)walk(tree.child(0)), repeatTag());
- else if ("+/".equals(head)) return Sequence.many1((Element)walk(tree.child(0)), (Element)walk(tree.child(1)), repeatTag());
- else if ("*/".equals(head)) return Sequence.many0((Element)walk(tree.child(0)), (Element)walk(tree.child(1)), repeatTag());
- else if ("++/".equals(head)) return Sequence.maximal1((Element)walk(tree.child(0)), (Element)walk(tree.child(1)), repeatTag());
- else if ("**".equals(head)) return Sequence.maximal0((Element)walk(tree.child(0)), repeatTag());
- else if ("++".equals(head)) return Sequence.maximal1((Element)walk(tree.child(0)), repeatTag());
- else if ("?".equals(head)) return Sequence.maybe((Element)walk(tree.child(0)), repeatTag());
- else if ("!".equals(head)) { Element e = (Element)walk(tree.child(0)); dropAll.add(e); return e; }
- else if ("&".equals(head)) return ((Sequence)walk(tree,0)).and(sequence(walk(tree, 1), true));
- else if ("and".equals(head)) return ((Sequence)walk(tree,0)).and(sequence(walk(tree, 1), true));
- else if ("&~".equals(head)) return ((Sequence)walk(tree,0)).not(sequence(walk(tree, 1), true));
- else if ("epsilon".equals(head)) return Union.epsilon;
- else if ("()".equals(head)) return Union.epsilon;
- else if (")".equals(head)) return SELF;
- else if ("caret".equals(head) || "^".equals(head)) {
- String s = string(tree.child(0));
- Element ret = CharRange.string(s, false);
- carets.put(ret, s);
- dropAll.add(ret);
- return ret;
- /*
- } else if ("^^".equals(head)) {
- return new Keep(walk(tree,0));
- */
- } else if ("psx".equals(head)) return ((PreSequence)walk(tree, 0)).buildSequence();
- else if ("nonTerminal".equals(head)) return getNonTerminal(string(tree.child(0)));
- else if ("::=".equals(head)) return nonTerminal(string(tree.child(0)), (Sequence[][])Reflection.lub(walk(tree, 1)), false, false);
- else if ("=".equals(head)) return nonTerminal(string(tree.child(0)), (Sequence[][])Reflection.lub(walk(tree, 1)), false, false);
- else if ("(".equals(head)) return buildUnion((Sequence[][])Reflection.lub(walk(tree, 0)));
- else if ("literal".equals(head)) { Element ret = string(string(tree.child(0))); dropAll.add(ret); return ret; }
- else if ("-".equals(head)) return new Range(walk(tree, 0).toString().charAt(0), walk(tree,1).toString().charAt(0));
- else if ("range".equals(head)) return new Range(walk(tree, 0).toString().charAt(0), walk(tree,0).toString().charAt(0));
- else if ("gram".equals(head)) return walk(tree, 0);
- else if ("psy".equals(head)) return (PreSequence)walk(tree, 0);
- else if ("->".equals(head)) { PreSequence p = (PreSequence)walk(tree, 0); p.follow = (Element)walk(tree, 1); return p; }
- else if ("/".equals(head)) return ((PreSequence)walk(tree, 0)).sparse((Element)walk(tree, 1));
- else if (" /".equals(head)) return ((PreSequence)walk(tree, 0)).sparse((Element)walk(tree, 1));
- else if ("~".equals(head)) return new Hack(new Invert(new Infer((Element)walk(tree, 0))));
- else if ("ps".equals(head)) return new PreSequence((Object[])walk(tree,0), null);
- else if (":".equals(head)) {
- String s = string(tree.child(0));
- return new Keep(s,walk(tree,1));
- } else if ("::".equals(head)) {
- PreSequence p = (PreSequence)walk(tree, 1);
- String s = string(tree.child(0));
- if (s.equals("[]")) p.unwrap = true;
- else p.tag = convertLabel(s);
- return p;
- }
- else if ("=>".equals(head)) {
- PreSequence p = (PreSequence)walk(tree, 0);
- p.tag = string(tree.child(1));
- return p;
- }
- else if ("[".equals(head)) {
- Range[] rr = (Range[])walk(tree, 0);
- Range.Set ret = new Range.Set();
- if (rr!=null) for(Range r : rr) ret.add(r);
- return set(ret);
- }
- else return super.walk(tree);
- }
-
- static class Keep {
- public final String label;
- public final Object o;
- public Keep(String label, Object o) { this.label = label; this.o = o; }
- }
-
- public Object convertLabel(String label) { return label; }
- public Object repeatTag() { return null; }
-
- public Object walk(String tag, Object[] argo) {
- if (argo.length==0) return super.walk(tag, argo);
- if (argo==null) return tag;
- if (tag==null || "".equals(tag)) return argo;
- return super.walk(tag, argo);
- }
-
- public Union buildUnion(Sequence[][] p) {
- return anonymousNonTerminal(p);
- }
-
- //////////////////////////////////////////////////////////////////////////////
-
- public class PreSequence {
- public Element follow = null;
- public final HashSet<Sequence> and = new HashSet<Sequence>();
- public final HashSet<Sequence> not = new HashSet<Sequence>();
- public /*final*/ Object tag;
- public final Object[] o;
-
- public PreSequence sparse(Object e) {
- Object[] ret;
- boolean[] drops;
- if (o.length <= 1) {
- ret = o;
- drops = new boolean[this.drops.length];
- System.arraycopy(this.drops, 0, drops, 0, this.drops.length);
- } else {
- ret = new Object[o.length * 2 - 1];
- drops = new boolean[o.length * 2 - 1];
- for(int i=0; i<o.length; i++) {
- Object oi = o[i];
- ret[i*2] = oi;
- drops[i*2] = this.drops[i];
- if (i*2+1<ret.length) {
- ret[i*2+1] = e;
- drops[i*2+1] = true;
- }
- }
- }
- PreSequence p = new PreSequence(ret, tag, drops);
- p.not.addAll(not);
- p.and.addAll(and);
- return p;
- }
-
- public PreSequence not(Sequence s) { not.add(s); return this; }
- public PreSequence and(Sequence s) { and.add(s); return this; }
-
- boolean[] drops = null;
- public PreSequence(Object o) { this(new Object[] { o }, null); }
- public PreSequence(Object[] o) { this(o, null); }
- public PreSequence(Object[] o, Object tag) { this(o, tag, null); }
- public PreSequence(Object[] o, Object tag, boolean[] drops) {
- this.o = o;
- this.tag = tag;
- this.drops = drops==null ? new boolean[o.length] : drops;
- }
-
- public Union buildUnion(String s) {
- Union u = new Union(s);
- u.add(buildSequence(u));
- return u;
- }
- public Union buildUnion() { return buildUnion("???"); }
- public boolean unwrap = false;
- public Sequence buildSequence() { return buildSequence(null, false, false); }
- public Sequence buildSequence(Union u) { return buildSequence(u, false, false); }
- public Sequence buildSequence(Union u, boolean lame, Object tag) {
- this.tag = tag;
- return buildSequence(u, lame, false);
- }
- public Sequence buildSequence(Union u, boolean lame, boolean dropAll) {
- if (tag!=null && tag.equals("[]")) unwrap = true;
- if (tag!=null && "()".equals(tag)) dropAll=true;
- if (u!=null) {
- for(Sequence s : and) u.add(s);
- for(Sequence s : not) u.add(s);
- }
- HashSet<Sequence> set = new HashSet<Sequence>();
- Element[] o2 = o==null ? new Element[0] : new Element[o.length];
- Object[] labels = new Object[drops.length];
- int nonDrop = 0;
- boolean keeping = false;
- if (o != null) {
- int j = 0;
- for(int i=0; i<o.length; i++) {
- Object oi = o[i];
- if (oi instanceof Keep) {
- if (!unwrap && tag==null) throw new Error("cannot have labels in an untagged sequence: " + ((Keep)oi).label);
- if (!keeping) { for(int k=0; k<i; k++) drops[k]=true; }
- drops[i] = false;
- keeping = true;
- labels[i] = ((Keep)oi).label;
- oi = ((Keep)oi).o;
- } else {
- if (keeping) drops[i] = true;
- }
- /*if (oi==SELF) o2[j] = u.new Subset("(("+u+"))", set);
- else*/ o2[j] = (Element)oi;
-
- if (MetaGrammar.dropAll.contains(o2[j])) drops[j] = true;
- nonDrop += drops[j] ? 0 : 1;
- o2[j] = o2[j];
- String s = carets.get(o2[j]);
- if (s!=null) { tag = s; if (o.length==1) drops[j] = false; }
- j++;
- }
- }
- Element[] expansion = o2;
- Sequence ret = null;
- if (dropAll || lame) ret = Sequence.drop(expansion, lame);
- else if (unwrap) ret = Sequence.unwrap(expansion, repeatTag(), drops);
- else if (keeping || tag!=null) ret = Sequence.rewritingSequence(tag, expansion, labels, drops);
- else {
- int idx = -1;
- for(int i=0; i<expansion.length; i++)
- if (!drops[i])
- if (idx==-1) idx = i;
- else throw new Error("multiple non-dropped elements in sequence: " + Sequence.drop(expansion,false));
- if (idx != -1) ret = Sequence.singleton(expansion, idx);
- else ret = Sequence.drop(expansion, false);
- }
- for(Sequence s : and) ret = ret.and(s);
- for(Sequence s : not) ret = ret.not(s);
- set.add(ret);
- if (this.follow != null) ret.follow = new Infer(this.follow);
- return ret;
- }
- }
-
public static void main(String[] args) throws Exception {
if (args.length != 2) {
System.err.println("usage: java " + MetaGrammar.class.getName() + " grammarfile.g com.yourdomain.package.ClassName");
out.append("\n // DO NOT EDIT STUFF BELOW: IT IS AUTOMATICALLY GENERATED\n");
Tree<String> ts = new CharParser(MetaGrammar.make()).parse(new FileInputStream(args[0])).expand1();
- Meta.MetaGrammarFile mgf = new MetaGrammar.Meta.MetaGrammarFile(ts);
- BuildContext bc = new BuildContext(mgf);
- for(Meta.MetaNonterminal nt : mgf.values()) {
- StringBuffer sb = new StringBuffer();
- nt.build(bc).toString(sb);
- System.err.println(sb);
- }
-
- Forest<String> fs = new CharParser(mgf.get("s").build(new BuildContext(mgf))).parse(new FileInputStream(args[0]));
+ Forest<String> fs = new CharParser(make()).parse(new FileInputStream(args[0]));
System.out.println(fs.expand1());
+
//GraphViz gv = new GraphViz();
//fs.toGraphViz(gv);
//FileOutputStream fox = new FileOutputStream("out.dot");