From: adam <adam@megacz.com>
Date: Sat, 8 Sep 2007 22:30:38 +0000 (-0400)
Subject: add slow epsilon-ness checker as static method in Element
X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=fcc038ff693cf2b3e91efcd348ea3a3b7fbb1829

add slow epsilon-ness checker as static method in Element

darcs-hash:20070908223038-5007d-59282544c4bc9844150b5a66c9074754a3e4b875.gz
---

diff --git a/src/edu/berkeley/sbp/Element.java b/src/edu/berkeley/sbp/Element.java
index 27a3ee6..a37e960 100644
--- a/src/edu/berkeley/sbp/Element.java
+++ b/src/edu/berkeley/sbp/Element.java
@@ -17,4 +17,30 @@ public abstract class Element implements SequenceOrElement {
     /** a more verbose version of toString() for displaying whole grammars */
     abstract StringBuffer toString(StringBuffer sb);
 
+    /** a slow and inefficient epsilon-ness checker used when constructing parse trees (see Union.epsilonForm()) */
+    public static boolean possiblyEpsilon(SequenceOrElement e) {
+        if (e instanceof Atom) return false;
+        if (e instanceof Sequence) {
+            Sequence s = (Sequence)e;
+            for(Sequence.Pos p = s.firstp(); !p.isLast(); p = p.next())
+                if (!possiblyEpsilon(p.element()))
+                    return false;
+            return true;
+        }
+        if (e instanceof Union) {
+            Union u = (Union)e;
+            if (u.visiting) return true;
+            try {
+                u.visiting = true;
+                for(Sequence s : u)
+                    if (possiblyEpsilon(s))
+                        return true;
+                return false;
+            } finally {
+                u.visiting = false;
+            }
+        }
+        throw new Error();
+    }
+    boolean visiting = false;
 }