tags: compiler design, systems
First Set
The first set is defined as the set of terminals that start the strings produced by the grammar rule or derived from this rule.
Example:
The Algorithm
Let’s say we have the following rules:
S \rightarrow AB \\ A \rightarrow a|\epsilon \\ B \rightarrow b \end{eqnarray}$$ The first of a terminal is itself, $FIRST(B) = \{b\}$, $FIRST(A) = \{a, \epsilon \}$, Now for a production choice $X \rightarrow ABC$, if $A$ produces $\epsilon$ then $FIRST(X)=FIRST(A)- \{\epsilon\} \bigcup FIRST(B, C)$, and so on with $FIRST(B, C)$. If A does not produce $\epsilon$ then $FIRST(X)=FIRST(A)\space only$. So from the above rules we can conclude that: $$\begin{eqnarray} FIRST(S) = \{a, b\} \\ FIRST(A) = \{a, \epsilon\} \\ FIRST(B) = \{b\} \end{eqnarray}$$ ## Follow Set The follow set is defines as **the set of terminals that appear just after the owner of this set**.  ## The Algorithm 1. If a grammar is the start symbol then $ is in its follow set  In 2 $\epsilon$ is not placed in the follow because it will never come after a rule, the last thing that can come after a rule is $. ## Constructing the LL(1) table  I think what is meant by First($\alpha$) is the whole production choice it self, not a single non-terminal. ## References 1. https://www.cs.uaf.edu/~cs331/notes/FirstFollow.pdf