# How to tell if a grammar is LALR(1) formally?

There is an “informal” definition of $$\operatorname{LR}(k)$$ (can be recognised by a parser that looks at $$k$$ symbols ahead) and a “formal” one (as a property of the set of rightmost derivations possible for the grammar). Is there a similar formal criterion of a grammar being $$\operatorname{LALR}(k)$$ or specifically $$\operatorname{LALR}(1)$$?

For context, I am interested in looking into grammar transformations that preserve the property of being $$\operatorname{LALR}(1)$$ (for example, does eliminating right recursion in an $$\operatorname{LALR}(1)$$ grammar result in a grammar that is still $$\operatorname{LALR}(1)$$?)

The answer to your first question is: Not that we know of.

A grammar is $$\hbox{LALR}(k)$$ if and only if its $$\hbox{LALR}(k)$$ automaton is deterministic. The only way that we know of checking that a grammar is $$\hbox{LALR}(k)$$ is to build the automaton, or something that essentially amounts to building the automaton.

The good news is that the key complication is empty derivations. So, for example, if a $$\hbox{LL}(1)$$ grammar has no nonterminals that have only empty derivations (i.e. if every nonterminal has at least one non-empty derivation), it is $$\hbox{LALR}(1)$$.

See Beatty, On The Relationship Between LL(1) And LR(1) Grammars for further results. You may find something in there that's useful to you.

Eliminating right-recursion can create parsing conflicts in an LALR(k) grammar.

Here's a very simple example with $$k=1$$.

\begin{align}S&\to L R\\ L&\to \epsilon\\ L&\to L a b\\ R&\to \epsilon\\ R&\to a c R\\ \end{align}

That grammar is LALR(1). If you change R to left recursive:

\begin{align}S&\to L R\\ L&\to \epsilon\\ L&\to L a b\\ R&\to \epsilon\\ R&\to R a c\\ \end{align} then it becomes LALR(2). (It's easy to produce grammars where the discrepancy is higher.)