LL-1 Parsers: Is the FOLLOW-Set really necessary?

Question

as far as I understand the FOLLOW-Set is there to tell me at the first possible moment if there is an error in the input stream. Is that right?

Because otherwise I'm wondering what you actually need it for. Consider you're parser has a non-terminal on top of the stack (in our class we used a stack as abstraction for LL-Parsers)

i.e.

[TOP]   X...[BOTTOM]

The X - let it be a non-terminal - is to be replaced in the next step since it is at the top of the stack. Therefore the parser asks the parsing table what derivation to use for X. Consider the input is

+ b

Where + and b are both terminals.

Suppose X has "" i.e. empty string in its FIRST set. And it has NO + in his FIRST set.

As far as I see it in this situation, the parser could simply check that there is no + in the FIRST set of X and then use the derivation which lets X dissolve into an "" i.e. empty string since it is the only way how the parser possibly can continue parsing the input without throwing an error. If the input stream is invalid the parser will recognize it anyway at some moment later in time. I understand that the FOLLOW set can help here to right away identify whether parsing can continue without an error or not.

My question is - is that really the only role that the FOLLOW set plays?

I hope my question belongs here - I'm sorry if not. Also feel free to request clarification in case something is unclear.

Thank you in advance

Answer 1

You are right about that. The parser could eventually just continue parsing and would eventually find a conflict in another way. Besides that, the FOLLOW set can be very convenient in reasoning about a grammar. Not by the parser, but by the people that constructs the grammar. For instance, if you discover, that any FIRST/FIRST or FIRST/FOLLOW conflict exists, you have made an ambiguous grammar, and may want to revise it.