An Introduction to Formal Languages and Automata, 7th Edition

15.4 FOLLOW FUNCTION

Next we define the FOLLOW function. FOLLOW makes use of a special symbol $ that indicates an end-of-string marker. The $ symbol is not a terminal or a variable, but rather it is a special symbol that appears to the immediate right of a string to help determine that all the terminals in an input string have been processed. This is a similar idea to a bottom of stack marker in an npda, which is a special symbol one can look at to see if all the symbols on the stack have been processed.

The FOLLOW function is applied to a variable and calculates the set of terminals or $ that can immediately follow that variable in some sentential form. Note that $ can always follow the start symbol S of a context-free grammar. Suppose $S\stackrel{}{\Rightarrow }$