CODEWITHSUNDEEP
parsinggrammarcontext-free-grammarrecursive-descentcompiler-construction
Random Coder
Random Coder

Reputation: 71

LL1 First and follow sets rules

I'm looking on building a parse table for an LL(1) grammar, and It all makes sense bar one aspect!?

The rules for the follow set seam to conflict.

• For each production X → αAβ, put FIRST (β) − {€} in FOLLOW(A)
• If € is in FIRST (β) then put FOLLOW(X) into FOLLOW(A)

they're rules 1&2 (3 isn't a problem).

How can you implement rule 2, if that production rule doesn't already qualify for rule 1?

so can someone explain the subtly of which rule applies where?

Upvotes: 4

Views: 2964

Answers (1)

Dervall
Dervall

Reputation: 5744

The first rule says that you put everything in FIRST(β) except for epsilon if the follow set contains it in the follow for A. The epsilon should not be there, since it would not be legal for A to be followed by nothing.

The second rule says that if β can be epsilon then everything that follows X is also a legal follow of A, since β can be derived from nothing.

The rules are not mutually exclusive. You'll need to apply all the rules on each production, it's not like if the production qualifies for rule 1 then you do not run rule 2. You'll run all of the rules until the FOLLOW set stabilizes and nothing more gets added.

Upvotes: 1

Related Questions