Search code examples
parsingcompiler-constructioncontext-free-grammarll-grammar

Finding FIRST sets in a grammar

Today I am reading how to find First and Follow of a grammar. I saw this grammar:

S → ACB | CbB | Ba

A → da | BC

B → g | ε

C → h | ε

The claim is that

FIRST(S) = FIRST(ABC) U FIRST(CbB) U FIRST(Ba)

= {d, g, h, ε} U {h, b} U {g, a}

= {d, g, h, ε, b, a}

I don't understand how a and b are in this set. Can anyone explain this?

Solution

  • Notice that B and C both are nullable (they can produce ε). This means that from the production

    S → CbB

    we get that b ∈ FIRST(S), since if we use the production C → ε we can get a production that starts with b.

    Similarly, note that

    S → Ba

    is a production, so we get a ∈ FIRST(S) because we can use the production B → ε to get an a at the front of a string derivable from S.

    Hope this helps!