0
$\begingroup$

In Sebesta's Concepts of Programming Languages 10th edition on page 189 he explains the concept of $\text{FIRST}$ sets using the following example:

$A \rightarrow aB \ | \ bAb \ | \ Bb$

$B \rightarrow cB \ | \ d$

The $\text{FIRST}$ sets for the RHSs of the $A$-rules are $\{a\}$, $\{b\}$, and $\{c, d\}$, which are clearly disjoint.

Why aren't the first two sets combined into a single set $\{a, b\}$ instead? If $\{c, d\}$ is constructed by taking the two leftmost terminal symbols from $B$ then why don't we likewise take the two leftmost terminal symbols from $A$ into a single set?

$\endgroup$
1
$\begingroup$

There are three $A$-rules, each one with its right-hand side: $aB$, $bAb$, and $Bb$. Each produces a set as its value for $FIRST$. $FIRST(aB) = \{a\}$, and $FIRST(bAb) = \{b\}$.

In its turn, $FIRST(Bb) = FIRST(B)$ (because $B$ does not derive the empty string), and $FIRST(B) = FIRST(cB) \cup FIRST(d) = \{c\} \cup \{d\} = \{c,d\}$.

Naturally, $FIRST(A) = \{a, b, c, d\}$.

$\endgroup$
  • $\begingroup$ Ah ok! I get it now. Sebesta gives only a cursory mention of FIRST and only used logical notation to describe the set, not walk through constructing it. And no mention of FOLLOW, or of PREDICT sets in general. What you wrote makes perfect sense. Thank you. $\endgroup$ – Dave Nov 6 '16 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.