I want to prove that grammar $$ \begin{cases} S'\rightarrow S\\ S\rightarrow aSb ~|~ A\\ A\rightarrow bA~|~b \end{cases} $$ isn't $LR(1)$. I've constructed parser table and got Shift-Reduce conflict.

I want to prove that without parser table, using another $LR(1)$ definition.

Here's definition: Grammar is $LR(1)$, if from

  1. $S' \Rightarrow^*_r uAw \Rightarrow_r uvw$
  2. $S' \Rightarrow^*_r zBx \Rightarrow_r uvy$
  3. $FIRST(w) = FIRST(y)$

$\Rightarrow uAy=zBx.$

So how can prove that?


$$S'\Rightarrow^*\underbrace{ab}_uA\underbrace{b}_w\Rightarrow \underbrace{ab}_u\underbrace{b}_v\underbrace{b}_w$$

$$S'\Rightarrow^*\underbrace{abbbb}_zA\underbrace{b}_x\Rightarrow \underbrace{ab}_u\underbrace{b}_v\underbrace{bbbb}_y$$

$$FIRST(w)=FIRST(y)=b$$ But: $$abAbbbb=uAy\neq zBx=abbbbAb$$

  • $\begingroup$ can u prove above definition?? $\endgroup$ – T.J. Nov 4 '13 at 5:09

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.