2
$\begingroup$

I am unable to understand how Canonical LR(1) grammar is more powerful than LookAhead LR(1). Both have lookahead symbols in their items and works almost similarly, so how can CLR(1) derive a larger set of languages than LALR(1).

$\endgroup$

2 Answers 2

4
$\begingroup$

LALR(1) is the grammar obtained by merging states of CLR(1). The states with the exact same production rules i.e. the exact same core, but different lookahead are combined together.

Specifically, consider $$I_i: A\rightarrow \alpha \bullet \beta, \; a \;\; \mbox{and}\;\; I_j: A\rightarrow \alpha \bullet \beta, \; b$$

The merged state looks like $$I_{ij}: A\rightarrow \alpha \bullet \beta, \; a/b$$

This merging introduces reduce-reduce conflict, even if the original LR(1) grammar was free of such conflicts. To show this, we will consider an example.

Let there be two states $I_i$ and $I_j$ in the LR(1) grammar.

$I_i:$

$A\rightarrow \alpha \bullet, \; p$

$B\rightarrow \alpha \bullet, \; q$

and $I_j:$

$A\rightarrow \alpha \bullet, \; r$

$B\rightarrow \alpha \bullet, \; s$

The merged state $I_{ij}$ is

$A\rightarrow \alpha \bullet, \; p/r$

$B\rightarrow \alpha \bullet, \; q/s$

Now, for the LALR(1) grammar to have a reduce-reduce conflict either

  • $p=s$ which is possible without a reduce-reduce conflict in $I_i$ and $I_j$ OR
  • $q=r$ which is also possible without a reduce-reduce conflict in $I_i$ and $I_j$

Thus, it proves why LALR(1) is less powerful than CLR(1).

$\endgroup$
3
$\begingroup$

The Canonical LR algorithm is not more powerful with respect to languages. The set of languages which have CLR grammars is exactly the same as the set of languages recognised by LALR grammars, or even by SLR grammars.

There are CLR grammars which not LALR. So the CLR algorithm applies to more grammars. But for any such grammar it is possible to construct an equivalent LALR grammar which recognises the same language. Or even an SLR grammar.

The same is true of the parameter $k$. If you have a CLR(k) grammar, you can construct a CLR(1) grammar (or an LALR(1) grammar or a SLR(1) grammar). So there is no such thing as a CLR(2) language. All languages either have an LR grammar or they don't. And if they have an LR grammar, they have lots of other LR grammars, some parseable with, say, LALR(1), and some not.

The CLR algorithm differs from the LALR algorithm in the number of states in the parsing automaton. CLR parsers have a lot more states than LALR parsers, and hence can make finer distinctions at the moment to decide whether to reduce.

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