Parsing & Applications of Grammars

FIRST and FOLLOW sets

To predict which grammar rule to use, a top-down parser asks two natural questions about each nonterminal: 'what tokens could it possibly start with?' and 'if it produces nothing, what could come right after it?'. FIRST answers the first question, FOLLOW answers the second. They are the small lookup tables that let a predictive parser glance one token ahead and know which rule to fire.

FIRST(X) is the set of terminals that can appear as the very first token of some string derived from X. For a rule A -> num B, num is in FIRST(A); for A -> B c where B might be empty, FIRST(A) includes FIRST(B) and possibly c. If a nonterminal can derive the empty string, the special marker for empty is recorded too. FOLLOW(A) is the set of terminals that can legally appear immediately after A in some sentential form; you compute it by looking at every rule where A appears on the right, X -> alpha A beta, and adding FIRST(beta), plus FOLLOW(X) when beta can vanish. These sets are computed by a fixed-point process: start them empty and keep adding until nothing new appears. Once known, the LL(1) table is filled by a single rule: put A -> alpha under every token in FIRST(alpha), and if alpha can be empty, also under every token in FOLLOW(A).

FIRST and FOLLOW are the engine behind predictive and LL parsing: without them you could not build a conflict-free parsing table or know when a grammar is LL(1). They also surface clashes precisely: if two alternatives of a nonterminal have overlapping FIRST sets, or an empty-deriving alternative collides with FOLLOW, the table gets two entries in one cell, which is the formal warning that the grammar is not LL(1) and must be reworked.

For E -> T E', E' -> + T E' | epsilon, T -> num: FIRST(T) = {num}, FIRST(E') = {+, empty}, FIRST(E) = {num}. FOLLOW(E) = {end-of-input, )} (whatever can follow a whole expression), and FOLLOW(E') = FOLLOW(E). Because FIRST(+ T E') = {+} and FOLLOW(E') excludes +, the choice for E' is conflict-free.

FIRST = what a symbol can start with; FOLLOW = what can come right after it.

FOLLOW is only consulted for productions that can derive the empty string; for a normal production you only need FIRST. Mixing this up is the most common mistake when filling an LL(1) table by hand.

Also called
FIRST setFOLLOW setFIRST 集FOLLOW 集