[antlr-interest] [PATCH] Fixes FOLLOW set computation

[Robin Green]

This patch against 2.7.2 fixes (I think) an issue where ANTLR would
sometimes fail to complete a FOLLOW set computation, resulting in a
symptom of bogus "unexpected token" exceptions being thrown by the
generated parser. (My grammar is unusual - it's a literalistic
grammar for a YAML parser for Java - so I suspect I have triggered
an unusual edge case here.)

(The patch also includes some additional information I added to the
debug statements, but that's not important.)

Re-reading it, though, the pre-existing comment saying "this is not
crucial" should probably be changed to say the exact opposite! It
seems that this is the critical code path for breaking cycles, and the
person who wrote the comment thought that it wasn't (maybe it wasn't
then). Correct me if I'm wrong.

In any case, IMHO documenting the contract of the containing method
here would have avoided or mitigated this kind of issue. Either this
code was at fault or a caller was - but without documentation it
was hard to tell which was to blame.

Regards,
-- 
Robin


--- antlr/LLkAnalyzer.old	2004-03-06 21:33:38.000000000 +0000
+++ antlr/LLkAnalyzer.java	2004-03-06 16:12:52.000000000 +0000
@@ -400,20 +400,15 @@
             RuleEndElement re = rs.getBlock().endNode;
             // The other entry may not exist because it is still being
             // computed when this cycle cache entry was found here.
-            if (re.cache[k] == null) {
-                // return the cycle...that's all we can do at the moment.
-                return (Lookahead)end.cache[k].clone();
-            }
-            else {
+            if (re.cache[k] != null) {
                 // replace this cache entry with the entry from the referenced computation.
                 // Eventually, this percolates a complete (no cycle reference) cache entry
                 // to this node (or at least gets it closer and closer).  This is not
                 // crucial, but makes cache lookup faster as we might have to look up
                 // lots of cycle references before finding a complete reference.
-                end.cache[k] = re.cache[k];
-                // Return the cache entry associated with the cycle reference.
-                return (Lookahead)re.cache[k].clone();
+                end.cache[k] = FOLLOW (k, re);
             }
+            return (Lookahead)end.cache[k].clone();
         }
 
         end.lock[k] = true;	// prevent FOLLOW computation cycles
@@ -427,17 +422,20 @@
             RuleRefElement rr = rs.getReference(i);
             if (DEBUG_ANALYZER) System.out.println("next[" + rule + "] is " + rr.next.toString());
             Lookahead q = rr.next.look(k);
-            if (DEBUG_ANALYZER) System.out.println("FIRST of next[" + rule + "] ptr is " + q.toString());
+            if (DEBUG_ANALYZER)
+              System.out.println("FIRST of next[" + rule + "," + k + "] ptr is " + q.toString());
             /* If there is a cycle then if the cycle is to the rule for
 			 * this end block, you have a cycle to yourself.  Remove the
 			 * cycle indication--the lookahead is complete.
 			 */
             if (q.cycle != null && q.cycle.equals(rule)) {
+                if (DEBUG_ANALYZER) System.out.println (rule + ": Deleting cycle to self");
                 q.cycle = null;	// don't want cycle to yourself!
             }
             // add the lookahead into the current FOLLOW computation set
             p.combineWith(q);
-            if (DEBUG_ANALYZER) System.out.println("combined FOLLOW[" + rule + "] is " + p.toString());
+            if (DEBUG_ANALYZER)
+              System.out.println("combined FOLLOW[" + rule + "," + k + "] is " + p.toString());
         }
 
         end.lock[k] = false; // we're not doing FOLLOW anymore
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20040306/9b2b65b2/attachment-0001.bin