World's most popular travel blog for travel bloggers.

Why are these FIRST sets not combined into a single set?

, , No Comments
Problem Detail: 

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?

Asked By : Dave
Answered By : André Souza Lemos

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\}$.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback