CODEWITHSUNDEEP
parsingcompiler-constructiongrammar
Andrej Žukov-Gregorič
Andrej Žukov-Gregorič

Reputation: 555

Calculating FIRST sets by hand

I'm having a slight problem that's been bugging me for quite some time now and I haven't been able to find a suitable answer online.

Given a grammar:

S = Sc | Eab | Db | b
D = EDcD | ca | ɛ
E = dE | DY
Y = Ed | Dad | ɛ

To find the FIRST set of say Y, so FIRST(Y), am I correct in assuming that it goes like this:

FIRST(Y)
= FIRST(Ed) ∪ FIRST(Dad) ∪ FIRST(ɛ)
= FIRST(E) ∪ (FIRST(D)\{ɛ}) ∪ FIRST(ad) ∪ {ɛ}
= FIRST(E) ∪ (FIRST(D)\{ɛ}) ∪ {a, ɛ}

Now the question is how do I find FIRST(E) and FIRST(D)?

Upvotes: 2

Views: 825

Answers (1)

Gareth McCaughan
Gareth McCaughan

Reputation: 19971

So, the problem with FIRST(E) and FIRST(D) is that E and D reference one another. And the solution is the usual one when you want a sort of "least fixed point" -- start with everything empty and keep iterating until they stabilize.

That is: first of all, initialize all your FIRST sets to the empty set. Now, repeatedly, consider each production and pretend your current estimates for the non-terminal's FIRST sets are the truth. (In reality, they will typically be "underestimates".) Work out what the production tells you about the FIRST set of its LHS, and update your estimate of that non-terminal's FIRST set accordingly. Keep doing this, processing all the productions in turn, until you've gone through all of them and your estimates haven't changed. At that point, you're done.

In this case, here's how it goes (assuming I haven't goofed, of course). The first pass produces successively S: {b}, D: {c,ɛ}, E: {c,d}, Y: {c,d,ɛ}. The second produces successively S: {b,c,d}, D: {c,d,ɛ}, E: {c,d,ɛ}, Y: {c,d,ɛ}. The third doesn't change any of those, so those are the final answers.

Upvotes: 4

Related Questions