X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FElement.java;h=a37e96036d65206b6be4f5e56c9970ef168f2d0b;hp=4ccde61eb49ecb9cf23c164c9f013cb5c7c8a0ce;hb=fcc038ff693cf2b3e91efcd348ea3a3b7fbb1829;hpb=0e17670bcfa7b0fe8eb3a2cac81f4b080a09fc98

diff --git a/src/edu/berkeley/sbp/Element.java b/src/edu/berkeley/sbp/Element.java
index 4ccde61..a37e960 100644
--- a/src/edu/berkeley/sbp/Element.java
+++ b/src/edu/berkeley/sbp/Element.java
@@ -1,21 +1,46 @@
+// (C) 2006-2007 all rights reserved; see LICENSE file for BSD-style license
+
 package edu.berkeley.sbp;
-import edu.berkeley.sbp.util.*;
-import edu.berkeley.sbp.*;
-import edu.berkeley.sbp.*;
-import java.io.*;
 import java.util.*;
-import java.lang.reflect.*;
-import java.lang.ref.*;
 
-/** <font color=green>the root superclass for all components of the grammar (terminals, nonterminals, literals, etc)</font> */
-public abstract class Element {
+/**
+ *  <font color=green>
+ *  the root superclass for all components of the grammar (terminals,
+ *  nonterminals, literals, etc)
+ *  </font>
+ */
+public abstract class Element implements SequenceOrElement {
 
     /** sorry, you can't make up new, custom elements */
     Element() { }
 
+    /** a more verbose version of toString() for displaying whole grammars */
     abstract StringBuffer toString(StringBuffer sb);
 
-    /** returns the Forest resulting from matching this element against the empty string */
-    Forest epsilonForm() { throw new Error("element " + this + " has no epsilon form"); }
-
+    /** 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;
 }