FirstAndFollowSets

From BarikWiki
Jump to: navigation, search

Here's the sample grammar for this problem:

E → T E'
E' → + T E'
E' → ε
T → F T'
T' → * F T'
T' → ε
F → (E)
F → id

Rules for First Sets

  1. If X is a terminal, then FIRST(X) = {X}.
  2. If there is a Production X → ε then add ε to first(X)
  3. If there is a Production X → Y1Y2..Yk then add first(Y1Y2..Yk) to first(X)
  4. First(Y1Y2..Yk) is either
  5. First(Y1) (if First(Y1) doesn't contain ε)

OR (if First(Y1) does contain ε) then First (Y1Y2..Yk) is everything in First(Y1) <except for ε > as well as everything in First(Y2..Yk)

  1. If First(Y1) First(Y2)..First(Yk) all contain ε then add ε to First(Y1Y2..Yk) as well.

Rule for Follow Sets

  1. First put $ in FOLLOW(S). S is the start symbol, and $ is the input right endmarker.
  2. If there is a production of the form A → aBb, and we want to compute FOLLOW(B), then this is everything in FIRST(b) except for ε.
  3. Now what if FIRST(b) above did contain ε or the production is of the form A → aB? Then everything in FOLLOW(A) is added to FOLLOW(B).