0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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).

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – tmhs
    Apr 15 at 6:34
  • $\begingroup$ 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! $\endgroup$
    – tmhs
    Apr 15 at 8:59
  • $\begingroup$ 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) $\endgroup$
    – tmhs
    Apr 15 at 8:59
  • $\begingroup$ Rules 3, 4, 5 are exactly the same rules I have stated, just formulated a bit differently… $\endgroup$
    – Nathaniel
    Apr 15 at 11:22
  • $\begingroup$ Also, of course $c\in \text{FIRST}(A)$, since $\varepsilon \in \text{FIRST}(F)$, and using your rule 4. $\endgroup$
    – Nathaniel
    Apr 15 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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