Drawtomata / FIRST and FOLLOW calculator
FIRST and FOLLOW calculator
Type a grammar above, one production per line, such as E -> E + T | T. Drawtomata computes FIRST and FOLLOW for every nonterminal and shows how the sets grow pass by pass.
Rules
FIRST(X) is the set of terminals that can begin a string derived from X, plus ε if X can derive ε.
- For a terminal a, FIRST(a) = {a}.
- For X → Y1 Y2 … Yk, add FIRST(Y1) − {ε}. If Y1 can vanish, add FIRST(Y2) − {ε}, and so on. If all of them can vanish, add ε.
FOLLOW(A) is the set of terminals that can appear right after A in some sentential form.
- Put $ in FOLLOW(S) for the start symbol S.
- For A → αBβ, add FIRST(β) − {ε} to FOLLOW(B).
- For A → αB, or A → αBβ where β can derive ε, add FOLLOW(A) to FOLLOW(B).
Apply the rules until no set changes. FIRST and FOLLOW are what the LL(1) table and the SLR table are built from.