Re: recursive parsers and FOLLOW sets

KB Sriram <kbs@best.com> writes:
>When generating recursive descent parsers from LL(1) grammars, are
>FOLLOW sets needed for anything other than detecting syntax errors
>"quicker" and error repair/recovery?


Follow sets are needed for computing director sets. Director sets can
be used for lookahead optimization (`if the next symbol in the input
is not an element of the director set of this alternative, then don't
try it'). If your grammar is LL(1) then a top down parser can make a
unique choice for an alternative by identifying the next symbol in the
input in the director set of an alternative.


>Specifically, if all I want is a parser that is able to identify valid
>(and invalid :-) sentences, whats the gotcha with generating a
>function for a "nullable" non-terminal that would match null and
>return on finding a token that wasn't in its FIRST set, and leave any
>error detection to procedures further up in the call stack?


Notice that you can transcribe the rules of an LL(1) grammar into
boolean parsing procedures. Empty producing alternatives should be
tried last and will always succeed without consuming a token. The
procedures for nonterminals which can fail, i.e. cannot produce empty,
are extended with an error-reporting alternative which is executed if
no other alternative succeeds.


Best regards, Caspar Derksen


----
Drs. C.F. Derksen caspard@cs.kun.nl
Dept. of Computer Science http://www.cs.kun.nl/agfl/
University of Nijmegen +31 24 3653362
--

Return to the comp.compilers page.
Search the comp.compilers archives again.