• 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 ϵ∈FIRST\epsilon\in\text{FIRST}, use the union of the FIRST set and the FOLLOW set (since the nonterminal may be ϵ\epsilon).

Snapshot: 263ed825330d3f75ad54c01c51966e0d78aa484674758003223e97b5241600233cbb1153230e688cdfcfb0b4ed017b0625fa736a302d010e1a3c3ddd8dd3a463 list?snapshot=263ed825330d3f75ad54c01c51966e0d78aa484674758003223e97b5241600233cbb1153230e688cdfcfb0b4ed017b0625fa736a302d010e1a3c3ddd8dd3a463