0
$\begingroup$

The grammar is this:
$$S \rightarrow a B c $$ $$B \rightarrow b B b $$ $$B \rightarrow \epsilon $$

The LR(1) states that I worked out were these

$$(1)$$ $$S \rightarrow .aBc$$ $\\\\$ $$(2)$$ $$S \rightarrow a.Bc$$ $$B \rightarrow .bBb$$ $$B \rightarrow .\epsilon $$ $\\\\$ $$(3)$$ $$B \rightarrow b.Bb$$ $$B \rightarrow .bBb$$ $$B \rightarrow .\epsilon$$ $\\\\$ $$(4)$$ $$B \rightarrow \epsilon.$$ $\\\\$

$$(5)$$ $$B \rightarrow bB.b$$ $\\\\$

$$(6)$$ $$B \rightarrow bBb.$$ $\\\\$

$$(7)$$ $$S \rightarrow aB.c$$ $\\\\$

$$(8)$$ $$S \rightarrow aBc.$$

The trouble seems to come primarily from state (3). In state (3) there is an S-R conflict on the lookahead of b. Also I feel that it makes the entire grammar not belong to any LR since on any lookahead of b...b, the same S-R conflict will exist. Is my reasoning correct?

$\endgroup$
1
$\begingroup$

Just as a slight nit, those aren't $LR(1)$ item sets, because they don't include the following terminal symbol

With that proviso, your reasoning looks good to me. Of course, the language is not inherently nondeterministic because you can rewrite $B$ as:

$$B \rightarrow \epsilon\,|\,Bbb$$

The palindrome language $L = \left\{ w w^R\,|\,w \in \Sigma^* \right\}, \left| \Sigma\right| > 1$ is the classic example of an inherently nondeterministic language. There exists an unambiguous grammar for $L$, but there is no $LR(k)$ grammar for any $k$.

$\endgroup$

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.