2
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

$$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$$

$\endgroup$
1
  • $\begingroup$ can u prove above definition?? $\endgroup$
    – T.J.
    Commented Nov 4, 2013 at 5:09

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.