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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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