Concept of First and Follow
The construction of a top-down parser is aided by FIRST and FOLLOW functions, that are associated with a grammar G. During top-down parsing, FIRST and FOLLOW allow us to choose which production to apply, based on the next input symbol.
Rules for First computation:
1) If x is terminal, then FIRST(x)={x}
2) If X→ ε is production, then add ε to FIRST(X)
3) If X is a non-terminal and X → PQR then FIRST(X)=FIRST(P)
If FIRST(P) contains ε, then
FIRST(X) = (FIRST(P) – {ε}) U FIRST(QR)
Rules for Follow computation:
Note: Epsilon (ε) can never be present in FOLLOW of any non-terminal symbol.
1) For Start symbol, place $ in FOLLOW(S)
2) If A→ α B, then FOLLOW(B) = FOLLOW(A)
3) If A→ α B β, then
If ε not in FIRST(β),
FOLLOW(B) = FIRST(β)
else do,
FOLLOW(B) = (FIRST(β)-{ε}) U FOLLOW(A)
Compiler Design LL(1) Parser in Python
Prerequisite: Construction of LL(1) Parsing Table, Classification of top-down parsers, FIRST Set, FOLLOW Set
In this article, we are going to see how to design LL(1) Parser compiler using Python.
Contact Us