Top down parsing - Compute FIRST and FOLLOW

0
votes

Given the following grammar:

S -> S + S | S S | (S) | S* | a

S -> S S + | S S * | a

For the life of me I can't seem to figure out how to compute the FIRST and FOLLOW for the above grammar. The recursive non-terminal of S confuses me. Does that mean I have to factor out the grammar first before computing the FIRST and FOLLOW?

1
parsingcontext-free-grammarll
possible duplicate of How to find FIRST and FOLLOW sets of a recursive grammar? – rici
If those two lines constitute a grammar, then it's ambiguous. I suspect each line is a separate grammar. In fact, even on its own, the first line is ambiguous (e.g. 2 different ways to derive aa*). Are you sure you've copied the problem correctly? – Michael Dyck

1 Answers

0
votes

The general rule for computing FIRST sets in CFGs without ε productions is the following:

  • Initialize FIRST(A) as follows: for each production A → tω, where t is a terminal, add t to FIRST(A).
  • Repeatedly apply the following until nothing changes: for each production of the form A → Bω, where B is a nonterminal, set FIRST(A) = FIRST(A) ∪ FIRST(B).

We could follow the above rules as written, but there's something interesting here we can notice. Your grammar only has a single nonterminal, so that second rule - which imports elements into the FIRST set of one nonterminal from FIRST sets from another nonterminal - won't actually do anything. In other words, we can compute the FIRST set just by applying that initial rule. And that's not too bad here - we just look at all the productions that start with a terminal and get FIRST(S) = { a, ( }.