# How to find First in a left recursive grammar?

One of the basic requirements for a grammar to be LL(1) is : For every pai r of productions A -> X | Y, First(X) and First(Y) should be disjointed.

If a grammar is left-recursive, then the set of productions will contain at least one pair of the form A -> AX|B; and hence, First(AX) and First(Y) will not be disjoint sets, because everything in the First(Y) will also be in the First(AX).

Source : Compiler Design by Dr. O.G. Kakde

How can I calculate the First of (AX) because First(A) = First(AX) U First(Y) goes recursively forever ?

## 1 Answer

Here is how to apply the production rule $$A\to AX$$ to compute $$\text{first}(A)$$.

When $$\epsilon\in\text{first}(A)$$, add all (non-$$\epsilon$$) members of $$\text{first}(X)$$ to $$A$$.

More generally, if there is a rule $$A\to AX_1X_2\cdots X_n$$,

When $$\epsilon\in\text{first}(A)$$, add all non-$$\epsilon$$ members of $$\text{first}(X_1)$$ to $$A$$. When $$\epsilon\in\text{first}(A)$$ and $$\epsilon\in\text{first}(X_1)$$, add all non-$$\epsilon$$ members of $$\text{first}(X_2)$$ to $$A$$. When $$\epsilon\in\text{first}(A)$$ and $$\epsilon\in\text{first}(X_1), \text{first}(X_2)$$, add all non-$$\epsilon$$ members of $$\text{first}(X_3)$$ to $$A$$, and so on.

The rules above are just specializations of the general rules. What is particular in this situation is that there is no effect when you add all members of $$\text{first}(A)$$ to $$\text{first}(A)$$. There is no concern about infinite recursion.

Here is a left-recursive grammar.
$$\quad S \to SX\mid Y$$
$$\quad X \to x$$
$$\quad Y \to y$$
We compute as the following.

• $$\text{first}(X)=\{x\}$$ by the rule $$X\to x$$.
• $$\text{first}(Y)=\{y\}$$ by the rule $$Y\to y$$.
• $$\text{first}(S)=\{y\}$$ by the rule $$S\to Y$$.
• Since $$\epsilon\not\in\text{first}(S)$$, ignore rule $$S\to SX$$.

Here is another left-recursive grammar.
$$\quad S \to SX\mid Y$$
$$\quad X \to x \mid \epsilon$$
$$\quad Y \to y \mid \epsilon$$
We compute as the following.

• $$\text{first}(X)=\{\epsilon, x\}$$ by the rules $$X\to x \mid \epsilon$$.
• $$\text{first}(Y)=\{\epsilon, y\}$$ by the rules $$Y\to y\mid\epsilon$$.
• add $$\epsilon, y$$ to $$\text{first}(S)$$ by the rule $$S\to Y$$.
• Since $$\epsilon\in\text{first}(S)$$, add $$x$$ to $$\text{first}(S)$$ by the rule $$S\to SX$$. So $$\text{first}(S)=\{\epsilon, x, y\}$$

Exercise. Compute the first set of the following grammar.
$$\quad E\to E - T \mid T$$
$$\quad T\to T * F \mid F$$
$$\quad F\to (\ E\ ) \mid I$$