An Introduction to Formal Languages and Automata, 7th Edition

15.3 FIRST FUNCTION

We have not given many details on how to choose a rule if a variable has more than one rule, or how to choose a righthand side to replace if there is more than one choice. Before giving those details, we define two functions useful in both LL and LR parsing: FIRST and FOLLOW. The FIRST function calculates a set of terminals from a sentential form that could be the first terminal in the string after the sentential form has replaced all the variables. Knowing the first terminal helps guide the parsing, that is, helps choose the next rule to apply.

DEFINITION 15.1

Given a context-free grammar G = (V, T, S, P), a ∈ T and w, v ∈ (V ∪ T)^*, the FIRST( w) is the set of terminals that can be the first terminal a in $w\stackrel{\ast }{\Rightarrow }av$. λ is in ...