[antlr-interest] What exactly does 'follow set' mean?

Terence Parr parrt at cs.usfca.edu
Sun Apr 17 14:01:04 PDT 2005


On Apr 17, 2005, at 9:00 AM, Monty Zukowski wrote:
>> In the doc it says that, when antlr parsers encounter an error they
>> look up tokens until they find one in the 'follow set' of the rule.
>
> So the idea is 'hey that doesn't belong here, so I'll just skip ahead 
> in the token stream until I see a token that the calling rule might 
> match.'  So that when the errorneous rule returns the calling rule 
> might be able to continue where it left off.
>
> Note that in ANTLR 2, the follow set for a rule is the union of the 
> lookahead following every call to the rule.  ANTLR 2 doesn't 
> distinguish follow sets based on the caller.
>
> Hey Ter, this may be able to improve in ANTLR 3 since you actually 
> know the follow set specific to the calling rule.  Or maybe you 
> figured that out already?  Wouldn't suprise me ;)

ANTLR v3 dynamically computes precise FOLLOW(r) for rule r when an 
error occurs in r. :)  It does this for excellent error recovery.  I 
use something like Josef Grosch's work in CoCo.

The FOLLOW set used in theory discussions is always the precise one: 
the set of all tokens that can follow references to a rule in all valid 
contexts; i.e., it's the FIRST of all viable suffixes of r.  er 
something like that...theory ain't my strong suit...just hacking :)

Ter
--
CS Professor & Grad Director, University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
Cofounder, http://www.jguru.com





More information about the antlr-interest mailing list