CODEWITHSUNDEEP
parsinggrammarcontext-free-grammarcompiler-construction
midas
midas

Reputation: 1848

LL(1) grammar. How to calculate follow set if one has self-recursion rules?

According to the rules from this paper :

  1. If A is the start nonterminal, put EOF in FOLLOW(A)
    Find the productions with A on the right-hand-side:
  2. For each production X → αAβ, put FIRST(β) − {EPSILON } in FOLLOW(A)
  3. If EPSILON is in FIRST(β) then put FOLLOW(X) into FOLLOW(A)
  4. For each production X → αA, put FOLLOW(X) into FOLLOW(A)

I have next piece in my grammar:

 ...
    A -> C B
    B -> , A
    C -> EPSILON
    C -> =
    B -> ;
 ...

When I try to calculate FOLLOW(B) according to the rule 4 I have to calculate FOLLOW(A) and vice versa. So I have StackOverflowException because of self-recursion.

What should I do?

Upvotes: 3

Views: 3094

Answers (1)

Apalala
Apalala

Reputation: 9224

You don't use recursion. You iterate, calculating the FOLLOW set based on what was calculated on the previous iteration:

  1. If A is the start nonterminal, put EOF (a new terminal indicating the end of input) in F[0](A).

  2. For each production X → αAβ, put FIRST(β) − {EPSILON} in F[n](A),

  3. and if EPSILON is in FIRST(β) then put F[n-1](X) into F[n](A)

  4. For each production X → αA, put F[n-1](X) into F[n](A).

  5. Stop when F[n](*) == F[n-1](*)

FOLLOW(*) == F[n](*)

Upvotes: 4

Related Questions