Let G be a grammar with non-terminal A, terminal a and these productions:

A -> A a

It is obvious that this grammar cannot be parsed. There is no way to "exit" the parsing process. However, I am not sure at what point I would determine the LL(1) property.

Let's first look at the FIRST set for A. By looking at our rule, FIRST(A) must contain FIRST(A). It does not contain any terminals and it doesn't contain epsilon. Therefore I believe it should be the empty set. Now for the set FOLLOW(A). With # being the terminator symbol, and A being our "entry point", FOLLOW(A) must contain #. As the non-terminal A is followed by a in our rule, FOLLOW(A) = {#, a}.

Now for building the parsing table:

For our rule, we examine FIRST(A a) which is the empty set, as FIRST(A) does not contain epsilon. We don't add anything to the parsing table. Now, if FIRST(A a) contains epsilon (which it does not), we examine the set FOLLOW(A). We skip this step, and are left with an empty parsing table.

It is clear that an empty parsing table would reject every input, leading me to believe the grammar must be "invalid". However, as I understand it, the LL(1) property is still fulfilled.

Is this correct, or is this grammar not LL(1) for some other reason? Can I conclude that having empty FIRST sets leads to unparsable grammars in general?


1 Answer 1


From wikipedia

A formal grammar that contains left recursion cannot be parsed by a LL(k)-parser or other naive recursive descent parser unless it is converted to a weakly equivalent right-recursive form


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.