[Solved]: How to prove formally that grammar isn’t LR(1)

ignougroup
Problem Detail: I want to prove that grammar $$ begin{cases} S’rightarrow S Srightarrow aSb ~|~ A Arightarrow 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?

Asked By : Alvar

Answered By : wece

$$S’Rightarrow^*underbrace{ab}_uAunderbrace{b}_wRightarrow underbrace{ab}_uunderbrace{b}_vunderbrace{b}_w$$ $$S’Rightarrow^*underbrace{abbbb}_zAunderbrace{b}_xRightarrow underbrace{ab}_uunderbrace{b}_vunderbrace{bbbb}_y$$ $$FIRST(w)=FIRST(y)=b$$ But: $$abAbbbb=uAyneq zBx=abbbbAb$$
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12470