Motivating the FIRST, FOLLOW, and FIRST+ sets

CS4240

for parsing context-free-language

we consider bottom-up parsing, where each character matches a nonterminal

the FIRST set of a nonterminal is all characters which may be the first character of that nonterminal

the FOLLOW set of a nonterminal is all characters which may follow that nonterminal

Consider parsing a string.

• It may seem like we can just match using the FIRST set of each nonterminal (so e.g., expr has the FIRST set including ( and the parser that sees ( can pick expr in its candidates)

• However, we cannot use the FIRST set to match which nonterminal if the FIRST set contains $\epsilon$, so if $\epsilon\in\text{FIRST}$, use the union of the FIRST set and the FOLLOW set (since the nonterminal may be $\epsilon$).