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

Question

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

Answer 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.

Answer 2

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.)