From: adam <adam@megacz.com>
Date: Fri, 20 Apr 2007 03:25:02 +0000 (-0400)
Subject: support for left recursion and ellipses in GrammarBuilder
X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=65c42fc8ec481eb1305a1f6bc005737b0870bc91

support for left recursion and ellipses in GrammarBuilder

darcs-hash:20070420032502-5007d-4a67291626cbd1024fc82bdb1b37300a3577de8c.gz
---

diff --git a/src/edu/berkeley/sbp/meta/GrammarBuilder.java b/src/edu/berkeley/sbp/meta/GrammarBuilder.java
index b3f4941..f38bd8e 100644
--- a/src/edu/berkeley/sbp/meta/GrammarBuilder.java
+++ b/src/edu/berkeley/sbp/meta/GrammarBuilder.java
@@ -85,7 +85,9 @@ public class GrammarBuilder {
 
     public Object walk(Tree t) {
         String head = (String)t.head();
-        while(head.indexOf('.') != -1) head = head.substring(head.indexOf('.')+1);
+        if (head.indexOf('.') != 0)
+            while(head.indexOf('.') != -1)
+                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);
@@ -98,6 +100,7 @@ public class GrammarBuilder {
         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)));
@@ -108,6 +111,11 @@ 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)));
@@ -153,8 +161,7 @@ public class GrammarBuilder {
                 File file = new File(f.getAbsolutePath()+File.separatorChar+fileName);
                 if (!file.exists()) continue;
                 try {
-                    String newPrefix = (String)walk(t.child(1));
-                    if (newPrefix.length() > 0) newPrefix += ".";
+                    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);
@@ -164,7 +171,7 @@ public class GrammarBuilder {
             }
             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) */
@@ -349,16 +356,19 @@ public class GrammarBuilder {
             }
             if (tag==null && multiNonDrop)
                 throw new RuntimeException("multiple non-dropped elements in sequence: " + Sequence.create(els, ""));
+            boolean lift = false;
+            if (elements.length > 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;
@@ -368,7 +378,11 @@ 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); }
@@ -403,6 +417,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); }
@@ -446,6 +461,7 @@ public class GrammarBuilder {
     }
 
     public abstract class ElementNode {
+        public boolean lifted = false;
         public String getOwnerTag() { return null; }
         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); }
@@ -531,11 +547,9 @@ public class GrammarBuilder {
             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;
         }
     }