# Construct non-recursive predictive parser for grammar $S \to Aa \mid b A c \mid Bc \mid bBa, A \to d, B \to d$

In the grammar for S production two bodies have same starting symbol

$S \to Aa \mid b A c \mid Bc \mid bBa$

So i removed the left factoring from those two productions

$S \to bC$

$C \to Ac Bc$

Then I calculated first and follow for all of them. Then i constructed parse table, but for the entry on state S when input symbol is d there are two possible productions

$A \to d$

$B \to d$

I don't have much knowledge about what to do when there is a conflict in the entry for this table, if I'm completely wrong please help me to find solution

You're looking at an implicit conflict in your grammar. Given \begin{align*} S &\to Aa \mid b A c \mid Bc \mid bBa \\ A &\to d \\ B &\to d, \end{align*} we know that a pair of rules $S \to \alpha$ and $S \to \beta$ "conflicts" if ${\rm first}(\alpha) \cap {\rm first}(\beta) \ne \varnothing$, that is, if the set of characters that can be immediately "consumed" by the productions $\alpha$ and $\beta$ intersects.

Intuitively, you can try to visualize what a 1-lookahead recursive-descent parser would do in the state $S$ when it sees a character that can shift to multiple productions. Say you're parsing $S$, and you encounter a symbol $b$; if you're given no other knowledge about the string you are parsing, then it's entirely uncertain whether you should take the $S \to bAc$ path or the $S \to bBa$ path. Therefore, for a grammar to be "well-formed" for a 1-lookahead recursive descent parser, we have to make sure that the grammar contains no such conflicts.

This also generalizes nicely for the case of n-lookahead. We say that two rules $S \to \alpha$ and $S \to \beta$ conflicts in the first $n$ words if ${\rm first}_n (\alpha) \cap {\rm first}_n(\beta) \ne \varnothing$. Intuitively, an n-lookahead parser will be confused if for a particular string of $n$-words, it can shift into multiple productions as well.

Now, besides the obvious conflict between $bAc$ and $bBa$, you should realize that ${\rm first}(Aa) = \{d\} = {\rm first}(Bc)$, so the rules $Aa$ and $Bc$ also conflicts. We can easily resolve this by "inlining" the nonterminals $A$ and $B$ directly and do the same left-factoring trick you did before: \begin{align} S &\to da \mid bdc \mid dc \mid bda \\ &\Rightarrow ({\rm left ~ factoring}) \\ S &\to d X \mid bd X \\ X &\to a \mid c \end{align}

Computing the 1-lookahead predictive table results in $$\begin{array}{ccccc} & a & b & c & d \\ S & & \to bdX && \to dX\\ X & \to a & & \to c \end{array}$$

which corresponds to the algorithm

function parseS(words):
if next word is b:
// -> bdX
consume b; consume d; parseX(rest)
else if next word is d:
// -> dX
consume d; parseX(rest)
else: error

function parseX(words):
if next word is a: consume a
else if next word is c: consume c
else: error