2

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?

1 Answer 1

2

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!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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