From fcc038ff693cf2b3e91efcd348ea3a3b7fbb1829 Mon Sep 17 00:00:00 2001 From: adam Date: Sat, 8 Sep 2007 18:30:38 -0400 Subject: [PATCH] add slow epsilon-ness checker as static method in Element darcs-hash:20070908223038-5007d-59282544c4bc9844150b5a66c9074754a3e4b875.gz --- src/edu/berkeley/sbp/Element.java | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) 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; } -- 1.7.10.4