I have a BNF for a recursive descent parser. One of the steps to solving this is to verify that the grammar is LL(1), but I keep coming up with verification that it is not.
The BNF in question, or more specifically, the exact area I'm having an issue:
<S> -> start <vars> <block>
<block> -> begin <vars> <stats> end
<vars> -> e | id = number <vars>
<stats> -> <if> | <block> | <loop> | <assign>
There is more to this, but these are the only productions that are relevant to this question, I believe.
My approach to solving this is to compute FIRST of the right hand sides of those productions that have a choice. If there is no choice, I skip, as I know they are already k=0.
FIRST(e | id = number <vars>) = {e, id} // Since it produces the empty set, I must also compute follow.
FOLLOW( e | id = number <vars> ) = FOLLOW(<vars>)
Non-terminal 'vars' appears in 2 productions: and , and is followed by two nonterminals: 'block' and 'stats'
FIRST(<block>) = {begin}
FIRST(<stats>) = { ... begin ... } // contains all terminals
Now, my problem. In computing the FOLLOW(), I have found two begin tokens, which leads me to say that this grammar is not LL(1). However, I don't believe that the answer to this exercise is that it is not possible to create a recursive descent parser, so I believe that I've made an error somewhere or that I have executed the algorithm incorrectly.
Can anyone point me in the right direction?
So you've correctly found that FOLLOW(var) = FIRST(block) ∪ FIRST(stats). These are all sets, so when you compute the union of the two first sets (each of which contains begin), you end up with just a single begin. As long as neither of these sets ends up containing id, everything is fine and your grammar is still LL(1).