Re: recursive parsers and FOLLOW sets (Caspar Derksen)
22 Mar 1996 21:24:24 -0500

          From comp.compilers

Related articles
recursive parsers and FOLLOW sets (KB Sriram) (1996-03-20)
Re: recursive parsers and FOLLOW sets (1996-03-22)
Re: recursive parsers and FOLLOW sets (1996-03-22)
| List of all articles for this month |

From: (Caspar Derksen)
Newsgroups: comp.compilers
Date: 22 Mar 1996 21:24:24 -0500
Organization: University of Nijmegen, The Netherlands
References: 96-03-127
Keywords: LL(1), parse

KB Sriram <> 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
Dept. of Computer Science
University of Nijmegen +31 24 3653362

Post a followup to this message

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