Is every LL(1) grammar also a LALR(1) grammar?

Question

So one source says it is and another says its not

one source says this :

another says this :

the closest answer i found is this :

Relationship between LR(0), LL(0), LALR(1), etc?

but this doesn't answer the relation between LL(1) and LALR(1)

also if you can answer the more general question, which is what is the relation between LL(k) and LALR(k) it would be even more helpful

thanks.

Answer 1

The definitive answer (at least on the SE Network) can be found in this answer in the computing science site, where parsing theory questions are likely to attract better responses.

When reading the charts in that answer, note that there is a difference between containment relationships for grammars and containment relationships for languages. One of the clearest instances of this is the fact that all LR(k) grammars can be mechanically transformed into LR(1) grammars, with the consequence that there are only two categories of LR languages: LR(0) and LR(1). (In fact, you can reduce LR(k) languages to SLR(1), so the various algorithmic distinctions also disappear at the language level.) LL(k) languages, on the other hand, are a strict containment hierarchy. And the union of LL(k) languages (for finite k) is a strict subset of LR(1).

For grammars, though, the relationships are not so simple. Clearly, LL(k), LR(k), LALR(k), SLR(k), etc., form hierarchies, intuitively because it is not necessary to use all the lookahead information, and because for any grammar it is possible to add productions which require k+1 lookaheads (for both LL and LR algorithms).

LL(k) grammars are necessarily LR(k) but they are not necessarily LALR(k). There is an exercise in Appel's Modern Compiler Implementation textbook which provides an example of an LL(1) grammar which is not LALR(1); you can find the grammar transcribed in this answer. That should provide an idea on how to construct examples for k > 1. (Finding LALR(k) grammars which are not LL(k) is trivial: all you need is left recursion.)