Defining nullable symbols and the first set of a grammar

Question

I'm practicing for an upcoming exam and am being tripped up by a review problem. The problem gives the following grammar:

$$S \rightarrow AB\$$$ $$A \rightarrow \epsilon | a | (T)$$ $$T \rightarrow T, S | S$$ $$B \rightarrow b$$

As far as I can tell, the only nullable symbol is $A$. It is the only non-terminal whose production contains the null symbol $\epsilon$. I don't think $S$, which contains $A$ in it's production, is a nullable symbol since the same production also contains $B$, which is not a nullable symbol, and both $A$ and $B$ would need to be nullable for $S$ to also be nullable. Is $A$ really the only nullable symbol in this grammar, or am I misinformed?

As for the first set, frankly, I'm just having trouble following my professor's notes for creating the first set. Could anyone help here or point me to a good resource for this?

Thank you all so much.

Answer 1

A nonterminal $X$ is nullable if you can generate the empty word from it. For example, since $A \to \epsilon$, we see that $A$ is nullable, while since the only production involving $B$ is $B \to b$, we see that $B$ is not nullable.

In class, you were shown algorithms for determining which nonterminals are nullable. These algorithms are important for computers implementing parsers. Human beings can also use these algorithms to determine which nonterminals are nullable, but (i) outside of a classroom setting, humans never have the urge to determine which nonterminals are nullable, (ii) often it can be determined by "direct inspection".

The first set of a nonterminal consists of all initial terminals in words generated by $X$ (including $\epsilon$, if $X$ is nullable, at least in some definitions). For example, since the only word generated by $B$ is $b$, then $\mathrm{FIRST}(B) = \{ b \}$. Similarly, the productions of $A$ immediately imply that $\mathrm{FIRST}(A) = \{ \epsilon, a, (\}$. Continuing, since $S \to AB\$$ is the only production of $S$, then since $A$ is nullable and $B$ isn't, $\mathrm{FIRST}(S) = \{ a,(,b \}$. This is the same as $\mathrm{FIRST}(T)$. Here I am implementing the FIRST algorithm in my head, without ever looking at it. Algorithms are necessary for computers, not necessarily for humans.

Summarizing, I suggest focusing on the definitions of nullable and FIRST rather than on the algorithms that can be used to compute them. It is much more important to understand what you're doing (and why) then to memorize some algorithm which you will never ever use in the future.