# Context Free Grammar: How to infer FIRST()

We are given the grammar rules

• $$A \to F B E$$

• $$B\to A C$$

These rules are only some of the rules of a larger grammar $$G$$, but we are not given the remaining rules of $$G$$. We are told that $$A$$ is the start symbol of $$G$$ and that the following holds:

• $$\{\varepsilon, c, d\}\subseteq \text{FIRST}(C)$$
• $$\{\varepsilon, e\} \subseteq \text{FIRST}(E)$$
• $$\{\varepsilon, f, g\} \subseteq \text{FIRST}(F)$$

Recall that end of file is denoted EOF.

Which of the following must hold?

• $$\varepsilon \in \text{FIRST}(B)$$
• $$f \in \text{FIRST}(B)$$
• $$c \in \text{FIRST}(B)$$
• $$d \in \text{FIRST}(B)$$
• $$a \in \text{FIRST}(B)$$
• $$EOF \in \text{FIRST}(B)$$

When I don't know what consist of $$A,B,C,D,E,F$$ given the condition above, how can I infer what $$\text{FIRST}(B)$$ would be?

My attempt was something like this: Given the condition, I can infer that $$\text{FIRST}(A)$$ may contain $$f, g$$ but absolutely can't have $$e$$. $$\text{FIRST}(B)$$ may contain $$f, g$$, but without knowing what $$\text{FIRST}(A)$$ is, I can't really figure out what $$\text{FIRST}(B)$$ is.

Am I missing something? Is there a way to fully infer what $$\text{FIRST}(B)$$ is without having all the information?

Recall that if $$X \to Y_1…Y_k$$ is a rule of the grammar, then:

• $$\Sigma\cap\text{FIRST}(Y_1)\subseteq \text{FIRST}(X)$$
• if, for some $$2\leqslant j \leqslant k$$, $$\varepsilon \in \bigcap\limits_{i=1}^{j-1}\text{FIRST}(Y_i)$$, then $$\Sigma\cap\text{FIRST}(Y_j)\subseteq \text{FIRST}(X)$$
• if $$\varepsilon \in \bigcap\limits_{i=1}^{k}\text{FIRST}(Y_i)$$, then $$\varepsilon\in\text{FIRST}(X)$$.

Since $$A\to FBE$$ is a rule, $$\Sigma \cap \text{FIRST}(F)\subseteq \text{FIRST}(A)$$. Since $$B\to AC$$ is a rule, $$\Sigma \cap \text{FIRST}(A)\subseteq \text{FIRST}(B)$$. That means $$\Sigma \cap \text{FIRST}(F)\subseteq \text{FIRST}(B)$$, and so $$f\in \text{FIRST}(B)$$, no matter what the other rules of the grammar.

On the other hand, one cannot guarantee that $$\varepsilon \in \text{FIRST}(B)$$. Indeed, the following grammar:

$$A\to FBE\mid a$$

$$B\to AC$$

$$C \to \varepsilon \mid c \mid d$$

$$E \to \varepsilon \mid e$$

$$F\to \varepsilon \mid f \mid g$$

satisfies all the conditions, but $$B$$ cannot be derivated into $$\varepsilon$$.

Now that I answered the first two propositions, it is your turn to work on the others (either by finding inclusions or counter-examples).

• Hi! I appreciate this. I have not learnt these rules. I was simply given how to calculate FIRST sets so this is very helpful. Given this rule, FIRST(B) does include f and g and we can't guarantee whether epsilon can be included because of the absence of FIRST(A). Did I understand that correctly?
– tmhs
Apr 15 at 6:34
• I tried to apply this to a new problem set but it only put. me in confusion: A ➝ F C B E which is one rule from a larger grammar G, but we are not given the remaining rules of G. We are told that A is the start symbol of G and that the following holds: {ε, c, d} ⊆ FIRST(C), {ε, e} ⊆ FIRST(E), {ε, a, b} ⊆ FIRST(F) The ask is given this, figure out FIRST(A). According to what you have introduced above, I know that FIRST(A) includes {a,b}. The answer reads that it should also include {c}. But based on how to calculate FIRST set (see following comment), that seems impossible!
– tmhs
Apr 15 at 8:59
• Rule I am referring to : 1. FIRST(x) = { x } if x is a terminal, 2. FIRST(𝜺) = { 𝜺 }, 3. If A → Bα is a production rule, then add FIRST(B) – { 𝜺 } to FIRST(A), 4. If A → B0B1B2…BiBi+1…Bk and 𝜺 ∈ FIRST(B0) and 𝜺 ∈ FIRST(B1) and 𝜺 ∈ FIRST(B2) and … and 𝜺 ∈ FIRST(Bi), THEN add FIRST(Bi+1) – { 𝜺 } to FIRST(A), 5. If A → B0…Bk and FIRST(B0) and 𝜺 ∈ FIRST(B1) and 𝜺 ∈ FIRST(B2) and … and 𝜺 ∈ FIRST(Bk), then add 𝜺 to FIRST(A)
– tmhs
Apr 15 at 8:59
• Rules 3, 4, 5 are exactly the same rules I have stated, just formulated a bit differently… Apr 15 at 11:22
• Also, of course $c\in \text{FIRST}(A)$, since $\varepsilon \in \text{FIRST}(F)$, and using your rule 4. Apr 15 at 11:30